Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
The Generalized Assignment Problem Read chapter Read first chapter

2021 | OriginalPaper | Chapter

4. Population-Based Metaheuristics

Authors : Vittorio Maniezzo, Marco Antonio Boschetti, Thomas Stützle

Published in: Matheuristics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A specialized thread of metaheuristic research, bordering and often overlapping with Artificial Intelligence, studied heuristics that evolved whole sets of candidate solutions, often named “populations” of solutions. Genetic algorithms were among the first results, and following their success it became common to get inspiration from some natural phenomenon to design the heuristic. This chapter considers three representative population-evolving metaheuristics, namely genetic algorithms, ant colony optimization, and scatter search (with path relinking) and shows how they have been complemented with mathematical programming modules to achieve better performance.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Single Solution Metaheuristics
next chapter Diving Heuristics
Footnotes
1
We remind that in the computational traces the decision variables are indexed from 0.
 
Literature
Aggarwal C, Orlin J, Tai R (1997) An optimized crossover for the maximum independent set. Oper Res 45:226–234CrossRef
Alfandari L, Plateau A, Tolla PA (2002) Two-phase path relinking algorithm for the generalized assignment problem. In: Proceedings of the fourth Metaheuristics international conference, pp 175–179
Baldacci R, Boschetti MA, Maniezzo V, Zamboni M (2005) Scatter search methods for the covering tour problem. In: Sharda R, Voß S, Rego C, Alidaee B (eds) Metaheuristic optimization via memory and evolution: Tabu search and scatter search. Springer, Boston, pp 59–91CrossRef
Beyer HG, Schwefel HP (2002) Evolution strategies – a comprehensive introduction. Natural Comput 1(1):3–52CrossRef
Blum C (2005) Beam-ACO – hybridizing ant colony optimization with beam search: an application to open shop scheduling. Comput Oper Res 32(6):1565–1591CrossRef
Blum C (2008) Beam-ACO for simple assembly lime balancing. INFORMS J Comput 20(4):618–627CrossRef
Borisovsky P, Dolgui A, Eremeev A (2009) Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder. Eur J Oper Res 195(3):770–779CrossRef
Colorni A, Dorigo M, Maniezzo V (1991) Distributed optimization by ant colonies. In: Varela F, Bourgine P (eds) Proceedings of the European conference on artificial life, ECAL’91, Paris. Elsevier Publishing, Amsterdam, pp 134–142
Colorni A, Dorigo M, Maniezzo V (1997) Metaheuristics for high-school timetabling. Comput Optim Appl 9(3):277–298
Cotta C, Troya J (2003) Embedding branch and bound within evolutionary algorithms. Appl Intell 18(2):137–153CrossRef
D’Andreagiovanni FA (2014) Hybrid exact-ACO algorithm for the joint scheduling, power and cluster assignment in cooperative wireless networks. In: Di Caro G, Theraulaz G (eds) Bio-inspired models of network, information, and computing systems. Springer, Berlin, pp 3–17CrossRef
Dolgui A, Eremeev A, Guschinskaya O (2010) MIP-based GRASP and genetic algorithm for balancing transfer lines. In: Matheuristics. Springer, Boston, pp 189–208
Dorigo M, Di Caro G (1999) The ant colony optimization meta-heuristic. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw Hill, London, pp 11–32
Dorigo M, Gambardella L (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66CrossRef
Dorigo M, Maniezzo V, Colorni A (1991) Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano
Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cyb Part B (Cyb) 26(1):29–41CrossRef
Eremeev AV (2008) On complexity of optimal recombination for binary representations of solutions. Evol Comput 16(1):127–147CrossRef
Flushing EF, Di Caro GA (2012) Exploiting synergies between exact and heuristic methods in optimization: an application to the relay placement problem in wireless sensor networks. In: Di Caro G, Theraulaz G (eds) Bionetics 2012. Lecture Notes for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 134, pp 250–265
Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8:156–166CrossRef
Glover F (1995) Scatter search and star paths: beyond the genetic metaphor. OR Spektrum 17:125–137CrossRef
Glover F (1997) A template for scatter search and path relinking. Technical Report, School of Business, University of Colorado
Glover F, Kelly JP, Laguna M (1996) New advances and applications of combining simulation and optimization. In: Charnes J, Morrice DJ, Brunner DT, Swain JJ (eds) Proceedings of the 1996 winter simulation conference, pp 144–152
Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Control Cyb 29(3):653–684
Goldberg D (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley Professional, Reading
Holland JH (1975) Adaptation in natural and artificial systems. MIT Press, Cambridge
Maniezzo V (1999) Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS J Comput 11(4):358–369CrossRef
Maniezzo V, Milandri M (2002) An ant-based framework for very strongly constrained problems. In: Dorigo M, Di Caro G, Sampels M (eds) Proceedings of ANTS2002, from ant colonies to artificial ants: third international workshop on ant algorithms. Lecture Notes in Computer Science, vol. 2463. Springer, Berlin, pp 222–227
Rechenberg I (1973) Evolutionsstrategie. Holzmann-Froboog, Stuttgart
Reimann M (2007) Guiding ACO by problem relaxation: a case study on the symmetric TSP. In: Bartz-Beielstein T, et al (eds) Hybrid metaheuristics. HM 2007. Lecture Notes in Computer Science, vol 4771, pp 45–56CrossRef
Rothberg E (2007) An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J Comput 19(4):534–541CrossRef
Schwefel HP (1981) Numerical optimization of computer models (Translation of Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie). Birkhäuser (1977). Wiley, Chichester
Sörensen K (2015) Metaheuristics - the metaphor exposed, international transactions in operational research. Special Issue: Math Model-Based Metaheuristics 22(1):3–18
Stützle T, Hoos HH (2000) Max-Min ant system. Future Gener Comput Syst 16:889–914CrossRef
Turing A (1950) Computing machinery and intelligence. Mind, LIX 238:433–460CrossRef
Walteros JL, Medaglia AL, Riano G (2014) Hybrid algorithm for route design on bus rapid transit systems. Transport Sci 49(1):66–84CrossRef
Yagiura M, Ibaraki T (1996) The use of dynamic programming in genetic algorithms for permutation problems. Eur J Operat Res 92:387–401CrossRef
Yagiura M, Ibaraki T, Glover FA (2003) Path relinking approach for the generalized assignment problem. Eur J Operat Res 169(2):548–569CrossRef
Metadata
Title
Population-Based Metaheuristics
Authors
Vittorio Maniezzo
Marco Antonio Boschetti
Thomas Stützle
Copyright Year
2021
Book
Matheuristics

Print ISBN: 978-3-030-70276-2

Electronic ISBN: 978-3-030-70277-9

Copyright Year: 2021

DOI
https://doi.org/10.1007/978-3-030-70277-9_4