Gli algoritmi genetici spiegati

L'evoluzione ha prodotto occhi, ali e cervelli senza un progettista, semplicemente conservando ciò che funziona e variandolo. Un algoritmo genetico prende in prestito questa idea per risolvere problemi al computer. Non ha bisogno di capire il problema, ma solo di distinguere una risposta migliore da una peggiore, il che lo rende uno strumento potente quando lo spazio delle risposte possibili è troppo grande e troppo strano per essere esplorato in altro modo.

Razzi che volano dal fondo di un campo aggirando un muro verso un bersaglio verde, con il volo migliore tracciato come linea tratteggiata
Razzi che volano dal fondo di un campo aggirando un muro verso un bersaglio verde, con il volo migliore tracciato come linea tratteggiata

L'idea

Negli anni Sessanta e Settanta John Holland, all'Università del Michigan, trasformò la teoria di Darwin in un algoritmo, descritto nel suo libro «Adaptation in Natural and Artificial Systems» del 1975. Più o meno nello stesso periodo Ingo Rechenberg e Hans-Paul Schwefel svilupparono in Germania le strategie evolutive per la progettazione ingegneristica. La ricetta comune: mantenere una popolazione di soluzioni candidate, assegnare loro un punteggio, lasciare che le migliori si riproducano con variazioni e ripetere per molte generazioni.

John Holland, che descrisse gli algoritmi genetici nel suo libro Adaptation in Natural and Artificial Systems del 1975.
John Holland, che descrisse gli algoritmi genetici nel suo libro Adaptation in Natural and Artificial Systems del 1975.

I geni e la popolazione

Ogni candidato è descritto da un cromosoma, un elenco di geni. Nel laboratorio i geni di un razzo sono le sue spinte, una per ogni istante del suo volo; in altri problemi potrebbero essere i bit di un numero, l'ordine delle città su un percorso o le dimensioni dei pezzi di un progetto. La prima generazione è casuale: esplora ampiamente lo spazio delle risposte, ma non ne contiene quasi nessuna buona.

La funzione di fitness

La fitness è l'unico numero che dice quanto è buono un candidato, ed è l'unica cosa che l'algoritmo sa del problema. Per i razzi premia soprattutto l'arrivo rapido, poi il fatto di finire vicino al bersaglio, e penalizza gli schianti. Una funzione di fitness ben scelta guida la ricerca con dolcezza verso buone risposte; una scelta con leggerezza premia la cosa sbagliata, e l'algoritmo sfrutterà ogni scappatoia che lascia aperta.

La selezione

I genitori vengono scelti in modo che i candidati più adatti abbiano più figli, ma anche quelli più deboli abbiano una possibilità, perché i loro geni possono contenere pezzi utili. La selezione a roulette assegna a ogni candidato una fetta di ruota proporzionale alla sua fitness; la selezione a torneo ne estrae alcuni a caso e prende il migliore. Una selezione più forte accelera i progressi, ma rende anche la popolazione più omogenea, il che può far terminare la ricerca troppo presto.

Crossover e mutazione

Il crossover combina due genitori: qui un figlio prende la prima parte dei suoi geni da un genitore e il resto dall'altro, così le manovre iniziali di un razzo possono incontrare quelle finali di un altro. La mutazione sostituisce alcuni geni a caso. Il crossover ricombina ciò che la popolazione ha già; la mutazione introduce ciò che non ha mai avuto. Il teorema degli schemi di Holland descrive come brevi blocchi costitutivi di geni buoni si diffondano nella popolazione grazie a questa miscela di selezione e ricombinazione.

Elitismo, esplorazione e sfruttamento

Copiare senza modifiche i pochi candidati migliori nella generazione successiva, cioè l'elitismo, garantisce che la risposta migliore non vada mai persa. Ogni algoritmo genetico deve bilanciare l'esplorazione, cioè provare nuove regioni dello spazio di ricerca, con lo sfruttamento, cioè perfezionare ciò che è già buono. Troppa poca variazione e la popolazione converge su un'unica risposta mediocre; troppa e non si stabilizza mai. Dimensione della popolazione, tasso di mutazione e pressione selettiva sono le manopole che regolano questo equilibrio.

Ottimi locali

Un algoritmo genetico segue solo la fitness, quindi può essere ingannato. Quando la strada verso la risposta migliore passa prima per risposte peggiori, la popolazione scala la collina più vicina e ci resta: un ottimo locale. Dietro i muri sfalsati del laboratorio, i razzi che si schiantano sotto il bersaglio ottengono un punteggio migliore di quelli che si allontanano per trovare il varco, così la popolazione si ammassa contro il muro. Tra i rimedi ci sono popolazioni più grandi, una mutazione più alta, il mantenimento della diversità nella popolazione e soprattutto una funzione di fitness migliore.

Esploralo

Apri il laboratorio di algoritmi genetici per far evolvere razzi attorno a un muro, un varco, dei pilastri, dei muri sfalsati o muri disegnati da te. Cambia la popolazione, il tasso di mutazione, la durata di vita e il metodo di selezione, attiva e disattiva l'elitismo e segui nel grafico quanto velocemente cresce la quota di razzi che raggiungono il bersaglio, o perché non cresce.

Domande frequenti

Un algoritmo genetico è una forma di intelligenza artificiale?

Appartiene al campo più ampio dell'IA e dell'apprendimento automatico, come metodo di ricerca e ottimizzazione. Non impara dagli esempi come una rete neurale; migliora le soluzioni candidate per tentativi e selezione. I due approcci vengono spesso combinati, per esempio facendo evolvere la struttura o i pesi di reti neurali, un approccio chiamato neuroevoluzione.

Un algoritmo genetico trova sempre la risposta migliore?

No. È un'euristica: di solito trova buone risposte a problemi difficili, ma non garantisce la migliore né dimostra quanto vi si avvicini. Per i problemi in cui un metodo esatto è abbastanza veloce, quel metodo è preferibile.

Qual è la differenza tra un algoritmo genetico e le strategie evolutive?

Entrambi sono algoritmi evolutivi. Gli algoritmi genetici classici puntano sul crossover di cromosomi simili a stringhe; le strategie evolutive lavorano soprattutto con la mutazione di numeri reali e spesso adattano da sole l'ampiezza delle proprie mutazioni strada facendo. I metodi moderni mescolano idee di entrambi.

Perché all'inizio i razzi sono così goffi?

I loro primi geni sono spinte del tutto casuali, che in media si annullano, quindi i razzi vanno alla deriva. Solo dopo che la selezione ha conservato i rari razzi che per caso spingevano più o meno nella direzione giusta, e il crossover ha combinato i loro tratti buoni, compaiono voli coordinati.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri il laboratorio di algoritmi genetici