 |
|
|
|
 |
 |
||
 |
 |
 |
|
|
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
Resources
|
