Algoritmi Genetici

Gli Algoritmi Genetici sono dei sistemi ad evoluzione dinamica.

Questi sistemi consentono di affrontare, con notevole efficacia, problemi di ottimizzazione e di ricerca molto complessi, in tempo reale e ad un relativo basso costo computazionale.

Si definiscono problemi di ottimizzazione tutti quei problemi nei quali, a partire da una certa quantità, dipendente dai valori di un insieme di variabili, occorre individuare i valori che quelle variabili devono assumere per rendere tale quantità massima o minima.

E' possibile individuare una vasta gamma di problematiche, appartenenti a campi d'indagine anche molto diversi tra loro, più o meno interessate da problemi di ottimizzazione. La definizione e l'ottimizzazione dei palinsesti nell'ambito della programmazione delle trasmissioni televisive, ad esempio, rappresenta un tipico problema di ottimizzazione nel campo della organizzazione dei media.

Per molti dei problemi di ottimizzazione esistono diversi algoritmi di risoluzione ben noti. Tuttavia, la maggior parte di essi, sebbene teoricamente corretti, prevedono dei tempi di calcolo assolutamente non praticabili anche solo per problemi di non elevata complessità.

Imitando la natura, sfruttando il rapporto dinamico tra evoluzione e selezione, gli Algoritmi Genetici consentono di esplorare, se non l’intero spazio, sicuramente una regione molto ampia delle possibili soluzioni di qualsiasi problema complesso, sia esso di tipo culturale o materiale.

Ci sono molti modi per implementare un algoritmo genetico. Quella che espongo di seguito è stata proposta da Holland ed è una delle metodologie più note e studiate. Possiamo dunque considerare Holland, in qualche modo, il padre dei primi algoritmi genetici.

Dato un qualsiasi problema di ottimizzazione, possiamo pensare all’insieme delle possibili soluzioni di quel problema come ad una “popolazione” di “individui soluzioni”. In questo insieme dunque ogni “individuo” sarà definito come l’insieme delle caratteristiche o dei valori di variabili capaci di fornire una soluzione al problema dato.

Ad esempio, se devo fare dei giri in città per acquistare diverse merci (pane, latte, scarpe, bulloni, antivirus per il PC, pezzi di ricambio per la mountain bike ecc…) il mio problema, se non posso accedere ad un unico magazzino con tutto ciò che mi occorre, è come definire un tracciato, una sequenza di visite ai negozi sparsi per la città, tale da:

1. percorrere il minor numero di chilometri possibile
2. spendere la minor quantità di denaro
3. impiegare il minor tempo possibile

Se non abitiamo in un paesino di frontiera con 100 abitanti ma, diciamo, in una città come Milano o Roma ciascuno può capire che di soluzioni possibili e, in qualche modo, accettabili ce ne sono diverse … molte magari non riusciamo neanche ad immaginarle, anche avendo un insieme ben definito di negozi e punti vendita della città.

Questo è un problema ben noto in letteratura definito “TSP” (Travelling Sales Person Problem), il problema del commesso viaggiatore, che appartiene alla classe dei problemi NP completi.

Dato un insieme di punti P(x, y), trovare il cammino minimo che connette tutti i punti in un grafo hamiltoniano (in modo tale che ogni punto sia connesso a due soli altri punti e il grafo sia chiuso). Il numero di percorsi possibili cresce esponenzialmente al crescere del numero dei punti, secondo l’equazione:

Numero Percorsi = (Numero Punti – 1)/2

Il TSP è uno dei classici problemi affrontabili con gli algoritmi genetici. Non che non si possa, almeno in linea di principio, affrontare con altre metodologie “classiche” di ricerca algoritmica, il fatto è che queste “altre soluzioni” classiche spesso o sono inefficienti o richiedono dei tempi di ricerca e di calcolo incredibilmente onerosi.

Per implementare il nostro algoritmo genetico dunque occorre innanzitutto definire una "popolazione" iniziale costituita da un numero casuale di possibili soluzioni, codificate in un “genotipo” di caratteri binari (0-1). Ogni individuo della popolazione di partenza rappresenta così una possibile soluzione al problema dato (nell’esempio una certa sequenza di negozi da visitare: fornaio-ferramenta-sportpertutti-planetsoftware; oppure ferramenta- planetsoftware-fornaio-sportpertutti ecc…).

Nella figura riportata sopra la serie di valori binari (bit string) codifica le caratteristiche di un "individuo" della popolazione nelle sue variabili principali. L’aspetto interessante qui è che abbiamo iniziato a rappresentare il nostro problema in un linguaggio diciamo, in qualche modo, più vicino a quello di un computer … e questo, considerando che il nostro problema in fondo è quello di esplorare uno spazio enorme di possibili soluzioni, ci fa ben sperare perché sappiamo che un computer, per molti aspetti un cretino velocissimo, è formidabile a fare un enorme quantità di cose molto semplici in un tempo incredibilmente breve.

Inizialmente, i valori codificati in binario della nostra popolazione di possibili soluzioni, saranno costituiti da valori inizializzati in modo random e, dunque, non rappresenteranno una popolazione efficace per risolvere il problema dato … a meno che non apparteniamo a quella classe di odiose persone che giocano una sola schedina nella vita e riescono a fare quattordici al primo colpo.
Come facciamo a quantificare la “bontà” di ciascun individuo e quella della popolazione nel suo complesso? Per fare questo occorre definire a priori una funzione di fitness o di bontà.

La definizione della funzione di fitness, insieme alla codifica binaria delle possibili soluzioni, è il perno centrale di tutta la questione. Se sbaglio a definirla, perché ho caratterizzato male il mio problema, mi mancano informazioni ecc.. molto probabilmente la mia popolazione non seguirà un destino evolutivo ed io non troverò mai una soluzione efficace o, forse, non troverò affatto una soluzione.

Nell’esempio citato sopra la mia funzione di fitness sarà in una forma tale da sommare, per ciascun individuo, le variabili chilometri_percorsi + denaro_speso + tempo_impiegato … quindi nella forma:

F(km,Euro,tmp …);

La questione quindi si pone nei termini:

ho una popolazione iniziale costituita da "individui-soluzioni" non ottimali. Come faccio a fare in modo che questa popolazione, inizialmente inefficace, possa seguire un destino evolutivo capace di far emergere una o più soluzioni efficaci?

Qui interviene l’emulazione di alcune dinamiche tipiche del mondo naturale come, ad esempio, la mutazione genetica, la selezione e l’accoppiamento tra specie capace di generare individui nel tempo più adatti a manipolare e a sopravvivere in un ambiente dato. Questa in fondo è stata l’intuizione principale di Holland quando pose le basi per i primi algoritmi genetici della Natural Computation.

Adesso, credo, siamo pronti per individuare e formalizzare un pochino le caratteristiche di un algoritmo genetico.

Definito dunque ogni individuo (soluzione possibile) come una sequenza di bit (bit string);
definita una popolazione di individui come una matrice NxN di “genomi” binari (bit string);
definita in modo preciso la mia funzione di fitness;
... siamo pronti a far evolvere il nostro piccolo mondo artificiale.

Imitando ciò che avviene in natura, la dinamica di evoluzione di ogni algoritmo genetico è caratterizzata da:

TRE OPERANDI

· Gene (bit string)
· Individuo
· Popolazione

TRE OPERATORI CICLICI

· Riproduzione
· Crossover
· Mutazione

I tre operandi (gene, individuo, popolazione) li abbiamo già visti e caratterizzati anche se, per il momento, non in modo formale. Ora proviamo a considerare anche gli operatori ciclici, cioè: riproduzione, crossover e mutazione.

La mutazione è piuttosto semplice. Immaginate che ogni tanto, agli individui che presentano il più basso livello di fitness viene data la possibilità di mutare a caso (random) qualcuno dei loro geni … un po’ come avviene in natura quando, per opera della radiazione solare, qualche gene di una pianta muta e produce una forma nuova magari più efficace e bella della precedente.

Per la riproduzione ed il crossover avviene quanto segue.

Immaginiamo di aver computato il fitness di ogni individuo (bit string) e della popolazione complessiva (matrice NxN di bit string) … molto probabilmente ci saranno alcuni individui buoni (soluzioni accettabili o quasi) e altri assolutamente inetti (soluzioni inaccettabili con fitness bassissimo) … questo lo possiamo verificare grazie al fatto che alcuni non riescono a minimizzare la funzione di fitness definita per il problema.

Imitando la natura decido che, al di sotto di una certa soglia di fitness alcuni individui avranno la possibilità di mutare random qualcuno dei loro geni, altri invece (senza speranza) moriranno perché sono troppo inadatti a vivere nell’ambiente dato.

Ma se alcuni individui muoiono, per evitare nel tempo di sterminare l’intera popolazione, come faccio a rimpiazzarli? Semplice, faccio "accoppiare" alcuni altri individui in modo tale da rigenerare la quantità di individui deceduti.

Quali individui faccio accoppiare? … ecco, qui le soluzioni sono tra le più diverse, quella che vi presento è la soluzione classica originariamente adottata da Holland … ma ce ne sono di più efficaci ed intelligenti. Quella originale di Holland tuttavia, è una delle più semplici e quindi è bene iniziare da questa.

