Myralgoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 maj 2022; kontroller kräver 2 redigeringar .

Myrkolonioptimeringsalgoritm ( myrkolonioptimering , ACO ) är en av de effektiva polynomalgoritmerna  för att hitta ungefärliga lösningar på resandeförsäljarproblemet , samt lösa liknande problem med att hitta rutter på grafer . Kärnan i tillvägagångssättet är att analysera och använda beteendemodellen för myror som letar efter vägar från kolonin till födokällan, och är en metaheuristisk optimering. Den första versionen av algoritmen, som föreslogs av Dr Marco Dorigo [1] [2] 1992 , syftade till att hitta den optimala vägen i en graf.

Historik

Översikt

Algoritmen är baserad på beteendet hos en myrkoloni som  markerar mer framgångsrika vägar med en stor mängd feromoner . Arbetet börjar med placeringen av myror vid toppen av grafen (städerna), sedan börjar myrornas rörelse - riktningen bestäms av en probabilistisk metod, baserad på formeln för formuläret:

,

var:

 är sannolikheten att röra sig längs vägen ,  är den reciproka av vikten (längden) av den e övergången,  är mängden feromon i den th korsningen,  är värdet som bestämmer algoritmens "girighet",  - värdet som bestämmer algoritmens "vallning".

Lösningen är inte exakt och kan till och med vara en av de sämsta, men på grund av väl vald heuristik ger iterativ tillämpning av algoritmen oftast ett resultat som är nära optimalt.

Flera metaheuristiska modeller av ACO har föreslagits i litteraturen. Tre av de mest framgångsrika bland dem är:

  1. myrsystem (Dorigo 1992, Dorigo et al. 1991, 1996),
  2. myrkolonisystem (ACS) (Dorigo & Gambardella 1997),
  3. MAX-MIN myrsystem (MMAS) (Stutzle & Hoos 2000).

Sammanfattning

I den verkliga världen går myror (inledningsvis) slumpmässigt och, efter att ha hittat mat, återvänder de till sin koloni, flammande stigar med feromoner . Om andra myror hittar sådana stigar är det mer sannolikt att de följer dem. Istället för att spåra kedjan förstärker de den när de kommer tillbaka om de så småningom hittar en källa till mat. Med tiden börjar feromonspåret avdunsta, vilket minskar dess attraktiva kraft. Ju mer tid det tar att resa vägen till målet och tillbaka, desto mer kommer feromonspåret att förångas. På en kort väg, i jämförelse, kommer passagen att vara snabbare, och som ett resultat förblir tätheten av feromoner hög. Feromonavdunstning har också funktionen att undvika strävan efter en lokalt optimal lösning. Om feromoner inte förångades, skulle den väg som valdes först vara den mest attraktiva. I detta fall skulle studier av rumsliga lösningar vara begränsade. Således, när en myra hittar en (till exempel kort) väg från kolonin till en födokälla, är det mer sannolikt att andra myror följer den vägen, och positiv feedback leder så småningom alla myror till samma kortaste väg.

Läs mer

Den ursprungliga idén kommer från att observera myror när de hittar den kortaste vägen från kolonin till sin matkälla.

  1. Den första myran hittar en matkälla (F) på något sätt (a) och återvänder sedan till boet (N), och lämnar efter sig ett feromonspår (b).
  2. Sedan väljer myrorna en av de fyra möjliga vägarna, förstärker den sedan och gör den attraktiv.
  3. Myror tar den kortaste vägen, eftersom feromoner från längre stigar avdunstar snabbare.

Bland experiment med att välja mellan två vägar av olika längd som leder från en koloni till en födokälla, har biologer märkt att myror som regel använder den kortaste vägen [6] [10] . Modellen för detta beteende är följande:

