Information Technology Reference
In-Depth Information
peaked around
ρ
0
=1
/
2 and thus it makes a much more di
>
cult case for the
CA (
ρ
0
is the density of 0s in the initial configuration).
Due to the high computational cost, we have performed 15 runs, each lasting
for 100 generations, for each of the asynchronous update policies. This is not
enoughto reachvery good results, but it is su
>
cient for studying the emergence
of well-defined computational strategies, which has been our main objective here.
3.2 Evolutionary Dynamics and Results: Synchronous CAs
Mitchell and co-workers performed a number of studies on the emergence of syn-
chronous CAs strategies for the density task during evolution (see e.g. [6], where
more details can be found). In summary, these findings can be subdivided into
those pertaining to the evolutionary history and those that are part of “final”
evolved automata. For the former, they essentially observed that, in successful
evolution experiments, the fitness of the best rules increase in time according to
rapid jumps, giving rise to what they call “epochs” in the evolutionary process.
Eachepochcorresponds rougly to a new, increasingly sopisticated solution
strategy. Concerning the final CA produced by evolution, it was noted that,
in most runs, the GA found non-sophisticated strategies that consisted in ex-
panding su
>
ciently large blocks of adjacent 1s or 0s. This “block-expanding”
strategy is unsophisticated in that it mainly uses local information to reach a
conclusion. As a consequence, only those IC that have low or high density are
classified correctly since they are more likely to have extended blocks of 1s or 0s.
In fact, these CAs have a performance around 0
.
6. However, some of the runs
gave solutions that presented novel, more sophisticated features that yielded bet-
ter performance (around 0
.
77) on a wide distribution of IC. These new strategies
rely on travelling signals that transfer spatial and temporal information about
the density in local regions through the lattice. An example of such a strategy
is given in figure 1, where the behavior of the so-called GKL rule is depicted [6].
The GKL rule is a hand-coded one but its behavior is similar to that of the best
solutions found by evolution.
3.3 Evolutionary Dynamics and Results: Asynchronous CAs
For the evolution of asynchronous CAs we have used GA parameters as described
in section 3.1. As expected, the evolved asynchronous CAs find it more di
>
cult
to solve the density task due to their stochastic nature. In fact, a given CA could
classify the same initial configuration in a different way depending on the update
sequence, and indeed, although synchronous CAs are delocalized systems, a kind
of central control is still present, because of the presence of a global clock. This is
not the case for asynchronous CAs. Nevertheless, for all the asynchronous update
methods CAs with fair capabilities were evolved. In table 1 we list the best rules
found by the GA for the three update modes. We note that the performance of
the solutions are lower than those for synchronous CAs.
The behavior of the CAs evolved with all three asynchronous updating modes
were very similar both from the point of view of the performance, as well as
