Algoritmi genetici

V parte: Selezione dei genitoridi

Ci avviamo ormai verso la definizione delle procedure operative di un algoritmo genetico. Ma prima di poter codificare l‘algoritmo, sono necessarie ancora ulteriori fasi di impostazione. In questo articolo ci occupiamo della "selezione dei genitori" per la riproduzione di una "popolazione" da cui estrarre le soluzioni.

Introduzione

Come visto nella pseudocodifica dell'algoritmo genetico, la prima operazione da effettuare sulla popolazione passata in ingresso è la selezione dei genitori per la riproduzione. La selezione viene fatta in base ai valori di fitness che presentano i singoli individui all'interno dell'intera popolazione. Una volta assegnato il valore di fitness a tutti gli individui, esistono diversi algoritmi che effettuano la selezione dei genitori: in questo articolo viene preso in considerazione l'algoritmo di Roulette Wheel Selection, che per la selezione, prende proprio in considerazione il valore di fitness degli individui. Il risultato della selezione è la creazione di una "piscina di accoppiamento" in cui vengono inseriti gli individui per la riproduzione. La creazione di questa piscina comporta diversi problemi riguardanti la dimensione e il numero di individui (pari o dispari) che può essere inserito: esistono diverse tecniche per risolvere queste situazioni, tra le quali il rimappaggio del fitness.

Parent Selection

La selezione dei genitori è il compito di allocare opportunità riproduttive a ciascun individuo. In principio, gli individui sono copiati dalla popolazione in una "piscina di accoppiamento", detta mating pool, dove gli individui migliori hanno molta probabilità di essere copiati più volte, mentre i peggiori potrebbero non essere copiati affatto. Sotto un severo schema di riproduzione, la dimensione della mating pool è uguale a quella della popolazione. Dopo di ciò, coppie di individui vengono tirati fuori dalla piscina e fatti accoppiare. Questo viene ripetuto finche' la piscina rimane vuota.
Il comportamento di un algoritmo genetico dipende fortemente dal modo in cui gli individui vengono scelti per andare nella mating pool. Possono esistere diversi metodi di selezione per il mating pool, ma il più semplice di questi è il roulette wheel selection, nel quale i genitori sono selezionati in base al loro fitness: i migliori cromosomi hanno maggiore probabilità di essere selezionati.

Figura 1 - Roulette Wheel Selection, basata sulla fitness.

Questo metodo può essere assimilato a una roulette in cui vengono piazzati tutti i cromosomi, ognuno dei quali occupa uno spazio grande in proporzione al suo fitness. Poi si lancia la pallina e si seleziona il cromosoma, quindi i cromosomi con alto fitness possono essere selezionati più volte.

Figura 2 - Pseudocodifica di Parent Selection.

In un altro metodo è possibile prendere il punteggio di fitness di ciascun individuo, rilevato su una nuova scala, utilizzando questo valore rimappato come numero di copie che vanno nella mating pool. Un altro metodo ancora produce un simile effetto, ma senza passare attraverso il passo di calcolare una fitness modificata. Questi metodi possono essere chiamati "Fitness rimappato esplicitamente" e "Fitness rimappato implicitamente".

Fitness rimappato esplicitamente

