Confronto con altre Tecniche

Molte tecniche di approccio generale (gener al purpose) sono state inventate per problemi di ricerca e ottimizzazione. Come i GA assumono che il problema sia definita da una funzione di fitness, che deve essere massimizzata. Ci sono ottime tecniche di ottimizzazione, alcune delle quali sono applicabili solo a domini limitati, come ad esempio la programmazione dinamica, cheè applicabile solo dove la funzione fitness è la somma delle funzioni fitness calcolate ad ogni fase del problema e non c'è interazione tra le varie fasi. Descriviamo ora alcune di queste tecniche.

Ricerca Casuale

L'approccio con la forza bruta per funzioni complicate è una ricerca casuale o enumerata. I punti nello spazio di ricerca sono scelti a caso o in qualche maniera sistematica, e il loro valore calcolato. E' un metodo poco intelligente e di solito viene evitato.

Metodo del gradiente

Sono stati inventati diversi metodi che funzionano bene per l'ottimizzazione di funzioni continue che si basano sull\'uso delle informazioni sul gradiente della funzione per guidare la direzione della ricerca. Se però la derivata della funzione non può essere calcolata, per esempio perchè la funzione è discontinua, spesso falliscono. Questi metodi sono generalmente detti hillclimb (scalata). Funzionano bene con funzioni che hanno un solo picco (unimodali), ma per funzioni con molti picchi (multimodali), hanno il problema che viene scalato il primo picco, ma esso può non essere il picco più alto. Un esempio è mostrato in fig. 6 dove partendo da un punto iniziale X scelto a caso, con movimenti verso l\'alto (uphill) viene localizzato il picco B, ma A e C non vengono trovati.

Ricerca Iterata

I metodi della ricerca casuale e quello del gradiente possono essere combinati per avere una scalata iterata. Una volta che un picco è stato trovato, la scalata inizia nuovamente da un altro punto scelto a caso. La tecnica ha il vantaggio della semplicità e dà buoni risultati con funzioni che non abbiano molti massimi locali. Comunque, poiché ogni prova è fatta isolatamente, non si ottiene una figura complessiva della forma del dominio. Mentre la ricerca casuale progredisce, si continuano ad allocare lo stesso numero di prove sia in regioni dove sono stati trovati alti valori di fitness, sia in regioni con basso fitness. Un Ga, invece, inizia con una popolazione iniziale casuale, e assegna via via maggiori tentativi alle regioni con più alto fitness. Questi è uno svantaggio se il massimo si trova in una piccola regione circondata su tutti i lati da regioni con basso fitness, ma questo tipo di funzione è difficile da ottimizzare con qualsiasi metodo, e in questo caso vince il metodo della ricerca iterata per la sua semplicità.

Simulated Annealing (temperatura simulata)

Questa tecnica è stata inventata da Kirkpatrick nel 1982 ed è sostanzialmente una versione modificata dell'hillclimbing. Iniziando da un punto scelto a caso nel dominio, viene fatto un movimento casuale: se il movimento porta a un punto più alto allora è accettato, se ci porta a un valore più basso è accettato con probabilità p(t), dove t è il tempo. All'inizio p(t) è vicino al valore 1, ma gradualmente tende a zero. Inizialmente ogni movimento viene accettato, ma la temperatura si riduce e la probabilità di accettare un movimento negativo diminuisce. A volte movimenti negativi sono necessari per evitare massimi locali, ma se sono troppi possono allontanarci dal massimo. Comunque come la tecnica della ricerca casuale, lavora con solo una soluzione candidata per volta e perciò non costruisce una figura complessiva dello spazio di ricerca e non vengono salvate le informazioni dai precedenti movimenti per guidarci verso la soluzione.