Related Research Articles
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. Some examples of GA applications include optimizing decision trees for better performance, solving sudoku puzzles, hyperparameter optimization, causal inference, etc.
In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.
In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.
In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems.
Marco Dorigo is a research director for the Belgian Funds for Scientific Research and a co-director of IRIDIA, the artificial intelligence lab of the Université Libre de Bruxelles. He received a PhD in System and Information Engineering in 1992 from the Polytechnic University of Milan with a thesis titled Optimization, learning, and natural algorithms. He is the leading proponent of the ant colony optimization metaheuristic, and one of the founders of the swarm intelligence research field. Recently he got involved with research in swarm robotics: he is the coordinator of Swarm-bots: Swarms of self-assembling artifacts and of Swarmanoid: Towards humanoid robotic swarms, two swarm robotics projects funded by the Future and Emerging Technologies Program of the European Commission. He is also the founding editor and editor in chief of Swarm Intelligence, the principal peer-reviewed publication dedicated to reporting research and new developments in this multidisciplinary field.
In mathematical optimization and computer science, heuristic is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.
Parallel metaheuristic is a class of techniques that are capable of reducing both the numerical effort and the run time of a metaheuristic. To this end, concepts and technologies from the field of parallelism in computer science are used to enhance and even completely modify the behavior of existing metaheuristics. Just as it exists a long list of metaheuristics like evolutionary algorithms, particle swarm, ant colony optimization, simulated annealing, etc. it also exists a large set of different techniques strongly or loosely based in these ones, whose behavior encompasses the multiple parallel execution of algorithm components that cooperate in some way to solve a problem on a given parallel hardware platform.
A hyper-heuristic is a heuristic search method that seeks to automate, often by the incorporation of machine learning techniques, the process of selecting, combining, generating or adapting several simpler heuristics to efficiently solve computational search problems. One of the motivations for studying hyper-heuristics is to build systems which can handle classes of problems rather than solving just one problem.
Fred Glover is Chief Scientific Officer of Entanglement, Inc., USA, in charge of algorithmic design and strategic planning for applications of combinatorial optimization in quantum computing. He also holds the title of Distinguished University Professor, Emeritus, at the University of Colorado, Boulder, associated with the College of Engineering and Applied Science and the Leeds School of Business. He is known for his innovations in the area of metaheuristics including the computer-based optimization methodology of Tabu search an adaptive memory programming algorithm for mathematical optimization, and the associated evolutionary Scatter Search and Path Relinking algorithms.
In numerical optimization, meta-optimization is the use of one optimization method to tune another optimization method. Meta-optimization is reported to have been used as early as in the late 1970s by Mercer and Sampson for finding optimal parameter settings of a genetic algorithm.
Xin-She Yang is Reader at the Middlesex University and was a senior research scientist at National Physical Laboratory, best known as a developer of various heuristic algorithms for engineering optimization. He obtained a DPhil in applied mathematics from Oxford University. He has given invited keynote talks at SEA2011, SCET2012, BIOMA2012 and Mendel Conference on Soft Computing. He has been elected as a Fellow of the Institute of Mathematics and its Application in 2021. He has been on the prestigious list of Highly Cited Researchers since 2016 by Clarivate Analyatics/Web of Science.
Iterated Local Search (ILS) is a term in applied mathematics and computer science defining a modification of local search or hill climbing methods for solving discrete optimization problems.
The berth allocation problem is a NP-complete problem in operations research, regarding the allocation of berth space for vessels in container terminals. Vessels arrive over time and the terminal operator needs to assign them to berths in order to be served as soon as possible. Different factors affect the berth and time assignment of each vessel.
HeuristicLab is a software environment for heuristic and evolutionary algorithms, developed by members of the Heuristic and Evolutionary Algorithm Laboratory (HEAL) at the University of Applied Sciences Upper Austria, in Hagenberg im Mühlkreis. HeuristicLab has a strong focus on providing a graphical user interface so that users are not required to have comprehensive programming skills to adjust and extend the algorithms for a particular problem. In HeuristicLab algorithms are represented as operator graphs and changing or rearranging operators can be done by drag-and-drop without actually writing code. The software thereby tries to shift algorithm development capability from the software engineer to the user and practitioner. Developers can still extend the functionality on code level and can use HeuristicLab's plug-in mechanism that allows them to integrate custom algorithms, solution representations or optimization problems.
Variable neighborhood search (VNS), proposed by Mladenović & Hansen in 1997, is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems. It explores distant neighborhoods of the current incumbent solution, and moves from there to a new one if and only if an improvement was made. The local search method is applied repeatedly to get from solutions in the neighborhood to local optima. VNS was designed for approximating solutions of discrete and continuous optimization problems and according to these, it is aimed for solving linear program problems, integer program problems, mixed integer program problems, nonlinear program problems, etc.
A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. It differs from local search heuristics which start with a complete solution and then try to improve the current solution further via local moves. Examples of some famous problems that are solved using constructive heuristics are the flow shop scheduling, the vehicle routing problem and the open shop problem.
This is a chronological table of metaheuristic algorithms that only contains fundamental algorithms. Hybrid algorithms and multi-objective algorithms are not listed in the table below.
The EURO Advanced Tutorials in Operational Research are a series of short books devoted to advanced topics in Operational Research that are not available in textbooks. The scope of a Tutorial is to provide more detail about advanced topics in a relevant field to researchers and practitioners. The Book Series was established in 2014 and is published by Springer Science+Business Media. It is an official publication of the Association of European Operational Research Societies.
References
- ↑ Maniezzo, Vittorio, Boschetti, Marco Antonio, Stützle, Thomas: Matheuristics, Algorithms and Implementations. Springer International Publishing (2021).
- ↑ Boschetti, Marco Antonio, Maniezzo, Vittorio: Matheuristics: using mathematics for heuristic design. 4OR 20(2), 173-208, 2022.
- ↑ Hybridizing Metaheuristics and Mathematical Programming. Series: Annals of Information Systems, Vol. 10 Maniezzo, Vittorio; Stützle, Thomas; Voß, Stefan (Eds.), Springer, 2009.
- ↑ Special Issue on Mathematical Contributions to Metaheuristics. Guest Editors: Vittorio Maniezzo, Stefan Voß, and Pierre Hansen, Journal of Heuristics, Volume 15, Number 3 / June, 2009 [ dead link ]
- ↑ Marco A. Boschetti, V. Maniezzo, M. Roffilli and Antonio Bolufé Röhler. Matheuristics: Optimization, Simulation and Control. Proc. of HM 2009, LNCS 5818, pp. 171–177, 2009. Springer-Verlag Berlin Heidelberg 2009