Information Technology Reference
In-Depth Information
Example 2
The
Fig.4 (a)
represents two arbitrary graphs generated in Phase I
for n
=4
and r
max
=1
. Patterns to be learnt P
1
= 0000
and P
2
= 1111
are
mapped onto the nodes of the attractor cycle of length 3 and 1 respectively. The
sets
0001
,
0010
,
0100
,
1000
and
1110
,
1101
,
1011
,
0111
are the noisy patterns
with noise of 1 bit added to P
i
(i
=1
,
2
, ···) respectively. These are mapped in
two attractor basins as shown in
Fig.4 (a)
.
Phase II
- From all the graphs selected in
Phase I
, we generate a state tran-
sition table. The
Fig.4 (b)
represents state transition tables derived from two
directed graphs shown in
Fig.4 (a)
. Total number entries in the state transition
table is
k · p
, where
k
is the number of patterns to be learnt and
p
is the number
of states in the graph generated as per the
Equation 1
. For the example, graphs
of
Fig.4 (a)
, the number of patterns to be learnt (
k
)is2(
P
1
and
P
2
) and the
number of states in each basin (
p
) is 5. So the total number entries in the state
transition table of
Fig.4 (b)
is 10.
Phase III
- Design the rule vector of the
GMACA
cells from the state tran-
sition table.
Consider
i
th
cell whose rule is to be identified. We concentrate on 3 columns
-(
i −
1)
th
,
i
th
and (
i
+1)
th
columns of all the
k · p
number of patterns of the
state transition table of
Fig.4 (b)
. Suppose, for a present state configuration of
the
i
th
cell, the next state is '0' for
n
0
times and '1' for
n
1
times, then state
'0' and '1' collides with each other to become the next state of the cell for that
configuration.
The
Fig.4 (c)
represents the neighborhood configurations along with the next
state of 2
nd
and 3
rd
cells of the patterns of two basins noted in
Fig.4 (b)
. For 2
nd
cell, there is no collision between next state '0' and '1' of the cell for 8 possible
configurations. Whereas for '000' neighborhood configuration, the next state of
3
rd
row of
Fig.4 (b)
) for 1 time and '1' (4
th
row of
Fig.4 (b)
) for 1 time. That
is,
n
0
= 1 and
n
1
= 1. So, for '000' configuration, the next state of 3
rd
cell may
be '0' or '1' generating an instance of collision.
In order to resolve this conflict we introduce the following heuristics.
3.2 Resolution of Collision
-
If
n
0
n
1
, the collision between state '0' and '1' is high. In that case, we
randomly decide the next state of a cell.
-
If
n
0
>> n
1
or
n
0
<< n
1
, the collision is minimum. In that case, the next
state of a cell is '0' if
n
0
>n
1
, otherwise '1'.
Design of a synthesis algorithm to arrive at an effective
GMACA
,weob-
served, is a
hard problem
. So, we fall back on the
Simulated Annealing
(
SA
)
program to solve this problem.
3.3 Simulated Annealing Program to Evolve Effective GMACA
Simulated annealing is a generalization of a Monte Carlo method for examining
the equations of state and frozen states of n-body systems. The
GMACA
synthe-
sis scheme can be elegantly mapped to this Monte Carlo approach. The current