Evolutionary Computation - Ex 5
| Eran Ziserman | 034301143 |
|---|
| Yonatan Shichel | 034472837 |
|---|
The code
CA.java: An implementation of the cellular automaton
CP.java: An implementation of the cellular program
Basic Algorithm Description
We have used the standard CP algorithm, as described in the assignment page, with the following modifications:
- Fitness: The basic fitness is either 0, when the following condition does not occur, and 1 otherwise:
where T indicates the time step.
- Crossover: Standard single-point crossover, with Pc=0.5.
- Mutation: Bitwise mutation on the binary representation of the rule, with Pm=0.1.
The mutation rate value describes the chance of getting a mutation in the rule, rather than the chance of getting a mutation in each bit.
- Generation limit: was set to 2000, or until avg. fitness of 1.0 has been reached.
- Time steps of CA run (M) was set to 150% of the CA size.
- Number of CA activations per generation (C) was set to 300.
Improvements and Tricks
After several experiments with the basic algorithm, we have observed the following convergence problems:
- "Border Struggle": when two blocks of "good rules" (ie: fitness=1), but with opposite synchronization (ie: 0101/1010) share a border.
According to the basic algorithm and fitness, the two border cells (each from a different block) will both have a fitness of 0, thus have one neighbour with fitness=1 (from their block)
and another with fitness=0 (from the opposite block). In this case, they should copy the rule from the good fitnessed neighbour and mutate it.
This causes the borderline to be at static position (only a mutation can stop this "struggle", causing one block to "win", but the probability of mutation is the same for the two blocks).
To solve this problem, we had to give one of the blocks a minor advantage. We have chosen the sync sequence ending with 0 to be the preferred one, by giving a fitness of EPSILON to the border cell of the "...1010" block. Formally:
This fitness addition help to solve the "border struggle" problem, by giving priority to one of the blocks.
- "Unit Struggle": when a single cell is "stuck" in the middle of a "good" block. This cell and its neighbours have a fitness of 0 (in case of "...0101" sequence).
According to the basic algorithm, this cell should remain the same (has the same fitness as its neighbours).
Solution: this problem is partially solved by the epsilon fitness mentions above (in case the good block is of the sequence "...1010"), but we have added the following rule:
"If the number of fitter neighbours is zero, AND the cell's fitness is zero too, perform a mutation on the cell's rule, otherwise keeps the original rule". We have assigned a different mutation rate of 0.2 for this mutation call.
Results
We have activated the Cellular Programming algorithm on Cellular automata of sizes N=100, 200, 300:
- We have found a solution for all the cases.
- We can see that the larger the problem is, the slower the convergence rate. This plot does not clearly shows this statement, but we came to this observation after running several CPs.
- On large scale applications (N=300), not every application of the CP program has managed to converge within the generation limit.
Sample solutions to the synchronization problem
Each image contains a space-time diagram for the CA given by the CP. At the bottom of each picture we have added the rule map of the automaton.
N=100:
N=200:
N=300:
Some Conclusions
We observed two stages in the evolvement of the CA.
- First stage: There is a great diversity of rules (since the rules have been initialized randomly), but the average fitness is very low - because most of the rules doesn't obey the fitness measures we have specified.
The rules that get good fitness values take over the poorer rules, so they expand over the CA's cells at almost linear rate. This stage takes no more than half of the CA size.
- Second stage: There is a small diversity of rules, set in blocks over the CA's cells. There are noticeable "border struggles" and "unit struggles" (as defined above), preventing the CP to achieve its goal.
This phase lasts until the termination of the CP, and have almost perfect average fitness (.98-.99). We have found that using the "epsilon fitness" and special mutation rules this phase can be shortened significantly.
Evolvement of CA's rulemaps (N=100), without optimization:
Evolvement of CA's rulemaps (N=100), with optimization:
- Scale of the plots: each vertical grid tick equals 50 generations.
- The upper plot was stopped after 300 generations without converging.
- Two stages can be clearly observed on both plots.
- There are two noticeable "border struggles" in the upper plot (left and middle), which prevented the CP from converging.
- The lower plot presents a successful "border struggle" (left side), where the darker rules had some priority over the brighter rules.
- In both plots, one can observe some mutations (darker/brighter single cells) on the borderline of two opposing rule blocks.