Una colonia di formiche Artificiali

Gli insetti sociali quali formiche, api, termiti. ecc., hanno da sempre affascinato gli studiosi poiché, sebbene il singolo insetto sembri agire in modo del tutto autonomo, l'attività dell'intera colonia appare altamente organizzata e denota un comportamento intelligente. In realtà, l'attività di una colonia di insetti è in gran parte auto-organizzata, nel senso che la coordinazione tra gli individui si attua mediante semplici interazioni (ad esempio una formica si limita a seguire la traccia lasciata da un'altra) che nell'insieme consentono di risolvere problemi complessi come individuare la via più breve verso una fonte di cibo.
Il tipo di intelligenza che si delinea in una colonia di insetti è detto Swarm Intelligence (intelligenza collettiva o di sciame). Studiando questo tipo di intelligenza, diversi gruppi di ricercatori nell'ambito dell'intelligenza artificiale hanno realizzato piccoli agenti software che cooperano per risolvere problemi di carattere combinatorio. Ad esempio, il modo in cui le formiche vanno alla ricerca di cibo ha suggerito un metodo innovativo per instradare le chiamate in un sistema di telecomunicazioni ad alto traffico, il modo in cui alcune specie di insetti raggruppano i morti nelle colonie e sistemano le larve ha fornito l’idea per realizzare un sistema di ricerca e raggruppamento dei dati in un database per il settore bancario, ed, infine, il sistema di suddivisione del lavoro tra le api potrebbe fornire indicazioni per organizzare le catene di montaggio nelle fabbriche.
In questo articolo si illustrerà un sistema basato sul comportamento di una colonia di formiche che definisce un algoritmo per la risoluzione di problemi di ottimizzazione combinatoria di carattere generale. Si mostrerà poi una variante in grado di risolvere il famoso problema del commesso viaggiatore. Nell’articolo successivo si presenterà un framework java che implementa tale sistema e, infine, si realizzerà un’implementazione della variante specifica per il problema del commesso viaggiatore a partire del framework proposto e per il Problema di Stainer sulle reti.

Swarm Intelligence

La Swarm Intelligence è una proprietà di un sistema composto da una molteplicità di agenti singolarmente non-intelligenti che esibiscono collettivamente un comportamento intelligente. Molti dei concetti base dell’Intelligenza Collettiva, come agente, evoluzione, comunicazione, parallelismo, comportamento emergente, ecc., sono presi in prestito dalla Artificial Life (AL). Anche il modello riprende quello proposto da AL: al livello più basso sono definite molte piccole unità e poche semplici regole che determinano le modalità di interazione locale reciproca. Da tali semplici interazioni scaturisce ad un livello più generale un comportamento “globale” coerente e non programmato in precedenza mediante specifiche regole.

Formiche reali

Indagando sul comportamento delle formiche durante la ricerca di cibo, un gruppo di ricercatori dell’Université Libre de Bruxelles, tra cui Denebourgh, Beckers e Goss, mostrarono che le processioni di formiche che si osservano in natura (e spesso nella nostra cucina”) sono originate da singole formiche che depositano lungo il percorso delle sostanze chimiche dette feromoni [1]. Poiché le altre formiche sono attratte da tali feromoni, queste tendono a seguire il percorso già segnato. In altre parole, durante il percorso le formiche emettono e seguono scie di feromone. Le prime formiche che ritornano al nido dopo aver raggiunto la fonte di cibo sono quelle che hanno percorso l’itinerario più breve, e poiché, quest’ultimo è il primo ad essere marcato due volte con i feromoni (all’andata e al ritorno) è preferito dalle altre compagne di nido.
Denebourgh dimostrò anche che le formiche sono capaci di adattarsi alle modifiche nell’ambiente circostante poiché riescono a trovare prontamente un nuovo percorso una volta che il vecchio non è più percorribile [2]. Si faccia riferimento alla figura 1. Le formiche stanno percorrendo quello che sembra essere il percorso più breve (a). Ad un certo punto un ostacolo occlude il passaggio (b). Le formiche alla sinistra dell’ostacolo non potendo proseguire devono scegliere se dirigersi verso destra o verso sinistra. Poiché non hanno nulla che possa suggerirgli quale sia il percorso migliore ci si aspetta che metà delle formiche vada a destra e metà a sinistra (c). Le formiche che hanno scelto il tratto più breve ricostruiscono la scia di feromone più velocemente delle altre e depositano sul tratto una maggior quantità di feromone per unità di tempo. Ciò attrae le altre formiche che, molto rapidamente, sceglieranno tutte il tratto più breve (d). L’aspetto più interessante di tale processo è che il comportamento emergente del sistema colonia-ostacolo sembra essere l’individuazione dell’itinerario più breve. Tutte le formiche si muovono alla stessa velocità, depositano la stessa quantità di feromone per unità di tempo e seguono il percorso che contiene più feromone. Da tale insieme di semplici regole di interazione locale scaturisce come comportamento emergente l’individuazione del percorso più breve.

