Solving the Synchronization and Density Problems using Cellular Automata Programming

Target: solve the density and synchronization problems using cellular automata programming.

By: Aviv Ron (ronav@cs.bgu.ac.il) (www.cs.bgu.ac.il/~ronav)

The Cellular automata:

We use cellular automata with R=1. This means that every cell has two neighbors, the one to its left and the one to its right.
The two cells in the edges are each others neighbors.

Thus each automaton has 8 states and there are 256 possible automatons.

The Cellular automata programming algorithm:

Initialize the cells with random states using biased sampling.

Initialize the functions (the automatons) of each cell with a random state.

FOR EACH generation:

FOREACH cell init its fitness to 0

FOR i=0 to loopsEachGeneration

FOR j=0 to steps

Assign the next value to all cells

Calculate fitness of run for each cell and add to the cells fitness

Evolve the functions of each cell

Selection:

Let n be the number of neighbors of a cell that have a bigger fitness value.

If n = 0 the cells function stays to the next generation with 10% chance of mutation

If n = 1 the cell gets the function from the fitter neighbor with 10% chance for mutation

If n = 2 with 50% chance take one of the neighbors functions. With 50% chance take a crossover of both of them.
in any way 10% chance for mutation.

Crossover:

Two point crossover:

Choose two random points between 1 to 8. Choose one parent to fill the values between these points and the other to fill the values outside these points.

Mutation:

Bitwise mutation:

Choose a random point between 1 to 8 and flip its value.

The Synchronization Problem

Fitness:

The cell gets a point bonus for each of:

Being equal to each neighbor ion the final step.

Having flipped its value in the last four steps.

For example a perfect fitness (5) would be given to: and fitness 0 to:

The parameters of the experiment:

A plot of the average fitness sampled at the end of each generation:	A plot of the functions of each cell thru generations:
		0 G e n e r a t i o n s 300

The best possible fitness for a cell is max(possible fitness of run) * loops each generation = 5 * 20 = 100

Thus we can see that the CA reached the maximal fitness for all its 29 cells.

This means that each cell managed to score a perfect fitness in every one of the 20 runs on random initial cells.

Let’s see some plots of the evolved CA working:

Plot 1	Plot 2	Plot 3	Plot 4

The percentage above each plot shows the percentage of ones in the initial cells state.

We can see that the more homogenous the initial state is, the faster the CA solves the problem.

Still the CA manages to deal also with harder initial states with 48% ones.

Another run of the same parameters:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 300
Plot 1	Plot 2	Plot 3		Plot 4

Now we will try a bigger CA:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 300
Plot 1	Plot 2	Plot 3		Plot 4

Another run with the same parameters:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 300
Plot 1	Plot 2	Plot 3		Plot 4

Summary:

The Synchronization problem can be solved using cellular programming.

We can see from the evolving of the functions thru generations how the evolution works and the better functions spread to their neighbors.

The Density Problem

Fitness:

The cell gets a point bonus for having the correct wanted value in each of the three last steps.

For example a perfect fitness (4) would be given to: and fitness 0 to:

For a CA with an initial number of ones bigger than 50%.

The parameters of the experiment:

A plot of the average fitness sampled at the end of each generation:	A plot of the functions of each cell thru generations:
		0 G e n e r a t i o n s 150

This plot shows the percentage of the average fitness from the best possible average fitness (in red) and the percentage of solved cases from the cases tried each generation (in blue).

We can see that the average fitness is low around 50%.

The solved cases plot shows that at a given time step (though the average fitness was still around 50%) almost 75% of the cases were solved.

This non linear relationship between the two is caused due to some cases being totally solved at the last step, while the fitness looks at the cells value in the last three steps.

The light blue colored function that dominates the function plot is the simple “majority rule” function – meaning if there are more ones turn to one else turn to zero.

The space time plots shown here represent cases being solved by the CA found on the generation which managed to solve the most cases (in this case from generation 57)

Plot 1	Plot 2	Plot 3	Plot 4

The percentage above each plot shows the percentage of ones in the initial cells state.

The percentage below shows the percentage of ones at the end of the run.

We can see the CA managed to solve simple cases but confronting a hard case of 51% ones it went in the wrong direction of reducing the ones to 6%.

Still these results are quite good.

Another run of the same parameters:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 150
Plot 1	Plot 2	Plot 3		Plot 4

This run had succeeded less better than the first, the best CA managing to solve only 54% .

Now we will try a bigger CA:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 150
Plot 1	Plot 2	Plot 3		Plot 4

Solving a 49 cell CA is even harder and the even simple cases like91% fail. The best CA managed to solve 44% of the test cases.

Another run with the same parameters:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 150
Plot 1	Plot 2	Plot 3		Plot 4

I will change the fitness function now to give more weight to the final state of the cell and also include the prior four steps of the cell.

So a cell gets 5 points for being in the correct state in the final step and another point for each correct state in the four steps before the last:

The results for the next parameters are shown:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 150
Plot 1	Plot 2	Plot 3		Plot 4

This time the CA had done better, managed to solve simple cases and its best managed to solve 65% of the test cases while having 83% of the possible average fitness.

Another run with the same parameters:

A plot of the average fitness sampled at the end of each generation:			A plot of the functions of each cell thru generations:
					0 G e n e r a t i o n s 150
Plot 1	Plot 2	Plot 3		Plot 4

Again the CA did nicely at certain points solving 85% of the 40 test cases given. What is interesting in this case is that the usual “majority function” which we so dominating up to now is in minority here, giving place to two other functions to take over.

Still we can see that the CA gets confused and turns the 26% plot 4 into 100%.

Summary:

CA programming had shown us that it knows to solve the synchronization problem, but only comes near (around 80% in better cases) to solving the density problem.

The Application:

Written in Java 5.0

Source code here

Executable jar here

Plots done using JFreeChart