Visualizza wikitesto di Algoritmo delle colonie di formiche

[[File:Safari ants.jpg|thumb|Alcuni comportamenti delle formiche sono la fonte di algoritmi di ottimizzazione (qui, le [[Dorylinae|formiche legionarie]] del genere ''[[Dorylus]]'')]]
Gli '''algoritmi delle colonie di formiche''' sono degli [[Algoritmo|algoritmi]] ispirati dal [[comportamento]] delle [[Formicidae|formiche]], o da altre specie che formano un [[Organismo vivente|superorganismo]], che sono una parte dell'[[Ottimizzazione (matematica)|ottimizzazione]] [[metaeuristica]].

Inizialmente proposto da [[Marco Dorigo]] [[et al.]], nel 1990<ref>{{cita libro|autore=A. Colorni|autore2=M. Dorigo|autore3=V. Maniezzo|titolo=''Distributed Optimization by Ant Colonies''|città=Parigi|editore=Elsevier Publishing|pp=134-142|anno=1991|lingua=inglese}}</ref><ref name="M. Dorigo, Optimization, Learning and Natural Algorithms">{{cita libro|autore=M. Dorigo|titolo=''Optimization, Learning and Natural Algorithms''|editore=PhD thesis|altri=Politecnico di Milano|anno=1992|lingua=inglese}}</ref>, per la ricerca dei percorsi ottimali in un [[grafo]], il primo algoritmo si basa sul comportamento delle formiche che cercano un percorso tra la loro colonia e una fonte di cibo. L'idea originale da allora si è diversificata per risolvere una classe più ampia di problemi, facendo quindi emergere diversi algoritmi attingendo da vari aspetti del comportamento delle formiche.

In inglese, il termine dedicato all'algoritmo principale è ''Ant Colony Optimisation'' (ACO). Gli specialisti riservano tale termine per un particolare tipo di algoritmo. Tuttavia, ci sono diverse famiglie di metodi basate sul comportamento delle formiche. In italiano, questi approcci sono raggruppati secondo i termini: ''algoritmi delle colonie di formiche'', ''ottimizzazione delle colonie di formiche'', ''formiche artificiali'' o diverse combinazioni di queste varianti.

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

I biologi hanno osservato, in una serie di esperimenti condotti dal 1989<ref name="S. Goss">{{cita libro|autore=S. Goss|autore2=S. Aron|autore3=J.-L. Deneubourg|autore4=J.-M. Pasteels|titolo=''The self-organized exploratory pattern of the Argentine ant''|editore=Naturwissenschaften|volume=76|pp=579-581|anno=1989|lingua=inglese}}</ref><ref>{{cita libro|autore=J.-L. Deneubourg|autore2=S. Aron|autore3=S. Goss|autore4=J.-M. Pasteels|titolo=''The self-organizing exploratory pattern of the Argentine ant''|editore=Journal of Insect Behavior|volume=3|p=159|anno=1990|lingua=inglese}}</ref>, che una colonia di formiche, con una scelta tra due percorsi di lunghezza diversa che conducono ad una fonte di cibo, tendeva ad utilizzare il percorso più breve.

Un modello che spiega il comportamento è il seguente:

# una formica corre più o meno a caso attorno all'ambiente della colonia;
# se scopre una fonte di cibo, ritorna più o meno direttamente al nido, lasciando nel suo percorso una scia di [[feromone]];
# il feromone diventa attraente, e le formiche che passano lì vicino tenderanno a seguire, più o meno direttamente, il percorso;
# tornando al nido, queste formiche ''rafforzeranno'' il percorso;
# se è possibile ottenere la stessa fonte alimentare da un percorso più breve, le formiche tenderanno a seguirlo
# il percorso corto sarà sempre più rafforzato, e quindi più attraente;
# il percorso lungo finirà per scomparire, infatti il feromone si volatilizza;
# alla fine tutte le formiche determinano e "scelgono" il percorso più breve.

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, a uno stato stabile in cui il percorso viene realizzato da tratti "migliori".

==Esempio: l{{'}}''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{{'}}''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;
# i percorsi di feromone evaporano ad ogni [[iterazione]].

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

:<math>p_{ij}^{k}\left(t\right)=\begin{cases}
\displaystyle\frac{\tau_{ij}\left(t\right)^{\alpha}\eta_{ij}^{\beta}}{{\displaystyle\sum_{l\in J_{i}^{k}}}\tau_{il}\left(t\right)^{\alpha}\eta_{il}^{\beta}}, & \text{con } j\in J_{i}^{k}, \\
0, & \text{con } j\notin J_{i}^{k},\end{cases}</math>

