Click here to Skip to main content
Click here to Skip to main content

Using an evolutionary algorithm to create a cellular automata

, 10 Mar 2014 Apache
Rate this:
Please Sign up or sign in to vote.
Use a Human Based Genetic Algorithm (HBGA) to create new and interesting cellular automata similar to Conway's Game of Life.

Introduction

A cellular automation uses a relatively simple algorithm to produce very complex patterns. These patterns are often visualized graphically. One of the most famous cellular automata is also the most simple. Conway's Game of Life can produce very complex patterns using only four rules. You can see my Javascript implementation of Conway's game of life here.

The goal of this article is to produce new and interesting cellular automata using a very simple cellular automata. I created a cellular automata named "Merge Physics" for my book Artificial Intelligence for Humans Volume 2: Nature Inspired Algorithms. I am currently in the process of writing this book. If you are interested in other cellular automata or nature inspired algorithms I encourage you to check out the book. Parameters to this Cellular Automata are discovered using a Human Based Genetic Algorithm (HBGA) this allows the user to direct the genetic operators such as crossover and mutation by controlling part of the selection process.

This very simple cellular automation contains 16 numeric constants that define how the universe performs. Different combinations of these numeric constants can produce some very interesting patterns. Some of these patterns are shown here.

Here is a very simple pattern that produces slowly growing purple blobs. The purple blobs are enclosed by a membrane, but have no degree of internal structure. This universe ultimately stabilizes.

The universal coordinates for the above "purple blob" universe are: (note, if you save this to a file to open in the Multiverse viewer, make sure there are no line breaks!)

[0.8500022604957287, -0.018862014555296902, -0.5920368462156294, 0.6025118473507605, -0.25332713280631114, -0.9442865152657809, 0.8385370421691785, 0.11515083295327955, 0.07865610718434457, -0.4461260674309575, 0.6233523022386354, -0.10991833670148407, 0.9372981778896297, 0.7423301656036665, 0.1214234643293226, 0.02417402657410897] 

