Neural Network Walker

Il progetto

Realizzare un programma che impari a muoversi lungo un determinato percorso e che diventi quindi capace di completare qualsiasi percorso dello stesso tipo.

Come funziona

Il programma deve imparare a completare un percorso che é fatto come un corridoio. A ogni movimento avrá quattro mosse a disposizione (su, giú, destra, sinistra) ma soltanto una direzione sará libera.
L'obiettivo é trovare una rete neurale che dica al programma qual'é la mossa da fare esaminando lo spazio vicino.
La rete neurale che cerco ha quattro neuroni input e quattro neuroni output.
I quattro input sono i quattro blocchi adiacenti al punto in cui si trova nel percorso e possono assumere due valori: +1 se il blocco é libero, -1 se é un muro o se é giá stato percorso.
I quattro neuroni output invece rappresentano le quattro possibili direzioni da prendere.
Il programma deve trovare i weights piú adatti affinché ogni output di direzione sia attivato dal giusto input di blocchi circostanti.


Esempio di rete neurale funzionante

L'algoritmo

L'algoritmo si divide in due parti: l'allenamento e il test.

Nella prima parte il programma cerca di completare il percorso di allenamento: un percorso piuttosto breve, ma che coinvolge almeno una volta tutte le mosse disponibili.
Imposto un algoritmo genetico con una popolazione da 100 individui, dove ogni individuo é un pacchetto di 16 weights per la rete neurale:
Genero random la prima popolazione, valuto l'individuo che é arrivato piú lontano dal punto di partenza e a partire da questo genero una nuova popolazione, dove ogni figlio muta alcuni dei weights. Anche di questa generazione trovo il migliore e lo faccio mutare. Ripeto il ciclo fino a quando il percorso non viene completato. Al completamento testo l'individuo.


Percorso di allenamento

La seconda parte verifica che l'individuo trovato effettivamente funzioni: viene generato un percorso casuale di 500 blocchi e viene usata una rete neurale con i weights dell'individuo per trovare la direzione a ogni passo. Se il percorso non viene completato senza errori, ricomincia la fase di allenamento.