Algoritmi genetici – esempio teorico

Continua la serie sugli algoritmi genetici. Dopo l’introduzione teorica del primo articolo, vediamo un esempio applicato ad un semplice problema di ricerca del minimo in una funzione matematica.

Supponiamo di voler massimizzare la seguente funzione nel campo dei numeri naturali:

f(n) = -n^2 + 256n \hspace*{1em} 0 \le n \le 255 \hspace*{2em}(1)

Il primo passo da effettuare è la codifica dell’unico parametro n; ad esempio, è possibile rappresentare n con una stringa di otto bit coincidente con la sua rappresentazione in alfabeto binario.

L’algoritmo genetico parte generando una popolazione casuale di N individui, ognuno dei quali è rappresentato da un diverso valore della variabile n. Ad esempio, si può considerare una popolazione di 5 individui.

Per ciascuno degli individui generati, si calcola il valore di fitness in base al modello del problema da risolvere; nel caso in esame il valore di fitness può essere definito in modo molto semplice attraverso il valore assunto dalla funzione (1) in corrispondenza del valore n associato all’individuo:

Il passo successivo è la scelta degli individui da riprodurre, scelta che dev’essere effettuata in modo tale da favorire gli individui a più alto valore di fitness, senza escludere però completamente gli altri per essere sicuri di sfruttare al meglio tutto il materiale genetico della popolazione a disposizione. Un modo molto semplice per fare ciò è assegnare a ciascun individuo una probabilità di riproduzione pari al rapporto percentuale tra il suo valore di fitness e la somma dei valori di fitness di tutti gli individui della generazione:

Nella fase di cross-over si scambiano parti delle stringhe dei genitori per formare gli individui “figlio”. Nel caso più semplice di “single-point cross-over” si tagliano le stringhe in una posizione scelta a caso, per produrre due segmenti “testa” e due segmenti “coda”. I segmenti “testa” sono poi scambiati per produrre due nuovi cromosomi di lunghezza completa. Il cross-over non è abitualmente applicato a tutte le coppie di individui selezionati per l’accoppiamento, ma con una certa probabilità (tipicamente tra 0.6 e 1.0). Se il cross-over non è applicato i figli sono generati semplicemente duplicando i genitori.

Si supponga di selezionare per la riproduzione il secondo e il quinto individuo e di incrociarli sul quarto bit. Per il secondo processo di riproduzione potrebbero essere selezionati il secondo e il terzo individuo, i cui cromosomi possono essere scambiati dal sesto bit:

A questo punto è possibile prendere entrambi i figli oppure uno solo. In ogni caso, il cromosoma dei figli è soggetto a mutazione, ovvero ogni gene è modificato con una probabilità bassa (tipicamente 0.001). La mutazione serve ad inserire un po’ di “casualità” nella ricerca per assicurare che nessun punto nello spazio abbia probabilità nulla di essere esaminato. Nell’esempio in esame, facendo riferimento alla prima coppia di figli generati, si supponga di mutare solo il primo bit del secondo figlio:

Il processo di generazione dei figli continua fino a quando il numero di individui generati uguaglia il numero iniziale di individui nella popolazione. In questo modo si completa la nuova generazione e il processo si ripete attraverso le fasi di valutazione, selezione, incrocio, mutazione, fino a che non si raggiunge il criterio di stop desiderato. Si può decidere di fermare l’algoritmo quando si ottiene la convergenza della popolazione, quando si raggiunge un determinato grado di idoneità oppure quando è stato effettuato un numero prefissato di generazioni.