Hangya kolónia algoritmus

Az algoritmusok a hangya kolóniák (angol, hangya kolónia optimalizálás, vagy ACO ) vannak algoritmusok által inspirált viselkedése a hangyák vagy más faj alkotó szuperorganizmusnak , és egy családját alkotják metaheuristics az optimalizálás .

Eredetileg Marco Dorigo et al. az 1990-es években az optimális utak grafikonon történő kereséséhez az első algoritmust a hangyák viselkedése inspirálta, akik utat keresnek a telepük és az élelmiszer- forrás között . Az eredeti ötlet azóta elágazik egy nagyobb problémaosztály megoldására, és számos algoritmus jött létre, amelyek a hangyák viselkedésének különböző aspektusait támasztják alá.

Angolul az algoritmus fő osztályának szentelt kifejezés az "  Ant Colony Optimization  " (ACO). A szakemberek ezt a kifejezést egy bizonyos algoritmustípusra fenntartják. Számos módszercsalád létezik azonban, amelyet a hangyák viselkedése ihletett. Francia nyelven ezeket a különböző megközelítéseket a következő kategóriákba sorolják: "hangyakolónia algoritmusok" , "hangyakolóniák általi optimalizálás" , "mesterséges hangyák" vagy e változatok különféle kombinációi.

Eredet

Az eredeti ötlet a hangyákban található élelmiszer-erőforrások kiaknázásának megfigyeléséből származik. Valójában ezek, noha egyénileg korlátozott kognitív képességekkel rendelkeznek , együttesen képesek megtalálni a legrövidebb utat az élelmiszerforrás és a fészek között.

A biológusok 1989-től végzett kísérletsorozatban azt figyelték meg, hogy egy hangyatelep, amely két egyenlő hosszúságú út közül választhat, amelyek táplálékforráshoz vezetnek, inkább a rövidebb utat választotta.

Ezt a viselkedést magyarázó modell a következő:

1. egy hangya (úgynevezett "cserkész") többé-kevésbé véletlenszerűen járja a telep körüli környezetet;
2. ha felfedez egy táplálékforrást, többé-kevésbé közvetlenül visszatér a fészkébe, feromonok nyomát hagyva útjában  ;
3. mivel ezek a feromonok vonzóak, a közelben elhaladó hangyák általában többé-kevésbé közvetlenül követik ezt az utat;
4. visszatérve a fészekbe, ugyanazok a hangyák megerősítik a nyomot;
5. ha két nyomvonal érhető el ugyanazon táplálékforráshoz, akkor a rövidebbet egyszerre több hangya fogja megtenni, mint a hosszút;
6. a rövid pálya ezért egyre inkább megerősödik, ezért egyre vonzóbb;
7. a hosszú pálya végül eltűnik, a feromonok ingadozóak;
8. Végül az összes hangya meghatározta és „kiválasztotta” a legrövidebb pályát.

A hangyák környezetüket kommunikációs eszközként használják  : feromonok lerakásával közvetett módon cserélnek információt, amelyek mind leírják "munkájuk" állapotát. A kicserélt információk helyi hatókörűek , csak a feromonok elhelyezésének helyén található hangya fér hozzá. Ezt a rendszert " stigmergynek  " nevezik  , és számos társas állatban megtalálható (különösen a termeszek fészkeiben lévő oszlopok építése esetén tanulmányozták ).

A túl bonyolult probléma megoldásának mechanizmusa, amelyet egyedül a hangyák kezelhetnek, jó példa az önszerveződő rendszerre . Ez a rendszer pozitív visszacsatoláson (a feromon lerakódás vonzza más hangyákat, amelyek viszont megerősítik) és negatív visszacsatolásokon (a pálya párolgással történő eloszlása ​​megakadályozza a rendszert versenyben). Elméletileg, ha a feromon mennyisége az összes ágon az idők folyamán ugyanaz marad, akkor nem választanának pályát. A visszacsatolások miatt azonban egy ág kis változata felerősödik, majd lehetővé teszi az ág választását. Az algoritmus lehetővé teszi, hogy egy olyan instabil állapotból, ahol egyik ág sem jelölhető meg jobban, mint egy másik, egy stabil állapotba, ahol az útvonal a „legjobb” ágakból alakul ki.

