Avete un problema da risolvere e state cercando la soluzione ma c’è un ma: ci sono tante, tantissime, troppe possibilità da vagliare e non vi basterebbe una vita intera per vagliarle tutte. State cercando il cosiddetto ago in un pagliaio.
Poniamo il caso che vogliate indovinare la parola che sto pensando in questo momento (spoiler alert: la parola che sto pensando è “processing”). Senza potervi avvalere di nessun altro indizio, probabilmente comincereste a chiedermi: “comincia con la lettera A?” No. “Comincia con la lettera B?” No. “lettera C?” Nope. “D? E? F? G? …” No, No, No, No … “P?” Yes! Bene, avanti: “Segue la lettera A?” No “lettera B? No. Insomma, ho reso l’idea? Che palle!
Fortunatamente oggi abbiamo a disposizione potenti calcolatori in grado di sobbarcarsi volumi di calcolo impressionanti in un una manciata di millisecondi, quindi il problema è risolto, giusto? Non proprio. Applicare la forza bruta appellandosi esclusivamente alla potenza di calcolo dei computer a nostra disposizione, può risultare comunque un processo molto, molto dispendioso sia in termini di risorse che di tempo.
Come sarebbe bello se un programma, un’applicazione, potesse evolvere il proprio calcolo attraverso algoritmi genetici che mettano in pratica strategie evoluzionistiche simili a quelle teorizzate da Charles Darwin, basate sul principio della selezione naturale ed evoluzione biologica. Bè, ciò non è solo bello ed affascinante, è anche possibile ed alla portata di chiunque voglia cimentarsi con qualche riga di codice.
Karl Sims – Evolved Virtual Creatures, Evolution Simulation, 1994
I tre principi della teoria Darwiniana che vogliamo applicare al nostro codice sono: ereditarietà, varietà e selezione. In parole semplici, affinchè avvenga una evoluzione naturale, è necessario che ci sia un passaggio di proprietà tra genitori e figli; è poi necessario che ci sia varietà nei dati passati di generazione in generazione (in caso contrario avremmo cloni perfetti). È infine necessario che intervenga un meccanismo di selezione per cui le caratteristiche di certi elementi, in un certo contesto, siano o meno preferibili rispetto a quelle di altri (un pinguino ha poche chance di sopravvivere nel deserto del Sahara. Viceversa, ha ottime probabilità di prosperare e riprodursi in Antartide).
Step 1: Inizializzazione. Creare una popolazione di N elementi, ciascuno con un proprio DNA, generato in modo casuale.
Passando dai pinguini alla programmazione, immaginiamo un DNA elettronico costituito da variabili: valori memorizzati nelle proprietà di un oggetto. La struttura del nostro algoritmo genetico prevede un primo step di inizializzazione, in cui viene creata una popolazione di elementi in modo casuale; una popolazione contraddistinta da tratti genetici che presentino una certa varietà tra un elemento e l’altro. Questi valori, memorizzati nelle variabili che costituiscono il DNA elettronico di ciascun elemento della popolazione, rappresentano il genotipo.
Step 2: Valutazione. Impiegare un metodo che valuti l’idoneità di ciascun elemento a rimanere nel nostro sistema.
Il passo successivo prevede l’utilizzo di una funzione che valuti tutti gli elementi della nostra popolazione, attribuendo ad essi un punteggio basato su determinati criteri, chiamato in gergo “fitness score” (mentre alla funzione, generalmente, ci si riferisce come “fitness function”).
Step 3: Selezione. Determinare quali sono gli elementi migliori, i cui caratteri genetici meritano di essere trasmessi alla generazione successiva.
Adesso non ci resta che decidere e programmare il meccanismo di selezione attraverso cui determinati geni vengono passati alle generazioni successive. A riguardo ci sono vari metodi; uno di questi prevede un approccio probabilistico, una sorta di “ruota della fortuna”: facciamo la media di tutti i punteggi di ciascuno dei “candidati alla riproduzione”, dividendo il punteggio di ciascuno per il punteggio totale (dato dalla somma di tutti i punteggi), sulla base delle percentuali ottenute determiniamo le probabilità di ciascun elemento di riprodursi. In questo modo il patrimonio genetico degli elementi che hanno ricevuto un punteggio migliore avrà maggiori probabilità di essere selezionato e viceversa.
Step 4 : Riproduzione. Combinare il DNA dei genitori, prevedendo un piccolo tasso di mutazione. Ripetere il processo con la nuova generazione.
L’ultima fase è quella della riproduzione, in cui entra in gioco il principio darwiniano dell’ereditarietà, la fase in cui avviene il passaggio delle informazioni genetiche alla generazione successiva, attraverso due momenti fondamentali: scambio e mutazione (crossover e mutation). Anche in questo caso, ci sono vari metodi: potremmo decidere di optare per una riproduzione asessuata da un unico individuo generante, oppure contemplare una coppia di genitori, ma anche tre, quattro, cinque… Siamo noi a decidere le regole del nostro mondo fatto di linee di codice.
Decidiamo di optare per un meccanismo di riproduzione basato su una coppia di genitori. Una parte del DNA di uno dei genitori viene scambiato con una parte del DNA dell’altro genitore (crossover). Prima d’essere assemblato nel DNA del nuovo elemento, il patrimonio genetico dei genitori, dopo essere stato “mischiato”, può subire una piccola mutazione, che contribuisce ad introdurre maggiore varietà nel processo evolutivo. La varietà deve essere come il sale, nelle ricette di cucina: quanto basta. Troppa varietà renderà di fatto nullo il processo evoluzionistico scaturito dal meccanismo di selezione dei genitori, troppo poca varietà e rischieremo di non avere mai quel particolare gene in grado di determinare un salto evolutivo.
Poniamo che, come risultato di un’evoluzione avvenuta generazione dopo generazione, il DNA dei nostri genitori sia costituito rispettivamente dalle lettere P, R, O, C, E, D, U, M, U, T e dalle lettere F, U, Z, A, T, A, S, I, N, G. Il nostro DNA, grazie al processo di crossover, potrebbe quindi risultare: D, U, M, U, T, A, S, I, N, G oppure P, R, O, C, E, F, U, Z, A, T oppure P, R, O, C, E, A, S, I, N, G. E magari, l’intervento di una piccola mutazione genetica: il cambiamento di una singola lettera del DNA, in quest’ultimo caso, potrebbe generare come risultato: P, R, O, C, E, S, S, I, N, G; le cui lettere, guarda caso, formano proprio la parola che vi avevo chiesto di indovinare all’inizio di questo post: “processing”. Se non fosse intervenuta quella piccola mutazione che ha modificato una A in una S, forse, anche attendendo mille generazioni, non saremmo mai arrivati a questo risultato. Per arrivare al quale abbiamo dovuto ripetere il processo di valutazione, selezione e riproduzione più e più volte, dai capostipiti ai genitori di “processing”.
Quella che avete appena letto è ovviamente solo una breve e sommaria introduzione al tema degli algoritmi genetici, parte di un vasto filone di ricerca, in forte espansione, che va sotto il nome di “Evolutionary Computing” (Computazione evolutiva). Per chi volesse approfondire, divertendosi con Processing, tra i tanti libri in circolazione consiglio caldamente The Nature of Code di Daniel Shiffman che volendo è disponibile anche online (al momento solo in lingua inglese).
Non potevo però concludere il post senza includere almeno un piccolo esempio pratico in cui vedere all’opera un algoritmo genetico. Si tratta di un esempio piuttosto semplice, ispirato dal libro di Shiffman e scritto in Javascript. Un mondo popolato da triangoli rossi e bianchi: cacciatori e prede. Per sopravvivere, le prede devono nutrirsi di quadratini verdi e sfuggire ad i cacciatori, mentre quest’ultimi, notoriamente allergici ai quadratini verdi, se non vogliono morire di fame devono cacciare.
See the Pen Evolving Creatures by Setup Draw (@SetupDraw) on CodePen.
Premete il mouse per aggiungere nuove prede; la barra spaziatrice per aggiungere nuovi cacciatori.
Più a lungo le prede sopravvivono, più probabilità hanno di riprodursi. Più prede riescono a cacciare i cacciatori più predatori si aggiungeranno alla caccia. Ogni qual volta una preda “muore” lascia dietro di se un quadratino verde: cibo per i suoi simili.
Le opportinità d’impiegare degli algoritmi genetici vanno ben oltre la programmazione di poligoni assassini. La struttura tipo dell’algoritmo genetico appena descritta, è infatti adattabile e riutilizzabile per una serie infinita di progetti. Dovrete solo definire la vostra “fitness function“, vale a dire, definire il criterio con cui attribuire un punteggio ai vostri elementi, e decidere come implementare il genotipo (da cosa è composto il DNA) ed il fenotipo (come si esprime/manifesta il DNA) del vostro sistema.
Se siete a corto di idee, ecco una lista di progetti interessanti, basati su algoritmi genetici: