Evoluzione di Automi Cellulari

La tesi é pensata essenzialmente su due livelli. Una prima parte, teorica, che raccoglie le principali nozioni relative agli automi cellulari e agli algoritmi genetici, a cui ne segue una seconda, sperimentale ed applicativa, in cui si sono tradotte in algoritmo le idee dell'articolo 'Evolution of Communication with a Spatialized Genetic Algorithm' di Patrick Grim, Trina Kokalis, Ali Tafti, e Nicholas Kilb, oltre all'aggiunta di spunti innovativi. Più nel dettaglio, nel primo capitolo si introducono gli automi cellulari, tra i più semplici modelli matematici possibili, dotati di caratteristiche discrete e locali. Si tratta di una semplice introduzione, con lo stretto indispensabile per affrontare i capitoli successivi. Nel secondo capitolo, invece, vengono presentati nel dettaglio gli algoritmi genetici, lo strumento per eccellenza usato per evolvere un automa cellulare, per riuscire cioè a trovare nel vasto numero di regole di transizione possibili, quella che meglio performa un obiettivo scelto. Ad una prima esposizione intuitiva, corrisponde una più ricca e precisa analisi nella parte finale del capitolo. Una particolare attenzione è qui data infatti alla teoria degli schemi, a quella dei blocchi costitutivi e alle critiche a queste teorie. Il capitolo 'approfondimenti' focalizza l'attenzione su tre possibili varianti implementabili in un algoritmo genetico: gli algoritmi genetici self-adaptive, quelli cellulari, e quelli dotati di più intorni. Il capitolo quarto illustra poi le principali applicazioni di quanto scritto in precedenza. Vengono solamente citati gli innumerevoli campi pratici in cui essi sono stati impiegati con successo, per poi in particolare concentrare l'attenzione sul 'problema della densità', tra i più studiati in letteratura a questo proposito. L'ultimo capitolo, 'Evoluzione di strategie comunicative', è dedicato allo studio dell'articolo sopra citato. Si sono riprodotti tutti gli esperimenti e gli studi condotti in passato, e contemporaneamente si sono aggiunte riflessioni personali ed innovative, corredate da alcune verifiche sperimentali. Infine, sono riportati gran parte degli algoritmi utilizzati, direttamente implementabili in Matlab.