Gli algoritmi genetici sono strumenti di intelligenza artificiale ispirati alla teoria dell‘evoluzione di Darwin: la selezione naturale, l‘adattamento e la teoria della sopravvivenza vengono utilizzati da questi strumenti per risolvere problemi di ottimizzazione computazionalmente difficili.

Introduzione

Tra la fine degli anni Cinquanta e l’inizio degli anni Sessanta dello scorso secolo, i ricercatori nel campo della computazione evolutiva cominciarono a interessarsi ai sistemi naturali nella convinzione che potessero costituire un modello per nuovi algoritmi di ottimizzazione. In questa ottica, i meccanismi dell’evoluzione naturale possono essere adatti per affrontare alcuni dei più pressanti problemi computazionali, ad esempio quelli riguardanti la ricerca della soluzione tra un numero enorme di alternative. Infatti, l’evoluzione biologica è assimilabile a un metodo di ricerca all’interno di un grandissimo numero di soluzioni, costituite dall’insieme di tutte le sequenze genetiche, i cui risultati, ossia le soluzioni desiderate, sono organismi altamente adattati, dotati di forte capacità di sopravvivenza e di riproduzione in un ambiente mutevole, che trasmetteranno poi alle generazioni future il loro materiale genetico.
In questo contesto, gli organismi possono essere quindi considerati come ottimi risolutori di problemi, poiche‘ sono in grado di sopravvivere nel loro ambiente sviluppando comportamenti e abilità che sono il risultato dell’evoluzione stessa.

Dalla genetica agli algoritmi genetici

Gli algoritmi genetici sono stati sviluppati basandosi sulle teorie evoluzionistiche di Darwin, presentate nel suo libro On the Origin of Species by Means of Natural Selection del 1859, e sono stati trattati per la prima volta da John Holland nel 1975.
Questo tipo di algoritmi si basa, infatti, sul principio darwiniano che gli elementi più adatti all’ambiente hanno maggiore possibilità di sopravvivere e di trasmettere le loro caratteristiche ai successori; in pratica, vi è una popolazione di individui che evolvono di generazione in generazione attraverso meccanismi simili alla riproduzione sessuale e alla mutazione dei geni. In tal modo, si avrà una ricerca euristica che privilegia le zone dello spazio di ricerca dove è maggiormente possibile trovare soluzioni migliori, non trascurando altre zone a più bassa probabilità di successo in cui saranno impiegate comunque un numero minore di risorse.
Questo tipo di algoritmi trae perciò spunto dai concetti introdotti nella genetica classica e delle popolazioni, adottando le stesse terminologie a contesti differenti. Risulta, quindi, necessario definire come la terminologia utilizzata in campo genetico possa essere ricondotta alla trattazione degli algoritmi genetici.

Terminologia genetica: evoluzione naturale

L’evoluzione naturale è la teoria di base su cui si fonda il pensiero di Darwin; egli sostiene infatti che l’evoluzione della specie può avvenire attraverso le seguenti modalità di azione.
L’evoluzione naturale agisce sul materiale genetico, ossia il genotipo, di un individuo e non sulle sue caratteristiche fisiche, il fenotipo: ogni variazione che promuove l’adattamento di un individuo emerge dal patrimonio genetico, non da ciò che i genitori avranno eventualmente appreso durante la loro vita.
La selezione naturale favorisce la riproduzione degli individui che migliorano l’adattabilità all’ambiente mutevole ed elimina gli individui dalla minore potenzialità riproduttiva. Dal punto di vista genetico, la selezione naturale promuove quelle particolari combinazioni genetiche che danno vita a un organismo più efficiente, selezionando il genotipo, non il fenotipo.
La riproduzione è il nucleo centrale del processo evolutivo: la variabilità generazionale di una specie è determinata dalla ricombinazione genica e dalle piccole mutazioni casuali del codice genetico. La riproduzione determina la ricombinazione del materiale genetico dei genitori, generando un’evoluzione molto più rapida di quella che si otterrebbe se tutti i discendenti contenessero semplicemente una copia dei geni di un genitore, modificata casualmente da una mutazione. Si tratta di un processo ad alto grado di parallelismo: non opera su una specie per volta, ma mette alla prova e cambia milioni di specie in parallelo.
L’evoluzione naturale opera su intere popolazioni attraverso processi ciclici e generazionali determinati esclusivamente dalle contingenze ambientali e dalle interazioni fra i vari organismi.

