L'informatica dell'evoluzione: un'introduzione agli algoritmi genetici

Foto di Hal Gatewood su Unsplash

Essendo uno scienziato informatico con un interesse per l'evoluzione e i processi biologici, il tema degli algoritmi genetici e, più in generale, il calcolo evolutivo è per me ciò che un negozio di caramelle è per un bambino di 5 anni: il Paradiso. La sola possibilità di poter unire due dei miei interessi in modo così semplice è stata estremamente esaltante e sarebbe sbagliato per me mantenere questa conoscenza ed eccitazione tutta per me.

Quindi, nel tentativo di testare alcuni dei miei apprendimenti finora e condividere le mie scoperte con il resto del mondo, ho deciso di mettere insieme una serie di articoli su questo argomento.

In questo post, fornirò una breve introduzione agli algoritmi genetici e spiegherò come imitano gli stessi processi naturali che hanno avuto luogo sulla Terra per miliardi di anni.

Vita sulla Terra

Negli ultimi 3,5 miliardi di anni, madre natura, tempo del padre, evoluzione e selezione naturale hanno collaborato per produrre tutte le forme di vita specializzate che vediamo oggi sulla terra: come la pianta carnivora di Venere acchiappamosche; l'Atlantico Flying Fish che dimora nell'oceano; pipistrelli che usano l'ecolocalizzazione; giraffe a collo lungo; ghepardi superveloci, api danzanti; e, naturalmente, il tuo, l'homo sapiens intelligente di strada.

Il Venus Flytrap è una pianta carnivora che si nutre principalmente di insetti e aracnidi.Alcuni pipistrelli usano l'ecolocalizzazione per navigare e cacciare le prede e contrariamente alla credenza popolare, i pipistrelli in realtà non sono ciechi; una specie di pipistrelli conosciuta come Le volpi volanti in realtà ha una vista migliore degli umani.I Pesci Volanti non possono volare allo stesso modo degli uccelli, tuttavia questi pesci possono fare salti potenti e semoventi fuori dall'acqua dove le loro lunghe pinne simili ad ali permettono loro di planare per distanze considerevoli sopra la superficie dell'acqua.

Inutile dire che la vita sulla Terra è uno degli esperimenti, se non di maggior successo, mai condotti nel nostro universo; e a giudicare dai risultati impressionanti di questo esperimento, è chiaro che l'evoluzione è chiaramente su qualcosa.

Di recente, noi umani - solo uno dei tanti prodotti finali di questo processo - ci siamo resi conto che potevamo anche trarre vantaggio da questo ingegnoso approccio alla risoluzione progressiva dei problemi e dagli anni '50, informatici, genetisti, matematici e biologi, hanno tentato di imitare questi processi biologici attraverso l'implementazione di simulazioni al computer. Con l'obiettivo di produrre soluzioni ottimali per problemi difficili, non banali, in modo efficiente.

L'orologiaio cieco

Uno dei primi libri che ho incontrato che ha suscitato il mio interesse nel campo della biologia evolutiva è stato The Blind Watchmaker, di Richard Dawkins. In questo libro, Richard Dawkins spiega come meccanismi complessi come l'ecolocalizzazione (un processo che i pipistrelli usano per navigare, caccia e foraggio, noto anche come bio-sonar), strutture complesse come ragnatele (che i ragni usano per attirare e catturare le loro prede), e strumenti complessi come l'occhio umano (quei due oggetti sferici che stai attualmente usando per leggere questo articolo) sono semplicemente il risultato di migliaia, se non di milioni di anni di evoluzione e adattamento.

La progressiva evoluzione dell'occhio umano. Ciò che è iniziato come semplici cellule fotosensibili, si è evoluto in uno strumento complesso che spesso diamo per scontato. I primi animali con qualcosa che somigliava a un occhio vivevano circa 550 milioni di anni fa. E, secondo i calcoli di uno scienziato, ci vorrebbero solo 364.000 anni perché un occhio simile a una macchina fotografica si evolva da un cerotto sensibile alla luce.