Holland impiega una tecnica definita “ruota delle probabilità” … in sostanza gli individui (soluzioni possibili - bit string) con il fitness più elevato hanno maggiori probabilità di essere scelti come individui per la riproduzione. Apro una breve parentesi qui per dire che questa tecnica, la quale somiglia molto alla soluzione ariana dei nazisti, non è affatto la migliore. In sostanza, sebbene la popolazione riesca ad evolvere nel tempo, le prestazioni globali sono decisamente inferiori rispetto a soluzioni nelle quali viene riconosciuta ad una più ampia popolazione la possibilità di accoppiarsi, anche se il fitness di qualcuno non è tra i migliori. Quest'ultima metodologia consente di mantenere molto più alta la biodiversità e di raggiungere livelli di eccellenza incredibili.

Dunque, una volta scelti random, tra i migliori o quasi secondo Holland, due individui per l’accoppiamento, la prole viene generata seguendo il classico meccanismo del crossover tra due genomi. Questo è esattamente ciò che avviene in natura quando, a partire da due cromosomi, il cromosoma di ciascun figlio risulta essere un mix di caratteristiche dei due genitori. Nel nostro caso i genomi sono delle stringhe di bit (0-1) quindi la di manica è quella riportata in figura:

Come si vede in figura, si sceglie un punto (o più punti) random nella sequenza di bit e, rispetto a quel punto, si generano due nuovi individui effettuando lo swap dei genomi parziali dei genitori.

In questo modo, ad ogni generazione, avrò alcuni individui che mutano e (forse) migliorano, altri che muoiono, altri ancora che si accoppiano per rimpiazzare con la prole i deceduti. La mia popolazione, generazione dopo generazione, evolve verso soluzioni sempre più raffinate.

Gli operatori ciclici di crossover e mutazione permettono di generare biodiversità e flessibilità e di realizzare qiundi le dinamiche tipiche dei sistemi biologici in evoluzione. Questi algoritmi consentono di esplorare l'intero spazio delle possibili soluzioni selezionando ad ogni nuova generazione gli "individui" che rappresentano le migliori soluzioni al problema dato. Partendo da un piccolo insieme di soluzioni, grazie alle dinamiche di accoppiamento e riproduzione tra diversi individui della popolazione, ognuno con un suo fitness più o meno elevato, gli Algoritmi Genetici consentono inoltre di generare soluzioni nuove ed impensabili.

Vediamo uno schema utile per comprendere meglio le fasi di implementazione di un Algoritmo genetico:

L'analogia con i processi di riproduzione e di evoluzione biologici è forte e questo permette di utilizzare tutta la potenza e la flessibilità tipiche dei sistemi viventi.

Gli Algoritmi Genetici dunque offrono una notevole trasparenza nel modo di elaborare i dati permettendo di generalizzare tecniche e metodologie in contesti decisamente diversi. Essi, infine, si presentano spesso come l'unica strada praticabile per individuare una o più soluzioni delle quali si conosca l'esistenza ma non la procedura algoritmica per individuarle.

Un esempio di come implementare questi principi ed applicarli ad un problema classico di ottimizzazione si trova nel problema dei tre colori. Il problema è stato presentato per la prima volta da L. Davis [Davis, 1991], in un articolo tecnico: il problema dei “3 colori”.

Data una griglia N×N, ogni cella della griglia deve essere riempita da un colore, a partire da un insieme di 3 colori costanti e diversi (ad esempio verde, rosso e blu).

I vincoli da rispettare sono:

a. ogni cella deve aver un colore diverso sia nella cella sopra che in quella sotto;
b. ogni cella deve aver un colore diverso sia nella cella destra che in quella sinistra;
c. l’ultima colonna della griglia è contigua alla prima colonna;
d. l’ultima riga della griglia è contigua alla prima riga.

I punti c e d fanno di questa matrice una struttura toroidale chiusa. I vincoli, nel loro insieme, rendono questo problema semplice da comprendere ed efficace per effettuare un test.

Ogni individuo della nostra popolazione dunque è composto di N×N geni (bit string) ed ogni gene ha un alfabeto di 3 caratteri, uno per colore. Inoltre la fitness massima che ogni individuo può raggiungere è data da 2 ×(N×N), cioè il massimo di non contiguità di colore per riga (N×N) ed il massimo di non contiguità di colore per colonna (N×N).

Se la griglia da colorare è 5 × 5, ogni “individuo” sarà formato da 25 geni e una fitness di 50 indicherà tutti gli individui che rispettano tutti e quattro i vincoli (a, b, c, d).

Da notare che in una griglia 5 × 5 le colorazioni possibili sono 847.288.609.443, mentre le combinazioni accettabili (50/50 punti) sono 1.000 [Davis, 1991].

GenAgents, una simulazione di una società virtuale popolata da agenti artificiali in interazione per lo studio della evoluzione di dinamiche cooperative (o competitive), rappresenta un ulteriore esempio di applicazione degli algoritmi genetici a problemi di simulazione di dinamiche complesse [vedi la voce "agenti artificiali" del menu' principale].