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