Példa: a "hangya rendszer"

Általános leírása

Az első javasolt hangyakolónia algoritmust Ant rendszernek hívják . Célja különösen az utazó eladó problémájának megoldása , ahol a cél a legrövidebb út megtalálása, amely lehetővé teszi városok összekapcsolását.

Az általános algoritmus viszonylag egyszerű, és egy hangyákra támaszkodik, amelyek mindegyike utat halad a lehetségesek között. Minden szakaszban a hangya néhány szabály szerint úgy dönt, hogy egyik városból a másikba költözik:

1. csak egyszer látogathat meg minden várost;
2. minél messzebb van egy város, annál kisebb az esélye annak, hogy megválasszák (ez a „láthatóság”);
3. minél nagyobb a feromonpálya intenzitása a két hegy közötti gerincen, annál valószínűbb az útvonal kiválasztása;
4. ha az útja befejeződött, a hangya minden megtett szélen lerakódik, több feromon, ha az út rövid;
5. a feromon nyomok minden iterációnál elpárolognak .

Hivatalos leírás

Az „arányos átmenet véletlenszerű szabálynak” nevezett elmozdulási szabály matematikailag a következő formában van megírva:

oénjk(t)={τénj(t)α⋅ηénjβ∑l∈Jénkτénl(t)α⋅ηénlβhaj∈Jénk0haj∉Jénk{\ displaystyle p_ {ij} ^ {k} \ bal (t \ jobb) = \ bal \ {{\ begin {mátrix} {\ frac {\ tau _ {ij} \ bal (t \ jobb) ^ {\ alfa } \ cdot \ eta _ {ij} ^ {\ beta}} {{\ scriptscriptstyle \ sum _ {l \ in J_ {i} ^ {k}}} \ tau _ {il} \ bal (t \ jobb) ^ {\ alpha} \ cdot \ eta _ {il} ^ {\ beta}}} és {\ textrm {si}} \, j \ J_ {i} ^ {k} \\ 0 és {\ textrm {si} } \, j \ notin J_ {i} ^ {k} \ end {mátrix}} \ right.}

ahol J i k az ant k k lehetséges elmozdulásainak listája, amikor egy i városban van , η ij a láthatóság, amely megegyezik két i és j város távolságának inverzével ( 1 / d ij ) és τ ij (t) a pálya intenzitása adott t iteráció mellett . Az algoritmust vezérlő két fő paraméter az α és β , amelyek szabályozzák az él intenzitásának és láthatóságának relatív fontosságát.

A gyakorlatban ahhoz, hogy a hangyák felfedezetlen nyomokat fedezzenek fel, ezeknek az „ismeretlen” városoknak a felfedezéséhez nem nulla valószínűséget rendelnek hozzá, amelyet a γ paraméter vezérel. Ily módon megírják az elmozdulás valószínűségét:

oénjk(t)={γ+τénj(t)α⋅ηénjβ∑l∈Jénk(γ+τénl(t)α⋅ηénlβ)haj∈Jénk0haj∉Jénk{\ displaystyle p_ {ij} ^ {k} \ left (t \ right) = \ left \ {{\ begin {mátrix} {\ frac {\ gamma + \ tau _ {ij} \ left (t \ right) ^ {\ alpha} \ cdot \ eta _ {ij} ^ {\ beta}} {{\ scriptscriptstyle \ sum _ {l \ in J_ {i} ^ {k}}} (\ gamma + \ tau _ {il} \ balra (t \ jobbra) ^ {\ alpha} \ cdot \ eta _ {il} ^ {\ beta})}} & {\ textrm {si}} \, j \ J_ {i} ^ {k} \\ -ban 0 és {\ textrm {si}} \, j \ notin J_ {i} ^ {k} \ end {mátrix}} \ right.}

Miután a városnézés befejeződött, egy hangya k egy mennyiségű feromont helyez el útvonalának minden szélén: Δτénjk{\ displaystyle \ Delta \ tau _ {ij} ^ {k}}

Δτénjk(t)={QLk(t)ha(én,j)∈Tk(t)0ha(én,j)∉Tk(t){\ displaystyle \ Delta \ tau _ {ij} ^ {k} (t) = \ balra {{\ \ begin {mátrix} {\ frac {Q} {L ^ {k} (t)}} és {\ textrm {si}} \, (i, j) \ itt: T ^ {k} (t) \\ 0 & {\ textrm {si}} \, (i, j) \ notin T ^ {k} (t) \ vége {mátrix}} \ jobb.}

ahol T k (t) az ant k által a t iteráción végzett túra , L k (t) az út hossza és Q egy beállítási paraméter.

Az algoritmus minden egyes iterációjának végén a hangyák által az előző iterációkban lerakódott feromonok elpárolognak:

ρτénj(t){\ displaystyle \ rho \ tau _ {ij} (t)}

Az iteráció végén megvan a még nem párolgó feromonok és az imént lerakódott feromonok összege:

τénj(t+1)=(1-ρ)τénj(t)+∑k=1mΔτénjk(t){\ displaystyle \ tau _ {ij} (t + 1) = (1- \ rho) \ tau _ {ij} (t) + \ összeg _ {k = 1} ^ {m} \ Delta \ tau _ {ij } ^ {k} (t)}

ahol m a t iterációhoz használt hangyák száma és ρ a beállítási paraméter.

Fő változatok

A hangyakolónia algoritmust eredetileg elsősorban az utazó eladó problémájának optimális megközelítésű megoldásainak előállítására , majd általánosabban a kombinatorikus optimalizálási problémákra használták . Látható, hogy a kezdetektől fogva felhasználása több területre is kiterjedt, a folyamatos optimalizálástól az osztályozásig vagy képfeldolgozás .

Az "ACO" keretrendszer

Néhány algoritmus (nevezetesen M. Dorigo és munkatársai által tervezett) mostantól az „Ant Colony Optimization” (ACO) kifejezés alá van csoportosítva. Ez a keretrendszer azonban azokra az algoritmusokra korlátozódik, amelyek egy grafikon összetevőihez társított paraméterek formájában megoldásokat készítenek, torz statisztikai modell felhasználásával.

Az ACO típusú módszer a következő algoritmikus sémát követi, amelyet paraméterez:

a kritérium megállás az algoritmus túllépték a számítási időt vagy az elosztott iterációk számát, a megoldás fejlesztési küszöbét, amely már nem kielégítő, vagy a kritériumok kombinációját a heurisztika (esetleg) a feltárási vagy kiküszöbölési utak kiválasztásának kritériuma, ... Egy építési feromon megoldások és pályák a megoldandó problémától és annak szerkezetétől függően 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.

Egy hatékony változata a hangyasav rendszer a Max-Min Ant Rendszer (MMAS), ahol csak a legjobb hangyák nyoma nyomvonalak és ahol a lerakódása feromonok korlátozza egy felső kötött (megelőzésére nyomvonal, hogy túlságosan megerősített), és egy határ marker - alacsonyabb (a megoldás feltárásának lehetőségét meghagyva). Ez az algoritmus jobb eredményeket ér el, mint az eredeti, és különösen elkerüli az idő előtti konvergenciát.

A másik legismertebb variáns az Ant Colony System (ACS), ahol egy új elmozdulási szabály (ún. „Arányos ál-véletlenszerű szabály”) kerül hozzáadásra a pályák elemeinek „helyi” frissítésével. Ennek a mechanizmusnak a célja a kutatás diverzifikációjának növelése.

Bizonyos verziók esetében be lehet bizonyítani, hogy az algoritmus konvergens (vagyis azt, hogy véges idő alatt képes megtalálni a globális optimumot). Az ant kolónia algoritmus konvergenciájának első bizonyítékát 2000-ben szolgáltattuk a gráf-alap hangya rendszer algoritmusához, majd az ACS és MMAS algoritmusokhoz. Mint a legtöbb metaheurisztikánál , nagyon nehéz elméletileg megbecsülni a konvergencia sebességét.

2004-ben Zlochin és munkatársai kimutatták, hogy az ACO típusú algoritmusok a sztochasztikus gradiens süllyedéshez , a kereszt-entrópiához és az eloszlásbecslés algoritmusaihoz hasonlíthatók . Javasolták, hogy ezeket a metaheurisztikákat csoportosítsák a „modellalapú kutatás” kifejezés alá.

Nehéz meghatározás

Nem könnyű pontos meghatározást adni arról, hogy mi a hangyatelep algoritmusa és mi nem, mert a meghatározás a szerzőktől és a felhasználástól függően változhat.

Nagyon általános módon az ant kolónia algoritmusokat populációs metaheurisztikának tekintjük , ahol minden megoldást a keresési térben mozgó hangya képvisel. A hangyák jelölik a legjobb megoldásokat, és kutatásuk optimalizálása érdekében figyelembe veszik az előző jelöléseket.

Úgy gondolhatunk rájuk, mint valószínűségi multi-ágens algoritmusokra , amelyek implicit valószínűségi eloszlást használnak az egyes iterációk közötti átmenethez. A kombinatorikus problémákra adaptált változataikban a megoldások iteratív felépítését alkalmazzák.

Egyes szerzők szerint az, ami megkülönböztetné a hangyasólyag-algoritmusokat a többi közeli metaheurisztikától (például eloszlásbecslési algoritmusok vagy részecskerész-optimalizálás), éppen az a konstruktív aspektusa. Valójában a kombinatorikus problémákban előfordulhat, hogy a legjobb megoldást találják meg, annak ellenére, hogy valójában egyetlen hangya sem tapasztalta volna meg. Így az utazó eladó problémájának példájában nem szükséges, hogy a hangya valóban a legrövidebb utat járja be: a legjobb megoldások legerősebb szegmenseiből lehet felépíteni. Ez a definíció azonban problematikus lehet valódi változó problémák esetén, ahol nincs szomszédsági struktúra.

A szociális rovarok kollektív viselkedése továbbra is inspirációs forrás a kutatók számára. Az algoritmusok sokfélesége (optimalizálás céljából vagy sem), amelyek azt állítják, hogy önszerveződnek a biológiai rendszerekben, felvetette a „ raj intelligencia  ” fogalmát  , amely nagyon általános keretrendszer, amelyben felírja a hangya telep algoritmusait.

Stigmergikus algoritmusok

A gyakorlatban megfigyelhetjük, hogy nagyszámú algoritmus azt állítja, hogy „hangyakolóniák” ihlették őket, anélkül, hogy mindig megosztanák a kanonikus hangyatelep optimalizálás (ACO) általános kereteit. A gyakorlatban a hangyák közötti, a környezeten keresztüli információcsere (a „stigmergy” elvet nevezik) elegendő ahhoz, hogy a hangyakolónia algoritmusok kategóriájába kerüljön. Ez az elv arra késztette a szerzőket, hogy létrehozzák a „stigmergikus optimalizálás” kifejezést.

Így találunk olyan módszereket, amelyeket a takarmányozás, a lárvák válogatása, a munkamegosztás vagy a szövetkezeti szállítás viselkedése inspirált.

Alkalmazások

A kombinatorikus variánsoknak előnye lehet más metaheurisztikákkal szemben abban az esetben, ha a vizsgált gráf dinamikusan változhat a végrehajtás során: a hangyakolónia viszonylag rugalmas módon alkalmazkodik a változásokhoz. Úgy tűnik, hogy ez érdekes lehet a hálózati útválasztás szempontjából .

A hangyakolónia algoritmusokat számos kombinatorikus optimalizálási problémára alkalmazták, a másodfokú hozzárendeléstől a fehérje hajtogatásáig vagy a járművezetésig . Sok metaheurisztikához hasonlóan az alapalgoritmust adaptálták dinamikus problémákra, valós változókra, sztochasztikus problémákra, több célú vagy párhuzamos megvalósításokra stb.

Történelmi

• 1959-ben, Pierre-Paul Grasse feltalálja az elmélet stigmergy megmagyarázni a fészekrakó viselkedését termeszek  ;
• 1983, Deneubourg és munkatársai a hangyák kollektív viselkedését vizsgálják  ;
• 1988, Moyson és Manderick cikket mutat be a hangyák önszerveződéséről ;
• 1989, Goss, Aron, Deneubourg és Pasteels munkája az argentin hangyák kollektív viselkedéséről, amely ötletet adott a hangyakolónia algoritmusainak;
• 1989, a táplálkozási magatartás modelljének bevezetése Ebling és munkatársai által;
• 1991 M. Dorigo javasolja Ant rendszer az ő doktori értekezés (ami nem tesszük közzé 1992-ig). V. Maniezzóval és A. Colornnal együtt közzétett egy technikai jelentést, amelyet öt évvel később fognak közzétenni;
• 1995, Bilchev és Parmee publikálja az első kísérletet a folyamatos problémákhoz való alkalmazkodásra;
• 1996 kiadvány a cikket az Ant rendszer  ;
• 1996, Stützle és Hoos feltalálja a MAX-MIN Hangya rendszert  ;
• 1997, Dorigo és Gambardella kiadják a Hangya telep rendszert  ;
• 1997, Schoonderwoerd és munkatársai tervezik az első alkalmazást a telekommunikációs hálózatokra  ;
• 1997, Martinoli és munkatársai inspirációt merítenek a robotvezérléshez szükséges hangya telep algoritmusaiból  ;
• 1998-ban Dorigo elindítja az első konferenciát, amely a hangyakolónia algoritmusainak szól;
• Stützle 1998 kínálja az első párhuzamos megvalósításokat;
• 1999, Bonabeau és munkatársai kiadnak egy könyvet, amely főleg a műhangyákkal foglalkozik  ;
• 1999 első alkalmazásai a jármű útválasztására , a hozzárendelési probléma (a másodfokú hozzárendelési probléma  változatában (in) ), a hátsó többdimenziós táska  ;
• 2000, a hangya telep algoritmusairól szóló tudományos folyóirat különkiadása;
• 2000, első alkalmazások ütemezésre , szekvenciális ütemezésre, kényszer-elégedettségre  ;
• 2000, Gutjahr a konvergencia első bizonyítékát adja egy hangyakolónia algoritmus számára;
• 2001, a hangyakolónia algoritmusok első használata a vállalatok részéről ( Eurobios és AntOptima );
• 2001, Iredi és munkatársai közzéteszik az első többcélú algoritmust;
• 2002, az első ütemterv- alkalmazás , Bayes-hálózatok  ;
• 2002, Bianchi és munkatársai javasolják az első algoritmust a sztochasztikus problémára  (en)  ;
• 2004, Zlochin és Dorigo azt mutatják, hogy egyes algoritmusok egyenértékűek a sztochasztikus gradiens süllyedéssel , a kereszt entrópiával és az eloszlás becslésével  ;
• 2005, első alkalmazások a fehérje hajtogatására .
• Prabhakar és munkatársai 2012-ben publikálnak olyan munkákat, amelyek a hangyák feromon nélküli tandem kommunikációjára vonatkoznak, tükrözve a számítógépes hálózat szervezésének alapelveit. A kommunikációs modellt összehasonlították az átviteli vezérlő protokollal .

Források

• (en) M. Dorigo, M. Birattari, T. Stützle, Hangya telep optimalizálása: Mesterséges hangyák mint számítási intelligencia technika , IEEE Számítási Intelligencia Magazin, 1. évfolyam, 4. szám, 28–39. oldal, 2006.
• (fr) Johann Dréo, Alain Petrowski, Éric Taillard, Patrick Siarry, Metaheuristics for nehezen optimalizálható , 2003 kivonat a hangya telepek algoritmusairól .
• (en) Éric Bonabeau, Marco Dorigo és Guy Theraulaz, Raj-intelligencia: A természettől a mesterséges rendszerekig , Oxford University Press, 1999. ( ISBN  0195131592 )
• (en) Marco Dorigo és Thomas Stützle, Ant Colony Optimization , Cambridge, MA, MIT Press / Bradford Books, 2004. ( ISBN  0262042193 )
• (fr) Nicolas Monmarché, Frédéric Guinand és Patrick Siarry (irányítása alatt), Mesterséges hangyák , Értekezés a számítástechnikai és informatikai rendszerek - IC2, Hermes,2009. november, 1. kötet (Az optimalizálás alapjaitól az ipari alkalmazásokig), 333 p. 16x24 keménytáblás, ( ISBN  978-2-7462-2119-2 ) . és 2. kötet (Új irányok a kollektív intelligenciához), 323 p. 16x24 keménytáblás, ( ISBN  978-2-7462-2349-3 ) .
• (en) Christine Solnon. Optimalizálás hangya kolóniákkal , Hermes-Lavoisier, 2008. augusztus, 192. o. ( ISBN  978-2-7462-1863-5 ) .

Megjegyzések és hivatkozások

1. A. Colorni, M. Dorigo és V. Maniezzo, Hangya-telepek elosztott optimalizálása, a mesterséges életről szóló első európai konferencia anyagai, Párizs, Franciaország, Elsevier Publishing, 134-142, 1991.
2. M. Dorigo, optimalizálás, tanulási és természetes algoritmusok , PhD értekezés, Politecnico di Milano, Olaszország, 1992.
3. S. Goss, S. Aron, J.-L. Deneubourg és J.-M. Pasteels, Az argentin hangya önszerveződő feltárási mintája , Naturwissenschaften, 76. évfolyam, 579-581. Oldal, 1989.
4. J.-L. Deneubourg, S. Aron, S. Goss és J.-M. Pasteels, Az argentin hangya önszerveződő feltáró mintája , Journal of Insect Behavior, 3. évfolyam, 159. oldal, 1990.
5. M. Dorigo, V. Maniezzo és A. Colorni, Hangya rendszer: optimalizálás együttműködő ügynökök kolóniájával , IEEE tranzakciók rendszereken, emberen és kibernetikán - B rész, 26. kötet, 1. szám, 29. oldal -41, 1996.
6. T. Stützle és HH Hoos, MAX MIN Ant Ant System , Future Generation Computer Systems, 16. évfolyam, 889–914., 2000. oldal.
7. M. Dorigo és LM Gambardella, Ant Colony System: A kooperatív tanulási megközelítés az utazó eladó problémájához , IEEE tranzakciók az evolúciós számításhoz, 1. kötet, 1. szám, 53-66. Oldal, 1997.
8. M. Zlochin, M. Birattari, N. Meuleau és M. Dorigo, Modellalapú keresés a kombinatorikus optimalizáláshoz: Kritikus felmérés , Annals of Operations Research, vol. 131. o. 373-395, 2004.
9. A. Ajith; G. Crina; R. Vitorino (szerk.), Stigmergic Optimization , Studies in Computational Intelligence, 31. évfolyam, 299 oldal, 2006. ( ISBN  978-3-540-34689-0 ) .
10. KM Sim, WH Sun, Ant kolónia optimalizálás az útválasztáshoz és a terhelés-kiegyensúlyozáshoz: felmérés és új irányok , IEEE tranzakciók a rendszereken, ember és kibernetika, A. rész, 33. kötet, 5. szám, 560–572. Oldal, 2003.
11. P.-P. Grassé, A fészek rekonstrukciója és az egyének közötti koordináció a Belicositermes natalensis és a Cubitermes sp. A stigmergy elmélet: Kísérlet a konstruktor termeszek viselkedésének értelmezésére , Szociális rovarok, 6. kérdés, p.  41-80 , 1959.
12. JL Denebourg, JM Pasteels és JC Verhaeghe, Valószínű viselkedés a hangyákban: Hibák stratégiája? , Theoretical Biology Journal, 105. szám, 1983.
13. F. Moyson B. Manderick, kollektív viselkedését hangyák: Példa önszerveződés Massive párhuzamosság , Proceedings of AAAI Spring Symposium on Parallel Összes Intelligence, Stanford, Kalifornia, 1988.
14. M. Ebling, M. Di Loreto, M. Presley, F. Wieland és D. Jefferson, az időgörbék operációs rendszerén megvalósított hangyafélék modell , az SCS multikonferencia terjesztése az elosztott szimuláción, 1989.
15. Dorigo M., V. Maniezzo és A. Colorni, Pozitív visszajelzés mint keresési stratégia , 91-016. Számú műszaki jelentés, Dip. Elettronica, Politecnico di Milano, Olaszország, 1991.
16. G. Bilchev és IC Parmee, The Ant Colony metafora Keresés Folyamatos tervezési tereket , Proceedings of the AISB Workshop on Evolutionary Computation. Terence C. Fogarty (szerk.), Evolutionary Computing Springer-Verlag, 1995. április 25-39.
17. R. Schoonderwoerd, O. Holland, J. és L. Bruten Rothkrantz, Hangyaalapú terheléselosztás a telekommunikációs hálózatokban , Adaptív viselkedés, 5. kötet, 2. szám, 169-207, 1997.
18. A. Martinoli, M. Yamamoto és F. Mondada, A bioinspirált kollektív kísérletek modellezéséről valódi robotokkal , a mesterséges élet negyedik európai konferenciája ECAL-97, Brighton, Egyesült Királyság, 1997. július.
19. M. Dorigo, ANTS '98 ANT telepeket Mesterséges Ants: First International Workshop on Ant Colony Optimization, hangyák 98 , Brüsszel, Belgium 1998 októberében.
20. T. Stützle, párhuzamosítás stratégiák Ant Colony Optimization , Proceedings of PPSN-V, a Fifth International Conference on Parallel problémamegoldás: Nature, Springer-Verlag, térfogat 1498, pages 722-731, 1998.
21. É. Bonabeau, M. Dorigo és G. Theraulaz, raj intelligencia , Oxford University Press, 1999.
22. M. Dorigo, G. Di Caro és T. Stützle, különszám „Ant algoritmusok” , Future Generation Computer Systems, 16. kötet, 8. számú, 2000.
23. WJ Gutjahr, Grafikonon alapuló hangyarendszer és annak konvergenciája , Future Generation Computer Systems, 16. évfolyam, 873–888., 2000. oldal.
24. S. Iredi, D. Merkle és M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms , Evolutionary Multi-Criterion Optimization, Első Nemzetközi Konferencia (EMO'01), Zürich, Springer Verlag, 359-372. Oldal, 2001.
25. L. Bianchi, LM Gambardella és M.Dorigo, An ant kolónia optimalizálási megközelítés a valószínű utazási eladó problémájához , PPSN-VII, Hetedik Nemzetközi Konferencia a Párhuzamos Problémamegoldásról a Természetből, Előadások a Számítástechnikában, Springer Verlag, Berlin, Németország , 2002.
26. Balaji Prabhakar , Katherine N. Dektar és Deborah M. Gordon : „  A hangyakolónia táplálkozási tevékenysége térinformációk nélkül  ”, PLOS Comput Biol , vol.  8,2012. augusztus 23, e1002670 ( ISSN  1553-7358 , PMID  22927811 , PMCID  3426560 , DOI  10.1371 / journal.pcbi.1002670 , online olvasás , hozzáférés : 2016. május 13 )

Lásd is

Kapcsolódó cikkek

• Szociális rovarok , kollektív intelligencia , komplex rendszer .
• Algoritmusok eloszlásbecsléssel , sztochasztikus gradiens süllyedéssel , kereszt entrópiával , az ACO formalizmussal egyenértékű algoritmusok .
• Optimalizálás részecske rajokkal , evolúciós algoritmus , hasonló módszerek.

Külső linkek

• (hu) Hangya telep optimalizálásának kezdőlapja , Marco Dorigo által fenntartott webhely, irodalomjegyzék, forráskódok.
• (fr) Bevezetés a hangyakolónia algoritmusaiba (az Internetes Archívum archiválta verzió )
• (en) „  listája irodalmi hivatkozások a mesterséges hangyák  ” ( Archív • Wikiwix • Archive.is • Google • Mit kell tenni? )
• ( fr ) ANT Colony Algorithm A hangya telep algoritmus Java-szimulációja módosítható terepen. Letölthető előadás, dokumentáció és forráskód.
• (en) Hangya telep algoritmusának alkalmazása az utazó eladó problémájára