Per fare in modo che la mating pool abbia la stessa dimensione della popolazione originale, la media del numero di prove riproduttive allocate a ogni individuo deve essere 0: questo effetto viene ottenuto rimappando il fitness di ogni individuo tramite la divisione dello stesso per la media del fitness della popolazione. Questo schema di rimappamento alloca prove riproduttive in proporzione al fitness grezzo, in accordo con la teoria di Holland.
C'è un importante aspetto pratico che necessita di essere chiarito: il fitness rimappato di ogni individuo, in generale, non sarà un intero, quindi poiche' solo un numero intero di copie può essere piazzata nel mating pool, è necessario convertire il numero in un intero in modo da non introdurre deviazione. Un metodo largamente utilizzato per effettuare questa operazione è stochastic universal sampling without replacement, ossia il campionamento stocastico universale senza rimpiazzamento.  Un metodo migliore è universal stochastic sampling, ossia il campionamento stocastico universale, un metodo elegante e teoricamente perfetto. E importante non confondere il metodo sampling con la selezione dei genitori. Differenti metodi di selezione dei genitori, saranno buoni per molte applicazioni, ma un buon sampling è sempre buono, per tutti i metodi di selezione.
Esistono inoltre diversi metodi per allocare prove riproduttive a individui in maniera direttamente proporzionale al fitness grezzo. Ad esempio, il Fitness Scaling è un metodo molto usato: il massimo numero di prove riproduttive allocato a un individuo è impostato a un certo valore, tipicamente 2. Questo è ottenuto sottraendo un numero appropriato a dal valore di fitness grezzo, poi dividendo la media del valore di fitness aggiustato. Sottraendo un importo fisso aumenta il rapporto massimo/media del fitness; deve essere posta attenzione per non generare fitness negativi.
Il Fitness Scaling tende a comprimere il range all'inizio, poi lentamente converge giù e aumenta la quantità di esplorazioni. Comunque, la presenza di un solo super fit, con fitness anche 10 volte superiore agli altri, può portare a sovra-compressione: se la scala del fitness è compressa il rapporto massimo/media del fitness è 2:1 allora il resto della popolazione avrà fitness abbastanza vicino a 1. Sebbene si sia prevenuta alla convergenza prematura, è stato fatto a spese dell'effettiva oscillazione fuori dalla funzione fitness. Come detto prima, se la funzione fitness è troppo oscillante, il genetic drift diventerà un problema, e la sovra-compressione porterà non solo a una performance più lenta, ma allontanerà l'algoritmo dall'ottimo.

Figura 3 - Fitness.

Un altro metodo di allocazione è il Fitness windowing, che funziona come il fitness scaling, eccetto che la somma da sottrarre è scelta differentemente. Il minimo del fitness in ogni generazione viene ricordato e viene sottratto il minimo fitness osservato nelle precedenti n generazioni, dove di solito n =10. Con questo schema la pressione di selezione, cioè il rapporto massimo/media delle prove di riproduzione allocate, varia durante l'esecuzione, e anche tra problema e problema. La presenza di un super-unfit può provocare sotto-espansione, mentre la presenza di un super-fit causa prematura convergenza, perche' non c'è influenza nel grado di scala applicato.
Il problema presentato dalle tecniche di scaling e windowing è che il grado di compressione dipende da un singolo, estremo individuo, sia esso il migliore o il peggiore. Le performance peggioreranno se l'individuo è eccezionalmente estremo.

Fitness Ranking è un altro metodo comune che evita di appoggiarsi su un individuo estremo. Gli individui sono ordinati a seconda del fitness grezzo, cioè il peggiore individuo avrà fitness 1, il secondo peggiore 2 e il migliore N, che corrisponde al numero di cromosomi nella popolazione; allora, i valori di fitness riproduttivo saranno assegnati in accordo al rango. Questo può essere fatto linearmente o esponenzialmente e dà un risultato simile al fitness scaling, in questo il rapporto massimo/media del fitness è normalizzato a un particolare valore; inoltre, questo assicura che il fitness rimappato di un individuo intermedio sarà regolarmente propagato. A causa di questo, l'effetto di uno o due individui estremi sarà trascurabile, indipendentemente da quanto piccolo o grande sia il valore del loro fitness in rapporto al resto della popolazione; in questo modo, i migliori cromosomi non differiscono molto dagli altri e questo può rallentare molto la convergenza. Il numero di prove riproduttive allocate, per esempio, al quinto miglior individuo sarà sempre lo stesso, qualunque sia il valore di fitness dei punti sopra o sotto: l'effetto è che la sovracompressione cessa di essere un problema.
Alcuni esperimenti dimostrano che il ranking è superiore al fitness scaling.

Fitness rimappato implicitamente

Questo metodo riempie la mating pool senza passare attraverso livelli intermedi di rimappamento del fitness.

