Assignment 5
Cellular Automata
Submitted by:
Lior Becker – 052690849, liorbecker@gmail.com , http://liorbecker.googlepages.com , http://liorbecker.googlepages.com/
Arie Ohana ID:
33771635 ohanaar
.
INDEX
2. Results - for the density problem
3. Results - for the sync problem
.
The assignment involves
solving two problems using cellular automata. The problems were:
1.
The
density problem – determining if the number if zero is larger then the number
of ones in a given binary series.
2.
The
synchronization problem – Given a series of bits, the automaton should oscillate
between two states: all zeros and all ones.
Process of work:
The main algorithm is
described in Moshe
Sipper's document.
1.
Radius
= 1.
2.
Non-uniform
rules.
3.
Evolving
every C=100 configurations.
4.
Number
of steps before determining fitness is M=29 and M=49.
Cell
representation:
A cell has a
rule table which is an 8 bit array. Each bit indicates a specific transition
rule. For example, assuming that the value of the 5th entry in the array
is 1, then if the left neighbor's state is 1 and the current cell's state is 0
and the right is 0 (e.g. 100 which is
In addition,
every cell has its own fitness counter. When in the fitness evaluation phase,
the fitness counter is increased if the cell's state matches its desired state
as stated by the problem solution.
Initialization:
1. In the density problem, The series of bits, which defines the automaton's state, is initialized
pseudo-randomly, so there will be a majority of either 1s or 0s. we generate the bits so the ration between zeros and ones is
between 0 and 1/3 with probability of 0.6, and between 0.2 and 0.45 otherwise.
2. In the synchronization problem,
The series of bits, which defines the automaton's state, is initialized randomly
(0,1).
Selection
method:
In both problems, since the radius is 1, every cell
has a pair of neighbors:
·
If
the fitness of the current cell is larger then the fitness of both neighbors,
no change is performed.
·
If
both neighbors have better fitness, the new rule table of the current cell is
the product of a crossover and mutation on the rule table of both neighbors.
·
If
only a single neighbor has a better fitness, its rule table is mutated and the current
cell's rule table is replaced with the product.
NOTE: These
rules of learning were all defined in Moshe Sipper's document.
Fitness
function:
For every cell we tested the cell's state (0/1)
against the cell's target.
1. In the density problem, each
cell's state should be as the majority of the bits in the initial bit series. Cell's
fitness is increased in this case.
2. In the synchronization problem, each
cell's state should be equal to his left and right neighbors and different from
his upper neighbor (his state one step before) .
For each one
of the three demands Cell fitness will be increased by 1/3.
NOTE:
the total fitness is value between (0...100), i.e. percentage of correct
answers.
Crossover:
Single point XO.
Mutation:
Pm = 0.01.
For
each bit in a rule table, if a mutation is being performed, the bit is flipped.
Number of cells = 29 and 49.
Num of generations = 500.
Step:
1. Set all fitness counters to zero.
2. For i=1 to C
do
a. Initialize cells with random bits as
described above.
b. For k=1 to M do
i.
Calculate
each cell's new state according to its rule table in "parallel".
c. Calculate fitness for all cells.
3. Update table rules (i.e. crossover and
mutation)
A step is
done 500 times. When the whole sequence is over the automaton has learned the
problem and ready to be tested on arbitrary input.
Results - for the density problem:
29 cells .
Figure 1:
Learning rate of our automata (Average fitness against generations)
Automaton: 232
232 232 236 232 232 232 168 168
168 168 168
168 184 184 184 184 184
184 184 184
184 184 184
248 238 232 232 232
Precision: 91%
(tested on 100 cases)
Automaton: 232 232 232 232 232
232 168 170 170 170 170 170
232 232 232 232 232 232
232 232 232
232 232 232
232 232 232
232 232
Precision:
88 % (tested on 100 cases)
Automaton: 232
232 232 232
232 232 232
232 232 184 184 184 184
184 184 184
184 184 184
232 232 232 232 232 232
232 232 232
232
Precision: 87.344826% (tested on 100 cases)
Figure 2:
Test cases of the final automata (space-time diagrams)
Automaton: 232
232 232 236 232 232 232 168 168
168 168 168
168 184 184 184 184 184
184 184 184
184 184 184
248 238 232 232 232
Precision: 91%
(tested on 100 cases)
49 cells .
Figure 3:
Learning rate of our automata (Average fitness against generations)
Automaton: 232
232 232 200 232 232 232 232
232 232 232
232 226 226 226 226 226
226 226 226
226 226 226
226 226 224 224 224 224
224 224 232 232 236 232 232 232 232 224 224
224 224 232 232 234 234 234
234 234
Precision: 88%
(tested on 100 cases)
Automaton: 184
104 234 234 238 232 234 234
234 234 232 232 232 232
232 232 232
104 232 232 232 232 232 232
232 232 232
232 232 232
232 232 232
232 232 232
232 168 168 168 168 184 184
184 248 248 184 184 184
Precision: 89.734695%
(tested on 100 cases)
Automaton: 170
170 170 234 234 226 226 226
226 226 226
226 226 232 232 232 232
232 232 232
232 232 232
232 232 232
232 232 232
232 232 232
224 224 224 224 224 224
240 240 176 170 170 170 170 170
170 170 170
Precision: 90.02041%
(tested on 100 cases)
Figure 4:
Test cases of the final automata (space-time diagrams)
Automaton: 170
170 170 234 234 226 226 226
226 226 226
226 226 232 232 232 232
232 232 232
232 232 232
232 232 232
232 232 232
232 232 232
224 224 224 224 224 224
240 240 176 170 170 170 170 170
170 170 170
Precision: 90.02041% (tested on 100 cases)
Results - for the sync problem:
29 cells .
Figure 5:
Learning rate of our automata (Average fitness against generations)
Automaton: 47 47 47 47 31 17 17
17 17 17
17 17 17
17 49 49 7 39 111 111 111 47 47
47 47 47
47 47 47
Precision: 100% (tested on 100
cases)
Automaton: 63 63 63 63 63
63 63 63
117 117 117 117 117 117
117 53 53 53 53 53
53 53 39 39 39 39
63 63 63
Precision:
100% (tested on 100 cases)
Automaton: 3 3 3 7 7 5 17 49 17 17 17 17
17 17 17
17 17 17
19 3 3 3 3 3 3 3 3 3 3
Precision: 100% (tested on 100 cases)
Figure 6:
Test cases of the final automata (space-time diagrams)
Automaton: 3 3 3 7 7 5 17 49 17 17 17 17
17 17 17
17 17 17
19 3 3 3 3 3 3 3 3 3 3
Precision: 100% (tested on 100 cases)
49 cells .
Figure 7:
Learning rate of our automata (Average fitness against generations)
Automaton: 47
47 47 47
95 81 89 81 81 81 81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
49 15 15 47 47 47 47 47
47
Precision: 100% (tested on 100 cases)
Automaton: 7
7 7 7
7 7 7
7 7 87 81 81 81 81
81 81 81
81 81 81
81 81 81
113 113 113 113 113 113
113 17 49 27 27 27 31 31 31
31 31 31
31 7 7 7
7 7 7
7
Precision: 100% (tested on 100 cases)
Automaton: 27
27 27 27
27 27 27
27 27 27
27 27 27
27 27 27
27 91 117 117 117 117 117
117 117 117
117 117 117
117 117 117
117 117 117
117 113 113 53 119 119 119 119
55 11 11 27 27 27
Precision: 100% (tested on 100 cases)
Figure 8:
Test cases of the final automata (space-time diagrams)
Automaton: 47
47 47 47
95 81 89 81 81 81 81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
81 81 81
49 15 15 47 47 47 47 47
47
Precision: 100% (tested on 100 cases)
1. DENSITY: It is easily observed that certain
rules appear more than others, for instance the rule 232 is much more dominant
then other rules. The reason for this may be that this rule expresses a relatively
good solution to the problem.
2. DENSITY: The
fitness of the cells was never perfect. Tough in most of the cases the fitness
was acceptable (around 85%), not all instances of the problem
were
solved.
Never the less you can see the improvement that
follows.
cells in the middle
have R2, and this pattern may differ a little. For instance:
5. SYNC: The fitness of the cells was
perfect (100%), we can say that the problem of sync is much "easier"
then the density.