Da sempre l’uomo prende ispirazione dalla natura per risolvere i propri problemi. Questo approccio noto come “biomimesi” ha permesso la progettazione di aerei più efficienti, ha fornito innumerevoli spunti per la robotica, per l’ingegneria dei materiali e per il miglioramento energetico degli edifici.
In questo post vogliamo introdurre uno degli esempi più famosi di biomimesi in ambito Computer Science: stiamo parlando dell’algoritmo Ant Colony Optimization. Questo algoritmo ispirato alle formiche permette di trovare il percorso migliore da un punto di partenza a un punto di destinazione.
In natura, le formiche in cerca di cibo inizialmente vagano a caso e una volta, dopo aver trovato una fonte di cibo, ritornano al formicaio lasciando dietro di sé tracce di feromone. Se altre formiche trovano questa traccia smettono di vagare a caso con una certa probabilità e percorrono tale traccia aggiungendo altro feromone. Il feromone tende a scomparire con il passare del tempo, più ne evapora più la traccia diventa meno attrattiva, quindi più un percorso richiede tempo per essere percorso più perde attrattività. Di conseguenza un percorso breve ha sempre più feromone rispetto a un percorso più lungo e quindi attrae sempre più formiche. In questo modo dopo un certo periodo di esplorazione tutte le formiche sono attratte dal percorso più breve tra il formicaio e la fonte di cibo.
Quindi, definendo una logica di aggiornamento del feromone (tempo di evaporazione, tempo di rilascio, quantità, …), modellando il problema da risolvere con un grafo e creando un insieme di formiche artificiciali, è possibile usare l’Ant Colony Optimization per trovare la strada più breve da una città all’altra, il percorso più breve da un router a un altro, risolvere problemi di scheduling fino a studiare le interazioni tra grafi che rappresentano delle proteine.
Figura A. Non c’è nessun ostacolo tra il cibo e il nido, quindi le formiche seguono un percorso diretto.
Figura B. Viene posizionato un ostacolo tra il cibo e il nido, quindi ora ci sono due possibilità: passare sopra l’ostacolo (percorso più breve) o passare sotto (percorso più lungo).
Figura C. Per un certo periodo le formiche passeranno sia sotto che sopra. Però siccome il percorso sotto è più lungo perde più feromone e quindi attrae sempre meno formiche, il percorso sopra invece è più corto, quindi perde meno feromone e vengono attratte sempre più formiche.
Figura D. Dopo un certo periodo tutte le formiche sono attratte dal percorso sopra che è il più corto.