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, or the Preservation of Favoured Races in the Struggle for Life del 1859, e sono stati trattati per la prima volta da John Holland nel 1975.
Questo tipo di algoritmi si basa 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.
Si avrà così 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.
Con algoritmo genetico si intende quindi una classe di algoritmi che trae spunto dai concetti introdotti nella genetica classica, adottando le stesse terminologie a contesti differenti. É necessario perciò definire come tale terminologia possa essere ricondotta alla trattazione degli algoritmi genetici.
Di questo ha parlato Marco durante il suo intervento all’open conference dell’Intré Camp di Ottobre 2019, concludendo con una dimostrazione pratica di utilizzo di un algoritmo genetico per indovinare il contenuto di una stringa di dieci caratteri.
Da algoritmi classici ad algoritmi genetici
Ogni sviluppatore normalmente è abituato a risolvere problemi.
Le tecniche tradizionali di implementazione vanno bene per:
- elaborare di moli di dati;
- gestire casi ben definiti: si analizza il problema, lo si identifica e si adotta una soluzione nota;
- ripetere deterministicamente delle operazioni.
Ma come ci comportiamo quando si devono riconoscere dei pattern (comportamentali ad esempio) o dobbiamo lavorare con informazioni incomplete? Oppure quando si ha la necessità di sviluppare soluzioni che devono evolvere nel tempo?
Prendiamo spunto dalla natura
Gli organismi si sono nella storia evoluti, sopravvive chi meglio si adatta. Il sociologo inglese Herbert Spencer coniò l’espressione
Survival of the fittest
ovvero Sopravvivenza del più idoneo, che venne usata per descrivere il modello di selezione naturale descritto da Darwin.
Tornando all’espressione di Spencer, fit significa idoneo e fittest il più idoneo. Da fit si deriva la parola fitness che in ambito genetico definisce il successo riproduttivo di un individuo o di un certo genotipo. Con il termine genotipo ci si riferisce all’insieme di tutti i geni che compongono il DNA di un organismo o di una popolazione.
Quando due o più assortimenti di caratteri ereditari conferiscono ai rispettivi organismi un diverso successo riproduttivo, allora si dice che presentano una fitness diversa.
La fitness si misura per mezzo del successo riproduttivo, ovvero dal numero medio dei figli in grado, a loro volta, di riprodursi.
Algoritmi genetici
Nel 1975 Holland propose per la prima volta gli algoritmi genetici che implementano tecniche di ricerca e ottimizzazione basate sul principio di selezione naturale.
Sono algoritmi particolarmente adatti a trovare nuove soluzioni per problemi difficili dove non si ha conoscenza completa dello spazio di ricerca. Partendo da una soluzione iniziale, la si modifica, combina con altre soluzioni per cercare di evolverla e quindi trovare un risultato migliore per il problema.
I dati vengono rappresentati mediante una codifica biologica, quindi si parla di geni -> cromosomi -> genotipo -> fenotipo e fitness. Per fenotipo si intende l’insieme di caratteristiche osservabili di un organismo o popolazione.
Differenze tra algoritmi genetici e algoritmi classici
Rispetto agli algoritmi classici, gli algoritmi genetici:
- lavorano con una codifica dei dati, non con i dati stessi;
- si basano su una popolazione di soluzioni tra le quali effettuare una ricerca, e non su un’ unica soluzione;
- trasportano informazioni nel tempo quando vengono applicati degli operatori; nuove informazioni possono essere generate oppure perse;
- utilizzano regole probabilistiche, non deterministiche.
Nel paragrafo successivo vengono introdotti gli elementi base di un algoritmo genetico e le fasi che lo compongono.
Elementi e fasi di un algoritmo genetico
Inizializzazione della popolazione
Si inizia con una popolazione di individui generati casualmente, oppure con:
- una popolazione generata in precedenza (e salvata);
- un insieme di soluzioni fornita da un esperto;
- diverse soluzioni fornite da un altro metodo/algoritmo euristico.
La codifica ideale è di tipo lineare, magari un array con la rappresentazione degli elementi costitutivi della soluzione (individualmente o per combinazione). Ricordando l’esercizio proposto per la demo finale, ovvero individuare il contenuto di una stringa di dieci elementi, Marco suggerisce una stringa binaria.
Fitness e selezione
La bontà, o fitness, di ogni individuo della popolazione deve essere misurata in modo da capire quali siano le migliori soluzioni scoperte fino a un determinato momento.
Riprendendo quanto scritto in precedenza, la fitness misura il grado di avvicinamento a un determinato obiettivo.
Per la soluzione ottimale la fitness può essere nota (è desiderata ma non si sa come arrivarci) oppure no (ottimizzazione).
Dopo aver valutato la fitness di tutte le soluzioni, si cerca di combinarle per ottenere nuove soluzioni migliori delle precedenti.
Si deve quindi esplorare lo spazio delle soluzioni al fine di trovare quelle più promettenti, ma non è detto che esista un percorso lineare ottimale: da due genitori può nascere una soluzione migliore o peggiore.
La selezione è la promozione a genitori solo (o soprattutto) delle soluzioni più promettenti; le peggiori possono essere scartate, dato che non si riproducono.
Ricombinazione (crossover)
Ogni figlio eredita caratteristiche da entrambi i genitori. Con quali proporzioni?
Riprendendo l’esempio della demo finale, Marco ipotizza che ogni nuova stringa potrebbe essere così generata:
- si potrebbe prendere la prima parte da un genitore e la seconda dall’altro (con lunghezza fissa o variabile);
- prendere porzioni da un genitore o dall’altro in maniera casuale;
- tramite dei singoli geni presi casualmente dall’uno o dall’altro genitore.
Qualche gene potrebbe subire delle variazioni casuali, o mutazioni. Magari con encoding binario, ovvero cambi di 0 in 1, o con encoding in altra base.
Una mutazione porta inevitabilmente a uno spostamento nello spazio delle soluzioni, generando nuove informazioni, e anche un recupero di informazioni che nel tempo si sono perse nella popolazione.
Terminazione
Un algoritmo genetico raggiunge questa fase per diverse ragioni:
- una soluzione raggiunge un criterio di accettazione minimo;
- viene raggiunto un numero prefissato di generazioni o individui;
- si esaurisce il budget allocato (in termini di tempo e costo); la ricerca di soluzioni può richiedere tempo e la loro esecuzione può necessitare di macchine con elevata capacità computazionale;
- semplicemente si decide di interrompere l’attività di ricombinazione per il miglioramento delle soluzioni.
Vantaggi e svantaggi degli algoritmi genetici
Pensare di adottare questa categoria di algoritmi porta a diversi vantaggi:
- tecnica di ricerca veloce: vengono prodotti risultati vicini all’ottimo in tempi ragionevoli;
- sono adatti alla parallelizzazione dell’elaborazione;
- sono semplici da sviluppare;
- non richiedono analisi approfondite o assunzioni sullo spazio delle soluzioni.
Ci sono comunque degli svantaggi:
- i risultati sono poco predicibili;
- l’esecuzione richiede molti cicli di calcolo;
- questi tipi di algoritmi Non sono completamente generalizzabili.
Riferimenti
- On the Origin of Species di Charles Darwin.
- Survival of the fittest di Herbert Spencer.
- Definizione di fitness in biologia.
- John Henry Holland.