Algoritmo genetico
Un algoritmo genetico è una particolare tipologia di algoritmi informatici basati su metodi euristici di ricerca e sul principio della selezione naturale. Sono chiamati "genetici" per il fatto di utilizzare criteri simili a quelli utilizzati nella genetica per spiegare l'evoluzione biologica delle specie. Gli algoritmi genetici appartengono alla categoria degli algoritmi naturali. Gli algoritmi genetici sono applicati per la ricerca delle soluzioni ottimali a problemi complessi, in cui la funzione obiettivo è discontinua e non lineare, per i quali è inefficace o dispendioso l'utilizzo degli algoritmi lineari classici. Gli algoritmi genetici non assicurano l'individuazione di una soluzione ottimale ma contribuiscono a determinare un insieme di soluzioni superiori rispetto alle soluzioni di origine. A partire da un medesimo problema e di un medesimo insieme di soluzioni possibili di partenza. A ogni esecuzione questi algoritmi possono evolvere verso soluzioni finali differenti. Per questa loro caratteristica gli algoritmi genetici sono utilizzati nello studio dell'intelligenza artificiale.
Come funziona un algoritmo genetico. Le possibili soluzioni di un problema sono dette "individui" ( elementi ) e contribuiscono a formare la "popolazione". Inizialmente si parte da una classe di soluzioni casuali. Nel corso dell'esecuzione l'algoritmo effettua una selezione degli elementi della popolazione a ogni iterazione e li combina per creare nuovi elementi ( nuova generazione ) della popolazione stessa. La combinazione di due soluzioni crea una terza soluzione ( nuova generazione ) che eredita dalle precedenti alcune caratteristiche e le combina in un nuovo patrimonio "genetico" in modo simile a quanto accade in natura. Oltre alla combinazione delle caratteristiche delle soluzioni discendenti, l'algoritmo genetico può introdurre delle mutazioni casuali che introducono nuove caratteristiche che si aggiungono a quelle originarie. I nuovi elementi incrementano il numero delle soluzioni. Come accade per la selezione naturale, i nuovi elementi più efficienti/efficaci (elementi forti) si sostituiscono a quelle meno efficienti/efficaci (elementi deboli). La successione delle generazioni determina l'evoluzione verso la soluzione ottimale. Gli elementi fondamentali di un algoritmo genetico sono i seguenti:
- Funzione di fitness. La funzione di fitness consente di calcolare la probabilità di riproduzione per ciascun elemento della popolazione. La funzione di fitness misura il livello di addattabilità di un individuo della popolazione ( una soluzione al problema ) all'ambiente.
- Selezione naturale. In base alle probabilità di riproduzione l'algoritmo seleziona gli elementi per la formazione delle nuove coppie. Generalmente, la selezione è l'accoppiamento delle soluzioni migliori, quelle con un valore più alto nella funzione di fitness, per generare altre soluzioni.
- Cross-over. Il cross-over determina la modalità di combinazione del patrimonio genetico degli elementi genitori negli elementi figli ( nuova generazione ). Il cross-over ( o crossover ) è l'accoppiamento di due soluzioni per generare altre soluzioni.
- Mutazione casuale. L'algoritmo genetico inserisce alcune variazioni casuali nel patrimonio genetico degli elementi figli. La mutazione è una modifica casuale di una variabile binaria all'interno di una soluzione per ottenere un'altra soluzione che può essere migliore o peggiore della precedente.
Esempio di algoritmo genetico. Per comprendere il funzionamento di un algoritmo genetico è opportuno ricorrere a un esempio pratico. Ipotizziamo di avere quattro elementi ( generazione 1 ) ognuno dei quali è una stringa composta da tre cifre da zero a nove. L'obiettivo dell'algoritmo consiste nel raggiungere un super-elemento ( 9|9|9 ). Nel nostro esempio gli elementi della prima generazione della popolazione sono i seguenti:
L'algoritmo genetico calcola per ogni elemento la probabilità di riproduzione mediante la funzione di fitness. Ad esempio, il primo elemento 3|2|9 ha un valore di fitness pari a 14 determinato dalla somma delle singole cifre 3+2+9 che lo compongono. La probabilità di riproduzione dell'elemento è data dal rapporto tra il suo valore di fitness (14) e il totale dei valori di fitness (48). In base alle probabilità di riproduzione l'algoritmo seleziona casualmente due coppie A e B ( selezione casuale ). È interessante evidenziare come l'algoritmo abbia selezionato due volte l'elemento 2|9|5, sia nella formazione della coppia A che nella formazione della coppia B, in quanto l'elemento ha una elevata probabilità di riproduzione (33%). Viceversa, l'elemento 1|1|1 non viene selezionato in nessuna delle due coppie in conseguenza della sua scarsa probabilità di riproduzione (6%). La selezione naturale ha premiato gli elementi più forti (2|9|5) e ha penalizzato quelli più deboli (1|1|1). Una volta formate le coppie è necessario calcolare la nascita dei nuovi elementi successori, i quali combinano in modo diverso le cifre degli elementi genitori sulla base di un punto di cross-over casuale. Nell'algoritmo genetico il cross-over consente di spezzare la stringa di un elemento ( stringa ) in due distinte sottostringhe.
Le sottostringhe degli elementi-genitori sono combinate tra loro in modo tale da generare le due nuove stringhe degli elementi-figli. Ad esempio, nella coppia A il cross-over casuale è la prima cifra ( sottostringa ) dell'elemento. Dati i due elementi genitori 3|2|9 e 2|9|5, i relativi elementi figli ( nuova generazione ) sono determinati dalla combinazione della prima sottostringa del primo elemento genitore ( 3| e 2| ) con le restanti sottostringhe del secondo elemento genitore ( 2|9 e 9|5 ). Gli elementi figli della coppia A sono, pertanto, 3|9|5 e 2|2|9.
Lo stesso criterio di generazione viene utilizzato per determinare gli elementi successori della coppia B. A questo punto l'algoritmo inerisce delle mutazioni casuali ( +1 / -1 ) sulle singole cifre degli elementi che modificano parzialmente il patrimonio genetico della generazione 2. Una volta ottenuta la seconda generazione della popolazione possiamo eseguire il secondo ciclo di elaborazione dell'algoritmo genetico.
Nel secondo ciclo di esecuzione dell'algoritmo genetico gli elementi della seconda generazione hanno probabilità di riproduzione simili. Per questa ragione tutti gli elementi della seconda generazione sono selezionati nella composizione delle nuove coppie A e B. A partire dal nuovo punto di cross-over sono così generati i nuovi elementi figli della terza generazione. Il ciclo si conclude con l'inserimento casuale di un'altra mutazione casuale. Ottenuta la terza generazione della popolazione possiamo eseguire il terzo ciclo di elaborazione dell'algoritmo genetico.
Nella terza generazione soltanto alcuni elementi hanno una probabilità di riproduzione elevata. Per questa ragione l'elemento forte 9|9|3 partecipa alla formazione di entrambe le coppie A e B mentre l'elemento debole 1|1|9 viene del tutto escluso dalla selezione naturale. Questo consente di potenziare ulteriormente gli elementi figli della quarta generazione. Tra gli elementi della quarta generazione otteniamo anche un super-elemento 9|9|9. L'obiettivo dell'algoritmo genetico è stato raggiunto.
La dinamica dell'algoritmo genetico
Inefficienza. Nell'algoritmo genetico la selezione degli elementi è determinata in modo casuale ( selezione naturale ). Questo implica un notevole spreco di risorse nell'evoluzione. La semplice selezione naturale non consente all'algoritmo di imparare dall'esperienza e di migliorare l'euristica della ricerca. Altri criteri di selezione, diversi dalla semplice selezione casuale, potrebbero consentire la convergenza verso la soluzione in modo più rapido. Ad esempio, un miglioramento all'algoritmo genetico potrebbe consistere nell'eliminazione degli elementi troppo deboli, al di sotto di una determinata soglia, fin dalla fase di generazione (nascita).
Completezza. Va comunque considerato che una ricerca informata potrebbe spingere l'algoritmo genetico a concentrare la ricerca in un particolare sottoinsieme dello spazio di ricerca. L'euristica potrebbe influenzare eccessivamente la computazione e i risultati finali dell'elaborazione.
Viceversa, pur essendo meno efficiente l'esplorazione randomizzata consente di esplorare anche le ipotesi più remote dello spazio di ricerca.
- Allele. Generalmente, negli algoritmi genetici le soluzioni sono rappresentate da stringe binarie. Ogni stringa è composta da una serie di bit, detti allele, che possono assumere il valore zero (0) o il valore uno (1).
- Perché si chiamano genetici. Gli algoritmi sono detti genetici in quanto si ispirano all'evoluzione biologica delle specie animali in natura. Le specie ( dati ) che si adattano meglio alle continue mutazione dell'ambiente, sono quelle che hanno maggiore probabilità di sopravvivenza ( migliori soluzioni ).
- Primi studi. Gli algoritmi genetici sono studiati negli anni '60-'70. Uno dei primi ricercatori a occuparsene è lo statunitense John Henry Holland, professore di informatica all''Università del Michigan ( USA ).
