Using a genetic algorithm to evolve behavior in multi dimensional cellular automata: emergence of behavior

ABSTRACT

Cellular automata are used in many fields to generate a global behavior with local rules. Finding the rules that display a desired behavior can be a hard task especially in real world problems. This paper proposes an improved approach to generate these transition rules for multi dimensional cellular automata using a genetic algorithm, thus giving a generic way to evolve global behavior with local rules, thereby mimicking nature. Three different problems are solved using multi dimensional topologies of cellular automata to show robustness, flexibility and potential. The results suggest that using multiple dimensions makes it easier to evolve desired behavior and that combining genetic algorithms with multi dimensional cellular automata is a very powerful way to evolve very diverse behavior and has great potential for real world problems.

REFERENCES

• 1: Th. Bäck, D. B. Fogel, and editors Michalewicz, Z., editors. Handbook of Evolutionary Computation. Oxford University Press and Institute of Physics Publishing, Bristol/New York, 1997.
• 2: A. David, B. Forest, and H. Koza. Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem, 1996.
• 3: P. Gacs, G. L. Kurdyumov, and L. A. Levin. One dimensional uniform arrays that wash out finite islands. Problemy Peredachi Informatsi, 12:92--98, 1978.
• 4: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 5: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 6: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 7: S. Inverso, D. Kunkle, and C. Merrigan. Evolutionary methods for 2-d cellular automata computation. www.cs.rit.edu/~drk4633/mypapers/gacaProj.pdf, 2002.
• 8: W. Li , N. H. Packard , C. G. Langton, Transition phenomena is cellular automata rule space, Physica D, v.45 n.1-3, p.77-94, Sep. 1990 [doi>10.1016/0167-2789(90)90175-O]
• 9: M. Mitchell and J.P. Crutchfield. The evolution of emergent computation. Technical report, Proceedings of the National Academy of Sciences, SFI Technical Report 94-03-012, 1994.
• 10: Melanie Mitchell , James P. Crutchfield , Peter T. Hraber, Evolving cellular automata to perform computations: mechanisms and impediments, Physica D, v.75 n.1-3, p.361-391, Aug. 1, 1994
• 11: S. Wolfram. Statistical mechanics of cellular automata. Reviews of Modern Physics, 55, 1983.
• 12: S. Wolfram. Theory and Applications of Cellular Automata. World Scientific, Singapore, 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation, Performance, Theory