The red universe below is one of my favorites (at least that I've discovered so far). There is quite a bit going on. This universe somewhat resembles a colorful version of Conway's game of life. However, space ships, guns and rakes abound! It is a very "busy" universe and rarely converges to a static state. There are also "cellular" structures that move about seemingly randomly. However, only the initial state is random. Everything else in Merge Physics is deterministic.

The universal coordinates for the above "red" universe are: (note, if you save this to a file to open in the Multiverse viewer, make sure there are no line breaks!)

[0.7975713097932856, 0.04290606443410394, -0.24797271002387022, 0.9078879446367496, 0.15307785453690795, 0.023971186791761356, 0.9064792766828782, -0.5248003131303094, -0.1456779635182246, 0.6998501852403781, -0.0026800425987849597, -0.8630977046192441, 0.06143751170130951, 0.8228374543146946, -0.11483923870647716, 0.6399758923339068] 

The yellow universe below is very "cell like". The cells have defined membranes, and are very much "in motion". Unlike the red universe (above) the cells do not move in strict horizontal or vertical directions. Rather, their movement is much more erratic in all directions.

The universal constants for the above "yellow" universe are: (note, if you save this to a file to open in the Multiverse viewer, make sure there are no line breaks!)

[-0.038821037762545973, -0.3142147390849097, -0.4104619476815943, 0.4183241126600188, -0.23956236782497298, 0.14375811274050476, 0.3601983851635112, 0.3609610607498582, -0.41685577251143485, -0.7590146203427757, 0.6837570487449369, -0.47571372942534185, 0.7636214557318858, 0.8853821669366322, -0.42507331035926454, 0.6800271811144061] 

If you would like to see the above three universes in motion, you might want to check out the following You Tube video. This video also teaches you to use the Multiverse Viewer.

[Multiverse Viewer Tutorial]

Background

There are a number of different terms that are often used to describe cellular automata and genetic algorithms. I will define those now, as I use them in this article.

Cell: One "grid square" in a universe. Each cell has a 3-sized vector that represents an RGB color. Each element of this vector ranges between -1 and 1. The value -1 means the color component is fully off, whereas the value of 1 means the color component is fully on.

Crossover: When two parents produce an offspring genome that contains some elements from both parents.

Genome: A genome is one life form in a genetic algorithm's population. Genomes are usually vectors of a fixed length. For this article genomes are the physics vectors of size 16.

Mutation: Mutation is when a single parent produces an offspring. The offspring genome vector will contain a vector that represents a slight distortion of the single parent.

Physics: The rules that govern how the universe changes each time frame. The physics of a universe is defined by 16 physical constants. These 16 physical constants are stored in a vector.

Time Frame: A universe's physics is run once per timeframe. The screen is updated at the end of each timeframe.

Universe: A universe is a grid of cells. A universe is usually initialized to random pixels. Each universe must have physics that define how the universe changes each time frame.

Merge Physics Background

The Merge Physics universe is essentially a grid of pixels or cells. Unlike Conway's Game of Life, individual cells are not simply on or off. The individual cells are made up of vectors of red, green and blue. Each pixels has one numeric vector where each component is in the range -1 to 1. A value of -1 means that the color component is fully off, whereas a value of 1 means the color component is fully on. For example white would be [1,1,1] and black would be [-1,-1,-1]. Blue would be [-1,-1,1]. This can be seen in the diagram below. Merge Physics is a very simple cellular automata.

This allows the universe to represent any of the RBG colors. Typically the universe is initialized to random color values. This is done by setting each cell to a vector of three random numbers between -1 and 1.

The physics works by adjusting each pixel value during a time frame. Each pixel is merged with a particular key color. The exact means by which this happens is defined by a vector of 16 values. These 16 values are the universal constants that define a universe's physics. Changing these 16 values can create many different universes. Some are very simple and stabilize to a single color quickly. Others are more interesting and produce complex patterns.

All physical constants must be between -1 and 1. You can think of these 16 vector constants as follows.

[vo,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12,v13,v14,v15] 

The diagram below shows how these constants map to their key colors.

The 16 physical constants are really 8 pairs for each of the 8 key colors. The key colors are black, red, green, yellow, blue, purple, cyan and white. The above chart shows the key colors in order by their index. The reg, green and blue columns show the values for the RGB components. Just like the universe pixels, -1 is full off and 1 is full on. The resulting color is shown in the 5th column. The last two columns show the vector indexes for each of the key color's limit and percent. These values come from physical constants vector.

Each color pixel is considered one by one. The average value of all eight of the pixels neighbors are considered. Neighbors are grid elements that are immediately N, S, E, W, NE, SW or SE of the current pixel. If the pixels is on an edge then a vector of three zeros is used for that pixel. This works well, because zero is the mean of -1 and 1. The mean is calculate over all color components of all neighbor pixels. The following equation calculates the mean of the color vectors of the neighbors.

N is the number of neighbors. N is typically 9, though it can be decreased for edge pixels. You can also treat off-grid pixels as zeros. Both approaches for handling edge pixels are mathematically equivalent.

The calculated value for the mean(mu, μ) is used to determine which of the key colors to move towards. We consider each of they key colors, in order by their limit values. Once we find a key color that has a higher limit value than the mean, we have found the target key color. The percent value (from the physical constant vector) is then used to determine how far towards the key color we should move. If the percent value is -1, then the current pixel will be left unchanged. If the percent value is 1, then the current pixel will immediately obtain the value of the key color. The percents are stored in the range -1 to 1, so they should be denormalized to actual percent values. This process is very simple and can be accomplished with the following formula.

The same value p is used for each of the three color components. The following shows how we finally calculate the value for the new cell (c), or pixel, based on the percent (p) for the red (r), green (g) and blue(b) values. We are basically moving the pixel vector towards the key color (k).

cn + 1 = [rn + p(rk − rn),gn + p(gk − gn),bn + p(bk − bn)]

Using the code

Java source code that implements a "Multiverse Viewer". This is a Java Swing application that uses multi-threading to run many universes side-by-side. You can use genetic algorithm constructs to create new universes. You start with a set of random universes. Uninteresting universes can be killed off replaced with new random universes. Multiple interesting universes can "mate" and create an offspring universe. A single interesting universe can create an offspring that is a mutated version of the parent. The multi-threaded code allows several universes to run fairly quickly on a multi-core machine.

The included download has no external dependancies. You can start the Multiverse Viewer by running the following class.

com.heatonresearch.aifh.vol2.examples.mergelife.viewer.MultiverseViewer

It is not difficult to use the Multiverse Viewer. I do have a real quick tutorial video here.

An interface, name Physics is provided that defines how a class can implement a physics system. The Physics interface is shown here.

package com.heatonresearch.aifh.vol2.examples.mergelife.physics;
 
import com.heatonresearch.aifh.vol2.examples.mergelife.universe.Universe;
 
import java.io.IOException;
 
public interface Physics {
    /**
     * Copy the physics constants vector from another array.
     * @param sourceData The source vector to copy.
     */
    void copyData(double[] sourceData);
 
    /**
     * @return Get the physical constants vector.
     */
    double[] getData();
 
    /**
     * Load the physical constants vector from a text file.
     * @param filename The filename.
     * @throws IOException
     */
    void load(String filename) throws IOException;
 
    /**
     * Save the physical constants vector to a text file.
     * @param filename The filename.
     * @throws IOException
     */
    void save(String filename) throws IOException;
 
    /**
     * Perform the actual physics.
     * @param outputUniverse The new output universe.
     * @param row The row of the cell we are processing.
     * @param col The column of the cell we are processing.
     */
    void processPixel(Universe outputUniverse, int row, int col);
 
    /**
     * Randomize the physics to random values.
     */
    void randomize();
} 

The most important member is processPixel. Any new physics class should provide its own processPixel method to update the next time frame's universe. As is common with most cellular automata the universe is double buffered. The physics class uses the current timeframe as source to update the next time frame. This prevents a partially updated universe from being used in any of the merge calculations.

Internally, Merge Physics is implemented inside of the following class.

com.heatonresearch.aifh.vol2.examples.mergelife.physics.MergePhysics 

The most important function is processPixel. It begins by accepting the outputUniverse, as well as the row and col we are updating.

public void processPixel(final Universe outputUniverse, final int row, final int col) {  

The first step is to calculate the mean of all of the neighbor cells. To do this we must take a total. We initialize it to zero.

    double total = 0;
        int cnt = 0;

We have an array of all of the key colors. We keep the coordinates of each neighbor in the rowTransform array. These tell us how to find each neighbor, they contain coordinates like [-1,0] meaning to move left one but nothing in the up down directory. This allows us to quickly loop over all of the neighbors. The following code places each neighbor's coordinates into otherRow and otherCol.

        for (int dir = 0; dir < this.rowTransform.length; dir++) {
            final int otherRow = row + this.rowTransform[dir];
            final int otherCol = col + this.colTransform[dir];
            if (this.universe.isValid(otherRow, otherCol)) { 

Next we must see if the neighbor cell is valid. It might be outside the universe, if it is an edge. If it is not valid, it simply does not contribute to the count. Since 0 is the mean of -1 and 1, this works well. Otherwise we sum the average of the color vector. We keep count of how many values we have summed, so we can take an overall mean later.

                final UniverseCell otherCell = this.universe.get(otherRow,
                        otherCol);
                total += otherCell.getAvg();
                cnt++;
            }
        } 

We now have a total. We convert this to a mean (or average).

        total/=cnt; 

We now have the mean. We now find the key color that it is closed to. Earlier, we sorted the key colors, by their thresholds, into the dataOrder variable. This allows us to easily find out what key color range the mean (from the previous step) is in.

        for (int i = 0; i < this.colorTable.length; i++) {
            final int idx = this.dataOrder[i];
            if (total < this.data[idx * 2]) { 

Once we find the key color to use, we move towards it by the specified percent. To do this we must loop over the red, green and blue values.

                for (int j = 0; j < outputUniverse.getCellSize(); j++) {
                    double d = this.colorTable[idx][j]
                            - this.universe.get(row, col, j);
                    double pct = this.data[1 + idx * 2];
                    pct = (pct + 1.0) / 2.0;
                    d *= pct;
                    outputUniverse.add(row, col, j, d);
                }
                break;
            }
        }
    } 

This same process is performed on every pixel, for every timeframe.


How to Run the Program

The source code for this program can be found at the following GitHub URL.  However, it is easiest to simply pull down the code for the entire Artificial Intelligence for Humans series from here.  Extract this to a folder and move to the subdir /aifh/vol2/vol2-java-examples and execute the following command:

Windows:

gradlew runMergeLife

UNIX/Mac:

./gradlew runMergeLife

Future Directions

This code is from Chapter 8 of Artificial Intelligence for Humans, Volume 2: Nature-Inspired Algorithms. The book is not yet completely written. Eventually, this code, and the rest of the book will be translated to C# and Python as well.

More links on the book.

History

Version 1.0, current version.









 

License

This article, along with any associated source code and files, is licensed under The Apache License, Version 2.0

Share

About the Author

JeffHeaton
Architect
United States United States
Jeff Heaton is a data scientist, PhD student and indy publisher. Jeff works primarily in the programming languages Python, R, C#, Java and C/C++. He is an active technology blogger, open source contributor, and author of more than ten books. His areas of expertise include Data Science, Predictive Modeling, Data Mining, Big Data, Business Intelligence and Artificial Intelligence. He is the lead developer for the Encog Machine Learning Framework open source project. Jeff holds a Masters Degree in Information Management from Washington University, is a Senior Member of the IEEE, a Sun Certified Java Programmer and a Fellow of the Life Management Institute.
Follow on   Twitter   Google+   LinkedIn

Comments and Discussions

 
QuestionHow to install and run PinmemberQuill McGee7-May-14 10:05 
AnswerRe: How to install and run PinmemberJeffHeaton24-Aug-14 11:45 
QuestionMy Vote of 5 PinmemberAbhishek Nandy10-Mar-14 22:41 
AnswerRe: My Vote of 5 PinmemberJeffHeaton11-Mar-14 1:49 
QuestionUsing this in one of my classes, neat stuff Pinmembertaheretaheri4-Mar-14 3:28 
AnswerRe: Using this in one of my classes, neat stuff PinmemberJeffHeaton4-Mar-14 10:36 
GeneralRe: Using this in one of my classes, neat stuff Pinmembertaheretaheri5-Mar-14 3:15 
QuestionInterpretation of your automaton? PinmemberStefan_Lang24-Feb-14 21:31 
AnswerRe: Interpretation of your automaton? PinmemberJeffHeaton25-Feb-14 12:41 
QuestionMisleading title PinmemberStefan_Lang24-Feb-14 21:19 
AnswerRe: Misleading title [modified] PinmemberJeffHeaton25-Feb-14 12:33 
GeneralRe: Misleading title PinmemberStefan_Lang25-Feb-14 21:56 
GeneralRe: Misleading title PinmemberJeffHeaton26-Feb-14 3:31 
GeneralRe: Misleading title PinmemberStefan_Lang26-Feb-14 5:57 
GeneralRe: Misleading title PinmemberJeffHeaton26-Feb-14 7:19 
GeneralRe: Misleading title PinmemberStefan_Lang26-Feb-14 22:18 
GeneralRe: Misleading title [modified] PinmemberJeffHeaton27-Feb-14 4:07 
GeneralRe: Misleading title PinmemberMember 1063050727-Feb-14 5:20 
GeneralRe: Misleading title PinmemberStefan_Lang27-Feb-14 5:47 
GeneralRe: Misleading title PinmemberMember 1063050727-Feb-14 7:36 
GeneralRe: Misleading title PinmemberStefan_Lang27-Feb-14 21:15 
GeneralRe: Misleading title PinmemberStefan_Lang27-Feb-14 5:35 
GeneralRe: Misleading title PinmemberMember 1063050727-Feb-14 5:15 
GeneralRe: Misleading title PinmemberStefan_Lang27-Feb-14 5:41 
GeneralRe: Misleading title PinmemberMember 1063050727-Feb-14 7:20 
GeneralRe: Misleading title PinmemberStefan_Lang27-Feb-14 21:04 
GeneralRe: Misleading title PinmemberJeffHeaton28-Feb-14 3:57 
GeneralRe: Misleading title PinmemberMember 1063050728-Feb-14 4:34 
GeneralRe: Misleading title PinmemberStefan_Lang28-Feb-14 5:11 
GeneralRe: Misleading title PinmemberMember 1063050728-Feb-14 4:39 
GeneralRe: Misleading title PinmemberStefan_Lang28-Feb-14 5:22 
GeneralRe: Misleading title PinmemberMember 1063050728-Feb-14 6:37 
GeneralRe: Misleading title PinmemberStefan_Lang2-Mar-14 23:11 
GeneralRe: Misleading title PinmemberMember 106305073-Mar-14 7:35 
GeneralRe: Misleading title PinmemberStefan_Lang28-Feb-14 5:45 
GeneralRe: Misleading title [modified] Pinmembertaheretaheri4-Mar-14 3:44 
GeneralRe: Misleading title PinmemberStefan_Lang4-Mar-14 21:21 
GeneralRe: Misleading title Pinmembertaheretaheri4-Mar-14 4:07 
GeneralRe: Misleading title PinmemberStefan_Lang4-Mar-14 22:27 
AnswerRe: Misleading title [modified] Pinmembertaheretaheri4-Mar-14 4:01 
GeneralRe: Misleading title PinmemberMember 106305074-Mar-14 5:14 
GeneralRe: Misleading title PinmemberStefan_Lang4-Mar-14 21:42 
GeneralRe: Misleading title Pinmembertaheretaheri5-Mar-14 3:38 
GeneralLooking for constructive advice, what would be a good accurate/clear title? (for article author) PinmemberJeffHeaton5-Mar-14 4:19 
GeneralRe: Looking for constructive advice, what would be a good accurate/clear title? (for article author) PinmemberStefan_Lang5-Mar-14 4:55 
GeneralRe: Looking for constructive advice, what would be a good accurate/clear title? (for article author) PinmemberJeffHeaton10-Mar-14 5:46 
GeneralRe: Misleading title PinmemberStefan_Lang5-Mar-14 4:35 
GeneralRe: Misleading title Pinmembertaheretaheri8-Mar-14 13:15 
GeneralRe: Misleading title PinmemberStefan_Lang9-Mar-14 23:31 
GeneralRe: Misleading title PinmemberMember 1063050710-Mar-14 5:29 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150128.1 | Last Updated 10 Mar 2014
Article Copyright 2014 by JeffHeaton
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid