|
|
|
Firefly
In this experiment, the BioWall is an autonomous evolving
hardware system capable of solving the so-called synchronization
task in two dimensions. The visitor is invited to try
and disrupt the synchronization process.
|
In 1997, the Logic Systems Laboratory presented an evolving hardware system
called Firefly, based on a cellular programming approach, in
which parallel cellular machines evolve to solve computational tasks.
The computational task studied and successfully solved is known
as synchronization: given any initial configuration, the non-uniform
CA must reach, within M time steps, a final configuration in which
all cells oscillate synchronously between all 0s and all 1s on successive
time steps. The novelty of Firefly is that it operates with no reference
to an external device (such as a computer that carries out genetic
operators) thereby exhibiting online autonomous evolution.
Whereas the original Firefly machine was able to find a solution for a one-dimensional
CA, we were able to evolve, on the BioWall's 3200 FPGAs, a CA that
solves the synchronization task in two-dimensions. The theoretical
bases of the extension from 1D to 2D are presented in a book.
The implementation on the BioWall consists of a two-state, non-uniform
CA, in which each cell (i.e., each FPGA of the BioWall) may contain
a different rule. The cells' rule tables are encoded as a bit-string,
known as the genome, that has a length of 25=32
bits for our 2D CA (the binary CA has a neighborhood of 5). Rather
than employ a population of evolving CAs, our algorithm evolves
a single, non-uniform CA of the size of the entire BioWall (one
cell of the CA in each unit of the BioWall, that is, 3200 cells),
whose rules are initialized at random. Initial configurations are
then randomly generated and for each configuration the CA is run
for M time steps. Each cell's fitness is accumulated over C initial
configurations: a single run's score is 1 if the cell is in the
correct state after M+4 iterations, and 0 otherwise. The (local)
fitness score for the synchronization task is assigned to each cell
by considering the last four time steps (M+1 to M+4): if the sequence
of states over these steps is precisely 0-1-0-1, the cell's fitness
score is 1, otherwise this score is 0. After every C configurations
the rules are evolved through crossover and mutation. This evolutionary
process is performed in a completely local manner, that is, genetic
operators are applied only between directly connected cells.
Unlike standard genetic algorithms, where a population of independent problem solutions globally evolves, our approach involves a grid of rules that co-evolves locally. The CA implemented on the BioWall performs computations in a completely local manner, each cell having access only to its immediate neighbors' states. In addition, the evolutionary process is also completely local, since the application of genetic operators as well as the fitness assignment takes occurs locally.
Using the above-described cellular programming approach on the BioWall, we have shown that a non-uniform CA of radius 1 can be evolved to successfully solve the synchronization task. In addition, after having found a set of successful rules, our machine allows the state of each CA cell to be changed by pressing on its membrane. The user can then observe how the machine synchronizes the 3200 cells.
For further information
- M. Sipper. The Evolution of Cellular Automata: The Cellular
Programming Approach. Springer-Verlag, Berlin 1997.
Resources
|
A synchronization step on the BioWall.
© C.
Teuscher
506KB JPEG |
|
|