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?