Anche se queste meraviglie della natura danno l'impressione di essere state costruite con uno scopo sin dall'inizio (cioè da un "creatore" consapevole), in realtà sono solo il risultato di iterazioni su iterazioni di tentativi ed errori, in bundle con sempre -modificare la pressione selettiva (ovvero un cambiamento nel clima, nell'habitat o nel comportamento e nelle capacità dei predatori o delle prede). Quindi, sebbene possano apparire e comportarsi come il risultato di un'ingegneria precisa e lungimirante, in realtà sono il risultato di un processo completamente cieco, un processo che non sa in anticipo quale sarebbe la "soluzione" perfetta.

Cosa sono gli algoritmi genetici e perché ne abbiamo bisogno?

Gli algoritmi genetici sono una tecnica utilizzata per generare soluzioni di alta qualità ai problemi di ottimizzazione e ricerca, che si basano su processi biologici fondamentali. Questi algoritmi sono usati in situazioni in cui la possibile gamma di soluzioni è molto ampia e dove gli approcci più basilari alla risoluzione dei problemi come la ricerca esaustiva / forza bruta consumerebbero troppo tempo e fatica.

Il problema del venditore ambulante pone la seguente domanda: "Dato un elenco di città e le distanze tra ogni coppia di città, qual è il percorso più breve possibile che visita ogni città e ritorna alla città di origine?" È un problema NP-difficile in ottimizzazione combinatoria.

Possiamo usare algoritmi genetici per fornire soluzioni di alta qualità a questo problema, a un costo molto più basso rispetto alle più primitive tecniche di risoluzione dei problemi, come la ricerca esaustiva, che richiederebbe di permutare attraverso tutte le possibili soluzioni.

Come funzionano gli algoritmi genetici?

Un algoritmo funziona ripetendo una serie di passaggi, fino a raggiungere un punto di terminazione predefinito. Ogni iterazione dell'algoritmo genetico produce una nuova generazione di possibili soluzioni, che, in teoria, dovrebbe essere un miglioramento rispetto alla generazione precedente.

I passi sono come segue:

1. Crea una popolazione iniziale di N possibili soluzioni (la zuppa primordiale)

Il primo passo dell'algoritmo è quello di creare un gruppo iniziale di soluzioni che fungono da soluzioni di base nella generazione 0. Ogni soluzione in questa popolazione iniziale porterà un insieme di cromosomi, che sono costituiti da una raccolta di geni, in cui ciascun gene è assegnato a una delle possibili variabili del problema. È importante che le soluzioni nella popolazione iniziale siano create con geni assegnati in modo casuale, al fine di avere un alto grado di variazione genetica.

2. Classificare le soluzioni della popolazione in base alla forma fisica (sopravvivenza del più adatto, parte 1).

In questo passaggio, l'algoritmo deve essere in grado di determinare ciò che rende una soluzione più "adatta" rispetto a un'altra soluzione. Questo è determinato dalla funzione fitness. Lo scopo della funzione fitness è valutare la fattibilità genetica delle soluzioni all'interno della popolazione, posizionando quelle con i tratti genetici più praticabili, favorevoli e superiori in cima alla lista.

Nel problema del commesso viaggiatore, la funzione di fitness potrebbe essere un calcolo della distanza totale percorsa dalla soluzione. Dove una distanza più breve equivale a una maggiore forma fisica.

3. Abbatti le soluzioni più deboli (sopravvivenza del più adatto, parte 2)

In questo passaggio, l'algoritmo rimuove le soluzioni meno adatte dalla popolazione. Il "più adatto" non significa necessariamente il più forte, il più veloce o il più feroce, come gli umani tendono generalmente ad assumere. Sopravvivere al più forte significa semplicemente che un organismo meglio equipaggiato deve sopravvivere nel suo ambiente, più è probabile che viva abbastanza a lungo da riprodursi e diffondere i suoi geni nella generazione successiva.

I passaggi 3 e 4 sono noti collettivamente come selezione.

4. Alleva le soluzioni più forti (sopravvivenza del più adatto, parte 3)

Le soluzioni rimanenti vengono quindi accoppiate tra loro al fine di accoppiare e riprodurre la prole. Durante questo processo, nella sua forma più elementare, ciascun genitore contribuirà con una% dei loro geni (in natura è una divisione del 50/50) a ciascuno dei loro discendenti, dove P1 (G)% + P2 (G)% = 100 %. Il processo per determinare quale dei geni dei genitori sarà ereditato dalla prole è noto come crossover.

5. Mutare i geni della prole (mutazione)

La prole conterrà una percentuale di geni "madre" e una percentuale di geni "padri" e, occasionalmente, ci sarà una "mutazione" di uno o più di questi geni. Una mutazione è essenzialmente un'anomalia genetica, un errore di copia che fa sì che uno o più geni della prole differiscano dai geni ereditati dai suoi genitori. Negli algoritmi genetici, in alcuni casi una mutazione aumenterà l'idoneità della prole, in altri casi la ridurrà.

È importante notare che non è necessario che vi sia una mutazione per ogni prole, la frequenza di mutazione richiesta può anche essere un parametro dell'algoritmo.

Negli algoritmi genetici, la selezione, il crossover e la mutazione sono noti come operatori genetici.

6. Risoluzione

I passaggi da 2 a 5 verranno ripetuti fino a un punto di terminazione predefinito. Questo punto di terminazione può essere uno dei seguenti:

  1. Tempo massimo / allocazione delle risorse raggiunti.
  2. È passato un numero fisso di generazioni.
  3. L'idoneità della soluzione dominante non può essere superata da nessuna generazione futura.

Convergenza della soluzione

1. Ottimale globale

Nella situazione ideale, la soluzione più adatta avrà il più alto valore di fitness possibile, ovvero sarà la soluzione ottimale, il che significa che non sarà necessario continuare con l'algoritmo e produrre ulteriori generazioni.

2. Ottimale locale

In alcuni casi, se i parametri dell'algoritmo non sono ragionevoli, la popolazione può tendere verso una convergenza prematura su una soluzione meno ottimale, che non è l'ottimale globale che stiamo cercando, ma piuttosto locale. Una volta qui, continuare l'algoritmo e produrre ulteriori generazioni potrebbe essere inutile.

Ottimale globale vs ottimale locale

Cosa accadrebbe se non ci fossero mutazioni?

A prima vista, le mutazioni possono sembrare una parte non necessaria e irrilevante del processo. Ma senza questo aspetto fondamentale della casualità, l'evoluzione per selezione naturale sarebbe completamente limitata alla varietà genetica stabilita dalla popolazione iniziale, e successivamente non ci sarebbero nuovi tratti introdotti nella popolazione. Ciò ostacolerebbe gravemente le capacità di risoluzione dei problemi della natura e la vita sulla terra non sarebbe in grado di "adattarsi" al suo ambiente, almeno non fisicamente.

Se questo fosse il caso nel nostro algoritmo genetico, a un certo punto della nostra simulazione, le generazioni future della popolazione non sarebbero in grado di esplorare parte dello spazio della soluzione che i loro predecessori non hanno esplorato. Una simulazione senza mutazioni restringerebbe gravemente la variazione genetica all'interno della popolazione e nella maggior parte dei casi - a seconda della popolazione iniziale - ci impedirebbe di raggiungere un ottimale globale.

Senza mutazioni, non avremmo mutanti e senza mutanti non avremmo il franchise X-men.

Cosa accadrebbe se la dimensione della popolazione non fosse abbastanza grande?

Recentemente sono stato al Jukani Wildlife Sanctuary di Plettenberg, dove ho avuto il privilegio di incontrare una tigre bianca. Era un animale davvero maestoso. Era grande, sembrava feroce, ed era anche cieco all'80% e peggiorava progressivamente con il passare degli anni.

Perché era cieco? Perché è un prodotto di generazioni di consanguineità. Queste tigri bianche vengono prodotte solo quando due tigri che portano un gene recessivo che controlla il colore del mantello vengono unite. Pertanto, al fine di garantire la continuazione di queste tigri in cattività, le persone hanno allevato queste tigri in una popolazione molto limitata al fine di mostrarle ai circhi, sfilarle negli zoo o tenerle come animali domestici.

Ma uno degli effetti negativi della consanguineità è che si limita fortemente la variazione genetica all'interno della specie, il che aumenta progressivamente le possibilità che i tratti recessivi dannosi vengano trasmessi alla prole.

La tigre bianca che ho incontrato al Jukani Wildlife Sanctuary nell'aprile 2019. Sembra maestoso, ma soffre.

Anche in natura, la consanguineità può essere ancora un grosso problema. Negli ultimi decenni, la popolazione di rinoceronti nell'Africa meridionale è stata notevolmente colpita dal bracconaggio e se la dimensione della popolazione raggiunge un numero abbastanza basso significherebbe che il mantenimento della diversità genetica di queste specie di rinoceronti minacciate sarebbe estremamente difficile. Quindi, anche se il bracconaggio non li porta completamente all'estinzione, la consanguineità potrebbe.

Foto di redcharlie su Unsplash.

Naturalmente, gli esseri umani non sono estranei all'allevamento. Un famoso risultato di consanguineità continua all'interno della nostra stessa specie è Carlo (Carlos) II di Spagna.

“Il re asburgico Carlo II di Spagna era tristemente degenerato con un'enorme testa deforme. La sua mascella asburgica si stagliava così tanto che le sue due file di denti non potevano incontrarsi; non era in grado di masticare. La sua lingua era così grande che riusciva a malapena a parlare. Allo stesso modo il suo intelletto era disabilitato. "

Il re asburgico Carlo II di Spagna. Suo padre era lo zio di sua madre, facendo di Charles il loro figlio, pronipote e cugino rispettivamente.

"Inbreeding" nel nostro algoritmo genetico, essenzialmente significa l'allevamento di soluzioni che hanno una composizione genetica molto simile, che, per fortuna, in questo caso, non porterebbe alla prole con una predisposizione ad eventuali anomalie fisiche. Ma se la popolazione è molto piccola e se tutte le soluzioni condividono una composizione genetica molto simile, l'idoneità delle generazioni future della popolazione sarà fortemente limitata. Ciò significa che potrebbe volerci molto più tempo per convergere su una soluzione ottimale a livello globale se ci arrivassimo del tutto.

L'ibridazione non è sempre una cosa negativa, dipende solo da quale fase della simulazione ci si trova. Nelle fasi molto avanzate della simulazione, poiché la popolazione converge verso un'optima globale / locale, è ovviamente molto difficile evitare la consanguineità, perché , in alcuni casi, molte delle soluzioni dominanti saranno molto simili tra loro e quindi condivideranno molti degli stessi tratti genetici.

Avvolgendo

Va bene, questo dovrebbe coprire le basi. Se hai domande, richieste o mutazioni genetiche da contribuire, lascia un commento qui sotto.

Nel prossimo post, approfondiremo un po 'di codice mentre esaminiamo come ciascuno degli operatori genetici sopra descritti si svolge nel mondo della programmazione. Ho usato il linguaggio di programmazione Ruby per la simulazione del software su cui ho lavorato, e in esso, mostro come in poche generazioni, un algoritmo genetico può produrre una parola o una frase predefinita da una raccolta iniziale di incomprensioni complete e assolute. Tutto il codice sarà ospitato su Github.