The DOI matches its Crossref record; 67 of the 67 references it cites were found in a registry or an index.
Metaheuristics in combinatorial optimization: Overview and conceptual comparison
Abstract
The field of metaheuristics for the application to combinatorial optimization problems is a rapidly growing field of research. This is due to the importance of combinatorial optimization problems for the scientific as well as the industrial world. We give a survey of the nowadays most important metaheuristics from a conceptual point of view. We outline the different components and concepts that are used in the different metaheuristics in order to analyze their similarities and differences. Two very important concepts in metaheuristics are intensification and diversification. These are the two forces that largely determine the behavior of a metaheuristic. They are in some way contrary but also complementary to each other. We introduce a framework, that we call the I&D frame, in order to put different intensification and diversification components into relation with each other. Outlining the advantages and disadvantages of different metaheuristic approaches we conclude by pointing out the importance of hybridization of metaheuristics as well as the integration of metaheuristics and other methods for optimization.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Genetic Algorithms in Search, Optimization and Machine Learning
Goldberg, D. E., & Robson, D. (1988) · Cited by 18,391
Ant system: optimization by a colony of cooperating agents
Dorigo, M., Maniezzo, V., & Colorni, A. (1996) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/3477.484436 · Cited by 12,067
An Introduction to Genetic Algorithms
Mitchell, M. (1996) · doi:10.7551/mitpress/3927.001.0001 · Cited by 11,340
Ant colony system: a cooperative learning approach to the traveling salesman problem
Dorigo, M., & Gambardella, L. M. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585892 · Cited by 8,081
The origins of order; self organization and selection in evolution
(1994) · International Journal of Biochemistry · doi:10.1016/0020-711x(94)90119-8 · Cited by 6,649
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Glover, F. (1990) · ORSA Journal on Computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,647
Bäck, T. (1996) · Oxford University Press eBooks · doi:10.1093/oso/9780195099713.001.0001 · Cited by 5,113
Future paths for integer programming and links to artificial intelligence
Glover, F. (1986) · Computers & Operations Research · doi:10.1016/0305-0548(86)90048-1 · Cited by 4,181
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
Černý, V. (1985) · Journal of Optimization Theory and Applications · doi:10.1007/bf00940812 · Cited by 3,436
Dorigo, M., & Stützle, T. (2004) · The MIT Press eBooks · doi:10.7551/mitpress/1290.001.0001 · Cited by 3,330
Integer and Combinatorial Optimization
Nemhauser, G., & Wolsey, L. (1988) · Wiley eBooks · doi:10.1002/9781118627372 · Cited by 3,176
Glover, F., & Laguna, M. (1997) · doi:10.1007/978-1-4615-6089-0 · Cited by 3,001
Ant Algorithms for Discrete Optimization
Dorigo, M., Caro, G. D., & Gambardella, L. M. (1999) · Artificial Life · doi:10.1162/106454699568728 · Cited by 2,808
Greedy Randomized Adaptive Search Procedures
Feo, T. A., & Resende, M. G. C. (1995) · Journal of Global Optimization · doi:10.1007/bf01096763 · Cited by 2,778
Evolutionsstrategie : Optimierung technischer Systeme nach Prinzipien der biologischen Evolution
Rechenberg, I. (1973) · Frommann-Holzboog eBooks · Cited by 2,440
Genetic algorithms with sharing for multimodal function optimization
Goldberg, D. E., & Richardson, J. T. (1987) · international conference on Genetic algorithms · Cited by 1,912
Variable neighborhood search: Principles and applications
Hansen, P., & Mladenović, N. (2001) · European Journal of Operational Research · doi:10.1016/s0377-2217(00)00100-4 · Cited by 1,902
An introduction to simulated evolutionary optimization
Fogel, D. B. (1994) · IEEE Transactions on Neural Networks · doi:10.1109/72.265956 · Cited by 1,503
Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
Shaw, P. (1998) · Lecture Notes in Computer Science · doi:10.1007/3-540-49481-2_30 · Cited by 1,366
HEURISTICS FOR INTEGER PROGRAMMING USING SURROGATE CONSTRAINTS
Glover, F. (1977) · Decision Sciences · doi:10.1111/j.1540-5915.1977.tb01074.x · Cited by 1,363
An Introduction To Probability Theory And Its Applications
Feller, W. (1950) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 1,246
Dueck, G., & Scheuer, T. (1990) · Journal of Computational Physics · doi:10.1016/0021-9991(90)90201-b · Cited by 1,232
The self-organizing exploratory pattern of the argentine ant
Deneubourg, J. L., Aron, S., Goss, S., & Pasteels, J. M. (1990) · Journal of Insect Behavior · doi:10.1007/bf01417909 · Cited by 921
Robust taboo search for the quadratic assignment problem
Taillard, É. D. (1991) · Parallel Computing · doi:10.1016/s0167-8191(05)80147-4 · Cited by 835
Battiti, R., & Tecchiolli, G. (1994) · ORSA Journal on Computing · doi:10.1287/ijoc.6.2.126 · Cited by 801
An updated survey of GA-based multiobjective optimization techniques
Coello, C. A. (2000) · ACM Computing Surveys · doi:10.1145/358923.358929 · Cited by 773
Dueck, G. (1993) · Journal of Computational Physics · doi:10.1006/jcph.1993.1010 · Cited by 765
Ant colony optimization for resource-constrained project scheduling
Merkle, D., Middendorf, M., & Schmeck, H. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2002.802450 · Cited by 759
Convergence of an annealing algorithm
Lundy, M., & Mees, A. (1986) · Mathematical Programming · doi:10.1007/bf01582166 · Cited by 693
Metaheuristics: A bibliography
Osman, I. H., & Laporte, G. (1996) · Annals of Operations Research · doi:10.1007/bf02125421 · Cited by 672
Memetic algorithms: a short introduction
Moscato, P. (1999) · McGraw-Hill Ltd., UK eBooks · Cited by 455
Artificial Intelligence through Simulated Evolution
(2009) · Evolutionary Computation · doi:10.1109/9780470544600.ch7 · Cited by 443
Guided local search and its application to the traveling salesman problem
Voudouris, C., & Tsang, E. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00099-x · Cited by 409
Variable neighborhood search for the p-median
Hansen, P., & Mladenović, N. (1997) · Location Science · doi:10.1016/s0966-8349(98)00030-8 · Cited by 403
An improved annealing scheme for the QAP
Connolly, D. T. (1990) · European Journal of Operational Research · doi:10.1016/0377-2217(90)90301-q · Cited by 400
Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems
Gomes, C. P., Selman, B., Crato, N., & Kautz, H. (2000) · Journal of Automated Reasoning · doi:10.1023/a:1006314320276 · Cited by 395
An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
Gambardella, L. M., & Dorigo, M. (2000) · INFORMS Journal on Computing · doi:10.1287/ijoc.12.3.237.12636 · Cited by 373
Evolution in Time and Space – The Parallel Genetic Algorithm
Mühlenbein, H. (1991) · Foundations of genetic algorithms · doi:10.1016/b978-0-08-050684-5.50023-9 · Cited by 328
Large-step Markov chains for the Traveling Salesman Problem
Martin, O. (2018) · doi:10.6083/nk322d67m · Cited by 321
An overview of evolutionary computation
Spears, W. M., Jong, K. A., Bäck, T., Fogel, D. B., & Garis, H. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-56602-3_163 · Cited by 312
Landscapes and their correlation functions
Stadler, P. F. (1996) · Journal of Mathematical Chemistry · doi:10.1007/bf01165154 · Cited by 258
Model-Based Search for Combinatorial Optimization: A Critical Survey
Zlochin, M., Birattari, M., Meuleau, N., & Dorigo, M. (2004) · Annals of Operations Research · doi:10.1023/b:anor.0000039526.52305.af · Cited by 247
Parallel GRASP with path-relinking for job shop scheduling
Aiex, R. M., Binato, S., & Resende, M. G. C. (2003) · Parallel Computing · doi:10.1016/s0167-8191(03)00014-0 · Cited by 218
Combining simulated annealing with local search heuristics
Martin, O. C., & Otto, S. W. (1996) · Annals of Operations Research · doi:10.1007/bf02601639 · Cited by 216
A phylogenetic, ontogenetic, and epigenetic view of bio-inspired hardware systems
Sipper, M., Sanchez, E., Mange, D., Tomassini, M., Perez-Uribe, A., & Stauffer, A. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585894 · Cited by 210
Landscapes, operators and heuristic search
Reeves, C. R. (1999) · Annals of Operations Research · doi:10.1023/a:1018983524911 · Cited by 201
Modeling building-block interdependency
Watson, R. A. R., Hornby, G. S., & Pollack, J. B. (1998) · Lecture notes in computer science · doi:10.1007/bfb0056853 · Cited by 187
Local search with constraint propagation and conflict-based heuristics
Jussien, N., & Lhomme, O. (2002) · Artificial Intelligence · doi:10.1016/s0004-3702(02)00221-7 · Cited by 184
Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics
Backer, B. D., Furnon, V., Shaw, P., Kilby, P., & Prosser, P. (2000) · Journal of Heuristics · doi:10.1023/a:1009621410177 · Cited by 183
A Grasp for Job Shop Scheduling
Binato, S., Hery, W. J., Loewenstern, D., & Resende, M. G. C. (2002) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-1507-4_3 · Cited by 169
Simulated Crossover in Genetic Algorithms
Syswerda, G. (1993) · Foundations of genetic algorithms · doi:10.1016/b978-0-08-094832-4.50021-0 · Cited by 168
Intensification and diversification with elite tabu search solutions for the linear ordering problem
Laguna, M., Martí, R., & Campos, V. (1999) · Computers & Operations Research · doi:10.1016/s0305-0548(98)00104-x · Cited by 163
Adaptive simulated annealing (ASA): Lessons learned
Ingber, L. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0001018 · Cited by 159
An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem
Campos, V., Glover, F., Laguna, M., & Martí, R. (2001) · Journal of Global Optimization · doi:10.1023/a:1012793906010 · Cited by 142
A framework for the description of evolutionary algorithms
Hertz, A., & Kobler, D. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00435-x · Cited by 124
A Constraint Programming Framework for Local Search Methods
Pesant, G., & Michel Gendreau, A. (1999) · Journal of Heuristics · doi:10.1023/a:1009694016861 · Cited by 101
Ant Colony Optimization and Stochastic Gradient Descent
Meuleau, N., & Dorigo, M. (2002) · Artificial Life · doi:10.1162/106454602320184202 · Cited by 98
Reactive search, a history-sensitive heuristic for MAX-SAT
Battiti, R., & Protasi, M. (1997) · ACM Journal of Experimental Algorithmics · doi:10.1145/264216.264220 · Cited by 94
Node-ejection chains for the vehicle routing problem: Sequential and parallel algorithms
Rego, C. (2001) · Parallel Computing · doi:10.1016/s0167-8191(00)00102-2 · Cited by 91
A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization
Calégari, P., Coray, G., Hertz, A., Kobler, D., & Kuonen, P. (1999) · Journal of Heuristics · doi:10.1023/a:1009625526657 · Cited by 77
Systematic versus stochastic constraint satisfaction
Freuder, E. C., Dechter, R., Ginsberg, M. L., Selman, B., & Tsang, E. P. K. (1995) · International Joint Conference on Artificial Intelligence · Cited by 68
Relaxed tours and path ejections for the traveling salesman problem
Rego, C. (1998) · European Journal of Operational Research · doi:10.1016/s0377-2217(97)00288-9 · Cited by 65
Discovery of RNA structural elements using evolutionary computation
Fogel, G. B. (2002) · Nucleic Acids Research · doi:10.1093/nar/gkf653 · Cited by 59
Thermostatistical persistency: A powerful improving concept for simulated annealing algorithms
Chardaire, P., Lutton, J. L., & Sutter, A. (1995) · European Journal of Operational Research · doi:10.1016/0377-2217(94)00058-k · Cited by 37
Fitness Landscapes and Performance of Meta-Heuristics
Fonlupt, C., Robilliard, D., Preux, P., & Talbi, E. (1999) · Springer eBooks · doi:10.1007/978-1-4615-5775-3_18 · Cited by 30
Ant colony optimization for the edge-weighted k -cardinality tree problem
Blum, C. (2002) · Cited by 16
Self-citation
Cited by
Cuckoo Search via Lévy flights
Yang, X.-S., & Deb, S. (2009) · 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC) · doi:10.1109/nabic.2009.5393690 · Cited by 6,185
Ant colony optimization theory: A survey
Dorigo, M., & Blum, C. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.05.020 · Cited by 2,295
Self-citationAskarzadeh, A. (2016) · Computers & Structures · doi:10.1016/j.compstruc.2016.03.001 · Cited by 2,216
A survey on optimization metaheuristics
Boussaïd, I., Lepagnot, J., & Siarry, P. (2013) · Information Sciences · doi:10.1016/j.ins.2013.02.041 · Cited by 1,655
Ant colony optimization: Introduction and recent trends
Blum, C. (2005) · Physics of Life Reviews · doi:10.1016/j.plrev.2005.10.001 · Cited by 1,308
Self-citation
Metadata
- Authors
- Blum, C., & Roli, A.
- Venue
- ACM Computing Surveys
- Published
- 2003-09
- Volume
- 35
- Issue
- 3
- Pages
- 268-308
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2004617458
- Cited by
- 3,236
- References
- 67
- FWCI
- 44.88
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.