Freccia inversa del tempo con algoritmo genetico e GPU
- Literature & Cie
- 17 févr. 2021
- 5 min de lecture
Un write-up della seconda posizione alla competizione Kaggle « Conway’s Reverse Game of Life 2020 »
Il 1º settembre 2020, Kaggle rilancia una precedente competizione "Conway’s Reverse Game of Life" con regole migliorate. La nostra posizione finale in questa competizione è una combinazione di tecniche diverse, e vi mostrerò un approccio che ha aiutato la squadra ad arrivare alla seconda posizione : un algoritmo genetico che ho scritto da zero. Molte delle migliori soluzioni erano basate su una ricerca sistematica di una soluzione che richiedeva migliaia di ore di CPU. Questo approccio innovativo e performante raggiunge una top 10 dopo aver eseguito solo 4 ore su una GPU.
Questo post del blog presenterà :
descrizione del concorso
come implementare un algoritmo genetico in python con python e la pytorch del framework di deep learning
risultati di tale attuazione
Descrizione concorso
Descrizione ufficiale del concorso disponibile sul sito Kaggle e parafrasata in questa sezione per facilitare la lettura :
Il gioco della vita è un automa cellulare creato dal matematico John Conway nel 1970. Il gioco consiste in una tavola di cellule che sono accese o spente. Si crea una configurazione iniziale di questi stati on/off e si osserva come si evolve. Ci sono quattro semplici regole per determinare lo stato successivo del tavolo da gioco, dato lo stato attuale :
1/ Sottopopolazione : se una cellula vivente è circondata da meno di due cellule vive, muore.
2/ Stasi : se una cellula vivente è circondata da due o tre cellule vive, sopravvive.
3/ Sovrappopolazione : se una cellula vivente è circondata da più di tre cellule vive, muore.
4/ Riproduzione : se una cellula morta è circondata da esattamente tre cellule, diventa una cellula viva.
Queste semplici regole risultano in molti comportamenti interessanti e sono stati al centro di un grande corpo di matematica. Come afferma Wikipedia :
Fin dalla sua pubblicazione, Conway’s Game of Life ha attirato molto interesse, a causa dei sorprendenti modi in cui i modelli possono evolversi. La vita fornisce un esempio di emergenza e di auto-organizzazione. È interessante per gli informatici, fisici, biologi, biochimici, economisti, matematici, filosofi, scienziati generativi e altri osservare il modo in cui modelli complessi possono emergere dall'applicazione di regole molto semplici. Il gioco può anche servire come analogia didattica, utilizzata per trasmettere la nozione un po' contro-intuitiva che "design" e "organizzazione" possono emergere spontaneamente in assenza di un progettista. Per esempio, il filosofo e scienziato cognitivo Daniel Dennett ha usato l'analogo dell'"universo" della Vita di Conway per illustrare ampiamente la possibile evoluzione di complessi costrutti filosofici, come la coscienza e il libero arbitrio, dalla relativamente semplice serie di leggi fisiche deterministiche che governano il nostro universo.
L’emergere dell'ordine da semplici regole genera una domanda interessante - cosa succede se regoliamo il tempo ?
Questa competizione è un esperimento per vedere se l'apprendimento automatico (o l'ottimizzazione, o qualsiasi metodo) può predire il gioco della vita al contrario. L'inizio caotico della Vita è prevedibile dalle sue estremità ordinate ? Kaggle ha creato molti giochi, li ha evoluti e ha fornito solo i tabelloni finali. Ci viene chiesto di prevedere il tabellone di partenza che ha portato a ogni tabellone.
Come funziona un algoritmo genetico ?
Gli algoritmi genetici sono tra le tecniche più affascinanti per l'ottimizzazione dei problemi. Si ispirano alla teoria dell'evoluzione naturale di Charles Darwin.
Come funziona l'algoritmo genetico :
1/ In primo luogo, l'algoritmo crea una popolazione iniziale casuale di individui.
2/ Punteggi ogni individuo della popolazione attuale calcolando quanto bene si risolve il problema.
3/ Seleziona individui, chiamati genitori, in base ai loro punteggi.
4/ Alcuni degli individui nella popolazione attuale che hanno un punteggio inferiore sono scelti come elite. Questi individui d'élite sono passati alla popolazione successiva.
5/ Produce figli dai genitori. I figli sono prodotti o facendo cambiamenti casuali - mutazione - o combinando le voci vettoriali di una coppia di genitori - crossover.
6/ Sostituisce la popolazione attuale con i bambini per formare la prossima generazione.
7/ Tornare al passo 2 a meno che non soddisfiamo un criterio di arresto.
Per questa competizione, gli individui considerati sono potenziali schede al loro stato iniziale. Per sfruttare appieno il pytorch, la popolazione è immagazzinata in un singolo tensore booleano con dimensioni (number_of_individuals, N, N) dove N è la dimensione di una tavola ; N=25 per questa competizione.
Popolazione iniziale casuale
Creare una popolazione iniziale casuale fatta di schede n_parents di dimensioni Nxn. Ho anche incluso un iper-parametro per impostare il numero di cellule vive (20% nel codice campione di seguito).
Punteggio individui
La metrica del concorso è definita nella sezione di valutazione del concorso :
Si sono valutati l'errore assoluto medio delle previsioni, fatto un passo avanti dal specificato, e rispetto alla soluzione finale fornito.
In altre parole, per segnare un individuo, dobbiamo applicare le regole del gioco della vita a questa tavola e contare quante cellule sono diverse dalla soluzione di destinazione.
Nota : ogni cella è espressa con un booleano, quindi calcolare l'errore assoluto per ogni cella tra l'input (tabellone dopo l'applicazione del gioco delle regole di vita) e il target può essere fatto con un solo xor. Allora possiamo calcolare il punteggio per tutti gli individui all'interno della popolazione con una somma solo sulle ultime due dimensioni del tensore.
Applica le regole del gioco della vita
Il primo passo è quello di determinare per ogni cellula quanti dei suoi vicini diretti sono vite. Per contare i vicini, stiamo usando una semplice convoluzione 2D su tutto il tabellone.
Note :
Sto usando float16 (precisione mista) in quanto offre una velocità x2 su RTX NVIDIA GPU. In t8 avrebbe offerto una velocità di x4 ma al momento della scrittura, pytorch non supportava la convoluzione con questo tipo.
Incrocio
Stiamo combinando le informazioni genetiche di due genitori per creare un nuovo individuo. La scelta casuale delle celle fra i due genitori era meno efficiente della sostituzione di una regione completa di un genitore con le celle da un altro genitore. Questo è il motivo per cui sto usando maschere di 17x17 quadrati casuali. Le cellule al di fuori del quadrato sono prese dal primo genitore e le cellule all'interno del quadrato sono celle dal secondo genitore. Per migliorare la velocità, 625 maschere vengono generate in anticipo e mantenute in memoria GPU e vengono scelte casualmente per ogni nuovo individuo.
Mutazione
Capovolgiamo casualmente le cellule dei genitori dal vivo alla morte e viceversa, con una probabilità di MUTAZIONE.
Risultati
I risultati di questa implementazione sono abbastanza buoni in quanto raggiunge la nona posizione nella competizione leader-board eseguendo meno di 4 ore sulla GPU del mio computer (9 ore sulla GPU di Kaggle). Il punteggio continua a migliorare se eseguiamo l'algoritmo più a lungo (ad esempio aumentando la dimensione della popolazione).
L'implementazione è anche efficiente in memoria in quanto possiamo far crescere la popolazione fino a 1 milione di individui su una GPU da 11GB.
Conclusione
Abbiamo visto come implementare da zero un algoritmo genetico su GPU usando pytorch. È una soluzione abbastanza performante sia in termini di velocità che di risultati.
Ho imparato molto lungo il percorso su algoritmo genetico, pytorch e come ottimizzare il calcolo sulla GPU.
Vorrei ringraziare i miei fantastici compagni di squadra : Konstantin, Robert e Maximiliano per i loro grandi approcci che spingono la squadra alla seconda posizione.
Codice sorgente completo
L'implementazione è disponibile come notebook Kaggle :
Così come sul mio repository di Github :
Referenze
Fonte (articolo di origine) : https://towardsdatascience.com/reverse-arrow-of-time-with-genetic-algorithm-and-gpu-1871a7b4fff8
Commentaires