lunedì 20 giugno 2011

Il gioco dell'evoluzione artificiale

La teoria dell'evoluzione delle specie viventi rappresenta uno dei pilastri della biologia e del pensiero moderno. Nonostante si tratti di una teoria giovane (fu formulata da Charles Darwin "soltanto" un secolo e mezzo fa) ad oggi i suoi principi generali sono ormai consolidati presso la comunità scientifica, grazie alle numerose prove scientifiche fin qui raccolte.
Tuttavia, al di fuori del mondo scientifico c'è tuttora chi si ostina a rifiutare la visione darwiniana, e perfino alcuni (fortunatamente rari) scienziati sono notoriamente contrari alla teoria, pur non avendo mai avuto il coraggio di proporre tali opinioni a riviste specialistiche.
Tra le visioni alternative che rifiutano o criticano il darwinismo, possiamo citare la teoria del "disegno intelligente", il "creazionismo", il "devoluzionismo": alcune di queste opinioni sono sostenute da posizioni religiose, altre soltanto da una discutibile critica ai fondamenti logici e sperimentali dell'evoluzionismo.
Le prove dell'ipotesi di Darwin, in realtà, sono talmente schiaccianti e definitive che non dovrebbe esistere più alcun dubbio sulla validità della teoria: non è questa la sede per elencarle tutte, anche perché si tratterebbe di spaziare dalle dimostrazioni paleontologiche a quelle legate alla distribuzione geografica delle specie viventi e dei fossili, e questo non è un blog che possa occuparsi in modo competente di queste discipline.
Sorprendentemente, però, una delle prove a mio parere più meravigliose della teoria dell'evoluzione ci viene offerta proprio dalla matematica e dall'informatica. Com'è possibile?
Prima di arrivare al punto, devo però fare un excursus sui contenuti dell'ipotesi di Darwin.

L’esempio classico, che trova spazio anche sui libri di scuola, è quello del collo della giraffa.

Tutti sappiamo che le giraffe hanno il collo lungo. Ma è anche noto, e lo era già ai tempi di Darwin, che il collo delle giraffe primitive era più corto. Secondo l'ipotesi di Darwin, di tanto in tanto, diciamo "per caso", o "per errore", può nascere una giraffa col collo un po’ più lungo. Essendo il collo lungo una mutazione genetica e non un carattere acquisito, si tratta anche di una caratteristica ereditaria, cioè i figli di una giraffa dal collo lungo avranno probabilmente anche loro il collo lungo.
In una certa epoca, a causa dell’impoverimento dei pascoli, molte giraffe avevano cercato di cibarsi non più soltanto dell’erba ma anche delle foglie degli alberi: nella dura competizione per il cibo, una giraffa dotata di un collo più lungo si sarebbe trovata quindi nettamente avvantaggiata. Il collo lungo, insomma, rappresentava un importante vantaggio competitivo, e quelle giraffe fortunate si ritrovavano ad avere, come dicono i biologi, una idoneità superiore alle loro cugine.
Un'alta idoneità comporta, in genere, una maggiore probabilità di sopravvivenza, una vita più lunga e un maggior benessere, ma anche una maggiore predisposizione a riprodursi e quindi un numero maggiore di figli. Questo meccanismo è alla base della cosiddetta selezione naturale, perché induce una specie di cernita tra gli individui più idonei e quelli meno idonei, o, per così dire, tra mutazioni più o meno vantaggiose. Secondo la teoria di Darwin è questo il vero motore dell’evoluzione.
La conseguenza fu che le giraffe dal collo lungo si diffusero rapidamente, sostituendo gradualmente quelle dal collo corto. Altre mutazioni casuali che potevano essersi verificate, ad esempio giraffe senza coda oppure con cinque zampe, sicuramente non avrebbero avuto lo stesso successo e la stessa diffusione, in quanto poco vantaggiose.

Il meccanismo della selezione naturale premia quindi le piccole mutazioni casuali che si rivelano più vantaggiose: queste si replicano nella discendenza, innescano un lento processo di evoluzione delle specie e si accumulano generazione dopo generazione, determinando sul lungo periodo vistosi e radicali cambiamenti. La teoria di Darwin, però, non spiega però altre cose: ad esempio come l’informazione sui caratteri ereditari venga registrata all’interno degli esseri viventi, e come questi caratteri vengano trasmessi dai genitori ai figli.
E' la genetica a fornire queste risposte, mostrando come le cellule del nostro corpo siano dotate di un nucleo che contiene particolari corpuscoli, chiamati cromosomi, di solito disposti a coppie: in ogni cellula di un essere umano, ad esempio, vi sono 23 coppie di cromosomi, ciascuna delle quali è formata da un cromosoma ereditato dal padre e da uno ereditato dalla madre. Ogni cromosoma è costituito da un lunghissimo filamento di una molecola chiamata DNA, tutto attorcigliato su se stesso come un gomitolo e suddiviso in porzioni chiamate geni. Una molecola di DNA è simile ad una scala a chiocciola, i cui "pioli" sono composti chimici detti basi azotate: il modo in cui queste basi si susseguono nei filamenti dei cromosomi costituisce una sorta di lunghissima sequenza codificata, detta genoma, che rappresenta il "libretto di istruzioni" , o, meglio, una enorme enciclopedia da consultare per costruire un essere vivente.

Tutte le informazioni "genetiche", cioè ereditarie, sono scritte qui: ad esempio la lunghezza del collo per la giraffa, il colore dei nostri occhi, e così via.
Quando queste informazioni vengono replicate in modo errato, si verificano le mutazioni già intuite da Darwin: ad esempio la comparsa delle giraffe dal collo lungo.
Oltre alla mutazione, l'altro fenomeno genetico fondamentale per i meccanismi dell'evoluzione è il crossing over, che avviene in ciascuno di noi durante la formazione dei gameti, le cellule che partecipano alla fecondazione: in ognuna delle coppie di cromosomi ereditati dai genitori, si verifica uno scambio reciproco di geni, fatto che favorisce l’incrocio dei programmi genetici e produce inedite mescolanze da trasmettere ai discendenti.


Negli anni Quaranta, alcuni illustri matematici, come Alan Turing, Norbert Wiener e John Von Neumann, cominciarono a studiare i fenomeni biologici dell'evoluzione e della genetica e intuirono la possibilità di replicare questi meccanismi in modo artificiale, utilizzando i primi calcolatori elettronici.

Perché imitare nei computer il comportamento della materia vivente? Quel era l'utilità di questo strano gioco dell'evoluzione artificiale?
Fin dagli albori dell’informatica i ricercatori si erano imbattuti in problemi difficili, che richiedono di trovare la soluzione ottimale tra una enorme quantità di soluzioni possibili. Ad esempio, è difficile far giocare un computer a scacchi, oppure fargli trovare il percorso più breve per visitare un insieme di città, oppure progettare una proteina che abbia un comportamento chimico desiderato. Purtroppo, l'approccio concettualmente più ovvio, cioè esaminare tutte le possibilità per scoprire qual è la migliore, appariva proibitivo, perché avrebbe richiesto un tempo di calcolo troppo lungo. Era necessario escogitare metodi più veloci, scorciatoie più efficienti.
L'idea vincente presa a prestito dalla biologia è presto detta. Invece di scandagliare, una per una, tutte le soluzioni possibili e alla fine scegliere la migliore, usiamo un approccio evolutivo: immaginiamo che ogni possibile soluzione del problema sia un "individuo", il cui genoma contiene le informazioni caratteristiche della soluzione rappresentata. Partendo da una "popolazione" iniziale scelta casualmente, gli individui vengono fatti "evolvere" simulando la comparsa di mutazioni casuali e il verificarsi di fenomeni di crossing over, similmente a quanto avviene nella realtà nelle cellule viventi. Generazione dopo generazione, vengono selezionati gli individui più idonei, cioè le soluzioni migliori, secondo un principio che imita la selezione naturale: potremmo definrila una sorta di "selezione artificiale". Generalmente questa metodologia, se ben applicata, porta ad avvicinarsi alla soluzione ottimale in tempi relativamente brevi.
L'approccio descritto corrisponde, con buona approssimazione, allo schema generale degli algoritmi genetici, proposti per la prima volta negli anni Settanta, dal ricercatore americano John Holland.

