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 l’esplorazione, 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 l’equilibrio 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 l’utilità 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 dell’accumulazione 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 l’informazione del gradiente nella funzione fitness, la funzione fitness fornisce un’inclinazione 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 l’epistasis saranno discussi successivamente.