Premessa

Voi programmatori mettete il codice, le performance ma non i principi di funzionamento.

Così mi è stato detto quando ho fatto vedere il video qui sotto. In effetti, mi sono accorto di averlo mostrato in diverse occasioni rispiegando ogni volta come funzionava il codice dietro le quinte. Spinto allora dal principio DRY, ho deciso di documentare il piccolo esperimento di algoritmo genetico che ho realizzato con Play Framework, Akka e Scala e la cui esecuzione è mostrata proprio dal filmato qui proposto. Più che un tutorial su questi temi, troverete una specie di diario di viaggio di cosa ho realizzato e imparato realizzando la copia di un’immagine usando degli algoritmi genetici con Scala.

Non so quante probabilità ci siano che uno dei lettori di CodingJam utilizzi i genetic algorithm (GA), tuttavia sono una classe importante di algoritmi che permette di risolvere svariati problemi. Ogni tanto è divertente sviluppare e presentare su questo blog qualcosa che non necessariamente derivi da un'esperienza di produzione, ma che permetta invece di esplorare argomenti sconosciuti. E' questo quello che ho fatto nel progetto LaGioconda e che qui vi racconto.

L’antenna NASA per la spedizione ST5 del 2006. Questa forma “bizzarra” è stata individuata da un algoritmo genetico per ottimizzare il guadagno del segnale

Algoritmi genetici

La teoria dell'evoluzione prevede che un organismo si adatti ad un ambiente ostile, modificando generazione dopo generazione le proprie caratteristiche. Solo gli organismi che si adeguano meglio e più in fretta sono in grado di sopravvivere. Un organismo vivente è composto da cellule che contengono cromosomi identici. Un cromosoma a sua volta consiste di geni che sono blocchi di DNA e codificano una specifica proteina.

La ricombinazione o crossover è il primo passo della riproduzione. I geni dei genitori generano un nuovo cromosoma (offspring) che può essere mutato. Durante la mutazione, uno o più elementi sono modificati a causa di errori nella replica. Il nuovo individuo può essere più o meno adatto all'ambiente in cui vive: chiamiamo fitness questa capacità. Gli individui con fitness migliore sono quelli con più alta probabilità di sopravvivenza e quindi di riproduzione.

Lo scopo di un algoritmo genetico è quello di risolvere un problema di ottimizzazione trovando la miglior soluzione possibile tra un gruppo di possibili risultati (popolazione) ispirandosi ai meccanismi dell'evoluzione.

Un GA parte da una popolazione casuale e applica un passo di riproduzione generando un nuovo set di individui. Se nella nuova generazione esiste un individuo la cui fitness è superiore ad una soglia richiesta, l'algoritmo termina. Altrimenti si ripete iterativamente la riproduzione e la valutazione dei nuovi individui. Per far in modo che l'evoluzione sia positiva, cioè il problema venga risolto, il crossover favorisce gli individui con fitness migliore. La mutation invece permette di introdurre delle variazioni casuali che potenzialmente migliorano il risultato.

Ma perché andare a scomodare questa metodologia e non scrivere direttamente del codice che risolva il problema? Si utilizza un GA quando:

• può essere complicato scrivere l'algoritmo o non è ben chiaro come farlo,
• il problema cambia in continuazione,
• non è possibile cercare in tutto lo spazio delle soluzioni,
• una soluzione "buona abbastanza" è accettabile.

Mona Lisa smile

Il tipo di problema che ho voluto risolvere è stata la copia di un’immagine: sapreste scrivere un algoritmo che posizioni 250 cerchi colorati in un rettangolo in modo tale che la disposizione di questi sia in grado di "disegnare" la Gioconda di Da Vinci? La risoluzione analitica potrebbe essere difficile, ma con una buona funzione di fitness a disposizione e un po' di tempo macchina si può provare la strada dell'algoritmo genetico. Volendo, si può anche trovare un'applicazione pratica a questo esperimento: potrebbe essere usato come compressore lossy di immagini. Il video mostra nel primo riquadro l'immagine originale, nel secondo l'algoritmo genetico che ho implementato assieme a due varianti nel terzo e quarto riquadro.

La codifica e decodifica

Una delle prime cose da decidere è come rappresentare il DNA di un individuo e come trasformare una soluzione del problema nei cromosomi e viceversa. Ho scelto l'approccio più semplice e più usato codificando ogni gene con una sequenza di 0 e 1.

Ho fatto corrispondere poi ogni cerchio ad un gene; un gene codifica la posizione del centro, il raggio ed il colore in RGB. Per semplificarmi un po' i calcoli, ho deciso che avrei copiato un'immagine 256×256. In questo modo ho usato 8 più 8 bit per il centro del cerchio, 4 per un raggio massimo di 16 pixel e 8 bit per ognuno dei tre colori di base, 44 bit in totale. Sempre per facilitarmi le cose, ho deciso che un individuo avesse un solo cromosoma che contenesse tutti i geni.

La funzione di fitness

