User:Hope09
From Wikipedia, the free encyclopedia
[edit] Evolving Cellular automata using Genetic Algorithms
Recently there has been a keen interest in building decentralized systems, be it sensor networks or more sophisticated micro level structures designed at network level and aimed at decentralized information processing. The idea of emergent computation came form the need of using distributed system to do information processing at the global level. Although, it is still an area in infancy but some people have started taking the idea seriously. Melanie Mitchell who is the Professor of computer science at Portland State University and also the Santa Fe Institute External professor has been working on the idea of using self evolving cellular arrays to study emergent computation and distributed information processing. Mitchell and colleagues at SFI are working on evolutionary computation to program cellular arrays for performing computations. Computation in decentralized systems is very different from classical systems where the information is processed at some central location depending on the system’s state. In decentralized system, the information processing occurs in form of global and local pattern dynamics.
The inspiration for such an approach comes from complex natural systems like insect colonies, nervous system and economic systems. The focus of the research is to know that how computation occurs in an evolving decentralized system. In order to model some of the features of these systems and to see how they give rise to emergent computation, Mitchell and collaborators at the SFI have applied Genetic Algorithms to evolve patterns in cellular automata. In their results they were able to show that the GA discovered rules that gave rise to sophisticated emergent computational strategies. Mitchell’s group used a single dimensional binary (each cell can have 2 states) array where each cell has 2 neighbors. The array can be thought of as a circle where the first and last cells in the array are neighbors to each other. The evolution of the array was tracked through the number of ones and zeros after each iteration. The results were plotted in form of space time diagrams which showed clearly that how the network evolved and what sort of emergent computation was visible. One thing in which the researchers were interested was to know the competing regions with regards to the density of ones or zeros.
The beauty of complex systems occurring in nature is that actions of simple components with local information and communication give rise to coordination global information processing. Although, it is not yet known that how such systems give rise to computation over global scale but models of the form of cellular automata may uncover a lot of hidden features of such systems. The motivation for such an approach comes from the need of understanding natural systems and also to engineer decentralized artificial systems which can give rise to emergent computation.
Mitchell’s group showed three levels of information processing occurring during iterations in evolving cellular automata. The first type was the storage and transmission of information due to particles (cell) interactions. The second level comprised of the geometric subroutines that implemented intermediate-scale computations for example the size competition between regions of low and high density. The third level is the global computation over entire lattices (emergent computation at the global scale).
The type of results produced by Mitchell’s group is interesting in the sense that a very simple single dimensional array of cellular automata produced results showing coordination over global scale which fits to the idea of emergent computation.
Future work in the area may include more sophisticated models using cellular automata of higher dimensions which can be used to model complex natural systems. Apart from emergent computation, various other aspects of complex natural systems are also studied using cellular automata which include communication and interaction in insect societies, cognition and other naturally occurring systems.
[edit] References
[1] Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
[2] The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
[3] The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
