Evoluzione degli Automi Cellulari
con Algorimi Genetici
In questa sottounitò vi parlerò di un progetto
al quale ho lavorato diversi anni
con Jim Crutchfield
di cui non avrete mai sentito parlare, e
Rajanhi Das che lavora all'IBM Research Center.
Era un progetto sull'evoluzione
di automi cellulari con algoritmi genetici
per fare calcoli collettivi.
Ho linkato un paper,
A Review of Recent Work,
dalla pagina dei materiali del corso
abbiamo guardato ad un particolare
compito di calcolo per gli automi cellulari.
Uno che era stato proposto all'origine
da Norman Packard.
Il computo è di disegnare un automa cellulare
che decide se
la configurazione iniziale delle celle ha
una maggioranza di celle nere o meno.
Quindi qui l'immagine,
c'è una configurazione iniziale
di un automa cellulare ad una dimensione
dove ci sono 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11 celle
e sei di loro sono nere,
quindi c'è la maggiora di celle nere.
Il comportamento desiderato sarebbe
dopo un certo numero di passaggi per
l'intero reticolo di diventare nero.
In maniera simile, se iniziate con la maggioranza di
celle bianche, otterete che l'intero reticolo
diventi bianco al successivo passo.
É semplice da descrivere
il compito di calcolo, ma variazioni di questo hanno
importanti applicazioni nel calcolo,
in maniera particolare nel campo della distribuzione di calcolo.
Quindi la domanda è:
come ottengo un automa cellulare
per fare questo? Allora, un modo per farlo è
che se avete un computer standard o tradizionale
che ha un'unità centrale per processare
e accesso casuale alla memoria
non è difficile progettare un programma
che risolvi una maggioranza di celle nere
o la maggioranza di celle bianche immagazzinate
da qualche parte nella memoria.
Tutto quello che fareste è scrivere un programma che
vada a questi localizzazioni di memoria,
contare il numero di celle nere,
usare un contatore centralizzato,
e un posto centralizzato nella memoria per mantenere
il conto, e vedere qual è più grande.
Ma ricordate che gli automi cellulari
non hanno un controllo centralizzato
non hanno alcun accesso casuale alla memoria.
Hanno solo celle individuali
che sono connesse con i loro vicini
quindi, non è immediatamente chiaro
come progettare un automa cellulare
per compiere questo compito.
Come detto prima, ci sono
256 automi cellulari elementari.
Sappiamo quello che fanno,
quel è il loro comportamento, e sappiamo
che nessuno di loro compie questo compito.
Come si evince, gli automi cellulari
dove ogni cella ha 4 vicini
anche i due più prossimi da entrambi i lati
non performano questo compito.
Quindi guardiamo agli automi cellulari,
nei quali ogni cella ha 6 vicini,
i tre più vicini da ogni lato
la tabella delle regole per questo tipo
di automi cellulari dà tutte
le possibile configurazioni di vicinato
di 7 celle, e specifica
per ogni configurazione quale stato aggiornato
dobrebbe essere della cella centrale al
passo successivo.
Un quiz rapido,
il nostro quiz ha due domande,
entrambe di calcolo e spero
che vi abutuiate a queste.
La prima domanda è
per un automa cellulare come questo
con sette celle di vicinato,
quante possibili
configurazioni di vicinato ci sono?
E la seconda domanda è:
quanti diverse tabelle delle regole per gli automi cellulari
ci sono per 7 celle
di vicinato?