Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
The Generalized Assignment Problem Kapitel lesen Erstes Kapitel lesen

2021 | OriginalPaper | Buchkapitel

4. Population-Based Metaheuristics

verfasst von : Vittorio Maniezzo, Marco Antonio Boschetti, Thomas Stützle

Erschienen in: Matheuristics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Single Solution Metaheuristics
Nächstes Kapitel Diving Heuristics
Fußnoten
1
We remind that in the computational traces the decision variables are indexed from 0.
 
Literatur
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, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge,CrossRef
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
Metadaten
Titel
Population-Based Metaheuristics
verfasst von
Vittorio Maniezzo
Marco Antonio Boschetti
Thomas Stützle
Copyright-Jahr
2021
Buch
Matheuristics

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

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

Copyright-Jahr: 2021

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