Overview
This Master of Science project report, completed at The University of Tennessee, Knoxville in August 2010, addresses a fundamental challenge in systems theory: inferring the functional relationships within cellular automata from observed behavior alone.
Cellular automata are computational models consisting of homogeneous sub-systems (cells) that evolve according to fixed transition rules based on the states of neighboring cells. These models have broad applications across physics, biology, and information theory, making the ability to reverse-engineer their governing rules highly valuable.
Key Contributions
Generalized DEVS Implementation
The project implements a discrete event system specification (DEVS) model capable of simulating cellular automata with arbitrary:
- State dimensionality
- Neighborhood configurations
- Transition functions
- Spatial and temporal dependencies
This generalized approach enables experimentation with diverse cellular automata configurations without modifying the underlying simulation framework.
Evolutionary Search Algorithm
The core contribution is the application of Population-Based Incremental Learning (PBIL) to the functional mask search problem. Given only observed state transitions, the algorithm:
- Represents candidate neighborhood functions as probability vectors
- Generates and evaluates candidate masks against observed data
- Iteratively refines the probability distribution toward the correct solution
- Employs entropy reduction metrics to evaluate mask quality
Experimental Results
The algorithm demonstrates remarkable efficiency compared to brute force search:
- For systems with 36 potential neighborhood members (approximately 68 billion possible masks), the algorithm achieved speedups of up to 2.2 million times faster than exhaustive search
- Median solution times of 356-2,466 generations depending on problem complexity
- High success rates in identifying correct or equivalent functional masks
Significance
This work bridges general systems theory with modern optimization techniques, providing a foundation for:
- Automated model identification from observational data
- Analysis of complex biological and physical systems
- Understanding emergent behavior in distributed systems
The methodology has potential applications in fields ranging from tumor growth analysis to traffic pattern optimization, where identifying the functional relationships between system components from observed behavior is critical.
Download
The complete project report, including detailed mathematical formalism, implementation specifics, and comprehensive experimental results, is available for download below.
Download MS Project Report (422 KB)
Citation
Coop, Robert A. “Functional Analysis of Cellular Automata.” Master’s Project Report, The University of Tennessee, Knoxville, August 2010.
Committee:
- Dr. Itamar Arel (Major Professor)
- Dr. Gregory Peterson
- Dr. Hairong Qi
- Dr. James Nutaro
