Fifty years of metaheuristics Martí, Rafael; Sevaux, Marc; Sörensen, Kenneth
European journal of operational research,
4/2024
Journal Article
Recenzirano
Odprti dostop
In this paper, we review the milestones in the development of heuristic methods for optimization over the last 50 years. We propose a critical analysis of the main findings and contributions, mainly ...from a European perspective. Starting with the roots of the area that can be traced back to the classical philosophers, we follow the historical path of heuristics and metaheuristics in the field of operations research and list the main milestones, up to the latest proposals to hybridize metaheuristics with machine learning. We pay special attention to the theories that changed our way of thinking about problem solving, and to the role played by the European Journal of Operational Research in the development of these theories. Our approach emphasizes methodologies and their connections with related areas, which permits to identify potential lines of future research.
•A review in the development of heuristic methods over the last 50 years.•The historical path of heuristics in Operations Research with the main milestones.•From heuristics to metaheuristics that changed our view on problem solving.•The role of EJOR in the metaheuristic literature.•The future of heuristic optimization.
Abstract
Quantum annealing (QA) is a heuristic quantum optimization algorithm that can be used to solve combinatorial optimization problems. In recent years, advances in quantum technologies have ...enabled the development of small- and intermediate-scale quantum processors that implement the QA algorithm for programmable use. Specifically, QA processors produced by D-Wave systems have been studied and tested extensively in both research and industrial settings across different disciplines. In this paper we provide a literature review of the theoretical motivations for QA as a heuristic quantum optimization algorithm, the software and hardware that is required to use such quantum processors, and the state-of-the-art applications and proofs-of-concepts that have been demonstrated using them. The goal of our review is to provide a centralized and condensed source regarding applications of QA technology. We identify the advantages, limitations, and potential of QA for both researchers and practitioners from various fields.
•This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems.•Given the ...hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions which are otherwise too expensive to compute or mathematically not well-defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
In concentrated solar power (CSP) plants based on parabolic trough collectors (PTC), the sun is tracked at discrete time intervals, with each interval representing a movement of the collector system. ...The act of moving heavy mechanical structures can lead to the development of cracks, bending, and/or displacement of components from their optimal optical positions. This, in turn, diminishes the overall energy capture performance of the entire system. In this context, we introduce two combinatorial optimization problems of great interest to PTC plants. The minimum tracking motion (MTM) problem is aimed at detecting the minimum number of movements needed while maintaining production within a given range. The maximal energy collection (MEC) problem seeks to achieve optimal energy production within a predetermined number of movements. Both problems are solved assuming scenarios where the energy collection function contains any number of local maximums/minimums due to optical errors of the elements in the PTC system. The MTM and MEC problems are solved in O(n) time and O(n2mω∗) time respectively, where n is the number of steps in the energy collection function, m the maximum number of movements of the solar structure, and ω∗ the maximal amplitude angle that the structure can cover. The advantages of the solutions are shown in realistic experiments. While these problems can be solved in polynomial time, we establish the NP-hardness of a slightly modified version of the MEC problem. The proposed algorithms are generic and can be adapted to schedule solar tracking in other CSP systems.
•New optimization problems are defined in the context of solar tracking.•Minimum Tracking Motion and Maximal Energy Collection are solved in polynomial time.•90% of the energy is captured with 75% of the movements of the solar collector.•A variant of the Maximal Energy Collection problem is NP-hard.
Hub location problems can be modeled in several ways, one of which is the path-based family of models that make use of four-index variables. Clique inequalities are frequently used to describe ...solution characteristics for optimization problems with binary variables. In this study, new valid inequalities of the clique type are introduced for the path-based family of hub location models. Some of their properties and corresponding lifting are discussed, and a separation heuristic algorithm is proposed. We also report a set of computational experiments to evaluate the usefulness of the proposals when embedded in a commercial solver.
•New clique inequalities are introduced for hub location models.•Some theoretical properties and liftings are discussed.•A separation procedure of strengthened clique inequalities is proposed.•Computational experiments are performed to evaluate the usefulness of the proposals.
We present a unifying framework for Selective Routing Problems (SRPs) through a systematic analysis. The common goal in SRPs is to determine an optimal vehicle route to serve a subset of vertices ...while covering another subset. They arise in diverse fields such as logistics, public health, disaster response, and urban development. To establish a unifying framework for different but related problems, we associate the notion of service with coverage and argue that routing is a tool of service. We classify SRPs according to their selectiveness degree and emphasize the breadth and depth of this problem in terms of its characteristics. This SRP framework helps us identify research gaps as well as potential future research areas. We present a generic mathematical model, use it to describe the connections among these problems and identify some identical problems presented under different names.
•We present a unifying framework and a generic model for Selective Routing Problems.•Problems in logistics, public health, disaster response, and urban development.•We classify SRPs according to their selectiveness degree.•We identify some identical problems presented under different names.•We identify research gaps as well as potential future research areas.
•Solve the problem of packing unequal rectangles into a circular fixed size container.•Propose a biased genetic algorithm hybridized with a local search algorithm.•Improve the decoding procedure and ...analyze its time complexity.•Three new initial layouts and a new set of position evaluation rules are proposed.•Produce over half of new best solutions out of 108 benchmark instances.
This study addresses the two-dimensional circular knapsack packing problem, which packs unequal rectangles into a circular container to maximize the number or the area of items packed. A biased genetic algorithm hybridized with a local search algorithm is proposed to solve the problem. The algorithm has a powerful global searching ability and is responsible for exploration, and a local search is applied for exploitation. Therefore, the proposed approach has an excellent search ability that can balance intensification and diversification well. A decoding procedure is proposed to transform the chromosome into a packing layout. The procedure first produces several initial layouts that contain a few rectangles, forms a complete layout for each initial layout, and selects the best one as the final packing layout. Three new types of initial layouts are considered. A new set of evaluation rules for the placement position and a random selection method are proposed. Computational experiments using two benchmark datasets showed that the evolutionary algorithm could provide better solutions than state-of-the-art algorithms from the literature, with 64 new best solutions out of 108 benchmark instances.
Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain ...experts and may often be suboptimal due to the hard nature of the problems. Reinforcement learning (RL) proposes a good alternative to automate the search of these heuristics by training an agent in a supervised or self-supervised manner. In this survey, we explore the recent advancements of applying RL frameworks to hard combinatorial problems. Our survey provides the necessary background for operations research and machine learning communities and showcases the works that are moving the field forward. We juxtapose recently proposed RL methods, laying out the timeline of the improvements for each problem, as well as we make a comparison with traditional algorithms, indicating that RL models can become a promising direction for solving combinatorial problems.
•Survey explores synergy of combinatorial optimization and reinforcement learning.•It covers recent papers showing how RL can be applied to solve canonical CO problems.•Graph neural networks are used as a method for graph representation in RL for CO.•Policy-based and value-based RL methods are used to learn the solutions to CO tasks.•Most of the reported experiments do not overlap.•This makes it hard to fairly compare the surveyed methods.
Nature-inspired optimization algorithms can solve different engineering and scientific problems owing to their easiness and flexibility. There is no need for structural modifications of optimization ...problems to apply meta-heuristic algorithms on them. Recently, meta-heuristic algorithms are becoming powerful methods for solving NP problems. In this paper, the authors propose a novel meta-heuristic algorithm suitable for continuous nonlinear optimization problems. The proposed method, Black Widow Optimization Algorithm (BWO), is inspired by the unique mating behavior of black widow spiders. This method includes an exclusive stage, namely, cannibalism. Due to this stage, species with inappropriate fitness are omitted from the circle, thus leading to early convergence. BWO algorithm is evaluated on 51 various benchmark functions to verify its efficiency in obtaining the optimal solutions for the problems. The obtained results indicate that the proposed algorithm has numerous advantages in different aspects such as early convergence and achieving optimized fitness value compared to other algorithms. Also, it has the capability of providing competitive and promising results. The research also solves three different challenging engineering design problems adopting BWO algorithm. The outcomes of the real case study problems prove the effectiveness of the proposed algorithm in solving real-world issues with unknown and challenging spaces.
•A novel bio-inspired Black Widow Optimization (BWO) Algorithm is proposed.•BWO is inspired by the bizarre mating behavior of black widow spiders.•BWO is compared with GA, PSO, ABC and BBO using 51 different benchmark functions.•BWO converges to the optimal value as quickly as possible.•BWO outperforms the other experimental algorithms in majority of test functions.
PDF
