Intelligenza Artificiale, tra formiche ed evoluzione

Quando si parla di "Specie dominante" nel regno animale, è consuetudine attribuire tale definizione all'uomo (sapiens sapiens, se vogliamo essere un po' più scientifici).

Eppure l'uomo non ha la forza del leone, la massa di una balena, la velocità di un ghepardo o le ali di un'aquila. Non ha una pelle coriacea né zanne affilate. L'uomo ha un arma che nessun animale fino ad ora è mai riuscito ad eguagliare: l'intelletto. Così la nostra razza si erge a baluardo e rappresentante ufficiale del pianeta Terra, in cima alla piramide alimentare, creatori di oggetti meravigliosi e armi letali.

_{L'evoluzione dell'uomo che lo ha portato ad inventare Steemit - click for source}

Nonostante questo, la natura ci offre degli esempi di come la risoluzione di problemi complessi non sia un'esclusiva della nostra razza: alcuni insetti riescono, grazie alla forza dei numeri, in imprese e decisioni tutt'altro che banali. Inoltre, pensate che la razza umana sarebbe arrivata dov'è ora, senza l'applicazione la legge della selezione naturale?

L'intelligenza artificiale negli anni non si è limitata a riprodurre il funzionamento del cervello umano: molto spesso si è ispirata alla natura e all'imitazione dei suoi principi per implementare (con più o meno successo) algoritmi per la risoluzione di problemi complessi. In questo articolo vorrei esplorare con voi due di questi metodi: Ant colony optimization e gli algoritmi genetici.

Ant Colony Optimization

Chi da bambino non ha mai perso del tempo a seguire i percorsi delle formiche? Personalmente, i formicai mi hanno sempre affascinato. Mi piaceva vedere come le formiche si impegnavano a raccogliere le briciole di pane che lasciavo loro e di come, in un attimo, la singola formica avesse richiamato decine delle sue compagne per condurre l'impresa.

