תרגיל 5

מגישים: שי שרעבי 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?

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.

Definitions

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

Representation

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:

 2 3 4 1 0 5 8 7 6

Example: Selection

Ranking Selection, B=2.0

Cross Over

Single point crossover, with chance of crossing = 0.7

Mutation

Bitwise mutation using mutation rate= 0.01

Fitness

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 CA’s size).

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

Results

Using Fitness#1 Best Rule for CA 10x10 00000000000001110000001000000011001001000100010101011111000011010010010001011001000101010001010100010101111001011100010110100101000100111011111100101001111111000011000110101111010011100011110100010001100011111001110101001111000000010001000100111111111111010000101100000001010101010011101101011111000000010101000110110111011001011100111101111101010100011000101101110011000110110011111100100101000110010101011010000101010111110111001101001001100101110001000100000001000101110111111100011111110111110110011101111111 Best Rule for CA 20x20

00000010010000010000010100010101000000100010000101110111111001110010010001010111011100010101111000110101001111011100111101111101001001001101010100101010111100010010011111001101100101111101111100110101001110111001111101000001111000011110000111010111001111110100100011101100010100110111110111110000111011010001110000001111100100000111011000000011001010110110001101011101100001000110101100000000010100000111010100110101011100001100010110101011110110110010000011010001011111110101010100001111100100111111011101110111 Best Rule for CA 30x30

00000000001100100101000100110111010000100101010111101001101011110000101000101001001000001100100100011101000001101001011101100101000101010000000010110011010110110000011100011100000000101011111100011010100100010011010100011001001110111011010101001101011111110001101000100100001011110100011100000001110010110100011111110011000011010001011111110011111100111101011100110010111101110010111100000010110000110110011001011101000100000010010111111011111001110011001110100101001101011110111110010001111011111001000101111111

Using Fitness#2 Best Rule for CA 10X10

00000100000001110000001101010011000101010000111100101000001000010100101001010101000011100000111110001001110101001101100010011001000101000111101100001100010110111100010000011110011000011001100100111101100111100001110101000011000100010110010110101101011111110101011001000000001110000010000000001100110100110101100000111011010000010001000101111100011000110001111001100010110100111111111100100001000000101001101011010101000011011100010101011011101110110011110111101111001111011100011101111111111001111001010101111111 Best Rule for CA 11X15

00000000000100000000010011110010010100100011110000001010100111110000010010011111000011011011101101011110010010110011110110101111000001011011000001000110011011110010010011011111100010011101110100010101010100111010101100011001011000010011101100010111011111110110010100110000010101010110101100100011001011100110110101110111000110000011010110100010010101101101101001010001000101001101111101010010001001010000001010010001111111011001000000000010001011010000110110111011001010010011111101011111101101111101101111111111

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. Conclusions

Does Size matter?

The running time of this assignment wasn’t 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 doesn’t 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 isn’t any correlation between the size of the CA we used to evolved the Rule and how well it will do on different sizes of CA’s.

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 weren’t 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.          That’s all folks.

Shai & Ran.