Myror använder miljön som kommunikationsmedel. De utbyter information indirekt, genom feromoner, under sitt "arbete". Informationsutbytet är lokalt till sin natur: endast de myror som befinner sig i omedelbar närhet av feromonstigarna kan lära sig om dem. Ett sådant system kallas stigmergi och är sant för många sociala djur (det har studerats för fallet med att bygga pelare i termitbon). Denna problemlösningsmekanism är mycket komplex och är ett bra exempel på systemsjälvorganisering. Ett sådant system är baserat på positiv (andra myror stärker feromonspåret) och negativ (avdunstning av feromonspåret) feedback. Teoretiskt, om antalet feromoner förblir detsamma över tiden över alla rutter, kommer det att vara omöjligt att välja en väg. Men på grund av återkoppling kommer små fluktuationer att göra att en av vägarna blir starkare och systemet stabiliseras mot den kortaste vägen.

Variationer av algoritmen

Följande är några av de mest populära varianterna av myrkolonialgoritmen.

Elite Ant System

Av det totala antalet myror sticker de så kallade "elitmyrorna" ut. Enligt resultaten av varje iteration av algoritmen förstärks de bästa rutterna genom att passera elitmyror längs dessa rutter och därmed ökar antalet feromoner på dessa rutter. I ett sådant system är antalet elitmyror en ytterligare parameter som måste bestämmas. Så för för många elitmyror kan algoritmen fastna vid lokala extrema.

MMAS (Max-Min ant system) [11]

Tillagda gränsvillkor för antalet feromoner (τ min ,τ max ). Feromoner avsätts endast på de globalt bästa eller bästa i iterationsvägarna. Alla kanter initieras med värdet τ max .

Proportionella pseudo-slumpmässiga regler

Presenteras ovan[ förtydliga ] [12] .

Myrrankningssystem (ASrank)

Alla lösningar rangordnas efter deras lämplighet. Antalet deponerade feromoner för varje lösning viktas så att lämpligare lösningar får fler feromoner än mindre lämpliga.

Långsiktig ortogonal myrkoloni (COAC)

COAC-feromonavsättningsmekanismen tillåter myror att söka lösningar tillsammans och effektivt. Med den ortogonala metoden kan myror i ett genomförbart område snabbt och effektivt utforska sina valda områden, med förbättrad global sökförmåga och precision.

Den ortogonala planeringsmetoden och den adaptiva radiestyrmetoden kan också utökas till andra optimeringsalgoritmer för att få bredare fördelar vid lösning av praktiska problem [13] .

Konvergens

Applikation

Exempel: pseudokod och formel

procedure ACO_MetaHeuristic while(not_termination) generateSolutions() daemonActions() pheromoneUpdate() end while end procedure

Kanter:
Myran kommer att flytta från nod till nod med en sannolikhet av:

, var:  är antalet feromoner på kanten ;  är parametern som styr påverkan av ; kantattraktionskraft (startvärde, vanligtvis , där d är avståndet);  är parametern som styr påverkan av .

Feromonuppdatering

,

var:

 är mängden feromon på bågen ,  är feromonens förångningshastighet,  är mängden avsatt feromon, vanligtvis definierad som: ,

var  är kostnaden för myrans väg (vanligtvis längden).

Andra exempel

Work-shop: problem med planering Bil: routingproblem

Det mest uppenbara och populära tillämpningsområdet för myrkolonialgoritmer är transportlogistik. Transportlogistikens uppgifter inkluderar sådana NP-hårda uppgifter som problem med resande säljare och fordonsdirigering [14] .

Uppgiftsproblemet Tilldelad uppgift

Svårigheter att definiera

Stigmergy-algoritmer

Termen "stigmergi" introducerades av den franske biologen P.-P. Grasse 1959 för att beskriva termiters beteende . Han definierade det som: " Stimulering av arbetare genom att öka deras produktivitet. » Termen kommer från två grekiska ord "stigma" (tecken, märke) och "ergo" (arbete, handling) [15] .

Se även

