Question

9. Explain how Conway’s Life works in the context of cellular automata. Describe the update rules of the Game of Life.

10. Explain how genetic programming can be used to solve problems.

Answer 1

9.

First, let’s get one thing straight. The term cellular automata is plural. Our code examples will simulate just one—a cellular automaton, singular. To simplify our lives, we’ll also refer to cellular automata as “CA.”

In this, our objects (mover, particle, vehicle, boid) generally existed in only one “state.” They might have moved around with advanced behaviors and physics, but ultimately they remained the same type of object over the course of their digital lifetime. We’ve alluded to the possibility that these entities can change over time (for example, the weights of steering “desires” can vary), but we haven’t fully put this into practice. In this context, cellular automata make a great first step in building a system of many objects that have varying states over time.

A cellular automaton is a model of a system of “cell” objects with the following characteristics.

• The cells live on a grid. (We’ll see examples in both one and two dimensions in this chapter, though a cellular automaton can exist in any finite number of dimensions.)

• Each cell has a state. The number of state possibilities is typically finite. The simplest example has the two possibilities of 1 and 0 (otherwise referred to as “on” and “off” or “alive” and “dead”).

• Each cell has a neighborhood. This can be defined in any number of ways, but it is typically a list of adjacent cells.

The Rules

For a space that is 'populated':

Each cell with one or no neighbors dies, as if by solitude.

Each cell with four or more neighbors dies, as if by overpopulation.

Each cell with two or three neighbors survives.

For a space that is 'empty' or 'unpopulated'

Each cell with three neighbors becomes populated.

The Controls

Choose a figure from the pull-down menu or make one yourself by clicking on the cells with a mouse. A new generation of cells (corresponding to one iteration of the rules) is initiated by the 'Next' button. The 'Start' button advances the game by several generations. Game speed is regulated by the speed dial and the size of the cells with the size dial.

10.

The process of using genetic algorithms goes like this:

1. Determine the problem and goal
2. Break down the solution to bite-sized properties (genomes)
3. Build a population by randomizing said properties
4. Evaluate each unit in the population
5. Selectively breed (pick genomes from each parent)
6. Rinse and repeat

When to Use Genetic Algorithms

GAs are not good for all kinds of problems. They’re best for problems where there is a clear way to evaluate fitness. If your search space is not well constrained or your evaluation process is computationally expensive, GAs may not find solutions in a sane amount of time. In my experience, they’re most helpful when there is a decent algorithm in place, but the “knobs” just need to be tweaked.

For Example…

On a recent project, we had an algorithm that we knew would work, but we needed to find the best possible settings for the tune-able parameters.

We were using pressure data from inside a testing lung to parse out breath waves and calculate derived values such as breath rate, tidal volumes, and peak pressures. We had many recordings of pressure data and knew the expected results. The goal was simple: find the set of variables that would get us as close as possible to the expected results. Our properties were a handful of settings for our existing algorithm: low/high thresholds, smoothing factors, averaging window sizes, etc.

A simpler illustration

To walk through how it works, let’s use something a little simpler: a cannon.

Like the old Cannon Fodder game, we have a cannon that has two variables: powder and elevation. Our goal is to shoot as far as possible. (Let’s pretend we don’t know about physics and don’t know that 45 degrees is the answer.)

Our goal: max distance
Our genomes: powder (0-100) P and elevation (-90-90 degrees) E

Initial population

We start by generating a sample population and evaluating its members. Normally, this sample would be much larger, but for our example, we’ll keep it small:

Powder	Elevation	Distance
5	-90	0
100	30	80
75	44	65
25	90	35
33	70	20

Given these results, we can use an elitist strategy to select the top X percent of the population to “reproduce.” Once selected, we use crossover/recombination to blend the best of the population.