: 22931521, 034477430


On this assignment we used a genetic algorithm to develop 2 dimensions cellular automata that solves the density problem while using Moore neighborhood.


How to use the Code?

Download Code

Compile and run CA.java

On screen will appear a window with 2 options:


Evolve Rule runs the evolution process to evolve new rules.



Initial State create some biased initail grid and let the Next State button to runs the time step of selected rule (that one can put within the code using a string called defaultRule)


At the end of each run a text file is generated containing the fitness of the best and average.

Using the Data members at the top of the CA.java code gives control of all variables.

The code itself is well documented.




Step: defines the initialized state of a grid at time t=0.

Calculation: shifting the whole grid from time t to time t+1

Bias: bias~Uniform(0,1), used to generate steps.

Rule: a set of bits that defines the next state of a cell according to his 9 neighbors (including itself).


The 2 dimensions density problem how it works?

The automata cell using 2 states (0,1) goal is to find if its initialized state (step) had more 0 or 1.


Each calculation the cells will change their state according to their neighbors (using the Rule) and after several calculations we would expect the all grid to turn into 0 or 1 according to the majority 0 and 1 at the step we started from.


The automata cell will use Moore neighborhood.


For example:

Grid n=10, m=10 with an initialized Step having 36 0 and 64 1.




















Each Calculation every cell changes itself according to the set Rule.

A Moore neighborhood means the set Rule will define the rules for 512 different states.



The Goal

Find the set Rule that solves as many steps as possible for a Cellular Automata with size NxM.



The Genetic Algorithm



Each individual is a set Rule of 512 states.

We used a string with size 512 to represent each Rule.


A cell state is represented via a binary number. The cell itself holds the most significant bit, and then according to an order each neighbor represents the next bit. This number X will find the value at location X on our 512 long string we call Rule.


We used the order below to generate a binary number:























Ranking Selection, B=2.0


Cross Over

Single point crossover, with chance of crossing = 0.7



Bitwise mutation using mutation rate= 0.01



We used 2 different fitness functions.

Both fitness function are mostly alike and has different variant toward the end.


For all Rules in population do (for 100 steps) {

Pick a bias.

Generate a Step

For each Rule in population do: {

Start from Step

Calculation(100) shift the CA to t=100.

Fitness (#1 / #2) calc fitness on the result after 100 calculations and saves it.}

Set the Rule overall fitness.}



Set Rule overall fitness:

For each step each rule gains a portion of his total fitness.

The Total fitness is:



Fitness #1:

The function counts the number of correct bits after 100 calculations.

Assuming all CA was supposed to turn into 1. After 100 calculations we have 5 cells with 1, then the fitness for this Rule would be 5 for that specific State.


The overall fitness will result the average percentage of correct bits on the #of_steps we try each generation.


Fitness #2:

The function checks if after 100 calculations we have got the right solution (all bits are correct).

If we do have a right solution for that step, the fitness would be the size of the CA (like fitness #1 - a correct solution means counting all the correct bits resulting the CAs size).


The overall fitness will result the percentage of correct solutions on the #of_steps we try each generation.





Using Fitness#1
















Best Rule for CA 10x10 00000000000001110000001000000011001001000100010101011111000011010010010001011001000101010001010100010101111001011100010110100101000100111011111100101001111111000011000110101111010011100011110100010001100011111001110101001111000000010001000100111111111111010000101100000001010101010011101101011111000000010101000110110111011001011100111101111101010100011000101101110011000110110011111100100101000110010101011010000101010111110111001101001001100101110001000100000001000101110111111100011111110111110110011101111111
















Best Rule for CA 20x20

















Best Rule for CA 30x30



Using Fitness#2
















Best Rule for CA 10X10

















Best Rule for CA 11X15




Rules Comparison

After evolving the 5 Rules with different CA sizes and fitness function we decided to put them all on the make and see how good they can compete one versus the other on their own playground.


We tested those 5 Best rules with 1000 Steps on a different CA size and with both kind of fitness functions.





Does Size matter?

The running time of this assignment wasnt easy. It kept our computer occupied for a few days especially as we increased the size of the CA.

The first question came to mind was What is the difference between the size of the CA, should it really effect the rule?


Looking on the best rules comparison we can see that it doesnt really matter, seems like the first Rule (the one that evolved on a 10x10 CA using fitness#1) is just better then the others. There isnt any correlation between the size of the CA we used to evolved the Rule and how well it will do on different sizes of CAs.



Fitness #1 versus #2

We started with fitness Funtion#1 that gives score even to partially solution. Only then we tested the second fitness function the gives score only for correct solutions. We had some trouble defining fitness function #2, we suffered from some generations that had very little variance and all shared fitness 0. We also had some long run of function #2 that ended with local optimum (a rule that no matter what the initial density ended with all 1s which has fitness of 0.5) To increase the variance we decided to use the Ranking selection to help us go through the first generations. The plots of function#2 shows the rough start on the first generation and the short distance between the average and the best can give us some idea regarding the low variance.


As for the results, the Rule comparison shows there werent any clear advantage to rules evolved through Function#1 and rules that evolved using Function#2.



Picture of our Best Rule in action!






We marked on the picture the islands of 1, take close care to see how they shrink each calculation.









Thats all folks.

Shai & Ran.