ALGORITMI GENETICI

Introduzione

L'avvento degli elaboratori elettronici ha rappresentato una svolta rivoluzionaria nella storia della scienza e della tecnologia, che sta accrescendo enormemente la nostra capacità di predire e controllare la natura in forme che erano a malapena immaginabili soltanto mezzo secolo fa. Per molti, il coronamento di questa rivoluzione sarà la creazione, sotto forma di programmi per il calcolatore, di nuove specie di esseri intelligenti e addirittura di nuove forme di vita. Il tentativo di costruire modelli per il cervello ha dato origine al settore delle reti neurali, quello di imitare l'apprendimento umano al settore dell'apprendimento automatico e, infine, la simulazione dell'evoluzione biologica ha dato vita al campo della computazione evolutiva, di cui gli algoritmi genetici sono l'esempio più importante.

Perché ispirarsi all'evoluzione per risolvere problemi computazionali?

Chi fa ricerca nel campo della computazione evolutiva è convinto che i meccanismi dell'evoluzione siano adatti per affrontare alcuni dei più pressanti problemi computazionali in svariati settori, poiché, per risolvere molti di questi, è necessario ricercare la soluzione tra un numero enorme di possibili alternative. Un esempio è il problema della progettazione delle proteine con l'aiuto del calcolatore, per risolvere il quale occorre avere un algoritmo che possa individuare una proteina con determinate proprietà tra un numero enorme di possibili sequenze di amminoacidi.

Breve storia della computazione evolutiva

Già negli anni Cinquanta e Sessanta molti informatici studiarono i sistemi evolutivi con l'idea che i meccanismi dell'evoluzione potessero essere usati come strumenti di ottimizzazione per i problemi d'ingegneria e durante gli ultimi trent'anni c'è stato un crescente interesse nei confronti dei metodi di risoluzione basati sui principi dell'evoluzione e dell'ereditarietà: tali sistemi considerano una popolazione di potenziali soluzioni, una funzione di selezione basata sulla 'fitness' degli individui e degli operatori genetici.

L'idea di base di questi sistemi consiste nel far evolvere una popolazione di potenziali soluzioni per un dato problema usando operatori che s'ispirano alla naturale variabilità genetica e alla selezione naturale.

Negli anni Sessanta, Rechenberg introdusse le 'strategie evolutive', metodo che imita i principi dell'evoluzione naturale e che egli utilizzò per ottimizzare parametri a valori reali per strutture aerodinamiche

Fogel, Owens e Walsh (1966) hanno sviluppato la 'programmazione evolutiva', una tecnica che consiste nel rappresentare le soluzioni candidate per un dato obiettivo come macchine a stati finiti, che sono fatte evolvere mutandone casualmente i diagrammi di transizione di stato e sezionando i più adatti.

Altre tecniche basate sull'evoluzione sono la 'programmazione genetica' proposta da Koza (1992), che tentò di far evolvere programmi LISP in grado di svolgere determinati compiti, e gli 'algoritmi genetici' (in breve AG) di John Holland (1975).

Tutti questi metodi formano l'ossatura del campo della computazione evolutiva, anche se generalmente tutti i sistemi basati sull'evoluzione sono chiamati Programmi Evolutivi.

Il programma evolutivo è un algoritmo probabilistico che considera una popolazione di n individui P(t) = per t iterazioni. Ogni individuo rappresenta una potenziale soluzione al problema e ogni soluzione x^t_i viene valutata mediante l'assegnazione di un valore di idoneità. Quindi si procede con la creazione di una nuova generazione della popolazione, rappresentata dall'iterazione t+1, selezionando gli individui più idonei e trasformandoli per mezzo di opportuni 'operatori genetici'.

Terminologia degli Algoritmi Genetici

Molti termini del linguaggio degli AG sono derivati dalla Biologia reale dove, tuttavia, identificano oggetti decisamente più complessi.

In Biologia, i cromosomi sono filamenti di DNA che fungono da progetto per l'organismo. Ogni cromosoma è composto da geni, ognuno dei quali codifica una particolare proteina; le proteine, a loro volta, determinano le caratteristiche specifiche dell'organismo, come ad esempio, il colore degli occhi.

In termini genetici, l' insieme dei parametri rappresentati da un particolare cromosoma è chiamato genotipo. Il genotipo contiene le informazioni richieste per costruire un organismo che è chiamato fenotipo. Gli stessi termini sono usati nei GA. Il fitness di un individuo dipende dalle performance del fenotipo. Questo può essere dedotto dal genotipo, cioè essere calcolato dal cromosoma, usando la funzione fitness.

