Algoritmo ACO

L'algoritmo ACO ( Ant Colony Optimization ) è un euristica che ricalca il comportamento naturale delle formiche. Si tratta di un algoritmo di ricerca del percorso ottimale tra un nodo di partenza (colonia di formiche) e un nodo obiettivo (cibo) basato sull'utilizzo di tecniche probabilistiche e sull'ottimizzazione metaeuristica. Il primo algoritmo ACO della storia viene sviluppato nel 1992 da Marco Dorigo. L'algoritmo ACO appartiene alla categoria degli algoritmi naturali ( swarm intelligence ) ossia alla categoria degli algoritmi che studiano i comportamenti naturali degli esseri viventi costruiti in milioni di anni di evoluzione. In natura le formiche si muovono a caso alla ricerca del cibo. Quando lo trovano, tornano a ritroso fino alla colonia depositando sul terreno dei segnali chimici (feromoni) al fine di tracciare un sentiero tra cibo e colonia per le altre formiche ( comportamento cooperativo ). Quando altre formiche incontrano il sentero tracciato dai feromoni, smettono di muoversi a caso e lo iniziano a percorrerlo anche loro. Col passare del tempo i feromoni evaporano e le formiche sono portate a compiere piccole variazioni di percorso. Il segnale dei feromoni tende a mantenersi più a lungo nei percorsi più brevi poiché sono anche quelli più frequentati dalle formiche. In conclusione, pur essendo ogni formica dotata di poca memoria e di scarsa intelligenza, tutte insieme riescono a risolvere un problema complesso senza bisogno di un'organizzazione centralizzata.

Algoritmo parallelo cooperativo. Dal punto di vista computazione l'algoritmo ACO viene eseguito in parallelo. Ogni agente (formica) si muove inizialmente a caso, le sue scelte sono frutto di un processo stocastico, e ha una memoria molto limitata. Quando un singolo agente trova un percorso fino all'obiettivo, lo marca (aggiornamento attivo ritardato) e lo comunica agli altri agenti (comunicazione), i quali iniziano dinamicamente a percorrerlo. Al ritorno alla base ogni agente "muore" dando vita a un nuovo agente (reset di memoria). Avendo una quantità di memoria limitata, gli agenti devono prendere in considerazioni le informazioni locali (ant routing table) prodotte dagli altri agenti. Per evitare che l'algoritmo converga troppo rapidamente su percorsi sub-ottimali l'algoritmo ACO deve, inoltre, integrare in sé un coefficiente di decadimento del percorso e una funzione di esplorazione.

• CoefIiciente di decadimento. ll coefficiente di decadimento riduce l'intensità della scia col passare del tempo (evaporazione del feromone) favorendo l'esplorazione dei percorsi alternativi.
• Variazioni di percorso. Alcuni algoritmi ACO prevedono anche la possibilità di variazioni di percorso incidentali generate dalla presenza di segnali extra depositati o rimossi da parte di appositi agenti "folletti".

L'esplorazione e le variazioni di percorso consentono di ottimizzare il percorso nel corso del tempo. Ogni miglioramento di percorso viene comunicato agli altri agenti, fino all'individuazione del cammino più breve ( cammino ottimale ).

Differenza algoritmi paralleli cooperativi e competitivi. L'algoritmo ACO è un algoritmo parallelo cooperativo e si distingue dagli algoritmi paralleli competitivi. In entrambi i casi gli agenti lavorano parallelamente e in modo autonomo alla soluzione dello stesso problema. Tuttavia, nel caso degli algoritmi competitivi ciò avviene senza alcuna cooperazione reciproca tra gli agenti. Al termine dell'elaborazione degli algoritmi competitivi viene selezionata soltanto la migliore soluzione finale. Tutte le altre soluzioni inferiori, elaborate dagli altri agenti, sono cestinate. Nel caso degli algoritmi ACO, invece, gli agenti condividono dinamicamente i risultati parziali nel corso dell'elaborazione. Pur restando autonomi, gli agenti ACO comunicano (output) agli altri agenti l'eventuale scoperta di un miglioramento di cammino (efficienza) e sono pronti ad accettare (input) le informazioni e i miglioramenti di cammino scoperti dagli altri agenti anche se non stati loro a trovarli. In conclusione, la cooperazione tra gli agenti consente di ottimizzare l'impiego delle risorse e di aumentare la velocità computazionale.