Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2018 | OriginalPaper | Chapter

27. A History of Metaheuristics

Authors: Kenneth Sörensen, Marc Sevaux, Fred Glover

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

share
SHARE

Abstract

This chapter describes the history of metaheuristics in five distinct periods, starting long before the first use of the term and ending a long time in the future.
The field of metaheuristics has undergone several paradigm shifts that have changed the way researchers look upon the development of heuristic methods. Most notably, there has been a shift from the method-centric period, in which metaheuristics were thought of as algorithms, to the framework-centric period, in which researchers think of metaheuristics as more general high-level frameworks, i.e., consistent collections of concepts and ideas that offer guidelines on how to go about solving an optimization problem heuristically.
Tremendous progress has been made in the development of heuristics over the years. Optimization problems that seemed intractable only a few decades ago can now be efficiently solved. Nevertheless, there is still much room for evolution in the research field, an evolution that will allow it to move into the scientific period. In this period, we will see more structured knowledge generation that will benefit both researchers and practitioners.
Unfortunately, a significant fraction of the research community has deluded itself into thinking that scientific progress can be made by resorting to ever more outlandish metaphors as the basis for so-called “novel” methods. Even though considerable damage to the research field will have been inflicted by the time these ideas have been stamped out, there is no doubt that science will ultimately prevail.
Literature
1.
go back to reference Ahuja RK, Ergun Ö, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discret Appl Math 123 (1): 75–102 Ahuja RK, Ergun Ö, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discret Appl Math 123 (1): 75–102
2.
go back to reference Baxter J (1981) Local optima avoidance in depot location. J Oper Res Soc 32:815–819 Baxter J (1981) Local optima avoidance in depot location. J Oper Res Soc 32:815–819
4.
go back to reference Chu T (2014) Human purpose and transhuman potential: a cosmic vision for our future evolution. Origin Press, San Rafael. ISBN:978-1-57983-0250 Chu T (2014) Human purpose and transhuman potential: a cosmic vision for our future evolution. Origin Press, San Rafael. ISBN:978-1-57983-0250
5.
go back to reference Colorni A, Dorigo M, Maniezzo V (1992) Distributed optimization by ant colonies. In: Varela FJ, Bourgine P (eds) Proceedings of the first European conference on artificial life. MIT Press, Cambridge, pp 134–142 Colorni A, Dorigo M, Maniezzo V (1992) Distributed optimization by ant colonies. In: Varela FJ, Bourgine P (eds) Proceedings of the first European conference on artificial life. MIT Press, Cambridge, pp 134–142
6.
go back to reference Corberán Á, Peiró J, Campos V, Glover F, Martí R (2016) Strategic oscillation for the capacitated hub location problem with modular links. J Heuristics 22 (2): 221–244 Corberán Á, Peiró J, Campos V, Glover F, Martí R (2016) Strategic oscillation for the capacitated hub location problem with modular links. J Heuristics 22 (2): 221–244
7.
go back to reference Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press, Cambridge. ISBN:978-0-262-03384-8 Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press, Cambridge. ISBN:978-0-262-03384-8
11.
go back to reference Fogel LJ, Owens AJ, Walsh MJ (1966) Artificial intelligence through simulated evolution. Wiley, New York Fogel LJ, Owens AJ, Walsh MJ (1966) Artificial intelligence through simulated evolution. Wiley, New York
12.
go back to reference García-Martínez C, Rodriguez FJ, Lozano M (2014) Tabu-enhanced iterated greedy algorithm: a case study in the quadratic multiple knapsack problem. Eur J Oper Res 232 (3): 454–463 García-Martínez C, Rodriguez FJ, Lozano M (2014) Tabu-enhanced iterated greedy algorithm: a case study in the quadratic multiple knapsack problem. Eur J Oper Res 232 (3): 454–463
16.
go back to reference Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers/Springer, Boston Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers/Springer, Boston
17.
go back to reference Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control and Cybern 29 (3): 653–684 Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control and Cybern 29 (3): 653–684
18.
go back to reference Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading
20.
go back to reference Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
21.
go back to reference Hopfield J (1982) Neural networks and physical systems with emergent collective computational capabilities. Proc Natl Acad Sci 79 (8): 2254–2558 Hopfield J (1982) Neural networks and physical systems with emergent collective computational capabilities. Proc Natl Acad Sci 79 (8): 2254–2558
22.
go back to reference Hvattum LM, Løkketangen A, Glover F (2004) Adaptive memory search for boolean optimization problems. Discret Appl Math 142 (1): 99–109 Hvattum LM, Løkketangen A, Glover F (2004) Adaptive memory search for boolean optimization problems. Discret Appl Math 142 (1): 99–109
25.
go back to reference Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. Int Ser Oper Res Manag Sci 57:321–354 Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. Int Ser Oper Res Manag Sci 57:321–354
26.
go back to reference Lozano M, Glover F, García-Martínez C, Rodríguez FJ, Martí R (2014) Tabu search with strategic oscillation for the quadratic minimum spanning tree. IIE Trans 46 (4): 414–428 Lozano M, Glover F, García-Martínez C, Rodríguez FJ, Martí R (2014) Tabu search with strategic oscillation for the quadratic minimum spanning tree. IIE Trans 46 (4): 414–428
29.
go back to reference Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts – towards memetic algorithms. Technical Report 826, Caltech Concurrent Computation Program, Pasadena Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts – towards memetic algorithms. Technical Report 826, Caltech Concurrent Computation Program, Pasadena
30.
go back to reference Polya G (2014) How to solve it: a new aspect of mathematical method. Princeton university press, Princeton Polya G (2014) How to solve it: a new aspect of mathematical method. Princeton university press, Princeton
33.
go back to reference Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40 (4): 455–472 CrossRef Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40 (4): 455–472 CrossRef
34.
go back to reference Ruiz R, Stützle T (2008) An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. Eur J Oper Res 187 (3): 1143–1159 CrossRef Ruiz R, Stützle T (2008) An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. Eur J Oper Res 187 (3): 1143–1159 CrossRef
36.
go back to reference Simon HA (1996) The sciences of the artificial, 3rd edn. MIT Press, Cambridge Simon HA (1996) The sciences of the artificial, 3rd edn. MIT Press, Cambridge
39.
go back to reference Sörensen K, Glover FW (2013) Metaheuristics. In: Gass SI, Fu MC (eds) Encyclopedia of operations research and management science, 663 3rd edn, pp 960–970, Springer, Boston, MA CrossRef Sörensen K, Glover FW (2013) Metaheuristics. In: Gass SI, Fu MC (eds) Encyclopedia of operations research and management science, 663 3rd edn, pp 960–970, Springer, Boston, MA CrossRef
43.
go back to reference Yagiura M, Iwasaki S, Ibaraki T, Glover F (2004) A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem. Discret Optim 1 (1): 87–98 CrossRef Yagiura M, Iwasaki S, Ibaraki T, Glover F (2004) A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem. Discret Optim 1 (1): 87–98 CrossRef
Metadata
Title
A History of Metaheuristics
Authors
Kenneth Sörensen
Marc Sevaux
Fred Glover
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_4

Premium Partner