Algoritmo delle colonie di formiche

Gli algoritmi delle colonie di formiche sono degli algoritmi ispirati dal comportamento delle formiche, o da altre specie che formano un superorganismo, che sono una parte dell'ottimizzazione metaeuristica.

Inizialmente proposto da Marco Dorigo et al., nel 1990^[1]^[2], 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 modifica

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)
2) Le altre formiche percorrono, indiscriminatamente, quattro percorsi possibili, ma il rafforzamento della pista rende più attraente il percorso più breve
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 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^[3]^[4], 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 termiti).

Il meccanismo che permette di risolvere un problema troppo complesso per essere affrontato da singole formiche è un buon esempio di sistema auto-organizzato. Questo sistema si basa su 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 modifica

Descrizione generale modifica

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

Il primo algoritmo delle colonie di formiche proposto è l'Ant system^[5] (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 modifica

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

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

dove $J_{i}^{k}$ è l'elenco dei possibili spostamenti di una formica $k$ quando si trova in una città $i,$ $\eta _{ij}$ la visibilità, che è uguale all'inverso della distanza $d_{ij}$ tra due città $i$ e $j$ e $\tau _{ij}(t)$ l'intensità della pista ad una data iterazione $t.$ I due parametri principali che controllano l'algoritmo sono $\alpha$ e $\beta ,$ che controllano l'importanza relativa della intensità e la visibilità di un bordo.

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

\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}}

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

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

\rho \tau _{ij}(t).

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

\tau _{ij}(t+1)=(1-\rho )\tau _{ij}(t)+\sum _{k=1}^{m}\Delta \tau _{ij}^{k}(t),

dove $m$ è il numero di formiche utilizzate per l'iterazione $t$ e $\rho$ un parametro di regolazione.

Varianti principali modifica

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 modifica

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)^[6], 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)^[7], 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^[8] 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 modifica

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 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 modifica

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"^[9].

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

Applicazioni modifica

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 di reti^[10].

Gli algoritmi delle colonie di formiche sono stati applicati a molti problemi di ottimizzazione combinatoria, dalla replicazione delle 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 modifica

Cronologia degli algoritmi delle colonie di formiche

1959, Pierre-Paul Grassé inventa la teoria della stigmergia per spiegare il comportemento durante la costruzione dei nidi di termiti^[11];
1983, Deneubourg ed i suoi colleghi studiano il comportemento collettivo delle formiche^[12];
1988, Moyson e Manderick presentano un articolo sull'auto-organizzazione delle formiche^[13];
1989, I lavori di Goss, Aron, Deneubourg et Pasteels, sul comportement collectifs des fourmis Argentines, daranno l'idea degli algoritmi delle colonie di formiche^[3];
1989, Implementazione di un modello di comportemento nella ricerca di cibo di Ebling ed i suoi colleghi^[14];
1991, M. Dorigo propone l'Ant System nella sua tesi del dottorato (che non sarà pubblicata prima del 1992^[2]). Scrive, con V. Maniezzo e A. Colorni, una relazione tecnica^[15], che sarà pubblicata cinque anni più tardi^[5];
1995, Bilchev e Parmee pubblicano il primo tentativo d'adattamento a problemi di continuità^[16];
1996, Pubblicazione dell'articolo sull'Ant System^[5];
1996, Stützle e Hoos inventano il MAX-MIN Ant System^[6];
1997, Dorigo e Gambardella pubblicano l'Ant Colony System^[7];
1997, Schoonderwoerd ed i suoi colleghi stanno sviluppando la prima applicazione di reti di telecomunicazioni^[17] ;
1997, Martinoli ed i suoi colleghi traggono ispirazione dagli algoritmi delle colonie di formiche per controllare i robot^[18] ;
1998, Dorigo lancia la prima conferenza dedicata agli algoritmi delle colonie di formiche^[19];
1998, Stützle propone la prima implementazione parallela^[20];
1999, Bonabeau ed i suoi colleghi stanno scrivendo un libro che tratta principalmente delle formiche artificiali^[21];
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^[22];
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^[23];
2001, primo utilizzo degli algoritmi delle colonie di formiche da parte delle aziende (Eurobios e AntOptima);
2001, Iredi ed i suoi colleghi pubblicano il primo algoritmo multi-obiettivo^[24];
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^[25];
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^[8] ;
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^[26].

