Prima di poter definire le procedure operative di un algoritmo genetico, è necessario procedere in una fase di setup, in cui si deve rappresentare il problema, definire gli obiettivi, e infine, codificare l‘algoritmo. In questo articolo verranno analizzate queste fasi.

Introduzione

Dire che gli Algoritmi Genetici sono procedure complesse, adattive, finalizzate alla risoluzione di problemi di ricerca e ottimizzazione, equivale a dire che sono procedure che cercano sostanzialmente il punto di massimo di una certa funzione, quando questa funzione è troppo complessa per essere massimizzata velocemente con tecniche analitiche ed è impensabile una procedura che esplori casualmente lo spazio delle soluzioni. L’algoritmo genetico seleziona le soluzioni migliori e le ricombina con diverse modalità affinche’ esse evolvano verso un punto di massimo. La funzione da massimizzare è detta fitness.

Il modello originario di Holland si basa su una popolazione di n stringhe di bit di lunghezza fissata l (n, l I N), generate in modo casuale. L’insieme delle stringhe binarie di lunghezza l ha 2l elementi e rappresenta lo spazio delle soluzioni del problema. Ogni stringa (genotipo) è la codifica binaria di una soluzione candidata (fenotipo). In generale la funzione di fitness si presenta nelle forma seguente:

Tramite questa funzione, a ogni genotipo

della popolazione iniziale P(t=0)è associato un valore

che rappresenta la capacità dell’individuo di risolvere il problema dato. Per determinare il valore di adattività, la funzione di fitness riceve in input un genotipo, lo decodifica nel corrispondente fenotipo e lo testa sul problema dato. Una volta conclusa la fase di valutazione degli individui della popolazione iniziale, si genera una nuova popolazione P(t+1) di nuove n soluzioni candidate applicando gli operatori di selezione, crossover, mutazione e inversione.

Rappresentazione del problema

Prima che un algoritmo genetico possa essere implementato, risulta necessario effettuare un’adeguata codifica del problema, detta representation. Una possibile codifica può essere la seguente:

in cui S è lo spazio delle soluzioni del problema, e X è lo spazio dei cromosomi, ossia lo spazio di ricerca.

Funzione di fitness

Insieme allo schema di codice usato, la funzione fitness è l’aspetto cruciale di ogni algoritmo genetico. Molta ricerca si è concentrata sull’ottimizzazione di tutte le parti degli algoritmi, poiche’ i miglioramenti possono essere applicati a una varietà di problemi. Molto spesso, comunque, si è trovato che solo un piccolo miglioramento del comportamento può essere fatto. Grefenstette ha indicato un insieme di parametri ottimali (crossover, mutazione, popolazione, etc), ma ha concluso che i meccanismi di base di un algoritmo genetico sono così robusti che, entro margini abbastanza grandi, i parametri non sono critici. Quello che è critico nel comportamento è invece la funzione fitness e lo schema di codifica usato.
Per un problema di massimizzazione, la funzione di fitness può coincidere con la funzione obiettivo, o con una sua trasformazione. È necessario notare che gli algoritmi genetici sono procedure di massimizzazione, quindi valori di fitness più alti son associati ad individui migliori. Ovviamente, per problemi di minimizzazione, la rappresentazione del problema e la stessa funzione di fitness devono necessariamente venire riformulati.
Idealmente, è auspicabile che la funzione fitness sia piatta e regolare, così che i cromosomi con fitness ragionevole siano vicini, nello spazio dei parametri, ai cromosomi con fitness leggermente migliore. Per molti problemi di interesse, purtroppo, non è possibile costruirla con questo andamento: se fosse possibile, inoltre, converrebbe usare il metodo hillclimb. Inoltre, perche’ gli algoritmi genetici funzionino bene, è necessario che la costruzione della funzione di fitness non preveda troppi massimi locali, o massimi troppo isolati.
La regola generale per costruire la funzione fitness, è che essa dovrebbe riflettere in qualche maniera il valore reale del cromosoma. Come detto sopra, per molti problemi, la costruzione può essere un passo ovvio, ad esempio in certi casi basta calcolare il valore di ogni cromosoma. Ma il valore reale di un cromosoma, non sempre è una quantità utile per la guida nella ricerca genetica: infatti, in problemi di ottimizzazione combinatoria, ci sono molti vincoli, e molti punti nello spazio rappresentano cromosomi non validi, e perciò hanno valore “reale” zero.
Perche’ un algoritmo genetico sia efficace, è necessario formulare una funzione dove il fitness di un cromosoma è visto in funzione di quanto è in grado di portare l’esplorazione verso un cromosoma valido: infatti, la conoscenza della locazione dei cromosomi validi, risulta essere indispensabile per poter assegnare ai punti vicini un buon valore di fitness.
Cramer ha suggerito che se il naturale obiettivo di un problema è tutto-o-niente, e risultati migliori possono essere ottenuti se si inventano dei sotto-obiettivi significativi. Un altro approccio è quello di considerare una funzione penalità, che rappresenta quanto i cromosomi sono inadeguati e costruisce la funzione fitness come:

costante   –>   penalità

