Introduzione agli algoritmi genetici
Lidea di applicare i principi dellevoluzionismo
naturale a sistemi artificiali nacque più di tre decenni fa ed
ha avuto un grande consenso ed un grande sviluppo di recente.
Oggi il loro impiego è assai frequente in diversi campi, dallottimizzazione
di sistemi allapprendimento automatico, dallo studio dei
sistemi sociali ed economici a quelli biologici (Cfr. [Mit96]).
Lidea di base è quella codificare la soluzione di un
problema sotto forma di una stringa di simboli detta genoma
(genome) e di utilizzare un popolazione di dimensione
costante di individui, ciascuno dei quali rappresentato da una
stringa diversa (quindi una diversa possibile soluzione per il
problema), e fare evolvere questa popolazione secondo i
meccanismi dellevoluzione biologica, al fine di ottenere la
migliore soluzione al problema.
Lo spazio di tutte le possibili soluzioni del problema dato è
detto spazio delle soluzioni (search space).
In genere gli algoritmi genetici sono applicati a problemi in cui
lo spazio delle soluzioni è troppo ampio per essere esplorato
per intero.
Linsieme dei simboli utilizzati per codificare il genoma può
essere un semplice codice binario (come in [Hol75]) o, come
proposto più recentemente un intero codice alfanumerico o
composto da numeri reali.
Un algoritmo genetico standard procede nel seguente modo: una
popolazione di individui viene generata in modo casuale o in base
a informazioni note. Ad ogni passo evolutivo, detto generazione
(generation), tutti gli individui vengono decodificati e
valutati secondo una particolare funzione dipendente dal problema
in esame detta funzione di fitness che
attribuisce a ciascuno di essi un valore detto appunto fitness
che da una misura di come lindividuo si avvicina alla
soluzione del problema.
La fase successiva consiste nella selezione
degli individui che dovranno formare la nuova generazione. La
selezione di un individuo dipende dal suo valore di fitness (cioè
quanto lindividuo è buono a risolvere il
problema): un valore più alto di fitness corrisponde ad una
maggiore possibilità di essere scelto come genitore
(parent) per creare la nuova generazione. Uno dei
criteri più utilizzati è quello di Holland (in [Hol75]) che
attribuisce una probabilità di scelta proporzionale al fitness.
Grazie al meccanismo della selezione, solo gli individui migliori
hanno la possibilità di riprodursi e quindi di trasmettere il
loro genoma alle generazioni successive.
Per la creazione di nuovi individui ad ogni generazione si
utilizzano due operazioni ispirate dallevoluzionismo
biologico: il crossover e la mutazione.
Una volta individuati una coppia di genitori con il meccanismo
della selezione, i loro genomi possono andare incontro a ciascuna
delle due operazioni con probabilità rispettivamente Pcross
(probabilità di crossover per coppia di individui, detta crossover
rate) e Pmut (probabilità di mutazione per gene,
detta mutation rate).
Se due genitori vanno incontro a crossover, il loro genoma viene
scambiato da un certo punto in poi (stabilito casualmente),
altrimenti rimangono inalterati. A questo punto, ogni simbolo del
loro genoma può andare incontro a mutazione con la probabilità
stabilita. Se un simbolo muta, esso viene semplicemente cambiato
in un altro scelto a caso.
I due individui che si ottengono così rappresentano i discendenti
(offspring) dei due genitori, e prenderanno il loro
posto nella prossima generazione. Se due genitori non vanno
incontro ne a crossover ne a mutazione, i discendenti saranno
identici ai genitori. Si ripete il processo fino ad ottenere un
numero di discendenti uguale a quello dei genitori.
Ottenuta la nuova generazione, si ripete il processo un numero
opportuno di volte, ottenendo di volta in volta una popolazione
che mediamente ha un valore di fitness elevato, al limite ottimo.
Il genoma degli individui così ottenuti codifica la soluzione
del problema cercata.
Tuttavia, bisogna tenere presente che essendo un processo
essenzialmente stocastico, non è garantita ne la convergenza, ne
il raggiungimento della soluzione ottima. Spesso infatti la
popolazione si stabilizza su ottimi locali che
possono differire da quello assoluto.
La figura seguente mostra un esempio tratto da [Mit96], in cui lobbiettivo
è ottenere un genoma composto solo da uni. Il genoma è
codificato con un codice binario (nella figura rosso=1, verde=0),
e la funzione di fitness è data dal numero di uni contenuti in
ogni individuo. Si nota che dopo solo due generazioni quasi tutta
la popolazione ha raggiunto lobbiettivo prefissato.
Un programma che implementa un algoritmo genetico è schematizzabile con il seguente pseudocodice:
inizializza la vecchia_popolazione (assegnando un genoma casuale a ciascun individuo) ripeti per il numero di generazioni voluto inizializza nuova_popolazione (nessun individuo) calcola il valore di fitness di ciascun individuo ripeti (numero individui)/2 volte seleziona casualmente due individui se rnd < Pcross applica crossover se rnd < Pmut applica mutazione aggiungi i due individui a nuova_popolazione fine ripetizione popolazione copia nuova_generazione in vecchia_generazione fine ripetizione generazioni
Non esistono dei risultati teorici certi riguardo
al numero ottimale della popolazione per un determinato problema,
così come non è chiaro quale sia il metodo migliore per
scegliere il valore delle probabilità di crossover e mutazione.
In genere si procede per via empirica a seconda delle
caratteristiche del particolare problema. Alcuni valori tipici
sono:
- popolazione: da 100 a 10000 (dipende molto dal problema);
- Pcross: circa 0.8;
- Pmut: attorno a 0.01.
Bibliografia essenziale:
[Hol75] J. H. Holland. Adaptation in Natural
and Artificial Systems. The University of Michigan Press,
1975
[Mit96] M. Mitchell. An Introduction to
Genetic Algorithms. MIT Press, 1996.