Algoritmul coloniilor de furnici

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Unele comportamente furnice sunt sursa algoritmilor de optimizare (aici, furnicile legionare din genul Dorylus )

Algoritmii coloniilor de furnici sunt algoritmi inspirați de comportamentul furnicilor sau de alte specii care formează un superorganism , care fac parte din optimizarea metaheuristică .

Propus inițial de Marco Dorigo și colab. , în 1990 [1] [2] , pentru a căuta căi optime într-un grafic , primul algoritm se bazează pe comportamentul furnicilor care caută o cale între colonia lor și o sursă de hrană. Ideea originală s-a diversificat de atunci pentru a rezolva o clasă mai largă de probleme, scoțând astfel în evidență diferiți algoritmi care se bazează pe diferite aspecte ale comportamentului furnicilor.

În limba engleză, termenul dedicat algoritmului principal este Ant Colony Optimization (ACO). Specialiștii rezervă acest termen pentru un anumit tip de algoritm. Cu toate acestea, există mai multe familii de metode bazate pe comportamentul furnicilor. În limba engleză, aceste abordări sunt grupate în funcție de termenii: algoritmi de colonii de furnici , optimizarea coloniilor de furnici , furnici artificiale sau diferite combinații ale acestor variante.

Origine

1) prima furnică găsește sursa de hrană (F), prin orice cale (a), apoi se întoarce la furnicar (N) lăsând în urmă o urmă de feromoni (b)
2) Celelalte furnici rulează fără discriminare patru rute posibile, dar întărirea pistei face cea mai scurtă rută mai atractivă
3) furnicile parcurg calea cea mai scurtă, porțiuni lungi de alte căi își pierd traseul feromonic

Ideea vine din observarea exploatării resurselor alimentare de către furnici. De fapt, acestea din urmă, chiar dacă sunt limitate la abilitățile cognitive ale unei singure furnici, sunt capabile, în mod colectiv, să găsească calea cea mai scurtă dintre o sursă de hrană și furnicar.

Biologii au observat, într-o serie de experimente efectuate începând cu 1989 [3] [4] , că o colonie de furnici, cu o alegere între două căi de lungimi diferite care duc la o sursă de hrană, avea tendința de a folosi calea mai scurtă.

Un model care explică comportamentul este după cum urmează:

  1. o furnică aleargă mai mult sau mai puțin aleator în jurul mediului coloniei;
  2. dacă descoperă o sursă de hrană, se întoarce mai mult sau mai puțin direct la cuib, lăsând o cale de feromoni în calea sa;
  3. feromonul devine atractiv, iar furnicile care trec în apropiere vor tinde să urmeze, mai mult sau mai puțin direct, calea;
  4. întorcându-se la cuib, aceste furnici vor întări calea;
  5. dacă aceeași sursă de hrană poate fi obținută dintr-o cale mai scurtă, furnicile vor tinde să o urmeze
  6. cursul scurt va fi din ce în ce mai consolidat și, prin urmare, mai atractiv;
  7. calea lungă va dispărea în cele din urmă, de fapt feromonul se evaporă;
  8. în cele din urmă toate furnicile determină și „aleg” calea cea mai scurtă.

Furnicile folosesc mediul ca mijloc de comunicare : fac schimb de informații indirect depunând feromoni, pentru a descrie starea „muncii” lor. Informațiile sunt schimbate local, de fapt o furnică are acces la feromon doar dacă se află în locul în care a fost depusă. Acest sistem se numește „ stigmergie ” și apare la diferite animale sociale (în special a fost studiat în cazul construcției de stâlpi în cuiburi de termite ).

Mecanismul care vă permite să rezolvați o problemă prea complexă pentru a putea fi confruntată cu furnici singure este un bun exemplu de sistem auto-organizat . Acest sistem se bazează pe reacții pozitive (depunerea feromonilor atrage alte furnici care vor întări calea) și negative (disiparea căii datorită evaporării împiedică blocarea sistemului). În teorie, dacă cantitatea de feromon rămâne aceeași în timp pe toate rutele, niciuna nu va fi aleasă. Cu toate acestea, datorită feedback-ului, o mică variație pe o cale va fi amplificată și, astfel, permite alegerea unei căi. Algoritmul vă permite să treceți de la o stare instabilă în care nici o cale nu este mai bună decât alta, la o stare stabilă în care calea este alcătuită din secțiuni „mai bune”.