Secondo alcuni è più utile considerare quanti vincoli sono violati piuttosto che quanti sono soddisfatti. Una buona funzione di penalità può essere costruita a partire dal costo di completamento stimato, cioè il costo necessario (stimato) per far diventare valido un cromosoma che non lo è.
La stima di funzioni approssimate è una tecnica che può qualche volta essere usata se la funzione fitness è troppo complessa o lenta da valutare. Se può essere creata una funzione più veloce che approssimativamente dà il valore della funzione fitness “vera”, l’algoritmo genetico può trovare, in un dato tempo di CPU, un cromosoma migliore di quello che avrebbe trovato usando la vera funzione fitness. Se per esempio la funzione semplificata è 10 volte più veloce, possono essere stimati 10 punti approssimati invece di valutare un solo punto esattamente, e questo è generalmente meglio; infatti un algoritmo genetico è abbastanza robusto da convergere anche in presenza del rumore (noise) introdotto dall’approssimazione. Questa tecnica deve essere usata dove la funzione fitness è stocastica.
Goldberg ha descritto anche altre tecniche che usano per esempio una computazione incrementale basata sul fitness dei genitori.

Problemi di Fitness Range

All’inizio di un’esecuzione, i valori per ciascun gene dei diversi membri della popolazione sono casualmente distribuiti: di conseguenza, è presente una grande propagazione di fitness individuali. Come l’algoritmo progredisce, particolari valori per ogni gene cominciano a predominare. Mentre la popolazione converge, il range del fitness si riduce. La variazione nel range del fitness spesso presenta i seguenti problemi:

Convergenza Prematura

Un classico problema con gli algoritmi genetici è che i geni provenienti da pochi individui con un fitness comparabilmente alto (ma non ottimale) possono rapidamente dominare la popolazione, causando la convergenza a un massimo locale. Una volta che la popolazione converge, l’abilità dell’algoritmo di continuare la ricerca per una soluzione migliore è effettivamente eliminata: il crossover di individui quasi identici può portare ben pochi miglioramenti. Solo la mutazione rimane per poter esplorare nuove zone, e questo semplicemente porta a una ricerca lenta e casuale.
Il teorema dello schema dice che si dovrebbero allocare prove riproduttive (o opportunità) in proporzione al loro fitness relativo. Ma quando si effettua un’operazione del genere si verifica una convergenza prematura a causa del fatto che la popolazione non è infinita. Per far lavorare bene l’algoritmo su una popolazione finita, si dovrebbe modificare la maniera con cui vengono scelti gli individui per la riproduzione.
L’idea base è che bisogna controllare il numero di opportunità che ogni individuo riceve in modo che non sia ne’ troppo basso ne’ troppo alto: l’effetto è quello di restringere il range del fitness che un qualsiasi individuo superfit possa improvvisamente prevalere.

Fine lenta

Questo problema è opposto al precedente. Dopo molte generazioni, la popolazione sarà convergente, ma non avrà localizzato precisamente il massimo locale. Il fitness medio sarà alto, ma ci sarà poca differenza tra la media e il miglior individuo. Conseguentemente ci sarà un insufficiente gradiente nella funzione fitness, per spingere l’algoritmo verso il massimo.
Le stesse tecniche usate per combattere la convergenza prematura combattono anche questo problema: lo fanno espandendo il range effettivo del fitness nella popolazione. Come con la prematura convergenza, il fitness scaling può portare a sovracompressione (o sottoespansione) dovuta a un individuo super poor.

Pseudocodifica di un algoritmo genetico

Una volta definita, quindi, la rappresentazione del problema e la relativa fitness di valutazione, si può procedere con la codifica reale dell’algoritmo.
L’algoritmo consiste nell’applicazione di operazioni, che tendono a modificare la popolazione dei geni, nel tentativo di migliorarli in modo da ottenere una soluzione sempre migliore.
L’evoluzione procede quindi in passi, per ognuno di questi viene per prima cosa eseguito un ordinamento dei geni sulla base del risultato della funzione di fitness. Vengono poi eseguite le operazioni su un numero di geni stabilito dai parametri dell’algoritmo, che in generale determinano quanti geni devono subire crossover e mutazioni, e in quale misura.
L’algoritmo evolve quindi attraverso i seguenti punti:

• generazione, in maniera casuale, una popolazione iniziale;
• creazione di una sequenza di nuove popolazioni, o generazioni: in ciascuna iterazione, gli individui della popolazione corrente sono usati per creare la generazione successiva, e a questo scopo si compiono degli ulteriori passi;
• ciascun membro della popolazione corrente è valutato calcolandone il rispettivo valore di fitness (idoneità);
• si determina un opportuno ordinamento di tali individui sulla base dei valori di fitness;
• gli individui più promettenti sono selezionati come genitori;
• a partire da tali individui si genera un pari numero di individui della generazione successiva, e ciò può avvenire secondo due modalità distinte, vale a dire effettuando cambiamenti casuali su un singolo genitore (mutazione) oppure combinando opportunamente le caratteristiche di una coppia di genitori (incrocio);
• gli individui così generati vanno a sostituire i genitori consentendo la formazione della generazione successiva;
• infine, l’algoritmo s’interrompe quando uno dei criteri d’arresto è soddisfatto.

Di seguito, viene presentata la pseudo-codifica di un algoritmo genetico canonico, secondo le direttive enunciate da Holland.

L’algoritmo sopra codificato, può essere rappresentato graficamente attraverso il seguente diagramma di flusso.

Conclusioni

In questo articolo si è visto come la definizione della funzione di fitness determini la riuscita dell’algoritmo. Nei seguenti articoli verranno analizati i singoli passi compiuti, evidenziando il ruolo che ha il fitness di ogni individuo.

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