Formiche Artificiali

Il comportamento delle formiche reali ha ispirato un sistema in cui un insieme di formiche artificiali cooperano, in parallelo, alla soluzione di un problema mediante lo scambio di feromoni artificiali depositati sui percorsi di un grafo. E’ interessante notare che tali feromoni conservati su una memoria condivisa (il grafo) rappresentano una particolare forma di comunicazione indiretta.
Si prenda un grafo generico G(V, A) dove V = {a1, … an) è l’insieme dei nodi e A = {(r,s) : r,s V} è l’insieme dei percorsi. Si consideri la funzione “costo” d(r,s) che associa al percorso dal nodo r al nodo s la misura del costo e la funzione “feromone” t(r,s) che associa al percorso dal nodo r al nodo s la quantità di feromone depositata. Si aggiunga quindi una regola di transizione di stato e una regola di aggiornamento del feromone mediante le quali, in base ad una determinata euristica, le formiche artificiali selezionano il successivo nodo da visitare e depositano feromoni sui cammini.
In generale l’euristica di selezione dell’itinerario è definita in modo che la singola formica posta nel nodo r, tenda a scegliere il cammino più breve e con il più alto quantitativo di feromone verso il nodo s, ossia scelga un s tale che d(r,s) è minimo e t(r,s) è massimo. L’euristica di aggiornamento del feromone è determinata in modo che, una volta individuato il cammino, la formica si sposti nel nodo selezionato depositando sul tratto una quantità di feromone proporzionale alla lunghezza del cammino percorso, ossia aggiornando il valore di t(r,s) di una quantità pari a to / d(r,s) (to è l’unità di feromone).
L’algoritmo generale appena descritto è la base per la realizzazione di varianti che risolvono problemi specifici. Ad esempio si può modificare l’euristica di aggiornamento del feromone aggiungendo un meccanismo di evaporazione (come si vedrà in seguito) che nel tempo decrementa la quantità di feromone lungo i cammini rendendo via via meno attraenti itinerari non più validi, oppure si può regolare l’euristica di selezione dei cammini aggiungendo una regola che limita il passaggio attraverso un cammino ad un determinato numero di formiche per evitare il sovraffollamento di un tratto e per consentire l’esplorazione di nuovi cammini.

Il problema del commesso viaggiatore

L’algoritmo della colonia di formiche si adatta molto bene alla soluzione di problemi di ottimizzazione combinatoria come il famoso problema del commesso viaggiatore (detto TSP, Traveling Salesman Problem). Dato un insieme di città, il TSP consiste nel trovare l’itinerario più breve in modo che il commesso viaggiatore possa visitare tutte le città una sola volta. Tale problema appartiene alla classe dei problemi np-completi (np sta per non polinomial) ossia quei problemi in cui l’individuazione della soluzione esatta richiede un numero di passi che aumenta esponenzialmente al crescere delle dimensioni del problema. Difatti, prendendo n città il numero di itinerari che il commesso viaggiatore può seguire è pari a n! e per individuare la soluzione esatta dovrebbe percorrerli tutti, ossia occorrerebbe eseguire n! iterazioni. Considerando che con appena quindici città il numero di itinerari è pari a circa 1,3 • 1012 l’individuazione dell’itinerario più breve è computazionalmente irrealizzabile.
Simili problemi solitamente vengono risolti con particolari algoritmi di ottimizzazione combinatoria che forniscono soluzioni sufficientemente buone ma non necessariamente esatte in un numero ragionevole di iterazioni. Il sistema della colonia di formiche si pone tra questi e si candida come uno dei più efficienti.

Ant Colony System

