Algoritmo delle colonie di formiche: differenze tra le versioni

Versione delle 21:40, 30 mar 2020

Versione delle 10:03, 24 mag 2021

Riga 7:

==Origine==

[[File:Aco branches.svg|thumb|1) la prima formica trova la fonte di cibo (F), tramite un percorso qualsiasi (a), poi ritorna al formicaio (N) lasciando dietro di sé una scia di feromone (b)<br/>2) Le altre formiche percorrono, indiscriminatamente, quattro percorsi possibili, ma il rafforzamento della pista rende più attraente il percorso più breve<br/>3) le formiche percorrono il percorso più breve, le lunghe porzioni di altri percorsi perdono la loro scia di feromone]]

L'idea nasce dall'osservazione dallo sfruttamento delle risorse alimentari da parte delle formiche. Infatti, quest'ultime, anche se limitatamente alle [[cognizione|capacità cognitive]] di una singola formica, sono in grado, collettivamente, di trovare il percorso più breve tra una fonte di cibo ed il formicaio.

Riga 30:

==Esempio: l<nowiki>'</nowiki>''Ant system''==

===Descrizione generale===

[[File:Aco TSP.svg|thumb|L'algoritmo ''Ant sistem'' ottimizza il [[problema del commesso viaggiatore]]: 1) una formica sceglie un percorso e ne crea uno col feromone<br/>2) tutte le formiche percorrono un certo numero di tracce, depositando ognuna una quantità di feromone proporzionale alla qualità del percorso<br/>3) ogni bordo del miglior percorso è più rinforzato rispetto agli altri<br/>4) l'evaporazione rimuove le soluzioni peggiori]]

Il primo algoritmo delle colonie di formiche proposto è l<nowiki>'</nowiki>''Ant system''<ref name="Ant system">{{cita libro|autore=M. Dorigo|autore2=V. Maniezzo|autore3=A. Colorni|titolo=''Ant system: optimization by a colony of cooperating agents''|editore=IEEE Transactions on Systems, Man, and Cybernetics--Part B|volume=26|pp=29-41|anno=1996|lingua=inglese}}</ref> (letteralmente ''sistema formica''). Ha lo scopo di risolvere il [[problema del commesso viaggiatore]], dove l'obiettivo è quello di trovare la via più breve per collegare una serie di città.

Riga 173:

</div>

* 1959, Pierre-Paul Grassé inventa la teoria della stigmergia per spiegare il comportemento durante la costruzione dei nidi di termiti<ref>{{cita libro|autore=P.-P. Grassé|titolo=''La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie : Essai d’interprétation du comportement des termites constructeurs''|editore=Insectes Sociaux|pp=41-80|anno=1959|lingua=francesefr}}</ref>;

* 1983, Deneubourg ed i suoi colleghi studiano il comportemento collettivo delle formiche<ref>{{cita libro|autore=J.L. Denebourg|autore2=J.M. Pasteels|autore3=J.C. Verhaeghe|titolo=''Probabilistic Behaviour in Ants : a Strategy of Errors?''|editore=Journal of Theoretical Biology|anno=1983|lingua=inglese}}</ref>;

* 1988, Moyson e Manderick presentano un articolo sull'auto-organizzazione delle formiche<ref name="F. Moyson, B. Manderick">{{cita libro|autore=F. Moyson|autore2=B. Manderick|titolo=''The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism''|editore=Actes de AAAI Spring Symposium on Parallel Models of Intelligence|città=Stanford, California|anno=1988|lingua=inglese}}</ref>;

Riga 205:

==Bibliografia==

* {{cita libro|autore=M. Dorigo|autore2=M. Birattari|autore3=T. Stützle|titolo=''Ant Colony Optimization : Artificial Ants as a Computational Intelligence Technique''|editore=IEEE Computational Intelligence Magazine|volume=1|pp=28–39|anno=2006|lingua=inglese}}

* {{cita libro|autore=Johann Dréo|autore2=Alain Petrowski|autore3=Éric Taillard|autore4=Patrick Siarry|titolo=''Métaheuristiques pour l’optimisation difficile''|anno=2003|url=http://www.eyrolles.com/Chapitres/9782212113686/chap4_Dreo.pdf|accesso=25 marzo 2016|lingua=francesefr}}

* {{cita libro|autore=Éric Bonabeau|autore2=Marco Dorigo|autore3=Guy Theraulaz|titolo=''Swarm Intelligence: From Natural to Artificial Systems''|editore=Oxford University Press|anno=1999|ISBN=0-19-513159-2|lingua=inglese}}

* {{cita libro|autore=Marco Dorigo|autore2=Thomas Stützle|titolo=''Ant Colony Optimization''|città=Cambridge|altri=MA|editore=MIT Press/Bradford Books|anno=2004|ISBN=0-262-04219-3|lingua=inglese}}

* {{cita libro|autore=Nicolas Monmarché|autore2=Frédéric Guinand|autore3=Patrick Siarry|titolo=''Fourmis artificielles''|editore=Traité Informatique et Systèmes d'Information - IC2, Hermes|anno=2009|volume=1 (Des bases de l'optimisation aux applications industrielles)|p=333 16x24|ISBN=978-2-7462-2119-2|lingua=francesefr}}

* {{cita libro|autore=Nicolas Monmarché|autore2=Frédéric Guinand|autore3=Patrick Siarry|titolo=''Fourmis artificielles''|editore=Traité Informatique et Systèmes d'Information - IC2, Hermes|anno=2009|volume=2 (Nouvelles directions pour une intelligence collective)|p=323 16x24|ISBN=978-2-7462-2349-3|lingua=francesefr}}

* {{cita libro|autore=Christine Solnon|titolo=''Optimisation par colonies de fourmis''|altri=Hermes-Lavoisier|anno=2008|p=192|ISBN=978-2-7462-1863-5|lingua=francesefr}}

==Voci correlate==