Information Technology Reference
In-Depth Information
finite CA of size
n
(with
n
odd for convenience) it is defined as follows: the CA
must relax to a fixed-point pattern of all 1s if the initial configuration of states
contains more 1s than 0s and, conversely, it must relax to a fixed-point pattern
of all 0s otherwise, after a number of time steps of the order of the grid size.
This computation is trivial for a computer having a central control. However,
the density task is non-trivial for a small radius 1-D CA since such a CA can
only transfer information at finite speed relying on local information exclusively,
while density is a global property of states configuration [6]. It has been shown
that the density task cannot be solved perfectly by a uniform, two-state CA with
finite radius [5], although a slightly modified version of the task can be shown to
enjoy perfect solution by suchan automaton [2]. In general, given a desired global
behavior for a CA, it is extremely di
>
cult to infer the local CA rule that will give
rise to the emergence of the computation sought. Since exhaustive evaluation of
all possible rules is out of the question except for elementary (
d
=1
,r
=1)
automata, one possible solution of the problem consists in using evolutionary
algorithms, as proposed by Mitchell
et al.
[6] for uniform and synchronous CAs
and by Sipper for non-uniform (the rules need not be all the same) ones [8].
3.1 Artificial Evolution of Cellular Automata
Here we use a genetic algorithm similar to the one described in [6] for syn-
chronous CAs, with the aim of evolving asynchronous CAs for the density task.
Eachindividual in the population represents a candidate rule and is represented
simply by the output bits of the rule table in lexicographic order of the neigh-
borhood (see section 2). Here
r
= 3 has been used, which gives a chromosome
lengthof 2
2
r
+1
= 128 and a searchspace of size 2
128
, far too large to be searched
exhaustively. The population size is 100 individuals, each represented by a 128-
bit string, initially randomly generated from a uniform density distribution over
the interval [0
,
1]. The fitness of a rule in the population has been calculated
by randomly choosing 100 out of the 2
n
possible initial configurations (IC) with
uniform density in the same manner as for the initial population and then it-
erating the rule on each IC for
M
=2
n
time steps, where
n
= 149 is the grid
size. The fitness of the rule is the fraction of ICs for which the rule produced
the correct fixed point, given the known IC density. At each generation a differ-
ent set of ICs is generated for each rule. After ranking the rules in the current
population according to their fitness, the 20% top rules are copied in the next
population without change. The remaining 80 rules are generated by crossover
and mutation. Crossover is single-point and is performed between two individu-
als randomly chosen from the top 20 rules with replacement and is followed by
single-bit mutation of the two offspring. The best 80 rules after the application
of the genetic operators enter the new population.
The performance of the best rules found at the end of the evolution is eval-
uated on a larger sample of ICs and it is defined as the fraction of correct clas-
sifications over 10
4
randomly chosen initial configurations. Moreover, the ICs
are sampled according to a binomial distribution, (i.e. eachbit is independently
drawn withprobability 1
/
2 of being 0). Clearly, this distribution is strongly
