CONVERGENCE TO UNIFORMITY IN A CELLULAR-AUTOMATON VIA LOCAL COEVOLUTION

Cellular programming is a coevolutionary algorithm by which parallel c ellular systems evolve to solve computational tasks. The evolving syst em is a massively parallel, locally interconnected grid of cells, wher e each cell operates according to a local interaction rule. If this ru le is identical for all cells, the system is referred to as uniform, o therwise, it is non-uniform. This paper describes an experiment that a ddresses the following question: Employing a local coevolutionary proc ess to solve a hard problem, known as density classification, can an o ptimal uniform solution be found? Since our approach involves the evol ution of non-uniform CAs, where cellular rules are initially assigned at random, such convergence to uniformity cannot be a priori expected to easily emerge. The question is of both theoretical and practical in terest. As for the latter, one major advantage of local evolutionary p rocesses is their amenability to parallel implementation, using commer cially available parallel machines or specialized hardware. Our experi ment shows that when such local evolution is applied to the density pr oblem, the optimal solution can be found.