ESPLORAZIONE E SFRUTTAMENTO (EXPLOITATION)
Un qualsiasi algoritmo di ottimizzazione efficiente, deve
usare due tecniche per trovare il massimo globale: esplorazione (exploration)
per esaminare nuove e sconosciute aree dello spazio di ricerca, e
sfruttamento (exploitation) per fare uso dei punti
precedentemente visitati per trovare punti migliori. Queste
richieste sono contraddittorie, e un buon algoritmo di ricerca
deve trovare un buon compromesso tra le due.
Una ricerca puramente casuale è buona per lesplorazione,
ma non fa nessuno sfruttamento, mentre un metodo
puramente di scalata (hillclimb) è buono per lo sfruttamento, ma
fa poca esplorazione. La combinazione di queste due tecniche può
essere abbastanza efficace, ma è difficile sapere dove si trova
lequilibrio migliore (cioè quanto sfruttamento bisogna
fare prima di arrendersi e esplorare di più?).
Holland ha dimostrato che un GA combina insieme esplorazione e
sfruttamento allo stesso tempo e in un modo ottimale. Comunque,
sebbene questo sia teoricamente vero, in pratica ci sono problemi
inevitabili. Holland infatti ha fatto certe semplificazioni:
1. la popolazione è infinita
2. la funzione fitness riflette accuratamente lutilità
della soluzione
3. i geni in un cromosoma non interagiscono significativamente.
La (1) non può essere mai verificata in pratica e a causa di ciò
il funzionamento del GA sarà soggetto a errori stocastici. Un
problema del genere, che si trova anche in natura è quello dello
deriva genetica (genetic drift).
Anche in assenza di qualsiasi pressione di selezione (cioè la
funzione fitness è costante), membri della popolazione
continueranno a convergere verso qualche punto nello spazio di
ricerca. Questo succede semplicemente a causa dellaccumulazione
di errori stocastici. Se un gene diventa predominante nella
popolazione, allora ha la stessa probabilità sia di diventare più
dominante nella generazione successiva, che meno dominante. Se
avviene un aumento della predominanza in alcune generazioni
successive, e la popolazione è finita, allora un gene si può
propagare a tutti i membri della popolazione. Una volta che un
gene converge in questa maniera, il crossover non può introdurre
nuovi valori di geni. Ciò produce un effetto a catena, così che
come le generazioni vanno avanti, ogni gene diventa eventualmente
fissato.
Il tasso di deriva genetica produce allora un limite inferiore
alla velocità con la quale un GA può convergere verso la
soluzione corretta. Così, se il GA sta sfruttando linformazione
del gradiente nella funzione fitness, la funzione fitness
fornisce uninclinazione sufficientemente grande per
contrastare ogni deriva genetica. Il tasso di genetic drift, può
essere anche ridotto introducendo la mutazione. Comunque, se la
mutazione è troppo elevata, le informazioni del gradiente
non possono essere sfruttate adeguatamente.
Le condizioni (2) e (3) possono essere verificate su funzioni
test che si comportano bene in laboratorio, ma sono difficili da
soddisfare nel mondo reale. I problemi con la funzione fitness e
lepistasis saranno discussi successivamente.