Funzione Fitness

Per ciascun problema da risolvere deve essere costruita una specifica funzione fitness. Dato un particolare cromosoma, la funzione fitness restituisce un singolo valore numerico 'fitness' o una 'ura di merito', che si suppone sia proporzionale alla utilità o abilità dell'individuo che il cromosoma rappresenta. Per molti problemi, in particolari funzioni di ottimizzazione, è ovvio che la funzione fitness deve misurare il valore stesso della funzione.

Algoritmo genetico

BEGIN Genera la popolazione iniziale
Calcola il fitness di ogni individuo
While Not finito DO
Begin /* ciclo riproduttivo */
Seleziona due individui dalla vecchia generazione per l'accoppiamento
/* influenzato in favore dei migliori */
ricombina i due individui per avere due discendenti
calcola il fitness dei due discendenti
inserisci i discendenti nella nuova generazione
End
IF la popolazione converge Then
Finito := TRUE
END
END

Il metodo di Holland

Gli algoritmi genetici (GA) sono metodi adattativi che possono essere usati per risolvere problemi di ricerca e ottimizzazione. Sono basati sui processi genetici degli organismi biologici : la selezione naturale e la riproduzione sessuale. La selezione naturale determina quali individui di una popolazione sopravvivono abbastanza per riprodursi (per esempio quelli in grado di riconoscere i predatori e di sfuggirgli), mentre la riproduzione sessuale determina la ricombinazione del

materiale genetico dei genitori dando luogo ad un evoluzione dei discendenti.

I principi di base dei GA sono stati definiti per la prima volta da Holland: essi simulano quei processi che nelle popolazioni naturali sono essenziali per l'evoluzione. In Natura, gli individui di una popolazioni competono uno con l'altro per risorse come cibo, acqua e territorio. Inoltre membri della stessa specie spesso competono per attrarre un comno. Quegli individui che hanno più successo nella sopravvivenza e nella riproduzione avranno un numero relativamente grande di discendenti.

Gli individui che si mostreranno essere meno adatti produrranno poca o forse nessuna prole. Questo significa che i geni degli individui più adattati (fit individuals) saranno trasmessi a un crescente numero di individui in ciascuna delle generazioni successive. La combinazione delle buone caratteristiche di diversi antenati possono a volte produrre una discendenza molto adattata (superfit), la cui qualità è superiore a quella di ciascun genitore. In questo modo le specie si evolvono e diventano sempre più adattate al loro ambiente. I GA usano una diretta analogia con il comportamento della natura. Lavorano con una popolazione di individui, ciascuno dei quali rappresenta una possibile soluzione del problema posto. A ogni individuo è associato un punteggio di adattamento 'fitness score' a seconda di quanto sia buona la soluzione al problema. In natura è equivalente a stabilire quanto un individuo riesce a competere per le risorse. Gli individui migliori hanno la possibilità di riprodursi incrociandosi con altri individui della popolazione. Questo produce nuovi individui discendenti che condividono alcune caratteristiche di ciascun genitore. Gli individui meno adattati hanno meno probabilità di riprodursi e quindi si estinguono. Una intera nuova popolazione di possibili soluzioni è così prodotta dalla selezione degli individui migliori della generazione corrente che accoppiandosi tra loro producono un nuovo insieme di individui. Questa nuova generazione contiene una proporzione più alta delle caratteristiche possedute dagli individui buoni della precedente generazione. In questo modo dopo molte generazioni le buone caratteristiche vengono proate a tutta la popolazione, essendo mischiate e scambiate con altre buone caratteristiche. Favorendo l'accoppiamento tra gli individui più adatti, vengono esplorate la aree più promettenti dello spazio di ricerca.

Se il GA è correttamente implementato, la popolazione evolverà in molte generazioni in modo che il fitness del miglior individuo e la media in ogni generazione cresca verso l'ottimo globale.

Durante la fase di riproduzione di un GA, gli individui sono selezionati tra la popolazione e ricombinati attraverso degli operatori genetici:

Selezione

L'operatore di selezione genera un numero casuale e seleziona l'individuo che ne contiene il valore.Quando un individuo è selezionato ne viene creata una copia e quest'ultima viene inserita nel così detto, mating pool. L'operatore di selezione determina, quali individui della vecchia popolazione hanno la possibilità di generare dei discendenti e poiché gli individui con fitness alta sono quelli favoriti l'operatore di selezione gioca, nel contesto dell'algoritmo genetico, il ruolo della selezione naturale per gli organismi viventi.

Crossover

