Project Name: Using GAs to find if simple Automata of Class III or IV evolve.
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
Project Area: GAs, ABS
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
Target: CFR 2019 (not funded)
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
People Needs and Allocation: One student at Master level (Thesis)
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
Skills: Programming
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
Description:
a. Description
The goal of this work is to determine if evolutionary algorithms will find emerging living cellular automata systems. More specifically, Conway’s [1] game-of-life is a cellular automata grid based computational system that Conway created with the theory that it is the simplest cellular automata system that exhibits emergent behavior from simple rules. The question of this research, is that if Conway’s theory is true, then will evolutionary algorithms evolve this ruleset or/and find other rulesets that have emergent behavior and are simple?
That is the technical jargon description of the problem. In plain language, I want to see if evolutionary algorithms (that are based on a heuristic “survival of the fittest”) will evolve an individual (a solution) that has the same or similar characteristics as a simple computational system called Conway’s game-of-life. Or, will the solutions that evolve from our experiments find new computational systems that have emergent behavior (emergent behavior is complex global behavior coming from simple rules).
This high-level question is hard to explain further without the reader understanding a few concepts, so I will return to the description of the problem below in the Context (see Our key question…).
b. Context
The two starting concepts to understand in this research question are cellular automata (CA) and evolutionary algorithms (EAs). We will introduce these two concepts and discuss how they have been integrated in previous research.
Cellular Automata (CA) is a computational paradigm where a small computational component, typically called a cell, has a defined state and rules that will define a new state of the cell where state (St) is defined for time t and the rules (R) determine a new state (St+1) at time t+1. Cells are, typically, organized into 2D grids or 1D lines and neighboring cells state is used to determine a cells next state. The earliest of these mathematical structures was studied by von Neumann in the 1940s, but CA is popularized by Conway’s Game-of-Life [1] and Wolfram’s systematic study of CAs [2]. CA has applications in biology, computation, cryptography, and people have argued CAs have a relation to our universe. Additionally, CAs are part of complexity theory and our understanding of computation.
Evolutionary algorithms (EAs) are a meta-heuristic class of algorithms typically used to optimize a solution to a problem. For example, genetic algorithms (GAs) are used to design antennas, build artificial intelligences, place circuits designs on Integrated Chips, and to schedule air traffic at major airports among other problems. The basic idea behind evolutionary algorithms is to create a population of solutions to a problem and then to update that population based on each individuals performance on the objective. New solutions (individuals) are created by mutations and crossover operations similar to how new individuals are created in nature. This is a heuristic approach to optimizing a problem using the idea of “survival of the fittest”.
To clarify, CA, EA, and GA acronyms are similar, but CA is a computational method and EAs, including GAs (we will focus on GA from now on), are meta-heuristic algorithms that search large solution spaces for good solutions in what we call optimization problems. These two concepts, however, have been explored together in a number of ways. Since CAs compute solutions to problems in parallel, researchers have used GAs to create CA rules that can perform a particular classification [3]. Additionally, CA systems have been seeded with digital images, and GAs observe and are trained on the CA computation to build a classifier system (this is an example approach to Optical Character Recognition systems) [4].
Our key question, however, is can a GA create CA systems that fall into Class IV of Wolfram’s [1] CA classifications (not Conway’s Game of Life is Class IV CA) [5]:
•Class I. CA evolving to a homogeneous state
•Class II. CA evolving periodically
•Class III. CA evolving chaotically
•Class IV. Includes all previous cases, known as a class of complex rules
This question differs from previous research as it is more of an origin question as opposed to an application questions done in previous integrations of GA and CAs.
The three key challenges to the design of such a system and our experiments are:
1.The creation of a software framework to allow experiments to execute.
2.Determining how to structure a genetic representation of a cell that can be manipulated and optimized by a GA.
3.Automatically identifying if a CA is a Class IV CA or is heading towards a Class IV CA, which is needed as the objective function for the GAs.
The existence of the system will allow us to address some interesting research questions that include:
1.Can GAs be designed to find Class IV CAs?
2.Is Conway’s Game of Life the simplest CA based on evolution via a GA (the research question of this proposal)? If not, what is the simplest CA that is of type Class IV?
3.What techniques can be used to identify emergent behavior in agent-based simulation?
4.What are good GA techniques for crossover and mutation within this space?
5.How does GA and actual biological evolution differ in a less well defined solution space?
Questions 1, 3, 4 and 5 are interesting questions that I hope to pursue with Miami undergraduates and master students in the years following the initial problem. Question 2 is the focus of this research.
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
References:
[1] Gardner, Martin (October 1970). "Mathematical Games – The fantastic combinations of John Conway's new solitaire game "life"". Scientific American. 223: 120–123.
[2] Wolfram, Stephen. A new kind of science. Vol. 5. Champaign, IL: Wolfram media, 2002.
[3] Mitchell, Melanie, James P. Crutchfield, and Rajarshi Das. "Evolving cellular automata with genetic algorithms: A review of recent work." Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA’96). Vol. 8. 1996.
[4] Khankasikam, Krisda. "A Combined Genetic Algorithm and Conway's Game of Life for Printed Lanna Character Recognition." International Journal of Computer Theory and Engineering 5.4 (2013): 653.
[5] Martinez, Genaro J., Juan C. Seck-Tuoh-Mora, and Hector Zenil. "Computation and universality: class IV versus class III cellular automata." arXiv preprint arXiv:1304.1242 (2013).
[6] Ehret, Alan, Peter Jamieson, and Michel A. Kinsy. "Scalable Open-Source Reconfigurable Architecture for Bacterial Quorum Sensing Simulations." International conference on HEART. (2018).
[7] Gosper, R. Wm. "Exploiting regularities in large cellular spaces." Physica D: Nonlinear Phenomena 10.1-2 (1984): 75-80.
[8] Theory of Self-Reproducing Automata, John Von Neumann
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------
Resources:
- http://golly.sourceforge.net/ - Simulates Cellular Automata Game of Lifes