La combinazione delle ipotesi darwiniane con la genetica ha dato luogo a principi che costituiscono le basi della genetica delle popolazioni, ossia la spiegazione dell’evoluzione a livello genetico delle popolazioni.
Una popolazione è definita come un gruppo di individui della stessa specie, che operano e si incrociano nello stesso luogo.
In biologia, i cromosomi sono i filamenti di DNA che fungono da progetto per l’organismo: ognuno di essi è composto da geni, che, attraverso la codifica di una particolare proteina, determinano le caratteristiche specifiche dell’organismo, come ad esempio il colore degli occhi. Le posizioni dei geni all’interno del cromosoma sono dette locus e le diverse configurazioni delle proteine sono dette alleli. La maggior parte degli organismi presentano più di un cromosoma, il cui insieme è detto genoma. Per genotipo si intende l’insieme dei geni del genoma. Il risultato finale dell’evoluzione fetale, cioè l’individuo, è detto fenotipo.
La riproduzione sessuale consiste nella ricombinazione del materiale genetico dei genitori, che dà luogo a un nuovo patrimonio completo per i discendenti; possono verificarsi comunque le mutazioni su singole parti del DNA.
La fitness è l’idoneità dell’individuo, ossia la probabilità che esso viva abbastanza da riprodursi. La selezione naturale promuove come genitori per la generazione successiva gli individui che hanno i fenotipi più adatti, codificati da particolari genotipi. Essa può essere:

• direzionale, nel caso favorisca l’aumento di frequenza di una forma estrema di un carattere;
• stabilizzante, se favorisce gli individui portatori di una forma intermedia di un certo carattere;
• divergente se sono favorite le forme estreme di un carattere a scapito di quelle intermedie.

L’evoluzione si basa quindi sui seguenti meccanismi:

• mutazione di alleli: fonte primaria di variabilità genetica;
• flusso genico: variazione delle frequenze degli alleli, dovuta ai movimenti migratori di alcuni individui, con conseguente introduzione o rimozione di determinati genotipi;
• deriva genetica: variazioni imprevedibili nelle frequenza degli alleli nel caso in cui una popolazione abbia un piccolo numero di componenti.

Questi concetti possono essere applicati nell’ambito degli algoritmi genetici, generando quella che viene chiamata “Evoluzione Artificiale”.

Terminologia degli algoritmi genetici: evoluzione artificiale

Nella terminologia degli Algoritmi Genetici, il cromosoma codifica una soluzione candidata di un dato problema di ricerca, attraverso la definizione di una stringa di bit, in cui i geni sono i bit della stringa e gli alleli, come proprietà dei geni, possono essere 1 o 0. L’incrocio, o crossover, è la ricombinazione del materiale genetico di due genitori composti da un singolo cromosoma e la mutazione nella variazione casuale del valore degli alleli in ogni locus del cromosoma. Il fenotipo è il significato del cromosoma, cioè la decodifica della soluzione candidata del problema.
Nelle applicazioni comuni si utilizzano individui a singolo cromosoma, quindi i termini genotipo, cromosoma e individuo sono equivalenti. Nei casi in cui la codifica del cromosoma rappresenti direttamente una soluzione candidata, come in alcune applicazioni in cui il cromosoma è una stringa di numeri reali anziche‘ di bit, possono coincidere anche i termini genotipo e fenotipo.

Principi di funzionamento

Il funzionamento di un algoritmo genetico è similare al processo evolutivo teorizzato da Darwin. Infatti, un algoritmo genetico parte da un certo numero di possibili soluzioni, dette popolazione, ognuna delle quali rappresenta un individuo, e provvede a farle evolvere nel corso dell’esecuzione: a ciascuna iterazione, esso opera una selezione di individui della popolazione corrente, impiegandoli per generare nuovi elementi della popolazione stessa, che andranno a sostituire un pari numero d’individui già presenti, e a costituire in tal modo una nuova popolazione per l’iterazione, o generazione, seguente. Tale successione di generazioni evolve verso una soluzione ottima del problema assegnato.
L’evoluzione viene ottenuta attraverso una parziale ricombinazione delle soluzioni, quindi ogni individuo trasmette parte del suo patrimonio genetico ai propri discendenti.
Finita la fase di evoluzione, la popolazione delle soluzioni viene analizzata e vengono tenute solo le soluzioni che meglio risolvono il problema: gli individui con le qualità più adatte all’ambiente in cui si trovano hanno quindi maggiori possibilità di sopravvivere e riprodursi. Queste soluzioni subiranno una nuova fase di evoluzione e così via, fino a generare una popolazione  di soluzioni che riescano a risolvere adeguatamente il problema posto.

Non vi è modo di decidere a priori se l’algoritmo sarà effettivamente in grado di trovare una soluzione accettabile; di norma gli algoritmi genetici vengono utilizzati per problemi di ottimizzazione per i quali non si conoscono algoritmi di complessità lineare o polinomiale.

Performance degli Algortmi Genetici

In breve, un algoritmo genetico è un algoritmo iterativo che opera su una popolazione di individui che codificano le possibili soluzioni di un dato problema. Gli individui sono valutati tramite una funzione che misura la loro capacità di risolvere il problema e identifica i più adatti alla riproduzione. La nuova popolazione si evolve in base a operatori random, ispirati alla riproduzione sessuale e alla mutazione. Il ciclo completo è ripetuto fino al raggiungimento di un dato criterio di fermata. L’utilizzo di questi algoritmi è essenzialmente legato alla programmazione dell’intelligenza artificiale in robotica, alla biocomputazione, allo studio dell’evoluzione dei sistemi cellulari paralleli, a particolari problemi di gestione e sistemi di ottimizzazione in ingegneria.
Gli algoritmi genetici hanno quindi i seguenti  punti di forza:

• possibilità di risolvere problemi complessi senza conoscere il preciso metodo di soluzione;
• capacità di auto-modificazione in base al mutamento del problema, risultando quindi adattivi;
• capacità di simulare alcuni fenomeni, data una struttura e una modalità operative isomorfe con quelle dell’evoluzione biologica.

I primi tentativi di progettazione di strumenti di ottimizzazione, le Strategie Evolutive di Rechemberg e la Programmazione Evolutiva di Fogel, Owens e Walsh, non produssero risultati interessanti, poiche‘ i test di biologia dei primi anni Sessanta mettevano in risalto l’operatore della mutazione, piuttosto che il processo riproduttivo per la generazione di nuovi geni. A metà degli anni Sessanta, un progresso significativo fu segnato proprio dalla proposta di John Holland, i cui Algoritmi Genetici sottolinearono per la prima volta l’importanza della riproduzione sessuale.
In alcune applicazioni, questi algoritmi trovano buone soluzioni in tempi ragionevoli, in altre possono impiegare giorni, mesi o anche anni per trovare una soluzione accettabile; ma poiche‘ essi lavorano con popolazioni di soluzioni indipendenti, è possibile distribuire il carico computazionale su più calcolatori, che produrranno simultaneamente diverse ipotesi con la conseguente riduzione dei tempi di calcolo.

Exploration ed Exploitation

Un qualsiasi algoritmo di ottimizzazione efficiente, deve usare due tecniche per trovare il massimo globale:

• Esploration (esplorazione): per esaminare nuove e sconosciute aree dello spazio di ricerca;
• Exploitation (sfruttamento): per usare i punti precedentemente visitati al fine di trovare punti migliori.

Queste richieste sono contraddittorie, e un buon algoritmo di ricerca deve trovare un buon compromesso tra le due. Una ricerca puramente casuale è buona per l’esplorazione, ma non fa nessuno sfruttamento, mentre un metodo puramente di scalata, come l’hillclimb, è buono per lo sfruttamento, ma fa poca esplorazione. La combinazione di queste due tecniche può essere abbastanza efficace, ma è difficile sapere dove si trova l’equilibrio migliore, ossia quanto sia necessario sfruttare prima di arrendersi ed esplorare oltre. Holland ha dimostrato che un algoritmo genetico combina insieme esplorazione e sfruttamento allo stesso tempo e in un modo ottimale.
Comunque, sebbene questo sia teoricamente vero, in pratica ci sono problemi inevitabili. Holland infatti ha fatto alcune semplificazioni:

1. la popolazione è infinita;
2. la funzione fitness riflette accuratamente l’utilità della soluzione;
3. i geni in un cromosoma non interagiscono significativamente.

La (1) non può essere mai verificata in pratica e a causa di ciò il funzionamento dell’algoritmo sarà soggetto a errori stocastici. Un problema del genere, che si trova anche in natura, è quello dello deriva genetica, enunciata sopra. Anche in assenza di qualsiasi pressione di selezione, cioè quando la funzione fitness è costante, membri della popolazione continueranno a convergere verso qualche punto nello spazio di ricerca. Questo succede semplicemente a causa dell’accumulo di errori stocastici: se un gene diventa predominante nella popolazione, allora ha la stessa probabilità sia di diventare più dominante nella generazione successiva, che meno dominante; se avviene un aumento della predominanza in alcune generazioni successive, e la popolazione è finita, allora un gene si può propagare a tutti i membri della popolazione. Una volta che un gene converge in questa maniera, il crossover non può introdurre nuovi valori di geni. Ciò produce un effetto a catena, in modo tale che, con il procedere delle generazioni, ogni gene diventa eventualmente fissato. Il tasso di deriva genetica produce allora un limite inferiore alla velocità con la quale un un algoritmo genetico può convergere verso la soluzione corretta. Così, se l’algoritmo sta sfruttando l’informazione del gradiente nella funzione fitness, la funzione fitness fornisce un’inclinazione sufficientemente grande per contrastare ogni deriva genetica. Il tasso di genetic drift, può essere anche ridotto introducendo la mutazione. Comunque, se la mutazione è troppo elevata, le informazioni del gradiente non possono essere sfruttate adeguatamente.
Le condizioni (2) e (3) possono essere verificate su funzioni test che si comportano bene in laboratorio, ma sono difficili da soddisfare nel mondo reale. I problemi con la funzione fitness e l’epistasis saranno discussi successivamente.

Conclusioni

Con un parallelismo tra il mondo delle scienze naturali e quello del calcolo computazionale, abbiamo introdotto il concetto di Algoritmo Genetico. Nel prossimo articolo si affronteranno più nel dettaglio le basi teoriche si cui si fondano questi strumenti, per poi procedere, nelle puntate successive, all’analisi dei vari algoritmi e delle loro applicazioni.

Riferimenti

[1]    Holland J., “Adaptation in Natural and Artificial Systems”, University of Michigan Press, 1976

[2]    Man K.F, “Genetic Algorithms”, Springer-Verlag London Limited, 1999