Il Crossover prende due individui, e taglia le stringhe dei loro due cromosomi in qualche posizione scelta a caso, per produrre due segmenti 'testa' (head)} e due segmenti 'coda' (tail). I segmenti coda sono poi scambiati per produrre due nuovi cromosomi di lunghezza completa. Ciascuno dei li eredità alcuni geni da ogni genitore. Se il crossover non è applicato i li sono generati semplicemente duplicando i genitori.

Mutazione

In funzione di una prefissata e usualmente piccola probabilità P_mutation, il valore dei bit di ogni individuo viene cambiato (da 0 in 1 o viceversa), come illustrato in ura 3.1. L'operatore di mutazione rappresenta il fenomeno genetico della rara variazione di elementi del genoma degli esseri viventi durante l'evoluzione.

mutazione

Inversione

L'operatore d'inversione prende casualmente due punti nella stringa che codifica l'individuo e inverte i bit tra le due posizioni. In biologia il significato di un gene spesso non dipende dalla sua posizione nel cromosoma e, di conseguenza, l'inversione ne lascia invariata la semantica. Per tale ragione l'inversione è raramente utilizzata sia nelle applicazioni pratiche che negli studi teorici.

Inversione

Il Teorema dello Schema di Holland

Definizione. Sia V = l'alfabeto attraverso cui sono costruiti gli individui dell'algoritmo genetico. Si definisce schema una stringa della stessa lunghezza l degli individui dell'algoritmo genetico, costruiti sull'alfabeto esteso V + = ( 0; 1; #) . Il teorema dello schema di Holland è la prima rigorosa spiegazione del perché gli algoritmi genetici funzionino. Uno schema è un modello di valori del gene che possono essere rappresentati (nella codifica binaria) da una stringa di caratteri dell'alfabeto V . Un cromosoma contiene gli schemi ottenuti sostituendo col simbolo '# ' uno o più dei suoi bit. Per esempio, il cromosoma'1010', contiene tra gli altri gli schemi 10##, #0#0, ##10 e ##1#. L'ordine di uno schema è il numero di simboli diversi da '#' che contiene e la lunghezza definita è la distanza tra i simboli diversi da '#' più esterni.

Esempio. Lo schema H 1 = # 0000 rappresenta l'insieme costituito dalle due stringhe aventi uno dei due simboli di V nella posizione 0 e il simbolo 0 nelle posizioni 2, 3, 4 e 5, cioè

H 1 = ( 00000; 10000 )

Il Teorema dello Schema spiega la potenza di un GA in termini di quanti schemi sono processati. Agli individui della popolazione viene data la possibilità di riprodursi, spesso chiamata prove di riproduzione e producono i li. Il numero di opportunità che ogni individuo riceve è in proporzione al suo fitness, quindi i migliori individui contribuiscono maggiormente ai geni della generazione successiva. Si presuppone che un alto valore di fitness sia dovuto al fatto che l'individuo possiede buoni schemi. Passando i migliori schemi alla generazione successiva, aumenta la probabilità di trovare soluzioni migliori. Holland ha dimostrato che la cosa migliore è assegnare prove di riproduzione in numero sempre maggiore agli individui che hanno il fitness più elevato rispetto al resto della popolazione, in modo che i buoni schemi abbiano un numero di prove crescente in modo esponenziale nelle generazioni successive (teorema dello schema). Ha mostrato inoltre che poiché ogni individuo contiene un gran numero di schemi diversi, il numero degli schemi che devono essere effettivamente processati è dell'ordine di n elevato 3, dove n è il numero di individui. Questa proprietà è detta parallelismo implicito ed è una delle motivazioni del buon funzionamento dei GA.

PROBLEMA DEL DILEMMA DEL PRIGIONIERO

Il Dilemma del Prigioniero è un gioco con due partecipanti: si basa su una scelta che ha sempre spaccato le coscienze: tradimento o fedeltà?

I due giocatori sono due prigionieri, i quali vengono chiusi in due celle distinte senza poter comunicare tra di loro. Entrambi vengono interrogati, nel tentativo di fare confessare loro un crimine grave, mentre senza confessione di nessuno dei due sono imputabili solo per un reato minore. Per spingere a confessare i prigionieri si promette a ciascuno di essi uno sconto di pena, sconto che sarà molto basso se confessano entrambi.

Il dilemma del prigioniero è quindi decidere se tradire o cooperare con l'altro; questo dilemma viene tradotto in un gioco tra due giocatori, dove ad ogni giocata ciascun prigioniero può tradire o cooperare con l'altro prigioniero.

Una partita è costituita dalla sequenza di decisioni di ciascun giocatore. I punti attribuiti ad ogni mossa corrispondono al numero di anni di prigione risparmiati rispetto al massimo di 5 e quindi l'obiettivo è ottenere il maggior numero di punti possibile.

Il punteggio sarà il seguente:

Come si può vedere, in questo gioco non esiste a priori un comportamento ideale nella singola giocata: se si considera la coppia nel suo insieme si risparmiano ben 6 anni di pena cooperando (non tradendo), ma ciascuno dei due può essere egoista e tradire per avere uno sconto più alto per se, pur così compromettendo la posizione dell'altro. Ma se entrambi tradiscono, lo sconto (il punteggio) per entrambi è di solo 1 anno, quindi inferiore rispetto a quello relativo a una doppia cooperazione.

Axelrod negli anni '80 studiava il dilemma del prigioniero e i giochi connessi, ed era interessato a sapere quale fosse il comportamento migliore nel caso di una partita intera, con più giocate, se ciascun giocatore avesse mantenuto memoria delle precedenti giocate dell'avversario; nel caso reale i due sfortunati criminali si sarebbero trovati più volte sotto interrogatorio, però sulla loro decisione avrebbe influito il ricordo di come si era comportato il comno le volte precedenti. Axelrod organizzò dei tornei nei quali invitò ricercatori di diverse discipline a proporre la loro strategia. Ogni partecipante gli inviò un programma basato su una diversa strategia che teneva presente la memoria, e i vari programmi giocarono ripetutamente l'uno contro l'altro. In tutti i tornei la vincitrice fu la più semplice delle strategie proposte: 'Tit for Tat' (traducibile come 'occhio per occhio'). Questa strategia coopera nella prima partita e poi, nelle partite successive, replica la mossa compiuta dall'altro giocatore nella precedente partita. In pratica offre cooperazione e la ricambia, ma se l'altro giocatore tradisce, punisce il tradimento col tradimento e continua a punire finché l'altro giocatore non comincia a cooperare.

Dunque l'antica legge del taglione sembrava il migliore atteggiamento possibile nei confronti di una scelta. Ma interessante era vedere quali strategie avrebbe potuto inventare un sistema d'analisi come l'AG. L'approccio dell'AG è quello di mantenere una popolazione di giocatori, ognuno dei quali ha una particolare strategia. Inizialmente la strategia di ogni giocatore è scelta casualmente. Dopodiché ad ogni passo il giocatore gioca e il suo punteggio è annotato. Alcuni giocatori sono quindi selezionati per creare la nuova generazione. Quando un nuovo giocatore viene creato da una coppia di genitori questi avrà una strategia di gioco che sarà costruita mediante l'incrocio delle strategie dei suoi genitori; l'operatore di mutazione introduce una certa variabilità tra le strategie dei giocatori cambiando casualmente la rappresentazione di questa strategia.

Il punto saliente è l'idoneità di una strategia. Axelrod scoprì che otto strategie tra le tante presenti erano rappresentative dell'intero insieme delle strategie. Questo insieme servì, in un primo esperimento, da ambiente per far evolvere le strategie appartenenti alla popolazione. Ogni individuo della popolazione giocava contro ciascuna delle otto strategie prefissate, ottenendo un punteggio, e come idoneità dell'individuo, veniva preso il punteggio medio ottenuto in tutte le partite giocate. L'AG aveva una popolazione di 20 strategie e Axelrod fece 40 diverse esecuzioni da 50 generazioni ciascuna. La maggior parte delle strategie evolute erano simili a 'Tit for Tat', in quanto ricambiavano la cooperazione e punivano il tradimento. Tuttavia spesso l'AG trovava strategie che ottenevano punteggi nettamente superiori a 'Tit for Tat'.

Sarebbe sbagliato concludere che l'AG scopre strategie migliori di qualunque strategia progettata dall'uomo. Il successo di una strategia dipende moltissimo dal suo ambiente, cioè dalle strategie contro le quali gioca ed in questo caso l'ambiente era fissato: consisteva in otto strategie progettate dall'uomo che non cambiavano nel corso di un'esecuzione. Non è necessariamente detto che queste strategie ad alto punteggio otterrebbero buoni punteggi in un ambiente diverso. 'Tit for Tat' è una strategia generalista, mentre le strategie che hanno ottenuto i punteggi migliori si erano evolute specializzandosi per sfruttare le debolezze specifiche delle otto strategie prefissate. Axelrod concluse che l'AG riesce a fare bene ciò che l'evoluzione fa spesso: sviluppare adattamenti altamente specializzati in risposta a particolari caratteristiche dell'ambiente.