Nella terminologia degli algoritmi genetici gli individui della popolazione vengono chiamati anche cromosomi: infatti, per semplicità, si assume che ogni individuo possieda un solo cromosoma, e possa quindi essere identificato con quell’unico cromosoma (In natura le specie viventi hanno di solito più cromosomi, ad esempio 46 nell'uomo, ma gli informatici sono molto meno bravi della Natura, per cui è già tanto che ci sia un solo cromosoma per individuo).

Uno delle questioni spinose che sorgono con gli algoritmi genetici consiste nel trovare un modo di codificare la soluzione all'interno del genoma dell'individuo. Ovviamente l'approccio da seguire dipende dal tipo di problema. Molto spesso le soluzioni vengono rappresentate come stringhe, o semplici successioni di simboli. Ad esempio, se il problema che vogliamo risolvere è quello di progettare una proteina, ossia determinare una sequenza di amminoacidi che, una volta sintetizzata in laboratorio, evidenzi determinate caratteristiche chimiche, allora potremmo rappresentare ogni individuo, cioè ogni proteina corrispondente a una possibile soluzione, tramite la sequenza di simboli di amminoacidi che rappresenta quella proteina.

Un'altra difficoltà cruciale da affrontare è legata al modo in cui, ad ogni generazione, dobbiamo misurare l'idoneità di ogni individuo, cioè di ciascuna soluzione che si trova nel nostro brodo di coltura. Il nostro ingrato compito è selezionare gli individui con l'idoneità più alta, e, ahimé, scartare quelli di peggiore qualità. Ad esempio, nel problema delle proteine, l'idoneità di una sequenza candidata di amminoacidi dipende dalle caratteristiche chimiche che tale sequenza esibirebbe una volta sintetizzata in laboratorio: l'algoritmo genetico dovrà quindi implementare particolari calcoli per misurare questo grado di qualità delle soluzioni.

Ecco allora lo schema generale del nostro "gioco dell'evoluzione artificiale", vale a dire la struttura base di un algoritmo genetico:
1. stabilire delle politiche per la codifica delle soluzioni e per la misurazione dell'idoneità;
2. costruire una popolazione iniziale casuale di individui che codifichino, tramite sequenze opportune di simboli, altrettante soluzioni possibili del problema;
3. ad ogni generazione:
• analizzare tutti gli individui presenti e scegliere quelli con idoneità più alta;
• accoppiare tra loro gli individui selezionati e sottoporli a crossing over;
• mutare alcuni dei figli ottenuti;
• se l'idoneità dell'individuo migliore è considerata abbastanza alta per i nostri scopi, terminare, altrimenti passare alla prossima generazione.

Superati gli scogli progettuali riguardanti la codifica delle soluzioni e i criteri di selezione degli individui più idonei, ciò che rimane potrebbe assomigliare ai giochi di una rivista di enigmistica: le operazioni di crossing over e di mutazione, infatti, applicate alle sequenze di simboli che rappresentano le soluzioni, sembrano uscite dalla "Pagina della Sfinge" della Settimana Enigmistica.
Il tipo più comune di crossing over tra due sequenze di simboli consiste nel tagliare in due ciascuna delle due sequenze, dando origine a due figli, l'uno formato dalla concatenazione della prima parte del primo genitore e della seconda del secondo, e l’altro formato dalla concatenazione della prima parte del secondo genitore e della seconda del primo. Una sorta di doppia sciarada incrociata tra due parole (gli appassionati di enigmistica correggeranno certamente le mie imprecisioni terminologiche), come nell'esempio seguente:

PIC-CO, ARTI-COLO --> PIC-COLO, ARTI-CO

Una mutazione, invece, non è altro che la variazione di una parte della sequenza di simboli che rappresenta una soluzione: nulla più che un semplice cambio di lettera in una parola.
Ad esempio:

PICCO --> PACCO

Grazie ai primi studi pioneristici di Turing, Von Neumann e Wiener, alla formalizzazione di Holland e alle ricerche successive, gli algoritmi genetici sono stati progressivamente perfezionati e hanno dato prova di funzionare ottimamente per la risoluzione di problemi difficili. In particolare, queste tecniche evolutive hanno permesso di affrontare con successo non soltanto problemi di ottimizzazione, ma anche problemi di modellazione e di predizione di dati. In questo caso si fanno evolvere modelli che cercano di descrivere un sistema complesso: ad esempio modelli ingegneristici di motori o di edifici, modelli biologici, modelli meteorologici o climatici, modelli finanziari, ecosistemi, modelli per giochi di simulazione, e così via. Spesso, per costruire modelli di questo tipo, gli algoritmi genetici vengono usati per fare evolvere strutture matematiche dette reti neurali, ognuna delle quali rappresenta un possibile modello del problema. L’accoppiata reti neurali – algoritmi genetici è utilizzata molto spesso e con ottimi risultati nelle attuali ricerche sull’intelligenza artificiale.
Quali conclusioni possiamo trarre dall'efficacia degli algoritmi genetici? Gli algoritmi genetici non sono altro che l'applicazione a problemi "umani" di un meccanismo naturale: certo, si tratta di un'idea applicata in modo semplificato e adattato, ma in realtà il copyright dell'idea non è nostro, ma di Madre Natura. E se l'idea alla base di questo gioco dell'evoluzione simulata funziona, questa è certamente un'ulteriore dimostrazione del fatto che l'evoluzione, quella naturale, funziona, e anche molto bene.
Potrebbe sembrare forzato il concetto di usare l'evoluzione per risolvere problemi: ma in realtà è esattamente ciò che ha fatto e continua a fare la Natura. L’evoluzione e la selezione naturale, che funzionano, generazione dopo generazione, attraverso un accumulo selettivo di piccole mutazioni vantaggiose, hanno dato prova di saper risolvere problemi molto difficili, escogitando soluzioni ingegnose e sofisticate. Pensiamo alla giraffa: il problema difficile della giraffa primitiva consisteva nel trovare un modo per mangiare le foglie degli alberi, e la geniale soluzione fu un progressivo allungamento del collo, attraverso le generazioni.
Altro esempio: il pipistrello. Dovendo cacciare di notte, il simpatico mammifero volante deve riuscire a individuare le prede nel buio: ebbene, l’evoluzione ha messo a punto, nel corso dei millenni, una tecnologia di ecolocazione davvero sofisticatissima, simile al nostro sonar, che farebbe invidia a molti ingegneri di oggi.
Gli informatici, insomma, dopo avere “rubato” ai biologi l’idea per inventare gli algoritmi genetici, hanno ricambiato il favore nel modo migliore che potessero escogitare: fornendo una affascinante dimostrazione del fatto che Darwin aveva ragione.
Spero che questa osservazione possa contribuire a convincere qualche persona ancora scettica rispetto alla teoria dell'evoluzione. E' vero che i principi della teoria di Darwin, ad un esame intuitivo, possono apparire “strani”, o “irragionevoli”: eppure, per quanto incredibile, l'evoluzione, sia quella naturale che quella artificiale, funziona. E come scrisse il poeta inglese George Byron: "E' strano, ma vero; perché la verità è sempre strana, più strana della fantasia.”

3 commenti:

  1. La verità non è strana, è logica. E di logico nella teoria darwiniana c'è appunto solo la fantasia. E' incredibile come dopo tutto il progresso in campo biologico si possano ancora fare affermazioni del genere: "Pensiamo alla giraffa: il problema difficile della giraffa primitiva consisteva nel trovare un modo per mangiare le foglie degli alberi, e la geniale soluzione fu un progressivo allungamento del collo, attraverso le generazioni".... Tanto è vero che troviamo ovunque animali con il collo lungo!! Che poi la giraffa abbia (tra le molte altre cose) un perfetto sistema valvolare di controllo della pressione sanguigna assolutamente unico e assolutamente indispensabile per avere la testa a tale altezza, tutto questo non ha nessuna importanza. La fantasia e i disegnini, infatti, devono essere alla base della scienza. MAh!! Contenti voi!

    RispondiElimina
  2. Caro Anonimo, il famoso esempio delle giraffe, così come viene riportato sui libri, risente, senza dubbio, di una certa dose di semplificazione. Anch'io non ho potuto che riportarlo in questa versione semplificata, ancorché valida e corretta (la invito però, se non l'ha fatto, a leggere anche la prima parte del post e non solo quella che lei cita).
    Il concetto di base, comunque, non mi pare sia travisato.
    D'accordo: il collo lungo non è l'unico carattere proprio delle giraffe; ma il sistema circolatorio speciale che lei cita è una conseguenza del collo allungato, non l'inverso.
    Poi, il fatto che non vi siano molti animali col collo lungo non capisco cosa c'entri: come ben sa, l'evoluzione è un processo attraverso il quale ogni specie sviluppa le proprie soluzioni in modo indipendente.
    E poi, caro anonimo: questo è un blog di divulgazione sulla matematica e sull'informatica, per cui non è pensabile prescindere da un taglio divulgativo, che fa uso anche di "disegnini", se possono servire.

    RispondiElimina
  3. Ho trovato questo articolo molto interessante e molto ben fatto. Tratta alcuni dei miei argomenti preferiti (evoluzionismo, algoritmi genetici, reti neuronali).
    Originale la considerazione finale sullo "scambio di favori" tra biologi e informatici.
    Complimenti.

    RispondiElimina

L'ultimo post di Mr. Palomar, anzi no

Sono trascorsi quasi 14 anni da quel Capodanno del 2011, quando Mr. Palomar  vide la luce. Da allora, molta acqua è passata sotto i ponti, c...