_{Un gruppo di formiche all'opera - click for source}

Una singola formica non dispone dell'intelligenza necessaria per capire quale sia il percorso migliore per arrivare al cibo. Ma un'intera colonia di formiche riesce ad esplorare il territorio circostante, a fare una mappa dei migliori percorsi verso il nutrimento e ad organizzare la raccolta in maniera efficiente ed ordinata.

Le formiche sono il tipico esempio di quella che viene chiamata "Swarm intelligence", l'intelligenza dello sciame. L'esempio delle formiche non è il solo: pensate ai gregge di pecore, agli stormi di uccelli migratori, ai banchi di pesci nel mare. La Swarm Intelligence permette ad un gruppo, formato da singole entità ben definite, di agire all'unisono verso un unico scopo, unendo i sensi e le capacità di ogni elemento in una sola, grande ed auto-organizzata mente collettiva.

_{Uno stormo di oche selvatiche è un altro esempio di Swarm Intelligence - click for source}

Prendiamo le formiche: partendo dal formicaio, ogni formica esplora l'ambiente circostante in maniera casuale, cercando il cibo in un determinato raggio. Quando lo trova, una formica ne raccoglie un po' e torna indietro al formicaio facendo al contrario la strada dell'andata e depositando sul suo percorso una "scia" di ferormone.
Le successive formiche tendono a seguire la scia di ferormone, facendo di tanto in tanto delle deviazioni (magari per seguire le scie di altre formiche) e arrivate al cibo percorrono tutte la strada dell'andata, depositando ferormoni e rinforzando la scia delle sue predecessori.

Con il passare del tempo, il sentiero con più ferormoni sarà forzatamente la via più veloce dal formicaio al cibo: questo perché, essendo la più rapida, viene percorso da più formiche in meno tempo. In questa maniera la via più veloce diventa l'unica percorsa (e quella con la scia di ferormoni più consistente), mentre tutti gli altri sentieri vengono dispersi nell'aria (il ferormone è una sostanza molto volatile che evapora in fretta).

Ecco perché le formiche si muovono sempre in fila indiana quando vanno a raccogliere il cibo.

Nel 1992 Marco Dorigo, un brillante scienziato italiano specializzato nell'intelligenza artificiale, decise di sfruttare questa "consapevolezza di gruppo" nei suoi studi, sviluppando i primi algoritmi di ACO (Ant Colony Optimization). I suoi studi sono ad oggi utilizzati in vari ambiti scientifici e compongono una branca importante nello sviluppo di intelligenze artificiali complesse.

Gli Algoritmi Genetici

La legge di Darwin è alla base dell'evoluzionismo e di quella branca dell'I.A. conosciuta come gli "Algoritmi genetici". La sua applicazione è molto semplice: in natura, la specie più forte e più adattabile sopravvive, le altre muoiono. Tale principio si applica non solo per gli animali più evoluti, ma anche per le specie più elementari come i batteri, i virus, i funghi e così via.

_{Combinare il DNA di individui diversi è il primo passo verso l'evoluzione - click for source}

Nel 1975 John Henry Holland, dottore di informatica e psicologia, teorizzò il suo Teorema degli Schemi, detta anche la Teoria fondamentale degli algoritmi genetici, portando le logiche dell'evoluzionismo all'interno dei calcolatori elettronici.

Vediamo brevemente ed in maniera semplice come si comportano questi algoritmi.

1. Viene creata una prima popolazione di soluzioni ad un determinato problema. Queste soluzioni vengono solitamente generate in maniera randomica.

2. Ad ogni elemento di questa popolazione viene applicata una funzione di Fitness: la funzione di Fitness permette di capire quanto l'elemento proposto si avvicini alla soluzione ottima, permettendo una sorta di "Classifica" delle soluzioni dalle più efficaci alle meno utili.

3. In base al tipo di selezione scelta (basata sui risultati della soluzione fitness ed altri fattori) viene "estratto" un sotto insieme di individui che rappresenterà il nostro primo campione base.

4. Tale campione viene usato per la "riproduzione": gli elementi del campione vengono combinati tra loro (a volte aggiungendo una variabile di casualità chiamata "mutazione") generando una nuova popolazione di individui.

5. Si ripetono i passi dal numero 2 al 4 fino ad ottenere una soluzione ottima.

I punti critici di tale algoritmo sono ovviamente il due ed il tre: la scelta di una buona funzione di fitness è propedeutica alla creazione di una popolazione ottimale, e la scelta di selezione può variare molto in base al tipo di problema affrontato (prendere solo gli elementi migliori potrebbe creare un problema di "ottimo locale", quindi spesso nel campione vengono inseriti elementi meno brillanti per ampliare il raggio di studio).

Inoltre il modo con cui questi elementi (in gergo, "Cromosomi") vengono combinati può essere la differenza tra una nuova popolazione di elementi validi ed una invece composta da soli "low performers"; esistono diversi metodi di combinazione (divisione a uno o due punti, combinazione omogenea ecc.) ognuno con i propri pro e contro, ma che richiedono uno studio molto più approfondito della materia.

Applicazioni e Conclusioni

L'Ant Colony Optimization e gli algoritmi Genetici fanno parte della categoria degli Algoritmi Euristici, ovvero quelle procedure probabilistiche che ricercano soluzioni più o meno approssimate per risolvere problemi impossibili da computare in un tempo ben definito (i cosiddetti problemi NP Completi, dei quali magari parleremo un altra volta).

E' evidente come le soluzioni offerte da questa tipologia di algoritmi non sia "certificata" come la migliore in assoluto; e anche se lo fosse, non ci sarebbe modo di dimostrarlo (proprio per il problema di non poter "computare" questa soluzione in maniera classica e deterministica).

_{Soluzione semplice al "Travelling Salesman Problem" - click for source}

Questi algoritmi sono stati utilizzati con successo nella risoluzione del problema del "Commesso Viaggiatore": avendo una rete di città collegate da strade più o meno lunghe, qual è il percorso più breve per visitare una sola volta tutte le città della mappa? Vi sarà sicuramente venuto in mente Google Maps: beh per trovare un cammino minimo tra due punti basta l'algoritmo dei cammini minimi di Dijkstra, ma se voleste trovare un cammino minimo tra tutte le più belle città del mondo, è necessario utilizzare algoritmi euristici.

Le applicazioni si trovano anche nel Problema dello zaino, nei complessi calcoli elettronici o spaziali, per la risoluzione di problemi biologici, chimici o medici (da cui l'esistenza della disciplina di bio-informatica).

Alla fine, anche l'uomo deve piegarsi alle meraviglie e alla genialità della natura!

---

Riferimenti:

• Ant colony optimization (Marco Dorigo, Mauro Birattari, Thomas Stutzle, 2006) http://ieeexplore.ieee.org/abstract/document/4129846/?reload=true
• Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence (John Henry Holland, 1992) https://books.google.it/books?hl=it&lr=&id=5EgGaBkwvWcC&oi=fnd&pg=PR7&dq=related:j0P6-Es7Jd8J:scholar.google.com/&ots=mIgm02Klpl&sig=pyJc0TxhBl6MxRQ0sT7XrNigmvE#v=onepage&q&f=false
• le 50 città da visitare almeno una volta nella vita, Randy Olson
  http://nbviewer.jupyter.org/github/rhiever/Data-Analysis-and-Machine-Learning-Projects/blob/master/optimal-road-trip/Computing%20the%20optimal%20road%20trip%20across%20the%20U.S..ipynb