Marco Dorigo dell’Universitè Libre de Bruxelles e Luca Maria Gambardella dell IDSIA di Lugano hanno messo a punto una variante all’algoritmo della colonia di formiche, detta ACS (Ant Colony System, [3] e [4]), specifica per il problema del commesso viaggiatore che fornisce un itinerario pressoché ottimale: m formiche vengono inizialmente posizionate su n città secondo una regola di inizializzazione (ad esempio in maniera casuale). Ogni formica genera un itinerario completo scegliendo di volta in volta la città da visitare in accordo con una regola di transizione di stato, con contenuto probabilistico, che porta la formica a scegliere preminentemente le città connesse con un percorso breve e ad alto contenuto di feromone. Mentre percorre il suo itinerario una formica modifica la quantità di feromone sui tratti percorsi applicando la regola di aggiornamento locale del feromone. Una volta che tutte le formiche hanno completato il loro itinerario (ossia sono tornate al punto di partenza avendo percorso una volta tutte le città) si applica la regola di aggiornamento globale del feromone: una frazione di feromone evapora su tutti i percorsi e, in seguito, la formica che ha percorso l’itinerario più breve deposita una certa quantità di feromone in proporzione alla sua lunghezza. Al temine dell’attività delle formiche l’itinerario più breve sarà più ricco di feromone e, contemporaneamente, poiché il feromone evapora, itinerari lunghi conterranno molto meno feromone rispetto a quelli brevi. Le formiche vengono poi riattivate per ripetere il percorso, ma, poiché stavolta sono attirate dai feromoni precedentemente depositati, la ricerca porterà ad una soluzione certamente migliore.
Le tre regole sono definite formalmente nel riquadro 2. La regola di transizione di stato (a) determina la prossima di città da raggiungere. Si noti l’importanza del parametro ß il quale specifica il peso relativo del feromone rispetto alla distanza. Si noti anche che moltiplicando il valore del feromone t sul tratto (r,s) con il corrispondente valore euristico (r,s) = 1 / d(r,s) si favorisce la scelta dei percorsi più brevi e con il maggior numero di feromoni. Si noti infine il bilanciamento mediante il parametro q0 (scelto in [0,1]) dell’attività di sfruttamento di un percorso già segnato da feromone (uso di conoscenza già acquisita) e l’attività di esplorazione di nuovi percorsi (apprendimento di nuova conoscenza). La formica genera un numero casuale q [0,1]. Se q = q0 la formica sceglierà un percorso già segnato altrimenti preferirà un nuovo percorso ottenuto mediante la distribuzione di probabilità definità dall’equazione (b) la che dà una misura della probabilità con la quale una formica sceglie di spostarsi dalla città r alla citta s.
La regola di aggiornamento locale del feromone (c) tende a diminuire leggermente la quantità di feromone lungo il tratto appena percorso in modo da renderlo meno attraente alle altre formiche in attività favorendo così l’esplorazione di nuovi cammini. Dorigo e Gambardella hanno provato sperimentalmente che senza tale regola le formiche tenderebbero a non esplorare nuovi percorsi allontanandosi raramente dalle vicinanze del migliore itinerario ricavato dall’iterazione precedente.
La regola di aggiornamento globale del feromone (d), applicata al termine dell’attività della colonia, consente di distribuire il maggior numero di feromoni sui tratti appartenenti agli itinerari più brevi. Tale regola tiene conto sia dell’evaporazione del feromoni depositati dalla precedente colonia di formiche sia dei feromoni depositati dalla nuova colonia. Si noti l’importanza del parametro a che specifica la costante di decadimento del feromone.
I due ricercatori hanno misurato le prestazioni di tale algoritmo confrontandole poi con quelle di alcuni tra i più famosi algoritmi di ottimizzazione combinatoria ed hanno ottenuto risultati sorprendenti: ACS sembra convergere più velocemente verso la soluzione esatta. Più specificamente, i due ricercatori hanno dimostrato sperimentalmente che, assegnando opportunamente i valori ai parametri a, ß, e q0 (nella fattispecie a = 0.1, ß = 2, = 0.1 e q0 = 0.9) il sistema fornisce soluzioni comparabili e quasi sempre migliori con un minor numero di iterazioni (per un approfondimento sulla scelta di tali valori dei parametri e per i risultati sperimentali si veda [4]).

Bibliografia
[1] Beckers, R., Denebourg, J.L., Goss, S., “Trails and U-turns in the selection of the shortest path by the ant Lasius niger”, Journal of theorethical biology 159, 387-415, 1992
[2] Goss, S., Aron, S., Denebourg, J.L., Pasteels, J.M., “Self-organized shortcuts in the Argentine ant”, Naturawissenshaften” 76, 579-581, 1989.

Riferimenti
[3] Marco Dorigo, “Behavior of Real Ants”, http://iridia.ulb.ac.be/~mdorigo/ACO/RealAnts.html
[4] Dorigo M., Gambardella L. M., “Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem”, http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html