Cellular Automata Machine for Pattern Recognition - Cellular Automata - page 275

state of a thermodynamic system is analogous to the current solution of synthesis
scheme, while the energy level for the thermodynamic system is analogous to at
the Cost Function . Finally, the ground state is analogous to the desired GMACA
rule space. So, we employ and appropriately tune the Simulated Annealing to
find out appropriate graphs to arrive at the desired GMACA .
Cost Function: To generate GMACA rules through Phase I-III , we define
a Cost Function ( C ) which is given by

C =1 −| ( n 0 − n 1 )

( n 0 + n 1 ) |

(2)

where n 0 and n 1 are the occurrence of state '0' and '1' of a cell for a particular
configuration respectively. If n 0 n 1 , then the value of C is high; whereas if
n 0 >> n 1 or n 0 << n 1 , then C becomes zero and we get effective GMACA
configurations.

1 1 1 0 1 1 0 1 1 0 1 1

1 1 1 0 1 1 0 1 1 0 1 1

0 1 1 1

0 1 1 1 1 1 1 1

1 1 1 1

Cycle Length = Cycle Length = 3

4

Present Sate Next State

1 1 0 1

Present Sate Next State

1 1 0 1 1 1 1 0 1 1 1 0

1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1

1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1

0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1

1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1

Neighborhood:
Next State:

1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 Neighborhood:

Next State:

1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

0 / 1 0 1 * 1 * * * 1 0 1 * 1 * * *

'Collision'

'No Collision'

Fig. 5. Example of Cycle Length Reduction of a Directed Graph

In Simulated Annealing an initial temperature ( TEMP Initial ) is set. The
temperature decreases exponentially during the process. At each temperature
point ( Temp point ) action is taken on the graphs based on the value of Cost
Function . The entire process continues till temperature becomes zero.
Based on the value of Cost Function , the new set of graphs are generated.
The entire process - generation of graphs, and its evaluation through the Cost
Function - that is, Phase I to III , continues till temperature becomes zero. So, the
emphasis is to arrive at graphs with low value of Cost Function . This demands
low collision. Following two schemes are employed to reduce the collision on
the randomly generated graph with attractor cycle length l ≤ L max in Phase