La funzione di fitness valuta quanto un membro della popolazione si stia avvicinando alla soluzione e meriti di riprodursi tramandando il suo patrimonio genetico. Di solito il valore è normalizzato dove 1 corrisponde al risultato perfetto.

Nel mio caso la funzione è intuitiva. Dato un individuo, i suoi geni vengono usati per disegnare i cerchi in una immagine in memoria. La bitmap così ottenuta viene confrontata pixel per pixel con Monna Lisa calcolando la distanza euclidea normalizzata. In altre parole, più i colori sono vicini punto per punto, migliore è l'immagine e più il fitness sarà vicino ad 1. Quest'ultimo valore è teorico, cioè verrebbe raggiunto probabilmente con tanti cerchi quanti i pixel dell'immagine originale.

L'algoritmo

Anche l'algoritmo ha una formulazione iterativa molto semplice:

1. generare casualmente una prima popolazione di n elementi;
2. valutare la funzione di fitness per ogni membro della popolazione corrente;
3. se tra gli individui ne esiste uno il cui fitness è superiore ad una soglia impostata, allora è stata trovata la soluzione al problema e l'algoritmo termina;
4. altrimenti tramite crossover e mutazione preparare una nuova generazione di individui e ritornare al passo 2.

Quello descritto è un schema generale a cui possono essere applicate molte varianti. Ad esempio, possiamo utilizzare diversi modi per scegliere quali individui sono candidati a riprodursi e quali invece non tramanderanno il loro patrimonio alla generazione successiva. Un metodo classico è la wheel selection, dove in pratica, la probabilità di riproduzione è proporzionale alla fitness. Supponiamo di avere tre individui e di ordinarli per fitness che può andare da 0 a 100, ad esempio (80, 70, 50). Il primo individuo avrà probabilità 80/200 = 40% di riprodursi, il secondo 70/200 = 35% e il terzo 50/200 = 25%. Generiamo un numero casuale tra 0 e 100. Se cade tra 0 e 40 (escluso), verrà scelto il primo individuo, tra 40 e 75 (escluso) verrà selezionato il secondo, altrimenti verrà preso il terzo.

Nulla vieta di applicare un altro criterio come ad esempio far riprodurre sempre un individuo scelto tra il miglior 50% della popolazione con uno scelto tra la popolazione rimanente. Quale funzionerà meglio? Difficile da dire, in questa classe di algoritmi bisogna sperimentare con diverse configurazioni e aggiustare il tiro valutando di volta in volta il comportamento. Una cosa sicuramente da evitare è quella di favorire troppo gli individui migliori. Un algoritmo genetico può richiedere molte generazioni prima di restituire un risultato accettabile, se favoriamo subito un individuo con una fitness ancora bassa, finiremo in un massimo locale, cioè in una soluzione buona ma non abbastanza. Perché l'algoritmo insisterà nel tramandare uno specifico patrimonio genetico senza cercare altrove altre soluzioni migliori.

Una tecnica che si può usare quando l'algoritmo converge troppo presto è quella presa in prestito dal simulated annealing. All'inizio dell'esecuzione l'algoritmo non favorisce troppo gli individui con fitness più alta ma lascia spazio anche a soluzioni non ottimali. Queste potrebbero però convergere verso risultati migliori di quello corrente. Man mano che le generazioni passano invece, incrementiamo la probabilità di riproduzione per gli individui migliori.

Crossover e mutation

Dopo aver scelto due individui, va deciso come combinare le loro informazioni genetiche. Il crossover che ho implementato prevede di costruire il nuovo individuo scegliendo gene per gene dal primo genitore o dal secondo con una probabilità del 50% ciascuno. Anche in questo caso, è possibile sbizzarrirsi e sperimentare altre modalità.

Come in natura, introduciamo un "errore di copia", cioè una variazione casuale nel patrimonio genetico. Questo cambiamento potrebbe essere positivo o negativo, sarà la funzione di fitness a valutarlo.

Nell'implementazione proposta la mutazione avviene con una probabilità del 5%. Sono modificati 4 geni scelti a caso e in ciascuno un bit casuale viene invertito. Perché questi parametri? Una probabilità di mutazione troppo alta, cambiare troppi geni o troppi bit trasforma il GA in una specie di ricerca pseudocasuale. In pratica, è come se generassimo soluzioni a caso e chiedessimo semplicemente di controllarle senza indirizzare l'algoritmo. Le combinazioni possibili sono troppe (2^(250*44)) perché la procedura risponda in tempi accettabili. D'altra parte, se le mutazioni sono limitate o infrequenti, ritorniamo al problema del massimo locale.

La mutazione introduce la possibilità che la nuova generazione sia peggiore di quella precedente. Per evitare questo si può introdurre il concetto di elitarismo. I migliori individui di una popolazione, di solito una percentuale piccola, vengono riportati nella generazione successiva.

Hillclimb e VecGen

Come avrete intuito dal video, ogni esecuzione dell'algoritmo richiede ore e nel mentre c'è molto tempo per pensare a come ottimizzarlo (o per dormire ;-)). Ho introdotto quindi due varianti. La prima si chiama Hill Climbing. Consiste nel prendere la soluzione corrente e cercare di vedere se "attorno" ce n'è una migliore. Per individuare un vicino, posso scegliere un cerchio e modificare leggermente le sue caratteristiche spostando il centro nelle quattro direzioni, aumentando o diminuendo il raggio e incrementando o decrementando ogni singolo canale del colore. Se una di queste variazioni permette di migliorare la fitness, allora posso usare questo nuovo individuo come soluzione e introdurlo nella popolazione.

Agire sulle caratteristiche del cerchio e non sul corrispondente gene vuol dire che stiamo uscendo dal GA e usando una tecnica di ottimizzazione diversa. L'Hill Climbing potrebbe anche essere utilizzato da solo, basterebbe partire da una soluzione a caso e ripetere la ricerca di un vicino migliore fin tanto che non si raggiunge la fitness desiderata. Per evitare di snaturare troppo l'algoritmo genetico ho deciso di usare questo metodo solo quando dopo un po' di generazioni l'individuo migliore non cambia fitness. Nel video, il terzo riquadro mostra l'effetto di questa ottimizzazione rispetto alla soluzione di base che è in seconda posizione.

La seconda variante è ispirata ad un software chiamato VecGen, di cui però non è disponibile il codice, ma restano i video su . Sono venuto a conoscenza di VecGen durante una presentazione del BeeScala 2016 ed è proprio da quel talk che mi è venuta l'idea di implementare l'algoritmo di cui parlo in questo post. In VecGen l'approccio è un po' diverso. Al posto di partire subito con 250 cerchi limitati a 16 pixel di raggio, parto con un solo cerchio che può avere un raggio di 256 pixel.

Sempre tramite GA e Hill Climbing cerco di posizionare il cerchio in modo da migliorare il valore di fitness. Quando non è più possibile migliorare la soluzione, aggiungo un secondo cerchio e riparto. Questa variante è presentata nel quarto riquadro e si può notare come il risultato finale si avvicini molto all'immagine originale, soprattutto se socchiudete gli occhi ;-). Non ho fissato un numero massimo di cerchi, semplicemente ho terminato l'algoritmo quando il risultato mi sembrava soddisfacente.

Scala, Akka e Play Framework

Lavorando correntemente con Scala, Akka e Play Framework è stato naturale per me usare queste tecnologie. In particolare ho scelto Akka perché volevo calcolare più fitness in parallelo sfruttando il multithreading senza doverlo programmare a basso livello. Tuttavia, nonostante l'uso di Akka, da subito mi sono accorto che le prestazioni non erano quelle che mi aspettavo. Indagando un po' con il profiler, ho realizzato che anche se provavo ad andare in parallelo, tutti gli attori si bloccavano nel medesimo punto, il calcolo della funzione di fitness. In effetti le API di Java sottostanti per il disegno dell'immagine non sono e non potranno mai essere multithreading. Quindi aumentare il grado di parallelismo con più thread non dava miglioramenti perché le chiamate venivano serializzate. Di fatto mi sono trovato davanti ad un vicolo cieco, con questo collo di bottiglia l'algoritmo ci avrebbe messo molto a girare.

Sono riuscito però a risolvere questo problema con un piccolo trucco: se in una singola JVM sono limitato dall'uso di una sola funzione di fitness alla volta, allora posso usare più virtual machine contemporaneamente. Akka permette di realizzare velocemente un servizio che giri su più nodi. Ho eseguito il cluster in locale lanciando più istanze del progetto con parametro backend o frontend. L'unico nodo di frontend realizzato con Play comunica con il browser e gestisce l'algoritmo come nella soluzione con singola virtual machine. Il calcolo della fitness viene demandato ad attori su istanze di backend: Akka si occupa di rendere trasparente la comunicazione tra attori su nodi diversi. Le JVM dedicate al backend sono state lanciate usando pochi megabyte di RAM. Ho potuto quindi utilizzare diverse istanze diminuendo di un ordine di grandezza il tempo richiesto per ottenere una soluzione accettabile.

Conclusioni

Come detto all'inizio, questo post non è un tutorial e non ha la pretesa di sostituirsi ad una trattazione rigorosa degli algoritmi genetici. Anche il codice è solo un punto di partenza e può essere sicuramente migliorato. Spero solo di aver incuriosito il lettore casuale nel voler usare un'immagine diversa, nel modificare l'algoritmo, variare la funzione di fitness, o sbirciare quello che si può realizzare con Akka in un ambiente distribuito. Personalmente mi sono divertito molto a realizzare questo progetto partendo, in pratica, da nessuna nozione sull'argomento. Ma se qualcuno sarà incuriosito dagli algoritmi genetici a causa (anche) di questo post, avrò ottenuto un risultato ancora più interessante.

Un grazie a Francesco e Ubaldo per l’aiuto sul frontend.