Ricordate che l'obiettivo è di progettare
un automa cellulare che prenderà
una configurazione iniziale
con una maggioranza di celle bianche e
eventualemnte finirà con tutte
bianche o, all'opposto, nere.
Una soluzione a cui poreste pensare
è di fare una maggioranza locale
in ognuna delle 7 celle vicine
così, se la maggioranza delle celle in
un vicinato è bianca
allora il centro della cella dovrebbe diventare bianco,
e allo stesso modo per il nero.
Comunque, se guardiamo al comportamento
di questo automa cellulare,
non performa in realtà questo compito.
Qui c'è un reticolo ad una dimensione
disposto in orizzontale.
Tempo 0 che inizia qui, e
e potete vedere la configurazione
iniziale casuale, e molto velocemente
le aree con una maggioranza di nero vanno al nero
e le aree con una maggioranza di
bianco al bianco
ma c'è un confine tra loro
dal momento che qui abbiamo 4 neri e
3 bainchi vicini ai 3 neri
e 4 bianchi e rimane tra neri
e bianchi il confine
nel tempo restante.
Quindi il problema è che non c'è modo,
come dire, per il gruppo a maggioranza nera
di communicare col gruppo a maggioranza bianca
e di processare la loro informazione combinata
da tutti i differenti gruppi
che insieme fanno la maggioranza
dell'intero reticolo.
La nostra sfida è di progettare
un automa cellulare che può prendere l'informazione
dalle aree locali e comunicarle
nel reticolo,
e avere quell'informazione combinata
in maniera che l'intero reticolo
può decidere collettivamente se
c'è una maggioranza, totale maggioranza,
di bianco o nero.
Non è un risultato banale.
Invece di progettarlo da soli,
quello che faremo è di usare
un algoritmo genetico per evolvere
gli automi cellulari per avere il comportamento desiderato.
Quindi questo vi apparirà familiare
dopo aver visto l'esempio dell'algoritmo genetico del robot Robby
poiché
hanno molto in comune.
Per sintetizzare di nuovo l'algoritmo genetico,
creeremo
una popolazione casuale di candidabili
regole per CA.
Il fitness di ogni automa cellulare
è quanto bene performa
la maggiornza dei compiti di classificazione.
L'automa cellulare più adatto si riproduce
con mutazioni e crossover,
e continuiamo questo processo,
per molte generazioni.
L'avete già visto prima.
Ricordate che il DNA per Robby era la sua strategia
in maniera simile, il DNA di un automa cellulare
è una codificazione delle sue regole.
Quindi se abbiamo una tabella di regola che assomiglia a questa,
assigniamo ad ogni cella bianca l'esito 0,
e ad ogni nera 1,
e la lista di 128 uno e zero
è il DNA che si evolverà.
Creiamo una popolazione di stringhe casuali
che rapprensenta la tabella di regole dell'automa cellulare
Quindi ognuna di queste stringhe
è una lista di 128 bit, o di 1 e 0.
Qui ho un centinaio di loro
ma puoi decidere quale dovrebbe essere
la dimensione della popolazione da solo.
Calcoleremo il fitness di una regola,
e il modo di farla è simile a quello di Robby.
Creiamo diversi ambienti
e testiamo la regola su questi ambienti
dove gli ambienti qui
saranno
le configurazioni iniziali del reticolo
e il fitness di una regola è la frazione
delle corrette classificazioni.
Ricordate quando dico regola qui,
intendo in realtà tabella di regole dove una regola
consiste di questi 128 stati aggiornati
che dicono all'automa cellulare quale
dovrebbe essere la cella centrale
in ogni possibile vicinato.
Qui il diagramma che vi mostra
come funziona.
Per ogni regola di automa cellulare
nella popolazione, qui c'è una di queste regole
potete creare la tabella delle regole corrispondente
qui di nuovo, e farò andare
l'automa cellulare corrispondente
usando questa regola su molti configurazioni di reticoli
iniziali casuali
qui c'è una configurazione iniziale
ed è aggiornata sulla regola.
Progettiamo un certo numero di
passi di tempo massimo per far in modo che questi aggiornamenti
prendano piede, e...
e se il comportamento di un automa cellulare
al tempo finale non è
la risposta corretta qui,
se ci fosse, per dire, una maggioranza
di celle nere, dovrebbero essere tutte nere
ma non è così. É classificato come errato.
Non c'è un credito parziale dato
per un certo numero di celle nere.
O è corretto o è errato.
Questo è errato.
Questo, invece, è corretto perché dopo
la maggiornaza di celle bianche, e dentro
il numero massimo di passi temporali
diventano tutte bianche e così via.
Il fitness è soltanto una frazione di queste
corrette classificazioni
quindi il fitness è tra 0 e 1
ora vediamo come funziona l'algoritmo
abbiamo una popolazione di
tabelle di regole casuali di automi cellulari.
Ora immaginiamo che il fitness sia stato calcolato
come segue.
Quello che accade è che le regole che si adattano meglio
sono selezionate per riprodurre loro stesse.
Per esempio, potremmo scegliere una regola 1 e
una regola 3 per i genitori.
Creeremmo una nuova generazione
via crossover e mutazione
ogni coppia di genitori
farebbe il crossover in un luogo selezionato casualmente
e i bambini prenderebbero la prima parte
da un genitore,
e la seconda parte
dall'altro genitore
e viceversa.
Quindi creeremo qui due bambini
da ognuno dei due genitori.
Faremmo alcune mutazioni casuali
se questo numero fosse selezionato per mutare
cambierebbe a 0,
e noi abbiamo due bambini
e continuiamo questo processo
di selezione dei genitori, e di creazione di bambini
finché la nuova generazione è completa.
Allora calcoliamo la fitness di
una nuova generazione e così via
continua ad iterare questo per molte generazioni
quando l'algoritmo genetico è concluso,
noi siamo nella stessa situazione
in cui eravamo nell'esempio del robot Robby.
L'algoritmo genetico ci ha dato
questa stringa di bit, 128 bit,
e dice di avere un'alta fitness.
Ma ora ci lascimo con la prospettiva
di provare a capire come funziona.