Exemplu: sistemul Ant

Descriere generala

Algoritmul Ant sistem optimizează problema vânzătorului călător : 1) o furnică alege o cale și creează una cu feromoni
2) toate furnicile parcurg un anumit număr de piste, fiecare depunând o cantitate de feromoni proporțională cu calitatea căii
3) fiecare margine a celui mai bun traseu este mai întărită decât celelalte
4) evaporarea elimină cele mai proaste soluții

Primul algoritm al coloniilor de furnici a propus „Sistemul de furnici [5] (literalmente sistemul de furnici). Acesta își propune să rezolve problema vânzătorului călător , unde scopul este de a găsi cea mai scurtă cale de a conecta o serie de orașe.

Algoritmul general este relativ simplu și se bazează pe un set de furnici, fiecare dintre ele traversând una dintre căile posibile. În fiecare etapă, furnica alege să se mute dintr-un oraș în altul, conform unor reguli:

  1. cu cât un oraș este mai îndepărtat, cu atât are mai puține șanse de a fi ales („vizibilitatea”);
  2. cu cât este mai mare intensitatea căii feromonilor situată pe creasta dintre două orașe, cu atât are mai multe șanse să fie aleasă;
  3. odată ce calea sa este finalizată, furnica depune, pe toate marginile încrucișate, mai mult feromoni dacă calea este scurtă;
  4. căile feromonice se evaporă cu fiecare iterație .

Descriere formală

Regula deplasării, numită „regulă de tranziție proporțională aleatorie” este scrisă matematic după cum urmează:

unde este este lista posibilelor mișcări ale unei furnici când se află într-un oraș vizibilitatea, care este egală cu inversul distanței între două orașe Și Și intensitatea pistei la o anumită iterație Cei doi parametri principali care controlează algoritmul sunt Și care controlează importanța relativă a intensității și vizibilității unei muchii.

Odată prin orașe, o furnică depuneți o cantitate de feromoni pe fiecare margine a drumului său:

unde este este plimbarea făcută de furnică la iterație lungimea căii e un parametru de ajustare.

La sfârșitul fiecărei iterații a algoritmului, feromonul depus în iterațiile anterioare ale furnicilor se evaporă:

Și la sfârșitul iterației, avem cantitatea de feromoni care nu s-a evaporat și ce va fi depus:

unde este este numărul de furnici utilizate pentru iterație Și un parametru de ajustare.

Principalele variante

Algoritmul coloniilor de furnici a fost inițial utilizat în primul rând pentru a produce soluții aproape optime pentru problema vânzătorului călător și, mai general, pentru probleme de optimizare combinatorie .

Contextul ACO

O parte din algoritmi (inclusiv cei proiectați de Dorigo și colegii săi) sunt acum grupați sub termenul „Ant Colony Optimization” (ACO). Acest cadru este limitat la algoritmi care construiesc soluții sub formă de parametri asociați cu componentele unui grafic, utilizând un model de parte statistică.

O metodă de tip ACO urmează următoarea schemă algoritmică, stabilită de:

  • un criteriu de oprire a algoritmului
un timp de calcul alocat sau un număr de iterații care ating un prag nesatisfăcător de îmbunătățire a soluției sau o combinație de criterii
(eventual)
  • o construcție de soluții și căi de feromoni
depinde de problema de rezolvat și de structura acesteia
 Inițializați căile feromone;
Închidere din cauza criteriului de oprire nerealizat :
 
    construirea de soluții componentă cu componentă,

    utilizarea (opțională) a euristicii ,
 
    actualizați căile feromone;

 Sfârșitul ciclului.

O variantă eficientă a sistemului Ant este sistemul Max-Min Ant System (MMAS) [6] , unde numai cele mai bune furnici urmăresc căile și unde depozitul de feromoni este limitat de o limită superioară (împiedicând prea multă întărire a unei căi) și de la una inferioară (lăsând posibilitatea de a explora orice soluție). Acest algoritm a obținut rezultate mai bune decât originalul și, în special, evită convergența prematură.

