Algoritmo delle colonie di formiche: differenze tra le versioni

Versione delle 03:59, 17 mag 2019

Versione attuale delle 23:42, 15 mar 2025

(11 versioni intermedie di 6 utenti non mostrate)

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 26:

Le formiche usano l'ambiente come mezzo di [[comunicazione]]: si scambiano informazioni indirettamente depositando feromone, in modo da descrivere lo stato del loro "lavoro". Le informazioni vengono scambiate in ambito locale, infatti una formica ha accesso al feromone solo se si trova nel luogo dove questo è stato depositato. Questo sistema è chiamato "[[stigmergia]]" e si verifica in vari animali sociali (in particolare è stato studiato nel caso della costruzione di pilastri nei nidi di [[Isoptera|termiti]]).

Il meccanismo che permette di risolvere un problema troppo complesso per essere affrontato da singole formiche è un buon esempio di sistema [[Auto-organizzazione|auto-organizzato]]. Questo sistema si basa su [[retroazione|retroazioni]] positive (la deposizione di feromone attira altre formiche che rafforzeranno il percorso) e negative (la dissipazione del percorso a causa dell'evaporazione impedisce al sistema di bloccarsi). In teoria, se la quantità di feromone rimane la stessa nel corso del tempo su tutti i percorsi, non ne verrà scelto alcuno. Tuttavia, a causa della retroazione, una piccola variazione su un percorso sarà amplificato e quindi consente la scelta di un percorso. L'algoritmo consente di passare da uno stato instabile dove nessun percorso è migliore di un altro, ada uno stato stabile in cui il percorso viene realizzato da tratti "migliori".

==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à.

L'algoritmo generale è relativamente semplice ed è basato su un insieme di formiche, ciascuna delle quali attraversa un percorso tra quelli possibili. In ogni fase, la formica sceglie di spostarsi da una città all'altra secondo alcune regole:

# più una città è distante, meno possibilità ha di essere scelta (la ''"visibilità"'');

# più l'intensità del percorso di feromone situato sul crinale tra due città è maggiore, più ha possibilità di essere scelto;

# una volta completato il suo percorso, la formica deposita, su tutti i bordi attraversati, più feromone se il percorso è breve;

Riga 41:

===Descrizione formale===

La regola di spostamento, chiamata ''"regola casuale di transizione proporzionale"'' è matematicamente scritta come segue:

:<math>p_{ij}^{k}\left(t\right)=\left\{ \begin{matrixcases}

<math>

\displaystyle\frac{\tau_{ij}\left(t\right)^{\alpha}\cdot\eta_{ij}^{\beta}}{{\scriptscriptstyle displaystyle\sum_{l\in J_{i}^{k}}}\tau_{il}\left(t\right)^{\alpha}\cdot\eta_{il}^{\beta}}, & \textrmtext{con }\, j\in J_{i}^{k}, \\

p_{ij}^{k}\left(t\right)=\left\{ \begin{matrix}

0, & \textrmtext{con }\, j\notin J_{i}^{k},\end{matrixcases}\right.</math>

\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}} & \textrm{con}\, j\in J_{i}^{k}\\

0 & \textrm{con}\, j\notin J_{i}^{k}\end{matrix}\right.

</math>

dove ''J<submath>J_{i</sub><sup>}^{k}</supmath>'' è l'elenco dei possibili spostamenti di una formica ''<math>k''</math> quando si trova in una città ''<math>i'',</math> ''η<submath>\eta_{ij}</submath>'' la visibilità, che è uguale all'inverso della distanza <math>d_{ij}</math> tra due città ''<math>i''</math> e ''j'' (''1/d<submath>ijj</submath>'') e ''τ<submath>\tau_{ij}(t)</submath> (t)'' l'intensità della pista ad una data iterazione ''<math>t''.</math> I due parametri principali che controllano l'algoritmo sono ''α''<math>\alpha</math> e ''β''<math>\beta,</math> che controllano l'importanza relativa della intensità e la visibilità di un bordo.

Una volta fatto il giro delle città, una formica <math>k</math> deposita una quantità <math>\Delta\tau^k_{ij}</math> di feromone su ogni bordo del suo percorso:

:<math>\Delta\tau_{ij}^{k}(t)=\begin{cases}

<math>

\Deltadisplaystyle\tau_frac{ijQ}{L^{k}(t)=\left}, & \text{con }(i,j)\beginin T^{matrixk}(t), \\

\frac{Q}{L^{k}(t)}0, & \textrmtext{con }\,(i,j)\innotin T^{k}(t),\\end{cases}</math>

0 & \textrm{con}\,(i,j)\notin T^{k}(t)\end{matrix}\right.

</math>

dove ''T<supmath>T^{k}(t)</supmath> (t)'' è il giro fatto dalla formica ''<math>k''</math> all'iterazione ''<math>t'',</math> ''L<supmath>L^{k}(t)</supmath> (t)'' la lunghezza del percorso e ''<math>Q''</math> un parametro di regolazione.

Alla fine di ogni iterazione dell'algoritmo, il feromone depositato nelle precedenti iterazioni delle formiche evaporano:

:<math> \rho \tau_{ij}(t).</math>

E alla fine dell'iterazione, si ha la quantità di feromone che non è evaporato e di quello che verrà depositato:

:<math>\tau_{ij}(t+1)=(1-\rho) \tau_{ij}(t) + \sum_{k=1}^{m}\Delta\tau_{ij}^{k}(t),</math>

<math>

\tau_{ij}(t+1)=(1-\rho) \tau_{ij}(t) + \sum_{k=1}^{m}\Delta\tau_{ij}^{k}(t)

</math>

dove ''<math>m''</math> è il numero di formiche utilizzate per l'iterazione ''<math>t''</math> e ''ρ''<math>\rho</math> un parametro di regolazione.

==Varianti principali==

L'algoritmo delle colonie di formiche è stato originariamente utilizzato principalmente per produrre soluzioni quasi ottimali per il [[problema del commesso viaggiatore]] e, più in generale, per i problemi di [[ottimizzazione combinatoria]].

=== Il contesto dell<nowiki>{{'</nowiki>}}''ACO'' ===

Parte degli algoritmi (compresi quelli progettati da M. Dorigo ede i suoi colleghi) sono ora raggruppati sotto il termine "Ant Colony Optimization" (ACO). Questo quadro si limita ad algoritmi che costruiscono delle soluzioni sotto forma di parametri associati ai componenti di un grafo, utilizzando un modello statistico di parte.

Un metodo di tipo ACO segue lo schema algoritmico seguente, impostato da:

Riga 83 ⟶ 77:

*'''un ''criterio d'arresto'' dell'algoritmo'''

:un tempo di calcolo o un numero d'iterazioni assegnati che raggiungono una soglia di miglioramento di soluzioni insoddisfacente, o una combinazione di criteri

*'''dell<nowiki>{{'</nowiki>}}''[[euristica]]'''''

: (eventualmente)

*'''una ''costruzione'' di soluzioni e di percorsi di feromone'''

Riga 90 ⟶ 84:

'''Inizializzare''' i percorsi di feromone;

'''Chiusura''' a causa del ''criterio d'arresto'' non soddisfatto :

'''costruzione''' delle soluzioni componente per componente,

utilizzo (facoltativo) dell<nowiki>{{'</nowiki>}}'''euristica''',

'''aggiornare''' i percorsi di feromone;

'''Fine''' del ciclo.

Una variante efficace all<nowiki>{{'</nowiki>}}''Ant sistem'' è il ''Max-Min Ant System'' (MMAS)<ref name="T. Stützle et H.H. Hoos">{{cita libro|autore=T. Stützle|autore2=H.H. Hoos|titolo=''MAX MIN Ant System''|editore=Future Generation Computer Systems|volume=16|pp=889-914|anno=2000|lingua=inglese}}</ref>, dove solo le migliori formiche tracciano dei percorsi e dove il deposito di feromone è limitato da un limite superiore (impedendo di rafforzare troppo un percorso) e da uno inferiore (lasciando la possibilità di esplorare qualsiasi soluzione). Questo algoritmo ha raggiunto risultati migliori rispetto all'originale, ed in particolare evita la convergenza prematura.

L'altra variante più conosciuta si chiama ''Ant Colony System'' (ACS)<ref name="M. Dorigo et L.M. Gambardella">{{cita libro|autore=M. Dorigo|autore2=L.M. Gambardella|titolo=''Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem''|editore=IEEE Transactions on Evolutionary Computation|volume=1|pp=53-66|anno=1997|lingua=en}}</ref>, dove una nuova regola di spostamento (chiamata "regola proporzionale pseudo-casuale") aggiunge un processo di aggiornamento dei percorsi di feromone "locali", lo scopo di questo meccanismo è quello di aumentare la diversificazione della ricerca.

Riga 105 ⟶ 99:

È possibile, per certi versi, dimostrare che l'algoritmo è convergente (vale a dire che è in grado di trovare l'ottimale globale in un tempo finito). La prima prova della [[convergenza]] dell'algoritmo delle colonie di formiche è stata scoperta nel 2000, grazie all'algoritmo ''graph-base ant system'', ed agli algoritmi ACS e MMAS. Come la maggior parte della metaeuristica, è molto difficile stimare la velocità di convergenza.

Nel 2004, Zlochin eie i suoi colleghi hanno dimostrato<ref name="Zlochin model-based search">{{cita libro|autore=M. Zlochin|autore2=M. Birattari|autore3=N. Meuleau|autore4=M. Dorigo|titolo=''Model-based search for combinatorial optimization: A critical survey''|editore=Annals of Operations Research|volume=131|pp=373-395|anno=2004|lingua=inglese}}</ref> che gli algoritmi di tipo ACO possono essere assimiliati ai metodi di stocastica gradiente di discesa, di cross-entropia e degli algoritmi per la stima della distribuzione. Hanno proposto di raggruppare queste metaeuristiche in ''ricerche sulla base di modelli''.

===Una definizione difficile===

Riga 123 ⟶ 117:

{{Vedi anche|Stigmergia}}

In pratica si osserva che un gran numero di algoritmi rivendicano una ispirazione alle ''colonie di formiche'', senza condividere sempre il quadro generale dell'ottimizzazione delle colonie di formiche (ACO). In pratica, lo scambio di informazioni tra formiche ''tramite'' l'ambiente (principio chiamato "stigmergia") è sufficiente per farli entrare nella categoria degli algoritmi di colonie di formiche. Questo principio ha portato alcuni autori a creare il termine ''"Stigmergic Optimization"''<ref>{{cita libro|autore=A. Ajith|autore2=G. Crina|editore=R. Vitorino|titolo=''Stigmergic Optimization''|url=https://archive.org/details/stigmergicoptimi0000unse|edizione=Studies in Computational Intelligence|volume=31|p=[https://archive.org/details/stigmergicoptimi0000unse/page/299 299]|anno=2006|ISBN=978-3-540-34689-0|lingua=inglese}}</ref>.

Ci sono anche metodi basati sul comportamento nella ricerca del nutrimento, la divisione del lavoro o nel trasporto in cooperazione.

Riga 173 ⟶ 167:

</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>;

* 1989, I lavori di Goss, Aron, Deneubourg et Pasteels, sul ''comportement collectifs des fourmis Argentines'', daranno l'idea degli algoritmi delle colonie di formiche<ref name="S. Goss" />;

* 1989, Implementazione di un modello di comportemento nella ricerca di cibo di Ebling ed i suoi colleghi<ref>{{cita libro|autore=M. Ebling|autore2=M. Di Loreto|autore3=M. Presley|autore4=F. Wieland|autore5=D. Jefferson|titolo=''An Ant Foraging Model Implemented on the Time Warp Operating System''|editore=Proceedings of the SCS Multiconference on Distributed Simulation|anno=1989|lingua=inglese}}</ref>;

* 1991, M. Dorigo propone l<nowiki>{{'</nowiki>}}''Ant System'' nella sua [[dottorato di ricerca|tesi del dottorato]] (che non sarà pubblicata prima del 1992<ref name="M. Dorigo, Optimization, Learning and Natural Algorithms" />). Scrive, con V. Maniezzo e A. Colorni, una relazione tecnica<ref>{{cita libro|autore=Dorigo M.|autore2=V. Maniezzo|autore3=A. Colorni|titolo= ''Positive feedback as a search strategy''|edizione=relazione tecnica numero 91-016|editore=Dip. Elettronica, Politecnico di Milano|anno=1991|lingua=inglese}}</ref>, che sarà pubblicata cinque anni più tardi<ref name="Ant system" />;

* 1995, Bilchev e Parmee pubblicano il primo tentativo d<nowiki>'</nowiki>adattamento a problemi di continuità<ref>{{cita libro|autore=G. Bilchev|autore2=I. C. Parmee|titolo=''The Ant Colony Metaphor for Searching Continuous Design Spaces''|editore=Proceedings of the AISB Workshop on Evolutionary Computation|altri=ed. Terence C. Fogarty, Evolutionary Computing Springer-Verlag|pp=25-39|anno=1995|lingua=inglese}}</ref>;

* 1996, Pubblicazione dell'articolo sull<nowiki>{{'</nowiki>}}''Ant System''<ref name="Ant system" />;

* 1996, Stützle e Hoos inventano il ''MAX-MIN Ant System''<ref name="T. Stützle et H.H. Hoos" />;

* 1997, Dorigo e Gambardella pubblicano l<nowiki>{{'</nowiki>}}''Ant Colony System''<ref name="M. Dorigo et L.M. Gambardella" />;

* 1997, Schoonderwoerd ed i suoi colleghi stanno sviluppando la prima applicazione di reti di telecomunicazioni<ref>{{cita libro|autore=R. Schoonderwoerd|autore2=O. Holland|autore3=J. Bruten|autore4=L. Rothkrantz|titolo=''Ant-based load balancing in telecommunication networks''|editore=Adaptive Behaviour|volume=5|pp=169-207|anno=1997|lingua=inglese}}</ref> ;

* 1997, Martinoli ed i suoi colleghi traggono ispirazione dagli algoritmi delle colonie di formiche per controllare i ''[[robot]]''<ref>{{cita libro|autore=A. Martinoli|autore2=M. Yamamoto|autore3=F. Mondada|titolo=''On the modelling of bioinspired collective experiments with real robots''|editore=Fourth European Conference on Artificial Life ECAL-97|anno=1997|lingua=inglese}}</ref> ;

* 1998, Dorigo lancia la prima conferenza dedicata agli algoritmi delle colonie di formiche<ref>{{cita libro|autore=M. Dorigo|titolo=''ANTS’ 98, From Ant Colonies to Artificial Ants : First International Workshop on Ant Colony Optimization''|editore=''ANTS 98''|città=Bruxelles|anno=1998|lingua=inglese}}</ref>;

* 1998, Stützle propone la prima implementazione parallela<ref>{{cita libro|autore=T. Stützle|titolo=''Parallelization Strategies for Ant Colony Optimization''|editore=Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag|volume=1498|pp=722-731|anno=1998|lingua=inglese}}</ref>;

Riga 198 ⟶ 192:

* 2004, Zlochin e Dorigo mostrano che alcuni algoritmi sono equivalenti al stocastico gradiente di discesa, la cross-entropia e gli algoritmi per la stima della distribuzione<ref name="Zlochin model-based search"/> ;

* 2005, prime applicazioni al ripiegamento delle proteine;

* 2012, Prabhakar ed i suoi colleghi pubblicano le loro ricerche relative alla comunicazione in coppia delle formiche senza feromone, che riflettono i principi di organizzazione della rete di computer. Il modello di comunicazione è stato confrontato al [[Transmission Control Protocol]]<ref>{{Cita pubblicazione|nome1=Balaji|nome2=Katherine N.|nome3=Deborah M.|cognome1=Prabhakar|cognome2=Dektar|cognome3=Gordon|titolo=The Regulation of Ant Colony Foraging Activity without Spatial Information|pubblicazione=PLOS Comput Biol|volume=8|data=23 agosto 2012|issn=1553-7358|pmid=22927811|pmcid=3426560|doi=10.1371/journal.pcbi.1002670|url=http://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1002670|pp=e1002670|accesso=11 giugno 2016|lingua=inglese}}</ref>.

== Note ==

Riga 204 ⟶ 198:

==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–3928-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|dataarchivio=3 marzo 2016|urlarchivio=https://web.archive.org/web/20160303192419/http://www.eyrolles.com/Chapitres/9782212113686/chap4_Dreo.pdf|urlmorto=sì}}

* {{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àurl=Cambridgehttps://archive.org/details/antcolonyoptimiz0000dori|altricittà=MACambridge|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==

Riga 220 ⟶ 214:

== Collegamenti esterni ==

* {{cita web|url=http://www.aco-metaheuristic.org/|titolo=Home Page dell'Ant Colony Optimization|lingua=en|accesso=25 marzo 2016|urlarchivio=https://web.archive.org/web/20131011081948/http://www.aco-metaheuristic.org/|urlmorto=sì}}

* {{cita web|1url=http://www.hant.li.univ-tours.fr/artantbib/artantbib.php|2titolo=Una lista di riferimenti bibliografici sulle formiche artificiali|lingua=en|urlmorto=sì|accesso=25 marzo 2016|urlarchivio=https://web.archive.org/web/20160304121823/http://www.hant.li.univ-tours.fr/artantbib/artantbib.php|dataarchivio=4 marzo 2016}}

* {{cita web|https://web.archive.org/web/2/http://www.cogs.susx.ac.uk/lab/nlp/gazdar/teach/atc/1999/web/johannf/index.html|Un'introduzione agli algoritmi delle colonie di formiche|lingua=en}}

* {{cita web|url=http://www.djoh.net/inde/ANTColony/applet.html|titolo=ANT Colony Algorithm|lingua=en}}

* {{cita web|1=http://www.hant.li.univ-tours.fr/artantbib/artantbib.php|2=Una lista di riferimenti bibliografici sulle formiche artificiali|lingua=en|urlmorto=sì|accesso=25 marzo 2016|urlarchivio=https://web.archive.org/web/20160304121823/http://www.hant.li.univ-tours.fr/artantbib/artantbib.php|dataarchivio=4 marzo 2016}}

* {{cita web|url=http://khayyam.developpez.com/articles/algo/voyageur-de-commerce/colonies-de-fourmis/|titolo=Applicazione di un algoritmo delle colonie di formiche al problema del commerciante viaggiatore|lingua=fr}}

* {{cita web|http://www.djoh.net/inde/ANTColony/applet.html|ANT Colony Algorithm|lingua=en}}

* {{cita web|http://khayyam.developpez.com/articles/algo/voyageur-de-commerce/colonies-de-fourmis/|Applicazione di un algoritmo delle colonie di formiche al problema del commerciante viaggiatore|lingua=fr}}

{{portale|biologia|matematica}}