Una di queste tecniche è la Tournament Selection. Ci sono alcune varianti: nella più semplice, la selezione di torneo binario, coppie di individui sono prese a caso tra la popolazione: chiunque abbia un alto fitness viene copiato nella mating pool, e insieme vengono sostituiti nella popolazione originale; questo è ripetuto finche' la piscina non è piena. Possono essere usati tornei più grandi, dove il migliore di n individui scelti a caso è copiato nella mating pool, e questo ha l'effetto di aumentare la pressione di selezione, perche' gli individui sotto la media difficilmente vinceranno i tornei, mentre i migliori avranno ottime probabilità.
Un'ulteriore generalizzazione è la selezione con torneo binario statistico, dove i migliori individui vincono i tornei con probabilità p dove 0.5 < p < 1. Usando valori più bassi di p si diminuisce la pressione di selezione, perche' gli individui sotto la media sono in proporzione più avvantaggiati nel vincere un torneo, mentre quelli sopra la media perdono probabilità. Aggiustando la probabilità di vincere o la dimensione del torneo, la pressione di selezione può essere resa grande o piccola a piacere. Goldberg e Deb hanno confrontato quattro differenti schemi: selezione proporzionale, fitness ranking, tournment selection e steady state selection, discusso in seguito, e hanno concluso che tramite opportuni aggiustamenti dei parametri, tutti gli schemi, ad eccezione della selezione proporzionale, hanno performance simili, quindi non c'è una tecnica migliore in assoluto.

Generation gaps e steady-state replacement

Il gap generazionale può essere definito come la percentuale di popolazione che viene sostituita a ogni generazione. Molto lavoro è stato fatto con gap 1: ogni volta viene sostituita l'intera generazione; ma recentemente la tendenza è a preferire un rimpiazzamento steady-state (stato stabile): questo opera al contrario, cioè solo pochi individui vengono sostituiti ogni volta.
Questo può essere un modello migliore rispetto a quanto avviene in natura: nelle specie con una vita breve, come alcuni insetti, i genitori depongono le uova e muoiono prima di vedere i figli; ma, nelle specie con una vita più lunga, figli e genitori convivono. Questo permette ai genitori di crescere i figli e di istruirli, ma crea anche competizione tra loro.
In questo caso, non bisogna considerare solo come individuare due genitori, ma si considera anche la selezione degli individui sfortunati affinche' muoiano e lascino spazio ai figli. Ecco alcuni degli schemi possibili:

  • si selezionano i genitori secondo il fitness, e si rimpiazza a caso;
  • si selezionano i genitori a caso, e la selezione per il rimpiazzamento viene fatta considerando l'inverso del fitness;
  • si selezionano i genitori e i rimpiazzandi secondo il criterio fitness / inverso del fitness;

L'essenziale differenza tra un rimpiazzamento convenzionale e generazionale in un algoritmo genetico e uno steady-state è che nel secondo caso le statistiche della popolazione, ad esempio il fitness medio, sono ricalcolate dopo ogni accoppiamento, che risulta computazionalmente più dispendioso se fatto incrementalmente, e i nuovi figli sono subito pronti per la riproduzione. Un algoritmo di questo genere ha l'opportunità di sfruttare un individuo promettente non appena viene creato.
Comunque gli studi di Goldberg e Deb hanno trovato che i vantaggi della tecnica steady-state sembrano essere correlati all'alto tasso di crescita iniziale. Lo stesso effetto può essere ottenuto, dicono, usando un fitness ranking esponenziale, o una selezione con un torneo di grande taglia, e non hanno trovato nessuna prova che il rimpiazzamento steady-state sia fondamentalmente migliore del generazionale.

Conclusioni

In questo articolo si è affrontata la prima parte dell'esecuzione di un algoritmo genetico, con particolare attenzione alla valutazione della fitness nella selezione dei genitori. Nel prossimo articolo verranno affrontate più nel dettaglio le tecniche di riproduzione dei geni, quali il crossover e la mutazione.

Riferimenti

[1] D.B. Fogel, "Evolutionary computation: toward a new philosophy of machine intelligence", IEEE Press, NewYork, 1995, ISBN 078035379X

[2] J.R Koza, "Genetic programming: on the programming of computers by means of natural selection", MIT Press, Cambridge, MA, 1992, ISBN 0262111705

[3] Alden H. Wright, "Genetic Algorithms for Real Parameter Optimization", 1991

 

 

 

Condividi

Pubblicato nel numero
134 novembre 2008
Luana Rinaldi è nata a Napoli nel 1980. Si è laureata in Ingegneria Informatica presso l‘Università degli studi di Roma Tre, portando avanti una tesi di ricerca in bioinformatica. Dal 2000 si occupa professionalmente di analisi, progettazione e sviluppo di applicazioni in linguaggio Java con una particolare attenzione alle tecnologie…
Articoli nella stessa serie
Ti potrebbe interessare anche