Uri Shaham, 34077636
10.4.08
Evolutionary algorithms- Ex.5
Description of the automat:
As learned in class, we use CN(1,di) architecture so each cell has 5 neighbors in distances -di , -1, 0, 1, di and a separate rule table (of length 32).
Inner loop: we run each configuration for M time units and then calculate the fitness of each cell and the average fitness of the automat.
Fitness calculation: a cell’s fitness is 1 iff it has an identical value to all its neighbors and an opposite value in the former time unit (that is, at time M-1). Otherwise the cell’s fitness is 0.
Outer loop: we run 20,000 iterations. In each iteration we start from a random biased configuration (with p=probability for 1) and run the inner loop. Fitness of each cell is accumulated. Once in 300 iterations we evolve rules and once in 1500 iterations we evolve connections (di for every cell).
Evolving rules: as in Prof. Sipper’s algorithm. For each cell we count how many neighbors have better fitness. Then:
If there are no fitter neighbors, we mutate the cell’s rule table.
If there is single neighbor with better fitness, we copy cell gets his neighbor rule table after mutation
If there are 2 or more fitter neighbors, we select to fitter neighbors and the cell gets a crossover of their rule tables, after mutation.
After evolving rules fitness of each cell is initialized to 0 again.
Evolving connections: For each cell i, if there is no fitter neighbor we don’t change the connections. Otherwise we randomly pick a fitter neighbor j and assign di <= dj .
Mutation: we flip each bit (separately) in the rule table with probability Pm.
Crossover: we choose a random crossover point (integer in range [1,31]) and cross the parents’ rule tables to get a new rule table.
Results:
Average fitness plots
N=65
First run: Pm=0.001, M=100
Second run: Pm=0.001, M=50
Third run: Pm=0.01, M=100
From the above plots we can learn 3 main things:
First, running each configuration for 50 time units is enough for solving the synchronization problem for N=65.
Second, it seems like mutation sometimes has a destructive effect on the automat and clearly Pm=0.01 makes the convergence too fluctuative, that is, also after getting solutions with avg fitness=1 the fitness deteriorates and the automat can’t maintain the good solutions found. As can be seen here, Pm=0.001 gives much better results and the high fitness is kept throughout the outer loop.
Third, in the good runs (that is, with Pm=0.001) the convergence occurs after no more than 13*300~4000 iterations of the outer loop.
N=129
First run: M=100, Pm=0.001
Second run: M=50, Pm=0.001
Third run: M=100, Pm=0.001
Also for N=129 we can see that the average fitness converges to 1. M=50 might not always to enough, as can be seen in the second plot, which is more fluctuative however fitness climbs back quickly right after each deterioration. In addition, we can see that it takes more iterations to converge with N=129- around 22*300~7000 iterations.
Space-time diagrams (plots with MS-Excel):
N=65, Pm=0.001, M=100. p is the probability for 1’s in the initial configuration. As closer as p is to 0.5, the problem is more difficult.
Run 1: p=0.2
Solution reached after 9 time unites
Run 2: p=0.4
Solution reached after 7 time units
Run 3: p=0.5
Solution reached after 19 time units
N=129, Pm=0.001, M=100
Run 1: p=0.2
Solution reached after 10 time units
Run 2: p=0.4
Solution reached after 16 time units
Run 3: p=0.5
Solution reached after 15 time units
From all above diagrams we can conclude that the solution is reached within, say, O(log N) time units (we doubled N however it takes approximately same number of time units to reach the solution), which is quite fast, I think.
Histograms of evolved connections (results of 2 runs for
each value of N. horizontal axis is di ,
vertical axis is # of cells using that di)
:
N=65
It seems like there is nothing we can say about the connections chosen. Regardless of the first bar to the left (all cells have d=1 connections) it seems that the distribution of the chosen values is quite uniform. No value was chosen by more than 4 cells. In addition, it seems like there is not much in common between the values chosen on the 2 runs (Pearson correlation coefficient between values of the 2 runs is -0.16. that means no correlation). We can’t spot popular values. However we can spot unpopular ones, that is, values that weren’t chosen by any cell in each of the two runs (like 5,21,29)
N=129
Same same. Still no correlation (-0.1). the most popular value was chosen 5 times (di =41, in run 1).
Conclusions:
1. Recommended probability for bit flips mutation: 0.001. Higher values make the convergence too fluctuative and interrupt the automat keep good rule tables
2. Larger N’s require more iterations to converge.
3. After the convergence to optimal rule tables, Solution is reached within approximately O(log N) time units.
4. It seems like the degrees of chosen connections are uniformly distributed, there is nothing else I can say about the values chosen here.
5. This was a very interesting exercise. We can see how local “black-box” behavior chosen independently by each cell creates a global problem-solving behavior of the entire automat.
Java source code: