Chapter 9. The Evolution of Code (1°Parte)

“Il fatto che la vita si sia evoluta dal nulla, circa 10 miliardi di anni
dopo che l’universo si è evoluto letteralmente dal nulla, è un fatto così sbalorditivo
che sarei pazzo a tentare le parole per rendergli giustizia.”
— Richard Dawkins

Nella scrittura di un programma informatico le variabili consentono di salvare i dati e riutilizzarli durante l’esecuzione. Questo, ovviamente, non è una novità. In effetti, si è andati ben oltre uno schizzo con una sola o due variabili e poi a strutture dei dati più complessi, variabili costituite da tipi personalizzati (oggetti) che includono sia dati che funzionalità.

Si sono creati piccoli mondi di motori e particelle e veicoli e cellule e alberi. Ora, in ogni esempio di questo libro, le variabili di questi oggetti devono essere inizializzate.
Forse avete creato un intero gruppo di particelle con colori e dimensioni casuali o un elenco di veicoli che iniziavano a muovere tutti nella stessa posizione x, y sullo schermo. Ma invece di agire come “architetti” assegnando le proprietà dei nostri oggetti attraverso casualità o ponderate considerazione, viene da chiedersi se si possa lasciare che un processo decida per noi.

Possiamo pensare alle variabili di un oggetto come al suo DNA? Gli oggetti possono creare altri oggetti e trasmettere il proprio DNA a una nuova generazione? La nostra simulazione può evolversi?

La risposta a tutte queste domande è sì. (…) Questo capitolo è dedicato all’esame del principi alla base dell’evoluzione biologica e alla ricerca di modi per applicare tali principi nel codice.

9.1 Algoritmi genetici: ispirati da eventi reali
È importante chiarire gli obiettivi di questo capitolo. Non approfondiremo la scienza della genetica e dell’evoluzione così come avviene nel mondo reale. Non ci saranno discussioni su nucleotidi, sintesi proteica, RNA e altri argomenti relativi agli attuali processi biologici di evoluzione. Invece esamineremo i principi fondamentali alla base della teoria evoluzionistica darwiniana e svilupperemo una serie di algoritmi ispirati a questi principi. Non ci interessa molto una simulazione accurata dell’evoluzione; piuttosto, ci preoccuperemo dei metodi per applicare tali strategie evolutive nel software.
Questo non vuol dire che un progetto con maggiore profondità scientifica non avrebbe valore, (…). Tuttavia, per il bene della didattica, ci atterremo alle basi, che saranno comunque complesse, ma al contempo, emozionanti.

Il termine “algoritmo genetico” si riferisce a uno specifico algoritmo implementato in un modo specifico per
risolvere tipi specifici di problemi. Mentre l’algoritmo genetico formale stesso servirà come file base per gli esempi che creeremo in questo capitolo, non ci si deve preoccupare di implementazione perfetta, dato che stiamo cercando usi creativi di teorie evolutive nel nostro codice. Questo capitolo sarà suddiviso nelle tre seguenti parti (con la maggior parte del tempo dedicato alla prima).

1. Algoritmo genetico tradizionale. Inizieremo con l’informatica tradizionale dell’algoritmo genetico. Questo algoritmo è stato sviluppato per risolvere problemi in cui lo spazio delle soluzioni è così vasto che un algoritmo di “forza bruta” richiederebbe semplicemente troppo tempo.
Ecco un esempio: sto pensando a un numero. Un numero compreso tra uno e un miliardo.
Quanto tempo ti ci vorrebbe per indovinarlo? Risolvere un problema con la “forza bruta” significa verificare ogni possibile soluzione. È uno? Sono due? Sono tre? È quattro? E così e così via. Anche se la fortuna gioca un fattore qui, con questo metodo ci troveremmo spesso ad aspettare pazientemente per anni :). Tuttavia, se potessimo dirvi se una risposta che avete dato è stata buona o cattiva? Caldo o freddo? Molto caldo? Caldo? Super, super freddo? Se potessimo valutare quanto “valdità” abbia una risposta, rispetto ad una altra, e arrivare così alla risposta più velocemente. La vostra risposta potrebbe evolversi.

