Principi di base

Un GA standard è rappresentato nella pagina successiva. Prima che un GA possa girare, deve essere compiuta un'adeguata codifica (representation) del problema. Abbiamo anche bisogno di una funzione fitness, che assegni una figura di merito a ogni soluzione codificata. Durante l'esecuzione i genitori devono essere selezionati per la riproduzione, e ricombinati per generare figli. Questi aspetti sono descritti sotto.

Codifica

Si assume che una possibile soluzione per un problema possa essere rappresentata come un set di parametri (detti geni) i quali sono uniti insieme per formare una stringa di valori (spesso chiamata cromosoma). Holland per primo ha mostrato, ed è ancora accettato da molti, che l'ideale è usare un alfabeto binario per la stringa. Per esempio, se vogliamo rappresentare una funzione di tre variabili, F(x,y,z)} , possiamo rappresentare ogni variabile con un numero binario di 10 bit. Il nostro cromosoma conterrà allora tre geni, e consisterà di 30 cifre digitali.

In termini genetici, l' insieme dei parametri rappresentati da un particolare cromosoma è chiamato genotipo. Il genotipo contiene le informazioni richieste per costruire un organismo che è chiamato fenotipo. Gli stessi termini sono usati nei GA. Il fitness di un individuo dipende dalle performance del fenotipo. Questo può essere dedotto dal genotipo, cioè essere calcolato dal cromosoma, usando la funzione fitness.

Algoritmo genetico

Funzione Fitness

Per ciascun problema da risolvere deve essere costruita una specifica funzione fitness. Dato un particolare cromosoma, la funzione fitness restituisce un singolo valore numerico "fitness" o una "figura di merito", che si suppone sia proporzionale alla utilità o abilità dell'individuo che il cromosoma rappresenta. Per molti problemi, in particolari funzioni di ottimizzazione, è ovvio che la funzione fitness deve misurare il valore stesso della funzione. Ma non è sempre questo il caso (per esempio per ottimizzazioni combinatorie).

Riproduzione

Durante la fase di riproduzione di un GA, gli individui sono selezionati tra la popolazione e ricombinati, producendo la discendenza che sarà compresa nella generazione successiva. I genitori sono selezionati a ca so usando uno schema che favorisce gli individui migliori. Gli individui buoni saranno probabilmente selezionati più volte per la riproduzione, mentre quelli peggiori potrebbero non essere mai scelti. Avendo selezionato due individui, i loro cromosomi sono ricombinati, tipicamente usando il meccanismo del crossover e la mutazione.

Il crossover prende due individui, e taglia le stringhe dei loro due cromosomi in qualche posizione scelta a caso, per produrre due segmenti "testa" (head)} e due segmenti "coda" (tail). I segmenti coda sono poi scambiati per produrre due nuovi cromosomi di lunghezza completa. Ciascuno dei figli eredità alcuni geni da ogni genitore. Questo è conosciuto come single point crossover. Il crossover non è abitualmente applicato a tutte le coppie di individui selezionati per l'accoppiamento. Si fa una scelta a caso, dove la probabilità di crossover applicata è tipicamente tra 0.6 e 1.0. Se il crossover non è applicato i figli sono generati semplicemente duplicando i genitori. Questo dà la possibilità a ogni individuo di propagare i propri geni nella generazione successiva senza la scissione operata dal crossover.

La mutazione è applicata a ogni figlio singolarmente dopo il crossover. Viene alterato a caso ogni gene con una probabilità bassa (tipicamente 0.001). La teoria tradizionale ritiene che il crossover sia più importane della mutazione per quanto riguarda la rapidità nell'esplorare lo spazio di ricerca. La mutazione porta un po' di "casualità" nella ricerca e aiuta ad assicurarci che nessun punto nello spazio abbia probabilità nulla di essere esaminato. (un punto di vista alternativo verrà discusso in seguito). Un esempio di due individui che si riproducono per generare due figli è mostrato in figura nella pagina successiva. La funzione di fitness è un esponenziale ad una variabile, con un massimo per x=0.2 ed è codificata con un numero di 10 bit. Nella tabella 1 sono mostrati due genitori e i figli che hanno prodotto quando sono incrociati sul secondo bit (senza mutazione). Ciò mostra come sia possibile che il crossover ricombini parti dei cromosomi dei due individui e produca figli con fitness più elevato. (Potrebbe anche produrre individui con fitness minore, ma essi avrebbero poche possibilità di riprodursi nella ge nerazione successiva).

Convergenza

Se il GA è correttamente implementato, la popolazione evolverà in molte generazioni in modo che il fitness del miglior individuo e la media in ogni generazione cresca verso l'ottimo globale. La convergenza èla progressione verso la crescente uniformit\à . Un gene converge quando il 95% della popolazione condivide lo stesso valore. La popolazione converge quando tutti i geni convergono.