dove <math>J_{i}^{k}</math> è l'elenco dei possibili spostamenti di una formica <math>k</math> quando si trova in una città <math>i,</math> <math>\eta_{ij}</math> la visibilità, che è uguale all'inverso della distanza <math>d_{ij}</math> tra due città <math>i</math> e <math>j</math> e <math>\tau_{ij}(t)</math> 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}
\displaystyle\frac{Q}{L^{k}(t)}, & \text{con }(i,j)\in T^{k}(t), \\
0, & \text{con }(i,j)\notin T^{k}(t),\end{cases}</math>

dove <math>T^{k}(t)</math> è il giro fatto dalla formica <math>k</math> all'iterazione <math>t,</math> <math>L^{k}(t)</math> 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>

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{{'}}''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.

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

*'''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{{'}}''[[euristica]]'''''
: (eventualmente)
*'''una ''costruzione'' di soluzioni e di percorsi di feromone'''
: dipende dal problema da risolvere e dalla sua struttura

 '''Inizializzare''' i percorsi di feromone;
 '''Chiusura''' a causa del ''criterio d'arresto'' non soddisfatto :

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

     utilizzo (facoltativo) dell{{'}}'''euristica''',

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

  '''Fine''' del ciclo.

Una variante efficace all{{'}}''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.

È 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 e 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===
[[File:Aco shortpath.svg|thumb|Con un algoritmo delle colonie di formiche, il percorso più breve, sul grafo, tra i punti A e B, è costruito attraverso una combinazione di diversi percorsi]]

Non è facile dare una definizione precisa di ciò che è o ciò che non è un algoritmo delle colonie di formiche, perché la definizione può variare a seconda degli autori e degli usi.

In modo molto generale, gli algoritmi delle colonie di formiche sono considerati come delle metaeuristiche di [[popolazione]], dove ogni soluzione è rappresentata da un movimento della formica sullo spazio di ricerca. Le formiche segnano le migliori soluzioni, e tengono conto delle marcature precedenti per ottimizzare la loro ricerca.

Essi possono essere considerati come algoritmi probabilistici multi-agente che utilizzano una distribuzione di probabilità implicita per la transizione tra ogni iterazione. Nelle loro versioni per problemi combinatori, usano una costruzione iterativa di soluzioni.

Secondo alcuni autori, la differenza fra gli algoritmi delle colonie di formiche ed altri processi metaeuristici simili (come gli algoritmi di stima della distribuzione o di ottimizzazione degli sciami di particelle) è proprio il suo aspetto costruttivo. Infatti, nei problemi combinatori, è possibile che alla fine sarà trovata la soluzione migliore, anche se nessuna formica l'avrà utilizzata in modo efficiente. Così, nell'esempio del problema del commesso viaggiatore, non è necessario che una formica effettivamente faccia il percorso più breve: può essere costruito da segmenti rinforzati delle soluzioni migliori. Tuttavia, questa definizione può essere problematica nel caso di variabili reali a problemi in cui nessuna struttura esiste nella zona.

Il comportamento collettivo degli [[insecta|insetti]] sociali rimane una fonte di ispirazione per i ricercatori. L'ampia varietà di algoritmi (per l'ottimizzazione e non) che sostengono l'auto-organizzazione nei sistemi biologici ha dato origine al concetto di "[[swarm intelligence]]", che è un quadro molto generale, al cui interno vi sono anche gli algoritmi delle colonie di formiche.

===Algoritmi di stigmergia===
{{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.

==Applicazioni==
[[File:Knapsack ants.svg|thumb|[[Problema dello zaino]]. Le formiche in numero limitato privilegiano la goccia di miele in piccole quantità, ma è più interessante dell'acqua zuccherata, più abbondante, ma meno nutriente]]
Le varianti combinatorie possono avere un vantaggio rispetto ad altre metaeuristiche, nel caso in cui il grafico studiato può cambiare in modo dinamico durante l'esecuzione: la colonia di formiche si adatterà in modo relativamente flessibile al cambiamento. Questo è interessante per l'[[instradamento]] [[Rete di computer|di reti]]<ref>{{cita libro|autore=K. M. Sim|autore2=W. H. Sun|titolo=''Ant colony optimization for routing and load-balancing : survey and new directions''|editore=IEEE Transactions on Systems|edizione=Man and Cybernetics, Part A|volume=33|pp=560-572|anno=2003|lingua=inglese}}</ref>.

Gli algoritmi delle colonie di formiche sono stati applicati a molti problemi di ottimizzazione combinatoria, dalla replicazione delle [[proteina|proteine]] allo smistamento dei veicoli. Come molte metaeuristiche, l'algoritmo di base è stato adattato ai problemi dinamici in variabili reali, problemi stocastici, multi-obiettivi o ad implementazioni parallele, etc.

==Storia==
<div class="thumb tright" style="width:210px">
<div class="thumbcaption">
<div class="magnify" class="internal">
<timeline>
ImageSize = width:210 height:300
PlotArea = width:170 height:280 left:40 bottom:10

DateFormat = yyyy
Period = from:1985 till:2005
TimeAxis = orientation:vertical
ScaleMajor = unit:year increment:5 start:1985

Colors=
   id:fond     value:white #rgb(0.95,0.95,0.98)
   id:marque   value:rgb(1,0,0)
   id:marque_fond value:rgb(1,0.9,0.9)
BackgroundColors = canvas:fond

Define $dx = 7 # décalage du texte à droite de la barre
Define $dy = -3 # décalage vertical
Define $dy2 = 6 # décalage vertical pour double texte

PlotData=
  bar:Leaders color:marque_fond width:5 mark:(line,marque) align:left fontsize:S

  from:1989  till:1989 shift:($dx,$dy)    text:comportamenti collettivi
  from:1991  till:1992 shift:($dx,$dy)    text:Ant System (AS)
  from:1995  till:1995 shift:($dx,$dy)    text:CACO
  from:1996  till:1996 shift:($dx,$dy)    text:Ant Colony System (ACS)
  from:1996  till:1996 shift:($dx,$dy2)   text:MAX-MIN Ant System (MMAS)
  from:2000  till:2000 shift:($dx,$dy)   text:GBAS
  from:2001  till:2001 shift:($dx,$dy)   text:multi-obiettivo

</timeline>
</div>
Cronologia degli algoritmi delle colonie di formiche
</div>
</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=fr}}</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{{'}}''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{{'}}''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{{'}}''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>;
* 1999, Bonabeau ed i suoi colleghi stanno scrivendo un libro che tratta principalmente delle ''formiche artificiali''<ref>{{cita libro|autore=É. Bonabeau|autore2=M. Dorigo|autore3=G. Theraulaz|titolo=''Swarm intelligence''|editore=Oxford University Press|anno=1999|lingua=inglese}}</ref>;
* 1999, prime applicazioni per lo smistamento dei veicoli, il problema assegnazione, lo zaino multi-dimensionale;
* 2000, edizione speciale di una rivista scientifica sugli algoritmi delle colonie di formiche<ref>{{cita pubblicazione|autore=M. Dorigo|autore2=G. Di Caro|autore3=T. Stützle|titolo=''special issue on “Ant Algorithms”''|editore=Future Generation Computer Systems|volume=16|anno=2000|lingua=inglese}}</ref>;
* 2000, prime applicazioni per la pianificazione, la programmazione sequenziale, la soddisfazione del vincolo;
* 2000, Gutjahr dà la prima dimostrazione della convergenza degli algoritmi delle colonie di formiche<ref>{{cita libro|autore=W.J. Gutjahr|titolo=''A graph-based Ant System and its convergence''|editore=Future Generation Computer Systems|volume=16|pp=873-888|anno=2000|lingua=inglese}}</ref>;
* 2001, primo utilizzo degli algoritmi delle colonie di formiche da parte delle aziende ([http://www.eurobios.com Eurobios] e [http://www.antoptima.com AntOptima]);
* 2001, Iredi ed i suoi colleghi pubblicano il primo algoritmo multi-obiettivo<ref>{{cita libro|autore=S. Iredi|autore2=D. Merkle|autore3=M. Middendorf|titolo=''Bi-Criterion Optimization with Multi Colony Ant Algorithms''|editore=Evolutionary Multi-Criterion Optimization|altri=First International Conference (EMO’01)|pp=359-372|anno=200|lingua=inglese}}</ref>;
* 2002, prime applicazioni per i tempi di progettazione del lavoro e per le reti Bayesiane;
* 2002, Bianchi ed i suoi colleghi propongono i primi algoritmi per i problemi stocastici<ref>{{cita libro|autore=L. Bianchi|autore2=L.M. Gambardella|autore3=M.Dorigo|titolo=''An ant colony optimization approach to the probabilistic traveling salesman problem''|editore=PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag|città=Berlino|anno=2002|lingua=inglese}}</ref>;
* 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|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 ==
<references/>

==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=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}}
* {{cita libro|autore=Marco Dorigo|autore2=Thomas Stützle|titolo=''Ant Colony Optimization''|url=https://archive.org/details/antcolonyoptimiz0000dori|città=Cambridge|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|ISBN=978-2-7462-2119-2|lingua=fr}}
* {{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|ISBN=978-2-7462-2349-3|lingua=fr}}
* {{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=fr}}

==Voci correlate==
*[[Insetti sociali]]
*[[Intelligenza collettiva]]
*[[Sistema complesso]]
*[[Particle Swarm Optimization]]
*[[Algoritmo evolutivo]]

== 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|url=http://www.hant.li.univ-tours.fr/artantbib/artantbib.php|titolo=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}}
* {{cita web|url=http://www.djoh.net/inde/ANTColony/applet.html|titolo=ANT Colony Algorithm|lingua=en}}
* {{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}}

{{portale|biologia|matematica}}

[[Categoria:Algoritmi sui grafi|Colonie di formiche]]
[[Categoria:Algoritmi di ottimizzazione|Colonie di formiche]]