## Evolving Local Rules to Perform Global Computations

*26 Jan 2011 11:36*

Some computational problems are very natural and easy in a centralized framework. Say you have a string of bits, and want to count how many of them are 0s. This is trivial, if you have a centralized memory. But suppose you don't; suppose instead you can only perform and record spatially localized operations, where you look at a bit and a few others near it, but do this for each part of the string in parallel. Then it turns out to be very hard to find rules which do well. This is interesting for a number of reasons. One, we're going to be building more and more distributed computers, and so we'd like to understand their scope and limits, and know what we can and cannot ask for in the way of global properties. Two, some of us are just generally into knowing about how local interactions produce global phenomena. Three, lots of biological computation, in particular what brains do, looks an awful lot like decentralized processors with local interactions solving (or faking) global problems, so maybe this will teach us something about ourselves.

Inspired, in part, by the last point, and by the general hardness of the task, quite a few people have turned to genetic algorithms as a way of finding local rules --- especially cellular automata --- which peform globally-simple computations in a decentralized way. Two of the leading test cases are density classification (does the input string contain more 0s than 1s?) and synchronization (get every cell to switch between 0 and 1 together). The point isn't that these are interesting or important tasks in themselves, which has escaped some people. If anything, the point is that these are trivial tasks, which decentralized systems nonetheless find very hard...

See also: Collective Cognition; Duality between Knowledge Centralization and Market Completeness; Evolutionary Design

- Recommended:
- The papers of the Evolving Cellular Automata Project
- James P. Crutchfield and Melanie Mitchell, "The Evolution of
Emergent Computation", Proceedings of the National Academy of
Sciences (USA)
**92**(1995): 10742--10746 [PDF preprint, journal link] - Thimo Rohlf and Stefan Bornholdt
- "Self-organized pattern formation and noise-induced control from particle computation", cond-mat/0312366 [Short version]
- "Morphogenesis by coupled regulatory networks", q-bio.MN/0401024 [Long version, which includes discussion of how to implement the CA rule by means of highly stylized gene regulatory networks]

- André A. Moreira, Abhishek Mathur, Daniel Diermeier and
Luís A. N. Amaral, "Efficient system-wide coordination in noisy
environments", Proceedings of the
National Academy of Sciences (USA)
**101**(2004): 12085--12090

- To read:
- Philippe Collard, Sebastien Verel, Manuel Clergue, "Local search heuristics: Fitness Cloud versus Fitness Landscape", arxiv:0709.4010
- Vitaly Feldman, "Robustness of Evolvability" [PDF preprint]
- Carlos Gershenson, "A General Methodology for Designing Self-Organizing Systems", nlin.AO/0505009
- Thilo Gross and Bernd Blasius, "Adaptive Coevolutionary Networks -- A Review", arxiv:0709.1858
- S. M. D. Seaver, A. A. Moreira, M. Sales-Pardo, R. D. Malmgren, D. Diermeier, L. A. N. Amaral, "Micro-bias and macro-performance", European
Physical Journal B
**67**(2009): 369--375, arxiv:0908.4261 - Colin Torney, Zoltan Neufeld and Iain D. Couzin, "Context-dependent interaction leads to emergent search behavior in social aggregates", Proceedings of the National Academy of Sciences (USA)
**106**(2009): 22055--22060 - Daniel Treisman, The Architecture of Government: Rethinking Political Decentralization [blurb]
- Sebastien Verel, Philippe Collard, Marco Tomassini, Leonardo
Vanneschi, "Fitness landscape of the cellular automata majority problem: View
from the Olympus", arxiv:0709.3974
= Theoretical Computer Science
**378**(2007): 54--77