Per evolvere le strategie con un algoritmo genetico
ci occorre codificarle in modo che
l'algoritmo genetico le possa trattare
quindi ecco come funziona. Quindi ricordate nel nostro esempio la strategia
con tutte le situazioni possibili rappresentate.
E c'è un'azione per ogni situazione possibile
ciò che ora possiamo fare, è prendere la lista di azioni
e ricordare
l'ordine delle possibili 243 situazioni.
Possiamo tagliare queste azioni e ricordare che la prima azione
corrisponde alla prima situazione
in cui tutto è vuoto. La seconda azione corrisponde alla seconda
situazione in cui tutto è vuoto eccetto
per la lattina nel sito corrente e così via.
Ora possiamo prendere questo elenco
di azioni e codificarle secondo
un codice numerico. Darò a ciascuna
azione un numero che è il suo codice.
Un numero da 0 a 6, e possso codificare questa
particolare strategia sostituendo il codice
per ciascuna altra azione nella lista.
Qui un 0 in questa prima posizione significa che
la prima situazione che è
tutto vuoto corrisponde all'azione di muoversi a Nord,
un 6 qui significa che la terza situazione
qualunque essa sia, nel nostro elenco ordinato,
corrisponde all'azione di muoversi casualmente e così via.
In questo modo abbiamo una lista di numeri
che rappresenta una strategia specifica.
Quando Robby sta per fare un'azione, lui osserva la sua situazione,
ricorda l'elenco delle situazione possibili
e dice ad esempio: "sono nella 201"
quindi guarda nella lista per la situazione 201
e capisce a che cosa corrisponde in termini di
azione da fare e fa questa azione.
E lo fa ancora ed ancora. Quindi ecco come lavora
con una strategia codificata,
e quindi potete pensare a questa strategia in senso molto metaforico
come se fosse il DNA di Robby che si evolverà,
questa lista di numeri. E questa lista ovviamente ha 243 valori,
quindi potete pensare a ciascuno di questi numeri come
un particolare gene e potete dire che Robby ha 243 geni.
Ovviamente l'analogia con la genetica non
significa che sia esatta, significa solo che è una sorta di semplice
concetto. Ok adesso una domanda:
quante possibili strategie ci sono per questa rappresentazione?
Noi vorremmo trovare una buona strategia ma la domanda è
quante ne dobbiamo considerare per trovarne una buona?
Possiamo domandarci quante ce ne sono. Se guardiamo a
243 posizioni differenti
e in ciascuna posizione ci possono essere sette azioni differenti
poiché qui abbiamo un numero da 0 a 6 che può andare qui.
Allora il numero totale di strategie possibili è
7 per 7 per 7 per ciascun numero possibile che possiamo mettere
in ciascuna posizione
243 volte, quindi la risposta è uno sbalorditivo 7 elevato alla 243
che è un numero astronomico
che non si può sperare di raggiungere nella vita e nemmeno
nella vita dell'intero universo.
E' un numero impossibile e nessuno
potrebbe cercare in questo numero di strategie possibili
e l'obiettivo è avere un algoritmo genetico
che cerca in modo intelligente in questo grande spazio
per una buona strategia. Siamo finalmente pronti a
capire come usare un algoritmo genetico per evolvere le strategie.
La prima cosa che faremo è generare
200 strategie casuali. Qui ho preso il numero 200
in modo arbitrario, è il numero delle strategie completamente casuali della
popolazione iniziale
di strategie. Quindi ecco una lista,
Quando ho eseguito il GA, esso
ha generato 200 individui. Per ciascun individuo c'è una strategia che farà
la sua sequenza di 243 numeri
Ciascun numero tra 0 e sei, in modo che possiate vedere che
sono casuali speriamo che lo siano.
Ok, adesso calcoleremo l'adattamento
di ciascuna strategia, con Robby che usa questa strategia per
fare un mucchio di azioni
in questo modo pieno di lattine vuote
e lo chiamerò ambiente
una configurazione particolare di lattine in questo mondo.
Iniziamo mettendo le lattine in modo casuale
poi lasciamo che Robby segua una particolare strategia per un certo numero di azioni
che farà. Calcoliamo la ricompensa meno le penalità
e lo facciamo ancora per un ambiente diverso che è una
configurazione diversa di lattine.
Lo facciamo molte volte e ciò che misura la strategia particolare
è la media di ricompense meno penalità
tra tutti questi differenti ambienti. A questo punto
abbiamo calcolato l'adattamento separatamente per 200 diverse
strategie e ora la parte divertente è
dove le coppie creano la prole una "ricombinazione sessuale"
scritto qui tra vigolette perché
sono stringhe di numeri in un computer
con mutazioni casuali. Più i genitori sono ben adattati
più prole creano. Quindi adesso noi prendiamo
due stringhe in modo da avere con una probabilità più alta
di scegliere quelli meglio adattati.
Ora creerò la prole scegliendo in un punto qui
nella stringa, dividendola in due
e la prole sarà questa:
la prima parte dal genitore 1 e la seconda parte dal genitore 2.
Ok, quindi ho fatto il figlio semplicemente
copiando parte del parente 1 e parte del 2 per creare il figlio
e poi nel figlio alcune posizioni
casuali saranno cambiate
cambiando questi due numeri tra 0 e 6,
quindi cambio casualmente alcuni numeri
e ora abbiamo il figlio. E continuiamo ancora e ancora così
fino a che abbiamo una nuova generazione.
Le vecchie generazioni muoiono completamente e quindi iniziamo di nuovo
al passo 2 con la nuova generazione
e facciamo ciò per tante generazioni
fino a che siamo contenti con la strategia che il GA ha trovato
o fino a che ci siamo stancati, poi usciamo.
Voglio farvi notare che il massimo di adattamento possibile di una strategia
è circa 500
perché ci sono in totale 100 quadrati
nel mondo di Robby e ogni volta che Robby inizia in un ambiente
ci sono circa 50 lattine, che è la metà dei siti
in cui ho le lattine. A volte è meno di 50 e a volte è di più
perché è casuale, ma la media è 50
e ciascuna lattina vale 50 punti
e quindi il punteggio massimo
che Robby può ottenere è circa 500
Prima di eseguire il GA
ho fatto una strategia manuale
la strategia più semplice che potevo pensare
cioè che se c'è una lattina nel sito la raccolgo
altrimenti se ce n'è una in un sito adiacente mi muovo lì
altrimenti scelgo una direzione casuale
e quindi ho implementato questa strategia
come una stringa di 243 valori.
Ho scritto un buon programma per fare questo. Poi
Robby ha usato questa strategia per raccogliere lattine in un numero di
ambienti diversi e ha preso il suo punteggio medio
in un numero di differenti ambienti e
l'adattamento medio è stato 346 di
circa 500 massimo possibile.
Ok, quindi non male.
Ma poi ho implementato l'algoritmo generico e l'ho eseguito
così come vi ho spiegato e ho trovato che
il suo adattamento medio è migliore
è 486
quasi perfetto. Quindi la domanda era
perché l'algoritmo genetico ottiene più
di me. Cosa fa,
per fare così bene?
E' una domanda non banale a cui rispondere.
Conosco la logica dietro alla mia strategia ma l'algoritmo genetico
alla fine della sua esecuzione fornisce una stringa
di 243 numeri e dice che la mia strategia
questa lavora bene, ha un buon adattamento,
ma è difficile per noi vedere esattamente come lavora
è una cosa analoga al genoma umano
sapete che il genoma umano è una sequenza, noi conosciamo
qual'è la sequenza, ma c'è
un grande salto tra questo e
sapere come funzionano le sequenze, queli funzioni hanno,
come i geni diversi danno luogo a diverse funzioni.
Quindi per osservare la strategia dell'algoritmo genetico
prima ho fatto lo schema per eseguire l'algoritmo genetico
disegnando l'andamento del migliore adattamento nella popolazione
come una funzione della generazione.
Come il tempo cresce, vedete come
i migliori individui nella popolazione migliorano.
Questa è la versione che
ho implementato in C,
sarete capaci di giocare con la versione che ho implementato in NetLogo
ma in verità è molto lenta
Quindi ho eseguito il C per avere questi risultati.
Quindi potete vedere che la prima generazione
si adatta molto lentamente è sotto lo 0
è negativa e vedremo il perché in un minuto.
Ma, molto velocemente, l'individuo migliore nella popolazione
inizia ad avere un adattamento più elevato
sapete che ciascuna generazione di una popolazione intera ruota in modo che
gli individui sono diversi in ciascuna generazione
l'adattamento rimane lo stesso per un po' e poi
ha un salto ripido fino a che non raggiunge un altro plateau
e fa un altro salto
tutte queste piccole variazioni
ci sono perché l'adattamento ha una componente di casualità
perché le lattine sono generate casualmente.
Le lattine non sono sempre lo stesso numero
e il layout delle lattine cambia da ambiente ad ambiente in modo
che hai diverso adattamento per lo stesso individuo
una diversa generazione perché si fanno tentativi su diverse configurazioni