Perché i GA funzionano

Molta della ricerca sui GA si è concentrata sul trovare regole empiriche per farli funzionare bene. Non c'è una teoria generalmente accettata che spieghi esattamente perché un GA ha certe proprietà, ma sono state fatte alcune ipotesi che possono parzialmente spiegarne il successo ed essere tenute in considerazione per implementare un buon algoritmo.

Gli Schemata e il Teorema dello Schema

Il teorema dello schema di Holland è la prima rigorosa spiegazione del perché gli algoritmi genetici funzionino. Uno schema (al plurale spesso schemata) è un modello di valori del gene che possono essere rappresentati (nella codifica binaria) da una stringa di caratteri dell'alfabeto {0,1,#}. Un cromosoma contiene gli schemi ottenuti sostituendo col simbolo "# " uno o più dei suoi bit. Per esempio, il cromosoma"1010", contiene tra gli altri gli schemi 10##, #0#0, ##10 e ##1#. L'ordine di uno schema è il numero di simboli diversi da "#\" che contiene e la lunghezza definita è la distanza tra i simboli diversi da "#\" più esterni (nell'esempio 2,3,1,3, rispettivamente).

Il Teorema dello Schema spiega la potenza di un GA in termini di quanti schemi sono processati. Agli individui della popolazione viene data la possibilità di riprodursi, spesso chiamata prove di riproduzione(reproduce trials), e producono figli. Il numero di opportunità che ogni individuo riceve è in proporzione al suo fitness, quindi i migli ori individui contribuiscono maggiormente ai geni della generazione successiva. Si presuppone che un alto valore di fitness sia dovuto al fatto che l'individuo possiede buoni schemi. Passando i migliori schemi alla generazione successiva, aumenta la probabilità di trovare soluzioni migliori. Holland ha dimostrato che la cosa migliore è assegnare prove di riproduzione in numero sempre maggiore agli individui che hanno il fitness più elevato rispetto al resto della popolazione, in modo che i buoni schemi abbi ano un numero di prove crescente in modo esponenziale nelle generazioni successive (teorema dello schema). Ha mostrato inoltre che poichè ogni individuo contiene un gran numero di schemi diversi, il numero degli schemi che devono essere effettivamente processati è dell'ordine di n elevato 3, dove nè il numero di individui. Questa proprietà è detta parallelismo implicito ed \è una delle motivazioni del buon funzionamento dei GA.

Building Block Hypothesis

La potenza dei GA sta nella loro capacità di trovare buoni blocchi di costruzione. Questi sono schemi di lunghezza definita corta formata da bit che lavorano bene insieme e tendono a portare miglioramenti quando sono incorporati nello stesso individuo. Uno schema di codifica ben riuscita è uno schema che incoraggia la formazione di building block, assicurandosi che:

1.i geni correlati siano vocini all'interno del cromosoma

2.ci sia poca interazione tra i geni

L' interazione tra geni, spesso chiamata epistasis, significa che il contributo di un gene al fitness dipende dal valore degli altri geni nel cromosoma. Infatti c'è sempre una certa interazione in una funzione multimodale, e questo è importante, perchè esse sono l'unico tipo di funzioni che vengono processate con i GA perchè problemi più semplici possono essere risolti più facilmente con altri metodi. Se queste regole sono rispettate, il GA sarà efficiente come predetto dal teorema dello schema. Sfortunatamente le c ondizioni (1) e (2) sono difficili da incontrare e spesso i geni possono essere correlati in modo che non sia possibile metterli vicino in una stringa monodimensionale (per esempio se sono collegati gerarchicamente). In molti casi, l'esatta natura del legame tra i geni può non essere conosciuto dal programmatore, così anche se sono relazioni semplici, può essere impossibile arrangiare la codifica per mostrarle. La condizione (2) è una precondizione per (1). Se il contributo per il fitness totale di ogni gene fosse indipendente dagli altri geni, allora sarebbe possibile risolvere il problema con l'hillclimbing cercando su ciascun gene alla volta. Chiaramente non è possibile in generale. Se fossimo sicuri che ogni gene interagisse solo con un piccolo numero d i altri geni e questi potessero essere messi vicini nel cromosoma, allora le condizioni (1) e (2) sarebbero verificate. Ma se c'è molta interazione tra i geni nessuna delle due condizioni può essere incontrata. Chiaramente, si dovrebbe cercare di disegnare gli schemi di codifica in modo da conformarsi alle raccomandazioni di Goldberg, poichè saremmo sicuri che il GA funzionerà nel modo migliore possibile. Da qui nascono due interessanti domande: Se ciò non è possibile, può un GA essere modificato in modo da migliorare il suo funzionamento in queste circostanze? (e se sì, come?). Queste domande sono entrambe argomento di ricerca.