Ant koloni algoritme

De algoritmer af ant kolonier (på engelsk, ant koloni optimering, eller ACO ) er algoritmer inspireret af adfærd af myrer eller andre arter, der udgør en superorganisme , og udgør en familie metaheuristikker for optimering .

Oprindeligt foreslået af Marco Dorigo et al. i 1990'erne, for at finde den optimale stier i en graf , blev den første algoritme er inspireret af opførslen af myrer på udkig efter en sti mellem deres koloni og en fødevare kilde . Den oprindelige idé er siden forgrenet for at løse en større klasse af problemer, og der er opstået flere algoritmer, der trækker på forskellige aspekter af myreadfærd.

På engelsk er udtrykket dedikeret til hovedklassen af algoritme " Ant Colony Optimization " (ACO). Specialister forbeholder sig dette udtryk for en bestemt type algoritme. Der er dog flere familier af metoder inspireret af myrers opførsel. På fransk er disse forskellige tilgange grupperet under udtrykkene: "ant colony algorithms" , "optimization by ant colonies" , "kunstige myrer" eller forskellige kombinationer af disse varianter.

Oprindelse

Den originale idé kommer fra observation af udnyttelse af madressourcer i myrer. Faktisk er disse, selvom de individuelt har begrænsede kognitive evner, kollektivt i stand til at finde den korteste vej mellem en fødekilde og deres rede.

Biologer har i en række eksperimenter, der blev udført fra 1989, observeret, at en myrekoloni, der har valget mellem to stier af ulig længde, der fører til en fødekilde, har tendens til at bruge den kortere vej.

En model, der forklarer denne adfærd, er som følger:

en myre (kaldet "spejder") strejfer mere eller mindre tilfældigt i omgivelserne omkring kolonien;
hvis den opdager en fødekilde, vender den tilbage mere eller mindre direkte til reden og efterlader et spor af feromoner på sin vej ;
disse feromoner er attraktive, og myrerne, der passerer i nærheden, har tendens til at følge mere eller mindre direkte dette spor;
vender tilbage til reden, vil de samme myrer forstærke sporet;
hvis det er muligt at nå to spor til den samme fødekilde, vil den kortere på samme tid blive rejst af flere myrer end den lange;
short track vil derfor blive mere og mere forstærket og derfor mere og mere attraktivt
det lange spor forsvinder til sidst, og feromonerne er flygtige;
I sidste ende bestemte alle myrer sig og “valgte” det korteste spor.

Myrer bruger deres miljø som et kommunikationsmedium : de udveksler indirekte information ved at deponere feromoner, som alle beskriver tilstanden for deres "arbejde". De udvekslede oplysninger har et lokalt omfang , kun en myre, der er placeret på det sted, hvor feromoner blev deponeret, har adgang til den. Dette system kaldes " stigmergy " og findes i flere sociale dyr (det er især blevet undersøgt i tilfælde af opførelse af søjler i termit reden ).

Mekanismen til løsning af et for komplekst problem til at blive tacklet af myrer alene er et godt eksempel på et selvorganiserende system . Dette system er baseret på positiv feedback (feromonaflejringen tiltrækker andre myrer, som igen styrker det) og negativ feedback (spredningen af banen ved fordampning forhindrer systemet i at køre). Teoretisk, hvis mængden af feromon forblev den samme over tid på alle grene, ville der ikke vælges noget spor. På grund af tilbagemeldingerne forstærkes imidlertid en lille variation på en gren og tillader derefter valget af en gren. Algoritmen gør det muligt at gå fra en ustabil tilstand, hvor ingen gren er mere markeret end en anden, til en stabil tilstand, hvor ruten dannes ud fra de "bedste" grene.

Eksempel: "myresystemet"

Generel beskrivelse

Den første foreslåede myrekolonialgoritme kaldes Ant-systemet . Det tager især sigte på at løse problemet med den rejsende sælger , hvor målet er at finde den korteste vej, der giver mulighed for at forbinde et sæt byer.

Den generelle algoritme er relativt enkel og er afhængig af et sæt myrer, der hver bevæger sig en sti blandt de mulige. I hvert trin vælger myren at flytte fra en by til en anden i henhold til nogle få regler:

hun kan kun besøge hver by én gang;
jo længere en by er, jo mindre chance har den for at blive valgt (dette er "synlighed");
jo større intensiteten af feromonsporet er placeret på højderyggen mellem to byer, jo mere sandsynligt vælges ruten;
når rejsen er afsluttet, lægger myren sig på alle de rejste kanter, flere feromoner, hvis rejsen er kort;
feromonsporene fordamper med hver iteration .

Formel beskrivelse

Forskydningsreglen, kaldet "proportional overgangs tilfældig regel", er skrevet matematisk i følgende form:

$p _ {{ij}} ^ {{k}} \ left (t \ right) = \ left \ {{\ begin {matrix} {\ frac {\ tau _ {{ij}} \ left (t \ right) ^ {{\ alpha}} \ cdot \ eta _ {{ij}} ^ {{\ beta}}} {{\ scriptscriptstyle \ sum _ {{l \ in J _ {{i}} ^ {{k}} }}} \ tau _ {{il}} \ left (t \ right) ^ {{\ alpha}} \ cdot \ eta _ {{il}} ^ {{\ beta}}}} og {\ textrm {si }} \, j \ i J _ {{i}} ^ {{k}} \\ 0 & {\ textrm {si}} \, j \ notin J _ {{i}} ^ {{k}} \ slut {matrix}} \ højre.$

hvor J i k er listen over mulige forskydninger for en myre k, når den er i en by i , η ij synligheden, som er lig med den omvendte afstand fra to byer i og j ( 1 / d ij ) og τ ij (t) intensiteten af sporet ved en given iteration t . De to hovedparametre, der styrer algoritmen, er α og β , som styrer den relative betydning af intensiteten og synligheden af en kant.

For myrerne at udforske uopdagede spor tildeles i praksis en ikke-nul sandsynlighed for at udforske disse "ukendte" byer, kontrolleret af parameteren γ. På denne måde skrives sandsynligheden for forskydning:

${\ displaystyle p_ {ij} ^ {k} \ left (t \ right) = \ left \ {{\ begin {matrix} {\ frac {\ gamma + \ tau _ {ij} \ left (t \ right) ^ {\ alpha} \ cdot \ eta _ {ij} ^ {\ beta}} {{\ scriptscriptstyle \ sum _ {l \ in J_ {i} ^ {k}}} (\ gamma + \ tau _ {il} \ venstre (t \ højre) ^ {\ alpha} \ cdot \ eta _ {il} ^ {\ beta})}} & {\ textrm {si}} \, j \ i J_ {i} ^ {k} \\ 0 og {\ textrm {si}} \, j \ notin J_ {i} ^ {k} \ end {matrix}} \ højre.}$

Når byturen er afsluttet, deponerer en ant k en mængde feromon på hver kant af sin rute: $\ Delta \ tau _ {{ij}} ^ {k}$

$\ Delta \ tau _ {{ij}} ^ {{k}} (t) = \ left \ {{\ begin {matrix} {\ frac {Q} {L ^ {{k}} (t)}} & {\ textrm {si}} \, (i, j) \ i T ^ {{k}} (t) \\ 0 & {\ textrm {si}} \, (i, j) \ notin T ^ {{ k}} (t) \ end {matrix}} \ højre.$

hvor T k (t) er tour fra myren k ved iteration t , L k (t) længden af stien og Q en indstillingsparameter.

I slutningen af hver iteration af algoritmen fordamper feromonerne, der er deponeret i tidligere iterationer af myrerne, fra:

$\ rho \ tau _ {{ij}} (t)$

Og i slutningen af iteration har vi summen af de feromoner, der ikke er fordampet, og dem, der lige er blevet deponeret:

$\ tau _ {{ij}} (t + 1) = (1- \ rho) \ tau _ {{ij}} (t) + \ sum _ {{k = 1}} ^ {{m}} \ Delta \ tau _ {{ij}} ^ {{k}} (t)$

hvor m er antallet af myrer, der bruges til iteration t og ρ en indstillingsparameter.

Hovedvarianter

Myrekolonialgoritmen blev oprindeligt brugt primært til at producere næsten optimale løsninger på det rejsende sælgerproblem og derefter mere generelt til kombinatoriske optimeringsproblemer . Det kan ses, at brugen siden starten har strakt sig til flere områder, fra kontinuerlig optimering til klassificering eller billedbehandling .

"ACO" -rammen

Nogle af algoritmerne (især dem designet af M. Dorigo og hans kolleger) er nu grupperet under udtrykket "Ant Colony Optimization" (ACO). Denne ramme er dog begrænset til algoritmer, der konstruerer løsninger i form af parametre, der er knyttet til komponenterne i en graf ved hjælp af en forudindtaget statistisk model.

En ACO- type metode følger følgende algoritmiske skema, parametreret af:

et kriterium for at stoppe algoritmen en beregningstid eller et tildelt antal iterationer overskredet, en løsningstærskel, der ikke længere er tilfredsstillende, eller en kombination af kriterier af heuristikker (muligvis) et kriterium for valg af veje til at udforske eller eliminere, ... en konstruktion af feromonløsninger og spor afhængigt af det problem, der skal løses, og dets struktur Initialisation des pistes de phéromone ; Boucler tant que critère d'arrêt non atteint : construire les solutions composant par composant, utilisation (facultative) d'une heuristique, mise à jour des pistes de phéromone ; Fin de la boucle.

En effektiv variant af det formiske system er Max-Min Ant System (MMAS), hvor kun de bedste myrer sporer spor, og hvor aflejringen af feromoner er begrænset af en øvre grænse (forhindrer et spor i at blive for forstærket) og en grænsemarkør lavere (giver mulighed for at blive undersøgt til enhver løsning). Denne algoritme opnår bedre resultater end originalen og undgår især for tidlig konvergens.

Den anden mest kendte variant er Ant Colony System (ACS), hvor en ny forskydningsregel (kaldet en "proportional pseudo-tilfældig regel") tilføjes en proces med "lokal" opdatering af sporelementerne. Feromoner, Målet med denne mekanisme er at øge diversificeringen af forskningen.

Det er muligt for nogle versioner at bevise, at algoritmen er konvergent (det vil sige, at den er i stand til at finde det globale optimale på en begrænset tid). Den første dokumentation for konvergens af en myre koloni algoritme blev tilvejebragt i 2000 for grafen-basen ant-systemet algoritme, derefter i ACS og MMAS algoritmer. Som med de fleste metaheuristikker er det meget vanskeligt teoretisk at estimere konvergensens hastighed.

I 2004 viste Zlochin og hans kolleger, at ACO-algoritmer kunne sammenlignes med stokastisk gradientnedstigning , kryds-entropi og distributionsestimeringsalgoritmer . De foreslog at gruppere disse metaheuristikker under udtrykket ”modelbaseret forskning”.

En vanskelig definition

Det er ikke let at give en præcis definition af, hvad en antikolonialgoritme er, og hvad der ikke er, fordi definitionen kan variere alt efter forfatterne og anvendelserne.

På en meget generel måde betragtes myrkolonialgoritmerne som populationsmetauristik , hvor hver løsning er repræsenteret af en myre, der bevæger sig på søgerummet. Myrerne markerer de bedste løsninger og tager hensyn til de tidligere markeringer for at optimere deres forskning.

Vi kan tænke på dem som sandsynlige multi-agent algoritmer ved hjælp af en implicit sandsynlighedsfordeling til at foretage overgangen mellem hver iteration. I deres versioner tilpasset kombinationsproblemer bruger de en iterativ konstruktion af løsningerne.

Ifølge nogle forfattere er det, der adskiller myrekolonialgoritmer fra andre tætte metheuristikker (såsom distributionsestimeringsalgoritmer eller partikel-sværmoptimering) netop dets konstruktive aspekt. Faktisk er det i kombinationsproblemer muligt, at den bedste løsning ender med at blive fundet, selvom ingen myre faktisk har oplevet det. Således er det i eksemplet med det rejsende sælgerproblem ikke nødvendigt for en myre at gå den korteste rute: den kan konstrueres fra de mest styrkede segmenter af de bedste løsninger. Denne definition kan dog være problematisk i tilfælde af reelle variable problemer, hvor der ikke findes nogen kvarterstruktur.

Den kollektive adfærd af sociale insekter forbliver en kilde til inspiration for forskere. Den store mangfoldighed af algoritmer (til optimering eller ej), der hævder at være selvorganiserende i biologiske systemer, har givet anledning til begrebet ' sværmintelligens ', som er en meget generel ramme, hvori den nedskriver antikolonialgoritmerne.

Stigmergiske algoritmer

Vi observerer i praksis, at et stort antal algoritmer hævder at være inspireret af ”ant-kolonier” uden altid at dele den generelle ramme for kanonisk antikolonioptimering (ACO). I praksis er brugen af udveksling af information mellem myrer via miljøet (princip kaldet "stigmergy") tilstrækkelig til at falde ind under kategorien antikolonialgoritmer. Dette princip har fået nogle forfattere til at skabe udtrykket "stigmergisk optimering".

Vi finder således metoder inspireret af opførsel af foder, sortering af larver, arbejdsdeling eller kooperativ transport.

Ansøgninger

Kombinationsvarianter kan have en fordel i forhold til andre metaheuristikker, i det tilfælde hvor den studerede graf kan ændre sig dynamisk under udførelse: Myrekolonien vil tilpasse sig relativt fleksibelt til ændringerne. Dette synes at være af interesse for netværk routing .

Antikolonialgoritmer er blevet anvendt på et stort antal kombinatoriske optimeringsproblemer, der spænder fra kvadratisk tildeling til proteinfoldning eller bærerute . Som mange metaheuristikker er den grundlæggende algoritme blevet tilpasset til dynamiske problemer, reelle variabler, stokastiske problemer, multi-objektive eller parallelle implementeringer osv.

Historisk

1959 Pierre-Paul Grasse opfinder teorien om stigmergi at forklare rede-bygning adfærd termitter ;
1983 Deneubourg og hans kolleger studere kollektive adfærd af myrer ;
1988 præsenterer Moyson og Manderick en artikel om selvorganisering i myrer;
1989, arbejde af Goss, Aron, Deneubourg og Pasteels, om den argentinske myres kollektive opførsel, hvilket gav ideen om myrekolonialgoritmer;
1989, implementering af en model for foderadfærd af Ebling og kolleger;
1991 foreslår M. Dorigo Ant System i sin doktorafhandling (som først offentliggøres i 1992). Han offentliggjorde sammen med V. Maniezzo og A. Colorni en teknisk rapport, som ville blive offentliggjort fem år senere;
1995 offentliggør Bilchev og Parmee det første forsøg på at tilpasse sig fortsatte problemer;
1996, offentliggørelse af artiklen om myresystemet ;
1996 opfinder Stützle og Hoos MAX-MIN Ant System ;
1997 udgiver Dorigo og Gambardella Ant Colony System ;
1997 designede Schoonderwoerd og hans kolleger den første applikation til telekommunikationsnetværk ;
1997 trækker Martinoli og hans kolleger inspiration fra myrekolonialgoritmer til robotkontrol ;
1998 lancerer Dorigo den første konference dedikeret til myrekolonialgoritmer;
1998 tilbyder Stützle de første parallelle implementeringer;
1999 udgav Bonabeau og hans kolleger en bog, der hovedsagelig beskæftiger sig med kunstige myrer ;
1999 første ansøgninger om routing af køretøj , tildelingsproblemet (i sin variant af det kvadratiske tildelingsproblem (in) ), den bageste multidimensionelle taske ;
2000, specialudgave af et videnskabeligt tidsskrift om myrekolonialgoritmer;
2000, første ansøgninger til planlægning , sekventiel planlægning, begrænsning af tilfredshed ;
2000 giver Gutjahr det første bevis på konvergens for en antikolonialgoritme;
2001, første brug af antikolonialgoritmer fra virksomheder ( Eurobios og AntOptima );
I 2001 offentliggør Iredi og hans kolleger den første multi-objektive algoritme;
2002, første ansøgninger til tidsplan design , Bayesian netværk ;
2002 foreslår Bianchi og hans kolleger den første algoritme for stokastisk problem (en) ;
2004 Zlochin og Dorigo viser, at nogle algoritmer svarer til stokastisk gradient afstamning , cross entropi og fordeling estimeringsalgoritmer ;
2005, første applikationer til proteinfoldning .
2012 offentliggør Prabhakar og hans kolleger arbejde vedrørende tandemkommunikation af myrer uden feromoner, der afspejler principperne for organisering af computernetværk. Kommunikationsmodellen er blevet sammenlignet med Transmission Control Protocol .

Kilder

(da) M. Dorigo, M. Birattari, T. Stützle, Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique , IEEE Computational Intelligence Magazine, bind 1, nummer 4, side 28–39, 2006.
(fr) Johann Dréo, Alain Petrowski, Éric Taillard, Patrick Siarry, Metaheuristik til vanskelig optimering , 2003 uddrag vedrørende algoritmerne for antikolonier .
(en) Éric Bonabeau, Marco Dorigo og Guy Theraulaz, Swarm Intelligence: From Natural to Artificial Systems , Oxford University Press, 1999. ( ISBN 0195131592 )
(da) Marco Dorigo og Thomas Stützle, Ant Colony Optimization , Cambridge, MA, MIT Press / Bradford Books, 2004. ( ISBN 0262042193 )
(fr) Nicolas Monmarché, Frédéric Guinand og Patrick Siarry (under ledelse), Kunstige myrer , afhandling om databehandling og informationssystemer - IC2, Hermes,november 2009, Bind 1 (fra det grundlæggende ved optimering til industrielle applikationer), 333 s. 16x24 Hardcover, ( ISBN 978-2-7462-2119-2 ) . og bind 2 (nye retninger for kollektiv intelligens), 323 s. 16x24 Hardcover, ( ISBN 978-2-7462-2349-3 ) .
(en) Christine Solnon. Optimering ved myrekolonier , Hermes-Lavoisier, august 2008, 192 s. ( ISBN 978-2-7462-1863-5 ) .

Noter og referencer

A. Colorni, M. Dorigo og V. Maniezzo, Distribueret optimering af Ant Colonies , procedurer fra den første europæiske konference om kunstigt liv, Paris, Frankrig, Elsevier Publishing, 134-142, 1991.
M. Dorigo, Optimization, Learning and Natural Algorithms , PhD thesis, Politecnico di Milano, Italy, 1992.
S. Goss, S. Aron, J.-L. Deneubourg og J.-M. Pasteels, Det selvorganiserede udforskende mønster af den argentinske myre , Naturwissenschaften, bind 76, side 579-581, 1989.
J.-L. Deneubourg, S. Aron, S. Goss og J.-M. Pasteels, Det argentinske myres selvorganiserende udforskningsmønster , Journal of Insect Behavior, bind 3, side 159, 1990.
M. Dorigo, V. Maniezzo og A. Colorni, Ant-system: optimering af en koloni af samarbejdsvillige agenter , IEEE-transaktioner på systemer, menneske og cybernetik - del B, bind 26, nummer 1, side 29 -41, 1996.
T. Stützle og HH Hoos, MAX MIN Ant System , Future Generation Computer Systems, bind 16, side 889-914, 2000.
M. Dorigo og LM Gambardella, Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem , IEEE Transactions on Evolutionary Computation, bind 1, nummer 1, side 53-66, 1997.
M. Zlochin, M. Birattari, N. Meuleau og M. Dorigo, Modelbaseret søgning efter kombinatorisk optimering: En kritisk undersøgelse , Annals of Operations Research, vol. 131, s. 373-395, 2004.
A. ajith; G. Crina; R. Vitorino (red.), Stigmergic Optimization , Studies in Computational Intelligence, bind 31, 299 sider, 2006. ( ISBN 978-3-540-34689-0 ) .
KM Sim, WH Sun, Ant koloni optimering for routing og load-balancing: undersøgelse og nye retninger , IEEE Transactions on Systems, Man og Kybernetik, del A, bind 33, nummer 5, side 560-572, 2003.
P.-P. Grassé, rekonstruktion af reden og interindividuel koordination i Belicositermes natalensis og Cubitermes sp. The Stigmergy Theory: Et forsøg på at fortolke konstruktortermitternes opførsel , sociale insekter, udgave 6, s. 41-80 , 1959.
JL Denebourg, JM Pasteels og JC Verhaeghe, probabilistisk adfærd i myrer: en fejlstrategi ? , Journal of Theoretical Biology, nummer 105, 1983.
F. Moyson B. Manderick, Den kollektive adfærd myrer: et eksempel på selvorganisering Massive Parallelitet , Proceedings of AAAI Spring Symposium on Parallelle modeller af Intelligence, Stanford, California, 1988.
M. Ebling, M. Di Loreto, M. Presley, F. Wieland og D. Jefferson, An Ant Foraging Model Implemented on the Time Warp Operating System , Proceedings of the SCS Multiconference on Distribueret Simulation, 1989.
Dorigo M., V. Maniezzo og A. Colorni, Positiv feedback som en søgestrategi , teknisk rapport nummer 91-016, Dip. Elettronica, Politecnico di Milano, Italien, 1991.
G. Bilchev og IC Parmee, Myren Colony metafor for Søgning Kontinuerlig Design Spaces , Proceedings of the AISB Workshop om Evolutionær Computation. Terence C. Fogarty (red.), Evolutionary Computing Springer-Verlag, side 25-39, april 1995.
R. Schoonderwoerd, O. Holland, J. Bruten og L. Rothkrantz, Ant-baseret load balancing i telekommunikationssystemer , Adaptive Behavior, bind 5, nummer 2, side 169-207, 1997.
A. Martinoli, M. Yamamoto og F. Mondada, Om modellering af bioinspirerede kollektive eksperimenter med ægte robotter , Fjerde europæiske konference om kunstigt liv ECAL-97, Brighton, UK, juli 1997.
M. Dorigo, ANTS '98, From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization, ANTS 98 , Bruxelles, Belgien, oktober 1998.
T. Stützle, Parallelization Strategies for Ant Colony Optimization , Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, bind 1498, side 722-731, 1998.
É. Bonabeau, M. Dorigo og G. Theraulaz, Swarm intelligence , Oxford University Press, 1999.
M. Dorigo, G. Di Caro og T. Stützle, specialudgave om "Ant Algorithms" , Future Generation Computer Systems, bind 16, nummer 8, 2000.
WJ Gutjahr, Et grafbaseret myresystem og dets konvergens , Future Generation Computersystemer, bind 16, side 873-888, 2000.
S. Iredi, D. Merkle og M. Middendorf, Bi-Kriterium Optimering med Multi Colony Ant Algoritmer , Evolutionary Multi-Criterion optimering, First International Conference (EMO'01), Zürich, Springer Verlag, side 359-372, 2001.
L. Bianchi, LM Gambardella og M.Dorigo, En myre koloni optimering tilgang til probabilistisk traveling salesman problem , PPSN-VII, syvende internationale konference om Parallel problemløsning fra naturen, Lecture Notes in Computer Science, Springer Verlag, Berlin, Tyskland , 2002.
Balaji Prabhakar , Katherine N. Dektar og Deborah M. Gordon , " The Regulation of Ant Colony Foraging Activity without Spatial Information ", PLOS Comput Biol , bind. 8,23. august 2012, e1002670 ( ISSN 1553-7358 , PMID 22927811 , PMCID 3426560 , DOI 10.1371 / journal.pcbi.1002670 , læst online , adgang 13. maj 2016 )

Se også

Relaterede artikler

Sociale insekter , kollektiv intelligens , komplekse system .
Algoritmer med fordelingsestimering , stokastisk gradientnedstigning , kryds-entropi , algoritmer svarende til ACO- formalismen .
Optimering med partikelsværme , Evolutionær algoritme , lignende metoder.

eksterne links

(da) Hjemmeside for optimering af myrekoloni, websted vedligeholdt af Marco Dorigo, bibliografi, kildekoder.
(fr) En introduktion til myrekolonialgoritmer (version arkiveret af Internet Archive )
(en) " En liste over bibliografiske referencer til kunstige myrer " ( Arkiv • Wikiwix • Archive.is • Google • Hvad skal jeg gøre? )
( fr ) ANT Colony Algorithm En Java-simulering af myrekolonialgoritmen med modificerbart terræn. Præsentation, dossier og kildekode, der kan downloades.
(da) Anvendelse af en myrekolonialgoritme på det rejsende sælgerproblem