Note modifica

^ (EN) A. Colorni, M. Dorigo e V. Maniezzo, Distributed Optimization by Ant Colonies, Parigi, Elsevier Publishing, 1991, pp. 134-142.
^ ^a ^b (EN) M. Dorigo, Optimization, Learning and Natural Algorithms, Politecnico di Milano, PhD thesis, 1992.
^ ^a ^b (EN) S. Goss, S. Aron, J.-L. Deneubourg e J.-M. Pasteels, The self-organized exploratory pattern of the Argentine ant, vol. 76, Naturwissenschaften, 1989, pp. 579-581.
^ (EN) J.-L. Deneubourg, S. Aron, S. Goss e J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, vol. 3, Journal of Insect Behavior, 1990, p. 159.
^ ^a ^b ^c (EN) M. Dorigo, V. Maniezzo e A. Colorni, Ant system: optimization by a colony of cooperating agents, vol. 26, IEEE Transactions on Systems, Man, and Cybernetics--Part B, 1996, pp. 29-41.
^ ^a ^b (EN) T. Stützle e H.H. Hoos, MAX MIN Ant System, vol. 16, Future Generation Computer Systems, 2000, pp. 889-914.
^ ^a ^b (EN) M. Dorigo e L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, vol. 1, IEEE Transactions on Evolutionary Computation, 1997, pp. 53-66.
^ ^a ^b (EN) M. Zlochin, M. Birattari, N. Meuleau e M. Dorigo, Model-based search for combinatorial optimization: A critical survey, vol. 131, Annals of Operations Research, 2004, pp. 373-395.
^ (EN) A. Ajith e G. Crina, Stigmergic Optimization, vol. 31, Studies in Computational Intelligence, R. Vitorino, 2006, p. 299, ISBN 978-3-540-34689-0.
^ (EN) K. M. Sim e W. H. Sun, Ant colony optimization for routing and load-balancing : survey and new directions, vol. 33, Man and Cybernetics, Part A, IEEE Transactions on Systems, 2003, pp. 560-572.
^ (FR) P.-P. Grassé, 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, Insectes Sociaux, 1959, pp. 41-80.
^ (EN) J.L. Denebourg, J.M. Pasteels e J.C. Verhaeghe, Probabilistic Behaviour in Ants : a Strategy of Errors?, Journal of Theoretical Biology, 1983.
^ (EN) F. Moyson e B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Stanford, California, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, 1988.
^ (EN) M. Ebling, M. Di Loreto, M. Presley, F. Wieland e D. Jefferson, An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the SCS Multiconference on Distributed Simulation, 1989.
^ (EN) Dorigo M., V. Maniezzo e A. Colorni, Positive feedback as a search strategy, relazione tecnica numero 91-016, Dip. Elettronica, Politecnico di Milano, 1991.
^ (EN) G. Bilchev e I. C. Parmee, The Ant Colony Metaphor for Searching Continuous Design Spaces, ed. Terence C. Fogarty, Evolutionary Computing Springer-Verlag, Proceedings of the AISB Workshop on Evolutionary Computation, 1995, pp. 25-39.
^ (EN) R. Schoonderwoerd, O. Holland, J. Bruten e L. Rothkrantz, Ant-based load balancing in telecommunication networks, vol. 5, Adaptive Behaviour, 1997, pp. 169-207.
^ (EN) A. Martinoli, M. Yamamoto e F. Mondada, On the modelling of bioinspired collective experiments with real robots, Fourth European Conference on Artificial Life ECAL-97, 1997.
^ (EN) M. Dorigo, ANTS’ 98, From Ant Colonies to Artificial Ants : First International Workshop on Ant Colony Optimization, Bruxelles, ANTS 98, 1998.
^ (EN) T. Stützle, Parallelization Strategies for Ant Colony Optimization, vol. 1498, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, 1998, pp. 722-731.
^ (EN) É. Bonabeau, M. Dorigo e G. Theraulaz, Swarm intelligence, Oxford University Press, 1999.
^ (EN) M. Dorigo, G. Di Caro e T. Stützle, special issue on “Ant Algorithms”, vol. 16, Future Generation Computer Systems, 2000.
^ (EN) W.J. Gutjahr, A graph-based Ant System and its convergence, vol. 16, Future Generation Computer Systems, 2000, pp. 873-888.
^ (EN) S. Iredi, D. Merkle e M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, First International Conference (EMO’01), Evolutionary Multi-Criterion Optimization, 200, pp. 359-372.
^ (EN) L. Bianchi, L.M. Gambardella e M.Dorigo, An ant colony optimization approach to the probabilistic traveling salesman problem, Berlino, PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, 2002.
^ (EN) Balaji Prabhakar, Katherine N. Dektar e Deborah M. Gordon, The Regulation of Ant Colony Foraging Activity without Spatial Information, in PLOS Comput Biol, vol. 8, 23 agosto 2012, pp. e1002670, DOI:10.1371/journal.pcbi.1002670, ISSN 1553-7358 (WC · ACNP), PMID 22927811. URL consultato l'11 giugno 2016.

Bibliografia modifica

(EN) M. Dorigo, M. Birattari e T. Stützle, Ant Colony Optimization : Artificial Ants as a Computational Intelligence Technique, vol. 1, IEEE Computational Intelligence Magazine, 2006, pp. 28–39.
(FR) Johann Dréo, Alain Petrowski, Éric Taillard e Patrick Siarry, Métaheuristiques pour l’optimisation difficile (PDF), 2003. URL consultato il 25 marzo 2016 (archiviato dall'url originale il 3 marzo 2016).
(EN) Éric Bonabeau, Marco Dorigo e Guy Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, 1999, ISBN 0-19-513159-2.
(EN) Marco Dorigo e Thomas Stützle, Ant Colony Optimization, Cambridge, MIT Press/Bradford Books, 2004, ISBN 0-262-04219-3.
(FR) Nicolas Monmarché, Frédéric Guinand e Patrick Siarry, Fourmis artificielles, 1 (Des bases de l'optimisation 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 e 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, Optimisation par colonies de fourmis, Hermes-Lavoisier, 2008, p. 192, ISBN 978-2-7462-1863-5.

Voci correlate modifica

Collegamenti esterni modifica

(EN) Home Page dell'Ant Colony Optimization, su aco-metaheuristic.org. URL consultato il 25 marzo 2016 (archiviato dall'url originale l'11 ottobre 2013).
(EN) Una lista di riferimenti bibliografici sulle formiche artificiali, su hant.li.univ-tours.fr. URL consultato il 25 marzo 2016 (archiviato dall'url originale il 4 marzo 2016).
(EN) ANT Colony Algorithm, su djoh.net.
(FR) Applicazione di un algoritmo delle colonie di formiche al problema del commerciante viaggiatore, su khayyam.developpez.com.

Portale Biologia

Portale Matematica

[1] (EN) A. Colorni, M. Dorigo e V. Maniezzo, Distributed Optimization by Ant Colonies, Parigi, Elsevier Publishing, 1991, pp. 134-142.

[M._Dorigo,_Optimization,_Learning_and_Natural_Algorithms-2] (EN) M. Dorigo, Optimization, Learning and Natural Algorithms, Politecnico di Milano, PhD thesis, 1992.

[S._Goss-3] (EN) S. Goss, S. Aron, J.-L. Deneubourg e J.-M. Pasteels, The self-organized exploratory pattern of the Argentine ant, vol. 76, Naturwissenschaften, 1989, pp. 579-581.

[4] (EN) J.-L. Deneubourg, S. Aron, S. Goss e J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, vol. 3, Journal of Insect Behavior, 1990, p. 159.

[Ant_system-5] (EN) M. Dorigo, V. Maniezzo e A. Colorni, Ant system: optimization by a colony of cooperating agents, vol. 26, IEEE Transactions on Systems, Man, and Cybernetics--Part B, 1996, pp. 29-41.

[T._Stützle_et_H.H._Hoos-6] (EN) T. Stützle e H.H. Hoos, MAX MIN Ant System, vol. 16, Future Generation Computer Systems, 2000, pp. 889-914.

[M._Dorigo_et_L.M._Gambardella-7] (EN) M. Dorigo e L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, vol. 1, IEEE Transactions on Evolutionary Computation, 1997, pp. 53-66.

[Zlochin_model-based_search-8] (EN) M. Zlochin, M. Birattari, N. Meuleau e M. Dorigo, Model-based search for combinatorial optimization: A critical survey, vol. 131, Annals of Operations Research, 2004, pp. 373-395.

[9] (EN) A. Ajith e G. Crina, Stigmergic Optimization, vol. 31, Studies in Computational Intelligence, R. Vitorino, 2006, p. 299, ISBN 978-3-540-34689-0.

[10] (EN) K. M. Sim e W. H. Sun, Ant colony optimization for routing and load-balancing : survey and new directions, vol. 33, Man and Cybernetics, Part A, IEEE Transactions on Systems, 2003, pp. 560-572.

[11] (FR) P.-P. Grassé, 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, Insectes Sociaux, 1959, pp. 41-80.

[12] (EN) J.L. Denebourg, J.M. Pasteels e J.C. Verhaeghe, Probabilistic Behaviour in Ants : a Strategy of Errors?, Journal of Theoretical Biology, 1983.

[F._Moyson,_B._Manderick-13] (EN) F. Moyson e B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Stanford, California, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, 1988.

[14] (EN) M. Ebling, M. Di Loreto, M. Presley, F. Wieland e D. Jefferson, An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the SCS Multiconference on Distributed Simulation, 1989.

[15] (EN) Dorigo M., V. Maniezzo e A. Colorni, Positive feedback as a search strategy, relazione tecnica numero 91-016, Dip. Elettronica, Politecnico di Milano, 1991.

[16] (EN) G. Bilchev e I. C. Parmee, The Ant Colony Metaphor for Searching Continuous Design Spaces, ed. 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. Bruten e L. Rothkrantz, Ant-based load balancing in telecommunication networks, vol. 5, Adaptive Behaviour, 1997, pp. 169-207.

[18] (EN) A. Martinoli, M. Yamamoto e F. Mondada, On the modelling of bioinspired collective experiments with real robots, Fourth European Conference on Artificial Life ECAL-97, 1997.

[19] (EN) M. Dorigo, ANTS’ 98, From Ant Colonies to Artificial Ants : First International Workshop on Ant Colony Optimization, Bruxelles, ANTS 98, 1998.

[20] (EN) T. Stützle, Parallelization Strategies for Ant Colony Optimization, vol. 1498, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, 1998, pp. 722-731.

[21] (EN) É. Bonabeau, M. Dorigo e G. Theraulaz, Swarm intelligence, Oxford University Press, 1999.

[22] (EN) M. Dorigo, G. Di Caro e T. Stützle, special issue on “Ant Algorithms”, vol. 16, Future Generation Computer Systems, 2000.

[23] (EN) W.J. Gutjahr, A graph-based Ant System and its convergence, vol. 16, Future Generation Computer Systems, 2000, pp. 873-888.

[24] (EN) S. Iredi, D. Merkle e M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, First International Conference (EMO’01), Evolutionary Multi-Criterion Optimization, 200, pp. 359-372.

[25] (EN) L. Bianchi, L.M. Gambardella e M.Dorigo, An ant colony optimization approach to the probabilistic traveling salesman problem, Berlino, PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, 2002.

[26] (EN) Balaji Prabhakar, Katherine N. Dektar e Deborah M. Gordon, The Regulation of Ant Colony Foraging Activity without Spatial Information, in PLOS Comput Biol, vol. 8, 23 agosto 2012, pp. e1002670, DOI:10.1371/journal.pcbi.1002670, ISSN 1553-7358 (WC · ACNP), PMID 22927811. URL consultato l'11 giugno 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]