2. Selezione interattiva. Una volta stabilito l’algoritmo dell’informatica tradizionale, si esamineranno altre applicazioni degli algoritmi genetici nelle arti visive. La selezione si riferisce al processo di evoluzione di qualcosa (spesso un file generato dal computer immagine) attraverso l’interazione dell’utente. Supponiamo che entriate in una galleria di un museo e vediate dieci dipinti. Con la selezione interattiva, sceglireste i vostri dipinti preferiti e consentireste un processo algoritmico per generare (o “evolvere”) nuovi dipinti basati sulle vostre preferenze.

3. Simulazione dell’ecosistema. L’algoritmo genetico dell’informatica tradizionale e le tecniche di selezione interattiva sono ciò che probabilmente troverete se cercate online o leggete un libro di testo sull’intelligenza artificiale. Ma come vedremo presto, in realtà non simulano veramente il processo di evoluzione così come avviene nel mondo reale. In questo capitolo, esploreremo le tecniche per simulare il processo di evoluzione in un ecosistema di pseudo esseri viventi. Come possono i nostri oggetti che si muovono su uno schermo incontrarsi, accoppiarsi e trasmettere i loro geni a una nuova generazione? 

9.2 Perché utilizzare algoritmi genetici?
Le simulazioni al computer dei processi evolutivi risalgono agli anni ’50. Gran parte di ciò che conosciamo sugli algoritmi genetici (noti anche come “GA”) lo si deve al lavoro di ricerca di John Holland, professore all’Università del Michigan, il cui libro Adaptation in Natural and Artificial Systems ha aperto la strada alla ricerca GA.

Oggi, gli algoritmi genetici fanno parte di un campo di ricerca più ampio, spesso indicato come “Evolutionary Computing”.
Per aiutare a illustrare l’algoritmo genetico tradizionale, inizieremo con le scimmie 🙂 No, non i nostri antenati evolutivi. Inizieremo con alcune scimmie immaginarie che digitano sulle tastiere con l’obiettivo di battere a macchina le opere complete di Shakespeare… Iniziamo!

Il “teorema della scimmia infinita” afferma quanto segue: Una scimmia che colpisce i tasti in modo casuale su una
macchina da scrivere finirà per digitare le opere complete di Shakespeare (dato un numero infinito di tempo). Il problema con questa teoria è che la probabilità che detta scimmia stia effettivamente digitando Shakespeare è così basso che anche se quella scimmia avesse iniziato a digitare ai tempi del  Big Bang, è incredibilmente improbabile che avremmo anche solo Amleto a questo punto (2021).
Consideriamo una scimmia di nome George. George digita su una macchina da scrivere ridotta contenente solo ventisette caratteri: ventisei lettere e una barra spaziatrice. Quindi la probabilità di George che preme un tasto qualsiasi è uno su ventisette.
Consideriamo la frase “To be or not to be” (la stiamo semplificando dal originale “Essere o non essere: questo è il problema”). La frase è lunga 39 caratteri. Se George inizia a digitare, la probabilità che ottenga il primo carattere corretto è 1 su 27. Poiché la probabilità lo farà anche il secondo carattere a destra è 1 su 27, ha 1 possibilità su 27 * 27 di ottenere il primo due caratteri nell’ordine corretto- Quindi la probabilità che Giorge digiti la frase completa è: (1/27) moltiplicato per se stesso 39 volte, cioè (1/27) 39 che equivale a: 66.555.937.033.867.822.607.895.549.241.096.482.953.017.615.834.735.226.163 possibilità di affrontarlo nel modo corretto!

Inutile dire che individuare solo questa frase, per non parlare di un’intera commedia, è altamente improbabile. Anche se George è una simulazione al computer e può digitare un milione di frasi casuali al secondo, e George avesse una probabilità del 99% di riuscire a farlo bene, dovrebbe tentare per 9.719.096.182.010.563.073.125.591.133.903.305.625.605.017 anni. (Nota che il si stima che l’età dell’universo sia di soli 13.750.000.000 di anni.)

