M.S. Project – Functional Analysis of Cellular Automata

This project was prepared to satisfy the thesis requirement for the Master of Science degree.  In this project, an evolutionary algorithm is used to infer the transition function for a generalized model of a two dimensional binary cellular automata.

Documents

M.S. Project Presentation (pdf export of presentation, 69 pages)

M.S. Project Report (pdf, 55 pages)

Abstract

Cellular automata are systems that consist of a number of homogenous sub-systems
(referred to as cells). Cellular automata models are used in many different disciplines
and are capable of exhibiting many different types of physical, biological, or
information-theoretic behaviors. Within a cellular automaton, each cell is associated
with a particular state. A new generation of cells are created according to some
fixed transition rule, where the next state of a cell is determined based on the state
history of some set of cells in the system (referred to as that cell’s neighborhood).
For determinate systems, the state progression of a cellular automata is uniquely
determined by its initial state, neighborhood function, and transition function. Given
only the neighborhood function of a determinate cellular automaton, one can infer
its transition function by observing the state transitions that take place and building
a lookup table that defines the transition function. However, given only observations
of the state transitions, it is difficult to infer the neighborhood function that governs
the cellular automaton. This project implements a discrete event specification model
of a general cellular automaton, uses this simulation to generate a number of different
state transition trajectories, and uses an evolutionary algorithm to search the space
of possible neighborhood functions in order to find the neighborhood function that
was originally used to generate the trajectories. Results are presented that show
the intelligent search algorithm is significantly more efficient than brute force search
under most circumstances.

%d bloggers like this: