Algoritmo delle colonie di formiche: differenze tra le versioni

Versione delle 10:09, 11 gen 2024

Versione attuale delle 23:42, 15 mar 2025

Riga 28:

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, a 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:

Riga 70:

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 Dorigo e 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.

Riga 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 87:

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

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

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

Riga 93:

'''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 172:

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

==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=fr|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}}