A pointer network based deep learning algorithm for unconstrained binary quadratic programming problem
یک شبکه اشاره گر مبتنی بر الگوریتم یادگیری عمیق برای مسئله برنامه نویسی درجه دوم باینری نامحدود-2020
Combinatorial optimization problems have been widely used in various fields. And many types of com- binatorial optimization problems can be generalized into the model of unconstrained binary quadratic programming (UBQP). Therefore, designing an effective and efficient algorithm for UBQP problems will also contribute to solving other combinatorial optimization problems. Pointer network is an end-to-end sequential decision structure and combines with deep learning technology. With the utilization of the structural characteristics of combinatorial optimization problems and the ability to extract the rule be- hind the data by deep learning, pointer network has been successfully applied to solve several classical combinatorial optimization problems. In this paper, a pointer network based algorithm is designed to solve UBQP problems. The network model is trained by supervised learning (SL) and deep reinforcement learning (DRL) respectively. Trained pointer network models are evaluated by self-generated benchmark dataset and ORLIB dataset respectively. Experimental results show that pointer network model trained by SL has strong learning ability to specific distributed dataset. Pointer network model trained by DRL can learn more general distribution data characteristics. In other words, it can quickly solve problems with great generalization ability. As a result, the framework proposed in this paper for UBQP has great potential to solve large scale combinatorial optimization problems.
Keywords: UBQP | Pointer network | Supervised learning | Deep reinforcement learning
Tabu search for min-max edge crossing in graphs
جستجوی تابو برای عبور از لبه های حداقل حداکثر در گراف ها -2020
Graph drawing is a key issue in the field of data analysis, given the ever-growing amount of information available today that require the use of automatic tools to represent it. Graph Drawing Problems (GDP) are hard combinatorial problems whose applications have been widely relevant in fields such as social network analysis and project management. While classically in GDPs the main aesthetic concern is re- lated to the minimization of the total sum of crossing in the graph (min-sum), in this paper we focus on a particular variant of the problem, the Min-Max GDP, consisting in the minimization of the maximum crossing among all egdes. Recently proposed in scientific literature, the Min-Max GDP is a challenging variant of the original min-sum GDP arising in the optimization of VLSI circuits and the design of in- teractive graph drawing tools. We propose a heuristic algorithm based on the tabu search methodology to obtain high-quality solutions. Extensive experimentation on an established benchmark set with both previous heuristics and optimal solutions shows that our method is able to obtain excellent solutions in short computation time.
Keywords: Combinatorial optimization | Graph drawing | Metaheuristics
A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs
یک رویکرد یادگیری تقویت برای بهینه سازی مسائل فروشنده دوره گرد چند گانه از طریق گراف-2020
This paper proposes a learning-based approach to optimize the multiple traveling salesman problem (MTSP), which is one classic representative of cooperative combinatorial optimization problems. The MTSP is interesting to study, because the problem arises from numerous practical applications and efficient approaches to optimize the MTSP can potentially be adapted for other cooperative optimization problems. However, the MTSP is rarely researched in the deep learning domain because of certain difficulties, including the huge search space, the lack of training data that is labeled with optimal solutions and the lack of architectures that extract interactive behaviors among agents. This paper constructs an architecture consisting of a shared graph neural network and distributed policy networks to learn a common policy representation to produce near-optimal solutions for the MTSP. We use a reinforcement learning approach to train the model, overcoming the requirement data labeled with ground truth. We use a two-stage approach, where reinforcement learning is used to learn an allocation of agents to vertices, and a regular optimization method is used to solve the single-agent traveling salesman problems associated with each agent. We introduce a S-samples batch training method to reduce the variance of the gradient, improving the performance significantly. Experiments demonstrate our approach successfully learns a strong policy representation that outperforms integer linear programming and heuristic algorithms, especially on large scale problems.
Keywords: Multi-agent reinforcement learning | Combinatorial optimization problems | Multiple traveling salesman problems | Graph neural networks | Policy networks
Heuristic algorithms based on deep reinforcement learning for quadratic unconstrained binary optimization
الگوریتم های ابتکاری مبتنی بر یادگیری تقویتی عمیق برای بهینه سازی باینری بدون محدودیت درجه دوم-2020
The unconstrained binary quadratic programming (UBQP) problem is a difficult combinatorial optimization problem that has been intensively studied in the past decades. Due to its NP-hardness, many heuristic algorithms have been developed for the solution of the UBQP. These algorithms are usually problem-tailored, which lack generality and scalability. To address these issues, a heuristic algorithm based on deep reinforcement learning (DRLH) is proposed in this paper. It features in inputting specific features and using a neural network model called NN to guild the selection of variable at each solution construction step. Also, to improve the algorithm speed and efficiency, two algorithm variants named simplified DRLH (DRLS) and DRLS with hill climbing (DRLS-HC) are developed as well. These three algorithms are examined through extensive experiments in comparison with famous heuristic algorithms from the literature. Experimental results show that the DRLH, DRLS, and DRLS-HC outperform their competitors in terms of both solution quality and computational efficiency. Precisely, the DRLH achieves the best-quality results, while DRLS offers a high-quality solution in a very short time. By adding a hill-climbing procedure to DRLS, the resulting DRLS-HC algorithm is able to obtain almost the same quality result as DRLH with however 5 times less computing time on average. We conducted additional experiments on large-scale instances and various data distributions to verify the generality and scalability of the proposed algorithms, and the results on benchmark instances indicate the ability of the algorithms to be applied to practical problems.
Keywords: Unconstrained binary quadratic | programming | Heuristic algorithm | Deep reinforcement learning | Neural network
Incorporating domain knowledge into reinforcement learning to expedite welding sequence optimization
تلفیق دانش دامنه ای به یادگیری تقویتی برای تسریع در بهینه سازی توالی پیوند-2020
Welding Sequence Optimization (WSO) is very effective to minimize the structural deformation, however selecting proper welding sequence leads to a combinatorial optimization problem. State-of-the-art algorithms could take more than one week to compute the best sequence for an assembly of eight weld beads which is unrealistic for the early stages of Product Delivery Process (PDP). In this article, we develop and implement a novel Reinforcement Q-learning algorithm for WSO where structural deformation is used to compute reward function. We utilize a thermo-mechanical Finite Element Analysis (FEA) to predict deformation. The exploration–exploitation dilemma has been tackled by domain knowledge driven ????-greedy algorithm into Q-RL which helps to expedite the WSO and we call this novel algorithm as DKQRL. We run welding simulation experiment using well-known Simufact® software on a typical widely used mounting bracket which contains eight welding beads. DKQRL allows the reduction of structural deformation up to ∼71% and it substantially speeds up the computational time over Modified Lowest Cost Search (MLCS), Genetic Algorithm (GA), exhaustive search, and standard RL algorithm. Results of welding simulation demonstrate a reasonable agreement with real experiment in terms of structural deformation.
Keywords: Welding sequence optimization | FEA based welding simulation | Reinforcement learning | Structural deformation | Residual stress | Artificial intelligence | Machine learning
A local search algorithm with reinforcement learning based repair procedure for minimum weight independent dominating set
یک الگوریتم جستجوی محلی با روش تعمیر مبتنی بر یادگیری تقویت کننده برای مجموعه سلطه مستقل از حداقل وزن-2020
The minimum weight independent dominating set problem (MWIDS) is a famous NP-hard combinatorial optimization problem. We herein propose a local search algorithm with reinforcement-learning-based repair procedure (LSRR). The proposed algorithm combines local search with repair procedure based on the mind of reinforcement learning. This algo- rithm iterates through three procedures: the greedy procedure to improve the initial solu- tion, the local search procedure to further improve the solution, and the repair procedure to destroy the initial solution and then reconstruct a new solution. In addition, because of the particularity of the weight functions in all benchmarks, we propose three novel scoring functions. Experiments are performed on two types of graphs including random graphs and random geometric graphs. Experimental results display that LSRR outperforms the previous MWIDS algorithms significantly.
Keywords: Minimum weight independent dominating | set problem | Local search | Reinforcement-learning-based repair | procedure | Scoring function
الگوریتم بهینه سازی ترکیبی MIGA و NLPQL برای بهینه سازی پارامترهای bus الکتریکی هیبریدی پلاگین
سال انتشار: 2017 - تعداد صفحات فایل pdf انگلیسی: 6 - تعداد صفحات فایل doc فارسی: 11
در این مقاله، اقتصاد سوخت به عنوان هدف بهینه سازی bus الکتریکی هیبریدی پلاگین (PHEB) انتخاب شده است. مدل ریاضی بهینه سازی پارامترهای نیروی برق PHEB است که بر اساس استراتژی مدیریت انرژی مطلوب است و استراتژی مدیریت انرژی این الگوریتم با استفاده از الگوریتم برنامه نویسی پویا (DP) انجام میشود. در مرحله اول، اقتصاد سوخت PHEB به عنوان هدف تابع بهینه سازی پارامتر انتخاب شد. سپس، الگوریتم بهینه سازی ترکیبی توسط الگوریتم ژنتیک چند جزیره (MIGA) و برنامه نویسی مستطیلی NLPQL طراحی شد. در ابتدا MIGA برای بهینه سازی جهانی مورد استفاده قرار گرفت و NLPQL برای بهینه سازی محلی استفاده شد. در نهایت، نتایج آزمایشات نشان داد که مصرف سوخت PHEB در هر 100 کیلومتر از 18.51 لیتر دیزل به 17.41 لیتر دیزلی رسید و مصرف برق در هر 100 کیلومتر، در سطح یکسانی حفظ شد.
کلمات کلیدی: بهینه سازی پارامترها | bus الکتریکی هیبریدی | الگوریتم ژنتیک چند جزیره | برنامه نویسی درجه دوم مرتبه NLPQL
|مقاله ترجمه شده|
A framework for secure IT operations in an uncertain and changing environment
یک چارچوب برای عملیات IT ایمن در محیط نامطمئن و در حال تغییر-2017
Article history:Received 5 February 2016Revised 2 March 2017Accepted 17 April 2017Available online 18 April 2017Keywords:Information securityIT security management Decision support framework Security investment decisions Combinatorial optimizationIn this paper, a quantitative approach is proposed that addresses various decision making challenges within the IT security process of an organization. The approach serves as a framework that facilitates multiple applications to optimize the security of IT systems in different environmental settings. Address- ing this problem is a critical challenge for almost all organizations and it still lacks a comprehensive and consistent quantitative treatment. The key question of the corresponding decision problem is which safeguards to select in order to achieve suﬃcient security. The proposed framework addresses this by establishing a generally applicable problem structure and by reusing existing knowledge in order to re- duce implementation costs of the approach. Based on this foundation, eﬃcient MILP models are applied to support the establishment of an effective IT security strategy. Depending on the knowledge an organi- zation is able to provide, decisions take uncertainty and even dynamic aspects into account. As a result, deployed safeguards are robust against uncertain security threats and remain stable over several plan- ning periods even if the system or the threat environment changes. This is a signiﬁcant advancement that results in higher security in the short-term and lower costs in the mid- and long-term.© 2017 Elsevier Ltd. All rights reserved.
Keywords: Information security | IT security management | Decision support framework | Security investment decisions | Combinatorial optimization
LibCoopt_ A library for combinatorial optimization on partial permutation matrices
LibCoopt _ یک کتابخانه ای برای بهینه سازی ترکیبی روی معیارهای جزئی جایگشتی-2017
LibCoopt is an open-source matlab code library which provides a general and convenient tool to approximately solve the combinatorial optimization problems on the set of partial permutation matrices, which are frequently encountered in computer vision, bioinformatics, social analysis, etc. To use the library, the user needs only to give the objective function and its gradient function associated with the problem. Two typical problems, the subgraph matching problem and the quadratic assignment problem, are employed to illustrate how to use the library and also its flexibility on different types of problems.
Keywords: Combinatorial optimization | Partial permutation matrices | Graduated projection | Deterministic annealing
A large neighborhood search heuristic for supply chain network design
یک جستجوی اکتشافی همسایه بزرگ برای طراحی شبکه زنجیره تامین-2017
Many exact and approximate solution techniques have been used to solve facility location problems and, more generally, supply chain network design problems. Yet, the Large Neighborhood Search technique (LNS) has almost never been suggested for solving such problems, although it has proven its efficiency and flexibility in solving other complex combinatorial optimization problems. In this paper, we propose an LNS framework for solving a four-layer single period multi-product supply chain network design prob lem. One important feature of the model is that it includes inter-modality: the itinerary followed by the cargo from origin to destination may take several transportation modes. Moreover, several modes may compete on some arcs. Location decisions for intermediate facilities (e.g. plants and distribution centers) are determined by the LNS while transportation modes and product flow decisions are determined by a greedy heuristic. As a post-optimization step, linear programming is used to optimize product flows once the structure of the logistics network is fixed. Extensive experiments, based on randomly generated instances of different sizes and characteristics, show the effectiveness of the method compared with a state-of-the-art solver.
Keywords: Supply chain network design | Facility location | Large Neighborhood Search