Cellular Automata solving Synchronization problem.   


 

Plot of average and best fitness versus evolution steps (generations) for 100 cell CA:

 
Plot of average and best fitness versus evolution steps (generations) for 200 cell CA:
Plot of average and best fitness versus evolution steps (generations) for 300 cell CA:

 


 

Space-time diagram of 100 cell automaton  , in 144 evolution steps , reached 200 ( maximal ) fitness for every cell:

 

 Space-time diagram of 100 cell automaton  , in 47 evolution steps , reached 200 ( maximal ) fitness for every cell:
Space-time diagram of 200 cell automaton  , in 89 evolution steps , reached 199 (out of 200)  average fitness:

 
Space-time diagram of 200 cell automaton  , in 93 evolution steps , reached 199 (out of 200)  average fitness:
Space-time diagram of 300 cell automaton , in 1107 evolution steps ,reached 4000 ( maximal ) fitness for every cell:

 


Improvements:
1) In every cell that reached the maximal fitness we are not making mutations in regular rate , but much lower - mostly we are just reproducing the cell rule genome (cloning),  it  improved the behavior of fitness function - less jumps.

2) We have noticed that the minimal fitness remains 0 in few cells throughout the entire run (it improves suddenly a few evolutionary steps before the end of the run ), to improve it in big automata we are checking the cells and mutating the cell rules genome in high rate of mutation probability.

 

Conclusions:
1) Behavior of the CA is stochastic - there is no guaranty , that 100 cell CA will reach its maximum fitness through X generations - it is randomic , but from the experiments we saw it converge after approximately 100 generations ( same for 200 cells CA) - it takes longer for 300 cells CA.

2) We are under the impression that scaling task is a hard one for CA's , our 300 cell CA doesn't manage to find the optimal solution , although it doesn't seem hopeless (after long night run he made it...).

3) Although at the beginning of the programming we thought that local evolutionary improvements won't influence globally on the CA , we understood it is not true .

                        So , one CAN make a difference , and the size DOES matter  J

                                                                                                                                                                                                     download source files of CA  question...