# 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, 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

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, 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
### Descrizione generale

Il primo algoritmo delle colonie di formiche proposto è l'Ant system (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:
    $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

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
Una variante efficace all'Ant sistem è il Max-Min Ant System (MMAS), 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), 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 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

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

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".
Ci sono anche metodi basati sul comportamento nella ricerca del nutrimento, la divisione del lavoro o nel trasporto in cooperazione.

## Applicazioni

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

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;
* 1983, Deneubourg ed i suoi colleghi studiano il comportemento collettivo delle formiche;
* 1988, Moyson e Manderick presentano un articolo sull'auto-organizzazione delle formiche;
* 1989, I lavori di Goss, Aron, Deneubourg et Pasteels, sul comportement collectifs des fourmis Argentines, daranno l'idea degli algoritmi delle colonie di formiche;
* 1989, Implementazione di un modello di comportemento nella ricerca di cibo di Ebling ed i suoi colleghi;
* 1991, M. Dorigo propone l'Ant System nella sua tesi del dottorato (che non sarà pubblicata prima del 1992). Scrive, con V. Maniezzo e A. Colorni, una relazione tecnica, che sarà pubblicata cinque anni più tardi;
* 1995, Bilchev e Parmee pubblicano il primo tentativo d'adattamento a problemi di continuità;
* 1996, Pubblicazione dell'articolo sull'Ant System;
* 1996, Stützle e Hoos inventano il MAX-MIN Ant System;
* 1997, Dorigo e Gambardella pubblicano l'Ant Colony System;
* 1997, Schoonderwoerd ed i suoi colleghi stanno sviluppando la prima applicazione di reti di telecomunicazioni;
* 1997, Martinoli ed i suoi colleghi traggono ispirazione dagli algoritmi delle colonie di formiche per controllare i robot;
* 1998, Dorigo lancia la prima conferenza dedicata agli algoritmi delle colonie di formiche;
* 1998, Stützle propone la prima implementazione parallela;
* 1999, Bonabeau ed i suoi colleghi stanno scrivendo un libro che tratta principalmente delle formiche artificiali;
* 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;
* 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;
* 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;
* 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;
* 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 ;
* 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.