Algoritmi Genetici

Da quando esiste l'uomo si cerca di osservare la natura per carpirne i segreti e per trarre da essi vantaggi.

Gli algoritmi genetici prendono il loro nome dall'osservazione della genetica e dai meccanismi che hanno permesso l'evoluzione degli esseri viventi.

La colpa è tutta di Darwin e della sua teoria secondo la quale l'attuale evoluzione è dovuta a precise regole naturali:

• Gli esseri viventi nascono, crescono e si evolvono in uno specifico ambiente
• Gli esseri viventi che meglio si adattano all'ambiente avranno maggiori possibilità di accoppiarsi
• Quando due esseri viventi si accoppiano danno origine ad un nuovo organismo che ha come DNA le composizione del DNA dei genitori
• il ciclo riprende il suo corso e la generazione successiva sarà un'evoluzione meglio adattata all'ambiente rispetto alla precedente

Cosa può servire tutto ciò in informatica? Semplice: per ottenere soluzioni in problemi apparentemente irrisolvibili grazie all'evoluzione dei dati! Ovviamente in modo più rapido rispetto a quanto avviene in natura...

 In pratica

Solitamente si gli algoritmi genetici vengono usati per lo studio di funzioni matematiche complesse, ma penso che solo i matematici possano in questo modo apprezzarne la potenza.

Abbiamo tra le mani un gioco automobilistico e vogliamo costruire il rivale perfetto, quello che non sbaglia mai una curva e frena sempre alla perfezione.

Facciamo noi una serie di partite e registriamo la nostra corsa: tutti i tasti che premiamo sulla tastiera li salviamo sotto forma di uno stream di byte.

Questi stream saranno i nostri campioni di DNA.

Partire da uno stream vuoto sarebbe possibile, semplicemente i tempi per ottenere la corsa perfetta si allungherebbero.

A questo punto ci troviamo una serie di DNA e dobbiamo iniziare a farli evolvere.

Mutazioni genetiche

In natura sono mutazioni del DNA causate dall'ambiente circostante, dobbiamo applicarle anche noi perché garantiscono la possibilità ti tentare tutte le strade possibili: le strade migliori avranno maggiore possibilità di sopravvivere.

Per applicarle è sufficiente scegliere a caso alcuni byte da cambiare con valore anch'esso casuale.

Fitness

In natura l'ambiente sancisce il DNA migliore ovvero quello che si è adattato meglio all'ambiente. 

Noi dobbiamo calcolare il DNA migliore applicando una formula che restituisca un valore chiaro e preciso circa la qualità dell'adattamento all'ambiente. In pratica dobbiamo stillare una classifica.

Nel nostro esempio è semplice: l'automobilista più veloce sarà il meglio adattato, quindi noi dovremmo far gareggiare (ovviamente con una simulazione accelerata) ogni DNA mutato e valutarne i tempi.

L'accoppiamento

Ora la parte più divertente. dobbiamo far accoppiare i nostri piloti!

Come selezioniamo le coppie? con un'estrazione casuale ma in cui il DNA meglio adattato avrà più possibilità di essere estratto in modo proporzionale alla fitness ottenuta.

Quindi il pilota con un giro di pista da 2 minuti avrà il doppio di probabilità di accoppiarsi rispetto al pilota che ha totalizzato 4 minuti.

Io mi immagino questa lotteria come una sorta di roulette con spicchi tanto più grandi quanto più il DNA si è adattato.

Ogni coppia formerà un nuovo DNA prendendo metà DNA del padre e metà della madre dando origine ad un nuovo stream di byte.

dovremmo ottenere tanti nuovi individui quanti quelli della popolazione iniziale, altrimenti poco alla volta resteremo senza niente. Ok, per fare questo dobbiamo metterci l'anima in pace e considerare il fatto che l'accoppiamento non può avvenire con lo stesso partner.

Non facciamoci problemi di coscienza!

Il DNA peggiore, semplicemente si estinguerà

Evoluzione

Ad ogni ciclo vitale vedremo che il DNA risultante sarà sempre più vicino all'adattamento perfetto pur non arrivandoci mai.

Esattamente come in natura la nuova generazione sarà meglio adattata all'ambiente circostante, per il semplice fatto che i più deboli non si accoppieranno e si estingueranno.

Conclusione

Per quanto possa sembrarvi strano, tutto ciò funziona quasi a confermare la teoria di Darwin. 

In natura tutto è più complesso, l'ambiente muta, e con esso l'adattamento. Ma come in ogni scienza anche in questo caso lo scopo principale è comprenderne i meccanismi fondamentali per usarli a nostro vantaggio.

Attenzione:

Questo voleva essere solo un'introduzione agli algoritmi genetici quindi l'argomento è tutt'altro che concluso. Molti sono i metodi utilizzati per la selezione dei genitori, molti metodi per mutare il DNA, molti i metodi per gestire l'accoppiamento.

Essenziale per addentrarsi nell'argomento è comprenderne le colonne portanti.