Reti neurali attraverso algoritmi genetici in C++. Parte II
23 November 2008 da Francesco
Algoritmi genetici.
Gli algoritmi genetici sono algoritmi particolari che si ispirano all’evoluzione naturale delle specie descritta da Darwin. Essi sono molto utilizzati nel risolvere problemi nei quali lo spazio di ricerca delle soluzioni non è ben definito e garantiscono sempre un avvicinamento alla soluzione ideale del problema. In un algoritmo genetico ogni individuo (cromosoma) possiede un DNA che rappresenta una potenziale soluzione del problema. Una popolazione di un certo numero di individui con DNA casuale viene creata e su di essa agiscono varie operazioni atte a simulare la selezione naturale per scegliere via via quelli che più si avvicinano alla soluzione desiderata. Il DNA di ogni individuo è in genere una soluzione del problema codificata in modo da facilitare le operazioni genetiche che bisogna fare su di essa (crossover, mutazioni genetiche, etc…, le vedremo fra poco).
Per fare un esempio, potremmo scegliere di creare un algoritmo genetico che cerchi due numeri interi che diano come somma il numero (intero) passatogli in input. Un esempio di DNA per questo algoritmo potrebbe essere il seguente:
00010100
Dove le due quartine rappresentano i due numeri da noi cercati codificati in forma binaria. La forma binaria non è l’unica possibile per codificare il DNA, infatti ognuno potrebbe scegliere di usare un’altra codifica, ma nel caso appena descritto si rivela abbastanza comoda (anche perchè è di facile decodifica). Ora abbiamo visto come si codifica il DNA, ma come avviene l’evoluzione? Vediamolo.
All’inizio viene creata una popolazione di individui con DNA casuale e ogni individuo di questa popolazione viene valutato, cioè gli viene dato un punteggio più o meno alto in base a quanto si è avvicinato alla soluzione che cerchiamo. Qui entra in gioco una delle parti più importanti nell’algoritmo genetico e cioè la funzione di fitness. Il fitness è proprio il punteggio ottenuto da ogni individuo e questa funzione serve a calcolarlo. Nel nostro caso è molto facile creare una funzione di fitness: per assegnare un punteggio basta semplicemente fare la differenza in valore assoluto tra il numero desiderato in output e il numero ottenuto tramite la somma dei due numeri codificati. Supponiamo di volere il numero 12 come output e di avere due cromosomi con il seguente DNA:
1) 00010010
2) 01000101
Il primo codifica i numeri 1 e 2 in forma binaria (0001 == 1, 0010 == 2) mentre il secondo i numeri 4 e 5 (0100 == 4, 0101 == 5). Ilcromosoma 1) da come risultato 3 mentre il 2) da come risultato 9. Se calcoliamo il fitness semplicemente facendo la differenza il primo avra’ un fitness di 121= 11, mentre il secondo 129= 3. Chiaramente nel nostro esempio il fitness più basso corrisponde al cromosoma migliore e un fitness pari a 0 corrisponde all’aver raggiunto la soluzione perfetta. La funzione di fitness in questo caso è molto semplice, ma spesso è un fattore determinante per la buona riuscita di un algoritmo genetico: scegliere una funzione di fitness al posto di un’altra puo’ cambiare drasticamente i risultati!
Dopo aver calcolato il fitness per tutti gli individui della popolazione, si passa alla riproduzione. La riproduzione avviene emulando la selezione naturale e cioè facendo sopravvivere gli individui più forti (quelli con il fitness migliore) ed eliminando quelli più deboli. Durante la riproduzione avvengono anche i fenomeni del crossover e della mutazione che servono a creare varietà genetica (altrimenti i cromosomi resterebbero sempre gli stessi) e che vedremo fra un istante.
Gli individui da far riprodurre non posso essere scelti casualmente, perchè altrimenti non si assisterebbe mai ad un miglioramento con il passare delle generazioni (ah, per generazione si intende ogni ciclo completo di riproduzione), perciò esistono vari metodi di selezione e noi useremo quella che viene chiamata selezione a torneo (tournament selection). Giusto per la cronaca, un altro dei metodi di selezioni molto utlizzati è la “roulette wheel selection” che assegna ad ogni cromosoma una probabilità di essere selezionato direttamente proporzionale al suo fitness. La selezione a torneo consiste nello scegliere casualmente N individui dalla popolazione di partenza e di confrontare il loro fitness: quello con il fitness migliore viene scelto per la riproduzione. La selezione a torneo permette di variare facilmente la pressione selettiva: più è alto il numero N degli individui partecipanti al torneo è più basse saranno le possibilità di riproduzione degli individui con fitness basso (con basso intendo semplicmente peggiore e non minore numericamente, perchè come abbiamo visto, nel nostro caso, un fitness minore equivale ad un punteggio migliore).
Gli individui con fitness basso, sono comunque tutt’altro che inutili perchè in seguito alla ricombinazione genetica, possono fornire materiale utile alla ricerca della soluzione (leggete più avanti per averne un esempio). In genere vengono scelti due cromosomi alla volta (e quindi vengono effettuati due “tornei”) e da loro nascono due nuovi individui. I figli, se così si possono chiamare, non avranno lo stesso patrimonio genetico dei genitori (altrimenti non assisteremmo mai ad un miglioramento e l’individuo migliore della prima generazione resterebbe sempre il migliore per tutte le generazioni seguenti) ma avranno un patrimonio che deriva dal loro in seguito ad alcune modifiche. Ad introdurre queste modifiche sono due operatori genetici: il crossover e la mutazione. Chi ha studiato un po’ di biologia dovrebbe conoscere almeno in linea teorica il crossover: esso avviene quando due cromosomi si rompono in un determinato punto e si scambiano una parte di DNA. Supponiamo di avere due cromosomi:
1) 00100 100 ( 2 + 4 = 6 ) fitness = 6
2) 00011 010 ( 1 + 10 = 11 ) fitness = 1
e supponiamo di scegliere come punto di rottura quello indicato dalla freccia. Effettuando il crossover nasceranno due figli con i seguenti DNA:
1a) 00100010 ( 2 + 2 = 4 ) fitness = 8
2b) 00011100 ( 1 + 12 = 13 ) fitness = 1
che come vedete sono l’incrocio dei due DNA precedenti. Il crossover è fondamentale perchè puo’ produrre nuovi cromosomi che si avvicinano molto di piu’ alla soluzione: nell’esempio il cromosoma 2b) dà come risultato 13 che è quasi la soluzione che cercavamo. E’ interessante notare come, in questo caso, un individuo con fitness basso (il cromosoma 1) con fitness 6) abbia contribuito in maniera fondamentale al raggiungimento della soluzione. Generalmente il crossover non avviene sempre, ma si stabilisce una probabilità (il 70% va bene) con cui farlo avvenire. Dopo aver creato i due nuovi individui su di essi agisce un altro operatore genetico, la mutazione, che effettua un cambiamento su un singolo gene del DNA. Se il DNA è codificato in forma binaria la mutazione non fa altro che trasforamare uno 0 in un 1 o viceversa. Anch’essa non si verifica in ogni riproduzioni ma ha una probabilità che in genere è molto piu’ bassa rispetto a quella del crossover. Questo procedimento di riproduzione si ripete fino a che la nuova popolazione non ha un numero di individui pari a quella vecchia e poi si ricomincia tutto da capo: si rivaluta il fitness dei nuovi individui (se tutto va bene troveremo qualcuno con un fitness migliore), si effettua una nuova riproduzione, etc… tutto questo si ripete fino a che non troviamo una soluzione accettabile al nostro problema.
Probabilmente sarete un po’ confusi, e ora vi starete chiedendo cosa c’entrino gli algoritmi genetici con le reti neurali. Fra un secondo vi sarà tutto più chiaro. Abbiamo detto che la parte fondamentale per ottenere risultati esatti con una rete neurale è trovare una configurazione ottimale dei pesi e sarà proprio per trovare i valori di tutti i pesi della rete che useremo gli algoritmi genetici. Il DNA dei nostri cromosomi rappresenterà i pesi della rete e via via cercheremo di individuare soluzioni migliori facendo riprodurre quei cromosomi il cui DNA fornisce risultati con un errore più basso quando viene eseguito nella rete. In pratica prendiamo un cromosoma e sostituiamo il suo DNA ai pesi della rete e verifichiamo quant’è l’errore prodotto: in questo caso la funzione di fitness corrisponde semplicemente all’errore, ed anche qui cromosomi con fitness più basso (e quindi con errore più basso) saranno migliori. C’e’ da notare anche che il DNA non verra codificato ma sarà costituito da un semplice vettore di double che contiene tutti i pesi di tutti i neuroni della rete neurale.
La parte sugli algoritmi genetici è terminata e spero che quello che ho scritto sia sufficiente a farvi capire quello che implementeremo. Consiglio ancora una volta a chi non ha ben chiari questi concetti di leggere alcuni dei tuorial sugli algoritmi genetici consigliati in fondo e soprattutto, di provare a realizzare una propria implementazione di un piccolo algoritmo genetico perchè può aiutare molto.
Tags: Algoritmi genetici
Pubblicato in Informatica | Commenti (5)
22 December 2008 alle 06:46
Ciao,
innanzi tutto complimenti per la guida!!!
Volevo solo chiedereti una cosa: su dove scrivi che 0011+ 0100 equivale a 2+4, lo 0011 (che starebbe per “2″) non dovrebbe essere 0010 (o non c’ho capito una mazza?)
ciao e grazie.
23 December 2008 alle 17:56
Ciao,
grazie per i complimenti
Effettivamente e’ giusto quello che dici, ho corretto proprio ora cambiando i DNA.
Ciao e grazie per la segnalazione.
30 April 2009 alle 06:39
ciao, complimenti per questo tutorial: mi ha chiarito davvero le idee
8 July 2009 alle 08:15
Ciao,
bel tutorial!
Non riesco a trovare l’archivio con il codice sorgente dentro?
dove si trova?
grazie
delo
8 July 2009 alle 08:24
scusa, ho trovato il link nella parte VI
delo