Cealaltă variantă mai cunoscută se numește Ant Colony System (ACS) [7] , unde o nouă regulă de deplasare (numită „regulă proporțională pseudo-aleatorie”) adaugă un proces de actualizare a căilor feromone „locale”, scopul a acestui mecanism este creșterea diversificării cercetării.

Este posibil, într-un fel, să demonstreze că algoritmul este convergent (adică este capabil să găsească optimul global într-un timp finit). Primele dovezi ale convergenței algoritmului coloniilor de furnici au fost descoperite în anul 2000, grație algoritmului sistemului de furnici bazat pe grafic și algoritmilor ACS și MMAS. La fel ca majoritatea metaheuristicilor, este foarte dificil de estimat viteza convergenței.

În 2004, Zlochin și colegii săi au demonstrat [8] că algoritmii de tip ACO pot fi asimilați cu algoritmi descendenți de gradient stocastic, entropie încrucișată și estimare a distribuției. Ei au propus să grupeze aceste metaheuristici în cercetări bazate pe modele .

O definiție dificilă

Cu un algoritm de colonii de furnici, cea mai scurtă cale, pe grafic, între punctele A și B, este construită printr-o combinație de mai multe căi

Nu este ușor să se dea o definiție precisă a ceea ce este sau ce nu este un algoritm de colonii de furnici, deoarece definiția poate varia în funcție de autori și utilizări.

Într-un mod foarte general, algoritmii coloniilor de furnici sunt considerați ca metaheuristică a populației , unde fiecare soluție este reprezentată de o mișcare a furnicii pe spațiul de căutare. Furnicile marchează cele mai bune soluții și iau în considerare marcajele anterioare pentru a-și optimiza căutarea.

Ele pot fi considerate algoritmi probabilistici multi-agenți care utilizează o distribuție implicită a probabilității pentru tranziția dintre fiecare iterație. În versiunile lor pentru probleme combinatorii, utilizează o construcție iterativă de soluții.

Potrivit unor autori, diferența dintre algoritmii coloniilor de furnici și alte procese metaheuristice similare (cum ar fi algoritmii pentru estimarea distribuției sau optimizarea roiurilor de particule) este tocmai aspectul său constructiv. Într-adevăr, în problemele combinatorii, este posibil să se găsească în cele din urmă cea mai bună soluție, chiar dacă nici o furnică nu a folosit-o eficient. Astfel, în exemplul problemei vânzătorului călător, nu este necesar ca o furnică să ia de fapt cea mai scurtă rută: poate fi construită din segmente întărite ale celor mai bune soluții. Cu toate acestea, această definiție poate fi problematică în cazul variabilelor reale la problemele în care nu există o structură în zonă.

Comportamentul colectiv al insectelor sociale rămâne o sursă de inspirație pentru cercetători. Marea varietate de algoritmi (pentru optimizare și altele) care susțin autoorganizarea în sistemele biologice a dat naștere conceptului de „ inteligență de roi ”, care este un cadru foarte general, în cadrul căruia există și algoritmi ai coloniilor de furnici.

Algoritmi stigmergici

Pictogramă lupă mgx2.svg Același subiect în detaliu: Stigmergy .

În practică, se observă că un număr mare de algoritmi pretind inspirație pentru coloniile de furnici , fără a împărtăși întotdeauna imaginea generală a optimizării coloniilor de furnici (ACO). În practică, schimbul de informații între furnici prin mediul înconjurător (un principiu numit „stigmergy”) este suficient pentru a le introduce în categoria algoritmilor coloniilor de furnici. Acest principiu i-a determinat pe unii autori să creeze termenul „Optimizare stigmergică” [9] .

Există, de asemenea, metode bazate pe comportament de a căuta hrană, divizarea muncii sau transportul cooperativ.

Aplicații

Problema rucsacului . Furnicile în număr limitat favorizează picătura de miere în cantități mici, dar este mai interesantă decât apa zaharată, mai abundentă, dar mai puțin hrănitoare

Variantele combinatorii pot avea un avantaj față de alte metaheuristici, în cazul în care graficul studiat se poate schimba dinamic în timpul execuției: colonia de furnici se va adapta relativ flexibil la schimbare. Acest lucru este interesant pentru rutare de rețea [10] .

Algoritmii de colonii de furnici au fost aplicați la multe probleme de optimizare combinatorie, de la replicarea proteinelor la sortarea vehiculelor. La fel ca multe metaheuristici, algoritmul de bază a fost adaptat problemelor dinamice în variabile reale, probleme stocastice, implementări multi-obiective sau paralele etc.

Istorie

Istoria algoritmilor coloniilor de furnici

  • 1959, Pierre-Paul Grassé inventează teoria stigmergiei pentru a explica comportamentul în timpul construcției cuiburilor de termite [11] ;
  • 1983, Deneubourg și colegii săi studiază comportamentul colectiv al furnicilor [12] ;
  • 1988, Moyson și Manderick prezintă un articol despre autoorganizarea furnicilor [13] ;
  • 1989, Lucrările lui Goss, Aron, Deneubourg și Pasteels, despre comportamentul colectiv al celor patru argentinieni , vor da ideea algoritmilor coloniilor de furnici [3] ;
  • 1989, Implementarea unui model comportamental în căutarea hranei de către Ebling și colegii săi [14] ;
  • 1991, M. Dorigo propune Sistemul furnicilor în teza sa de doctorat (care nu va fi publicată înainte de 1992 [2] ). El scrie, împreună cu V. Maniezzo și A. Colorni, un raport tehnic [15] , care va fi publicat cinci ani mai târziu [5] ;
  • 1995, Bilchev și Parmee publică prima încercare de adaptare la problemele de continuitate [16] ;
  • 1996, publicarea articolului despre sistemul furnicilor [5] ;
  • 1996, Stützle și Hoos inventează sistemul MAX-MIN Ant [6] ;
  • 1997, Dorigo și Gambardella publică Sistemul de colonii de furnici [7] ;
  • 1997, Schoonderwoerd și colegii săi dezvoltă prima aplicație a rețelelor de telecomunicații [17] ;
  • 1997, Martinoli și colegii săi se inspiră din algoritmii coloniilor de furnici pentru a controla roboții [18] ;
  • 1998, Dorigo lansează prima conferință dedicată algoritmilor coloniilor de furnici [19] ;
  • 1998, Stützle propune prima implementare paralelă [20] ;
  • 1999, Bonabeau și colegii săi scriu o carte care tratează în principal furnicile artificiale [21] ;
  • 1999, primele aplicații pentru sortarea vehiculelor, problema atribuirii, rucsacul multidimensional;
  • 2000, ediția specială a unei reviste științifice privind algoritmii coloniilor de furnici [22] ;
  • 2000, primele aplicații pentru planificare, programare secvențială, satisfacerea constrângerii;
  • 2000, Gutjahr dă prima demonstrație a convergenței algoritmilor coloniilor de furnici [23] ;
  • 2001, prima utilizare a algoritmilor de colonii de furnici de către companii ( Eurobios și AntOptima );
  • 2001, Iredi și colegii săi publică primul algoritm multi-obiectiv [24] ;
  • 2002, primele aplicații pentru timpii de proiectare a posturilor și rețelele bayesiene;
  • 2002, Bianchi și colegii săi propun primii algoritmi pentru problemele stochastice [25] ;
  • 2004, Zlochin și Dorigo arată că unii algoritmi sunt echivalenți cu gradientul stocastic de descendență, entropie încrucișată și algoritmi de estimare a distribuției [8] ;
  • 2005, primele aplicații la plierea proteinelor;
  • 2012, Prabhakar și colegii săi își publică cercetările legate de comunicarea pereche a furnicilor fără feromoni, reflectând principiile organizării rețelei de calculatoare. Modelul de comunicare a fost comparat cu Protocolul de control al transmisiei [26] .

Notă

  1. ^ (EN) Colorni A., M. Dorigo și V. Maniezzo, Optimizare distribuită de Ant Colonies , Paris, Editura Elsevier, 1991, pp. 134-142.
  2. ^ a b ( EN ) M. Dorigo, Optimizare, învățare și algoritmi naturali , Politecnico di Milano, teză de doctorat, 1992.
  3. ^ a b ( EN ) S. Goss, S. Aron, J.-L. Deneubourg și J.-M. Pasteels, Modelul explorator autoorganizat al furnicii argentiniene , vol. 76, Naturwissenschaften, 1989, pp. 579-581.
  4. ^ (EN) J.-L. Deneubourg, S. Aron, S. Goss și J.-M. Pasteels, Modelul explorator auto-organizator al furnicii argentiniene , vol. 3, Journal of Insect Behavior, 1990, p. 159.
  5. ^ a b c ( EN ) M. Dorigo, V. Maniezzo și A. Colorni, Sistemul furnicilor: optimizarea de către o colonie de agenți cooperanți , vol. 26, IEEE Transactions on Systems, Man, and Cybernetics - Partea B, 1996, pp. 29-41.
  6. ^ a b ( EN ) T. Stützle și HH Hoos, Sistemul MAX MIN Ant , vol. 16, Future Generation Computer Systems, 2000, pp. 889-914.
  7. ^ a b ( EN ) M. Dorigo și LM Gambardella, Sistemul Ant Colony: o abordare de învățare cooperativă a problemei vânzătorului călător , vol. 1, IEEE Transactions on Evolutionary Computation, 1997, pp. 53-66.
  8. ^ a b ( EN ) M. Zlochin, M. Birattari, N. Meuleau și M. Dorigo, Căutare bazată pe model pentru optimizare combinatorie: un sondaj critic , vol. 131, Annals of Operations Research, 2004, pp. 373-395.
  9. ^ (EN) și G. A. Ajith Crina, Optimizare stigmergică , vol. 31, Studies in Computational Intelligence, R. Vitorino, 2006, p. 299, ISBN 978-3-540-34689-0 .
  10. ^ (EN) KM Sim și WH Sun, Optimizarea coloniilor de furnici pentru rutare și echilibrare a sarcinii: sondaj și noi direcții , vol. 33, Man and Cybernetics, Part A, IEEE Transactions on Systems, 2003, pp. 560-572.
  11. ^ ( FR ) P.-P. Grassé, The reconstruction du nid et les coordinations inter-individelles chez Belicositermes natalensis și Cubitermes sp. La théorie de la Stigmergie: Essai d'interprétation du comportement des termites constructeurs , Insectes Sociaux, 1959, pp. 41-80.
  12. ^ (EN) Denebourg JL, JM Pasteels și JC Verhaeghe, Comportamentul probabilist la furnici: o strategie de erori? , Journal of Theoretical Biology, 1983.
  13. ^ (EN) și B. F. Moyson Manderick, Comportamentul colectiv al furnicilor: un exemplu de autoorganizare în paralelism masiv , Stanford, California, Simpozionul de primăvară Actes de AAAI privind modelele paralele de inteligență, 1988.
  14. ^ (EN) M. Ebling, M. Di Loreto, M. Presley, F. Wieland și D. Jefferson, Un model ant furajare implementat pe sistemul de operare Time Warp , Proceedings of the SCS Multiconference on Distributed Simulation, 1989.
  15. ^ (EN) Dorigo M., V. și A. Maniezzo Colorni, Feedback pozitiv ca strategie de căutare , raport tehnic nr. 91-016, Dept. Electronics, Politehnica din Milano, 1991.
  16. ^ (EN) G. Bilchev și IC Parmee, Metafora Coloniilor de furnici pentru căutarea spațiilor de proiectare continuă , și. Terence C. Fogarty, Evolutionary Computing Springer-Verlag, Proceedings of the AISB Workshop on Evolutionary Computation, 1995, pp. 25-39.
  17. ^ (EN) R. Schoonderwoerd, O. Holland, J. și L. Bruten Rothkrantz, Echilibrarea sarcinii bazată pe furnici în rețelele de telecomunicații , vol. 5, Comportament adaptiv, 1997, pp. 169-207.
  18. ^ (EN) A. Martinoli, M. Yamamoto și F. Mondada, Despre modelarea experimentelor colective bioinspirate cu roboți reali , A patra conferință europeană privind viața artificială ECAL-97, 1997.
  19. ^ (EN) M. Dorigo, ANTS '98, De la coloniile de furnici la furnicile artificiale: primul atelier internațional de optimizare a coloniilor de furnici , Bruxelles, ANTS 98 , 1998.
  20. ^ (EN) T. Stützle, Strategii de paralelizare pentru optimizarea coloniilor de furnici , vol. 1498, Proceedings of PPSN-V, a cincea conferință internațională privind rezolvarea paralelă a problemelor din natură, Springer-Verlag, 1998, pp. 722-731.
  21. ^ ( EN ) É. Bonabeau, M. Dorigo și G. Theraulaz, Inteligența roiului , Oxford University Press, 1999.
  22. ^ (EN) M. Dorigo, G. Di Caro și T. Stützle, număr special pe „Algoritmi ant” , vol. 16, Future Generation Computer Systems, 2000.
  23. ^ (EN) WJ Gutjahr, Un sistem de furnici bazat pe grafice și convergența acestuia , vol. 16, Future Generation Computer Systems, 2000, pp. 873-888.
  24. ^ (EN) Iredi S., D. Merkle și M. Middendorf, Optimizarea bi-criteriului cu algoritmi de furnici multi colonii , Prima conferință internațională (EMO'01), Optimizare evolutivă multi-criteriu, 200, pp. 359-372.
  25. ^ ( EN ) L. Bianchi, LM Gambardella și M. Dorigo, O abordare de optimizare a coloniilor de furnici pentru problema probabilistică a vânzătorului călător , Berlin, PPSN-VII, a șaptea conferință internațională privind rezolvarea paralelă a problemelor din natură, Note de curs în informatică, Springer Verlag, 2002.
  26. ^ (EN) Balaji Prabhakar, Katherine N. Dektar și Deborah M. Gordon, The Regulation of Ant Colony Foraging Activity Without Spatial Information , în PLOS Comput Biol, vol. 8, 23 august 2012, pp. e1002670, DOI : 10.1371 / journal.pcbi.1002670 , ISSN 1553-7358 ( WC ACNP ) , PMID 22927811 . Adus la 11 iunie 2016 .

Bibliografie

  • ( EN ) M. Dorigo, M. Birattari și T. Stützle, Optimizarea coloniei de furnici: furnici artificiale ca tehnică de inteligență computațională , vol. 1, IEEE Computational Intelligence Magazine, 2006, pp. 28–39.
  • ( FR ) Johann Dréo, Alain Petrowski, Éric Taillard și Patrick Siarry, Métaheuristiques pentru o optimizare dificilă ( PDF ), 2003. Accesat la 25 martie 2016 .
  • ( EN ) Éric Bonabeau, Marco Dorigo și Guy Theraulaz, Inteligența roiului: de la sistemele naturale la cele artificiale , Oxford University Press, 1999, ISBN 0-19-513159-2 .
  • ( EN ) Marco Dorigo și Thomas Stützle, Optimizarea coloniilor de furnici , Cambridge, MIT Press / Bradford Books, 2004, ISBN 0-262-04219-3 .
  • ( FR ) Nicolas Monmarché, Frédéric Guinand și Patrick Siarry, Fourmis artificielles , 1 (Des bases de optimization aux applications industrielles), Traité Informatique et Systèmes d'Information - IC2, Hermes, 2009, p. 333, ISBN 978-2-7462-2119-2 .
  • ( FR ) Nicolas Monmarché, Frédéric Guinand și Patrick Siarry, Fourmis artificielles , 2 (Nouvelles directions pour une intelligence collective), Traité Informatique et Systèmes d'Information - IC2, Hermes, 2009, p. 323, ISBN 978-2-7462-2349-3 .
  • ( FR ) Christine Solnon, Optimizare prin colonii de fourmis , Hermes-Lavoisier, 2008, p. 192, ISBN 978-2-7462-1863-5 .

Elemente conexe

linkuri externe