Il punto di tutti questi numeri incredibilmente grandi non è quello di farvi venire il mal di testa, ma di dimostrare che un algoritmo di forza bruta (digitando ogni possibile frase casuale) non è una strategia ragionevole per arrivare casualmente alla frase “To be or not to be” . Attraverso gli algoritmi genetici, mostreremo invece che possiamo partendo da frasi casuali, trovare la soluzione tramite un’evoluzione simulata.
Ora, vale la pena notare che questo problema (trovare la frase “”To be or not to be”) è ridicolo. Poiché conosciamo la risposta, tutto ciò che dobbiamo fare è digitarla.

Tuttavia, il punto qui, è che risolvere un problema con una risposta nota ci consente di testare facilmente
il nostro codice. Una volta risolto con successo il problema, possiamo sentirci più sicuri e usare algoritmi genetici per fare un lavoro utile/reale: risolvere problemi con risposte sconosciute. Quindi questo primo esempio non ha alcuno scopo reale se non quello di dimostrare quanto sia “genetico” il nostro lavoro. (…) 😉

9.3 Selezione naturale darwiniana
Prima di iniziare a esaminare l’algoritmo genetico, prendiamoci un momento per descrivere i tre principi fondamentali dell’evoluzione darwiniana che saranno richiesti quando implementeremo la nostra simulazione. Affinché la selezione naturale avvenga come avviene in natura, tutti e tre questi elementi devono essere presenti.

1. Eredità. Deve essere in atto un processo in base al quale i bambini ricevono i geni dei loro genitori. Se le creature vivono abbastanza a lungo da riprodursi, allora i loro tratti vengono trasmessi ai loro figli nella prossima generazione di creature.
2. Variazione. Ci deve essere una varietà di tratti presenti nella popolazione o in mezzo con cui introdurre la variazione. Ad esempio, supponiamo che ci sia una popolazione di coleotteri in cui tutti i coleotteri sono esattamente uguali: stesso colore, stessa taglia, stessa apertura alare, stesso tutto. Senza alcuna varietà nella popolazione, i bambini  saranno sempre identici ai genitori e gli uni agli altri. Nuove combinazioni di tratti saranno impensabili e niente potrà evolversi.
3. Selezione. Ci deve essere un meccanismo attraverso il quale alcuni membri di una popolazione abbiano l’opportunità di essere genitori e trasmettere le proprie informazioni genetiche e altri no. Questo è in genere indicato come “sopravvivenza del più adatto”. Per esempio, diciamo che ogni giorno una popolazione di gazzelle viene inseguita dai leoni. Le gazzelle più veloci hanno maggiori probabilità di sfuggire ai leoni e sono quindi più propense a vivere più a lungo e avere la possibilità di riprodursi e trasmettere i propri geni ai propri figli. Il termine il più adatto, tuttavia, può essere un po ‘fuorviante. In generale, consideriamo il significato come “più grande”, “più veloce” o “più forte”. Anche se questo a volte può succedere, in alcuni casi, la selezione naturale opera in base al principio che alcuni tratti si adattano meglio all’ambiente della creatura e quindi producono una maggiore probabilità di sopravvivenza e di riproduzione. Non ha nulla a che fare quindi con un concetto di “migliore” (dopotutto, questo è un termine soggettivo). Nel caso della digitazione delle nostre scimmie, ad esempio, una scimmia più “in forma” è quella che ha digitato una frase più vicina a “essere o non essere”.

Nei prossimi articoli passeremo attraverso la narrazione dell’algoritmo genetico. Lo faremo nel contesto della scimmia che scrive. L’algoritmo stesso sarà diviso in due parti: un insieme di condizioni per inizializzazione (ad esempio, la configurazione di Processing ()) e i passaggi che vengono ripetuti più e più volte (ad es. Processing’s draw ()) fino a quando non arriveremo alla risposta corretta.

Bibliografia

Daniel Shiffman The Nature of Code 2012