Anteckningar

  1. ↑ A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies , actes de la première conférence européenne sur la vie artificielle, Paris, Frankrike, Elsevier Publishing, 134-142, 1991.
  2. ↑ M. Dorigo, Optimization, Learning and Natural Algorithms , doktorsavhandling, Politecnico di Milano, Italien, 1992.
  3. ↑ P.-P. Grasse, La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La theorie de la Stigmergie: Essai d'interpretation du comportement des termites constructeurs , Insectes Sociaux, numero 6, sid. 41-80, 1959.
  4. ↑ JL Denebourg, JM Pasteels och JC Verhaeghe, Probabilistic Behavior in Ants: a Strategy of Errors? , Journal of Theoretical Biology, numero 105, 1983.
  5. ↑ F. Moyson, B. Manderick, Myrornas kollektiva beteende: ett exempel på självorganisering i massiv parallellism , Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Kalifornien, 1988.
  6. ↑ 1 2 S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, Den argentinska myrans självorganiserade utforskande mönster , Naturwissenschaften, volym 76, sidorna 579-581, 1989
  7. ↑ M. Ebling, M. Di Loreto, M. Presley, F. Wieland, et D. Jefferson, An Ant Foraging Model Implemented on the Time Warp Operating System , Proceedings of the SCS Multiconference on Distributed Simulation, 1989
  8. ↑ S. Iredi, D. Merkle och M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms , Evolutionary Multi-Criterion Optimization, First International Conference (EMO'01), Zürich, Springer Verlag, sidorna 359–372, 2001.
  9. ↑ L. Bianchi, LM Gambardella et M. Dorigo, An ant colony optimization approach to the probabilistic traveling salesman problem , PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, Berlin, Allemagne , 2002.
  10. ↑ J.-L. Deneubourg, S. Aron, S. Goss och J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine an , Journal of Insect Behavior, volym 3, sidan 159, 1990
  11. ↑ T. Stützle et HH Hoos, MAX MIN Ant System , Future Generation Computer Systems, volym 16, sid 889–914, 2000
  12. ↑ M. Dorigo et LM Gambardella, Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem , IEEE Transactions on Evolutionary Computation, volym 1, numero 1, sidorna 53-66, 1997.
  13. ↑ X Hu, J Zhang och Y Li (2008). Ortogonala metoder baserade på myrkolonisökning för att lösa kontinuerliga optimeringsproblem. Journal of Computer Science and Technology , 23(1), s.2-18.
  14. ↑ Kazharov A. A., Kureichik V. M. Myralgoritmer för att lösa transportproblem. Nyheter från den ryska vetenskapsakademin. Teori och styrsystem. 2010. Nr 1. S. 32-45.
  15. ↑ Bonabeau, E. "Redaktörens introduktion: Stigmergy." specialnummer av artificiellt liv på Stigmergy. Volym 5, nummer 2 / Våren 1999, s.95-96. http://www.stigmergicsystems.com/stig_v1/stigrefs/article1.html

Litteratur

  • M. Dorigo , 1992. Optimering, lärande och naturliga algoritmer , doktorsavhandling, Politecnico di Milano, Italien.
  • M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics-Del B, 26(1): 29-41.
  • M. Dorigo & LM Gambardella , 1997. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem." IEEE Transactions on Evolutionary Computation, 1(1): 53-66.
  • M. Dorigo, G. Di Caro & LM Gambardella, 1999. "Myralgoritmer för diskret optimering". Artificiellt liv, 5(2): 137-172.
  • E. Bonabeau, M. Dorigo och G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems , Oxford University Press. ISBN 0-19-513159-2
  • M. Dorigo & T. Stützle, 2004. Ant Colony Optimization , MIT Press. ISBN 0-262-04219-3
  • M. Dorigo, 2007. Myrkolonioptimering . Scholarpedia.
  • C. Blum, 2005 Myrkolonioptimering: Introduktion och senaste trender. Physics of Life Reviews, 2: 353-373
  • Shtovba S. D. Ant-algoritmer, Exponenta Pro. Matematik i applikationer. 2004. Nr 4
  • Kirsanov M.N. Grafer i lönn. — M .: Fizmatlit , 2007. — 168 sid. - ISBN 978-5-9221-0745-7 . http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
  • M. Dorigo, M. Birattari & T. Stützle, 2006 Myrkolonioptimering: artificiella myror som en beräkningsintelligensteknik .

Länkar