Self-adaptive mutation rates in genetic algorithm for inverse design of cellular automata

ABSTRACT

Self-adaptation is used a lot in Evolutionary Strategies and with great success, yet for some reason it is not the mutation adaptation of choice for Genetic Algorithms. This poster describes how a self-adaptive mutation rate was used in a Genetic Algorithms to inverse design behavioral rules for a Cellular Automata. The unique characteristics of this search space gave rise to some interesting convergence behavior that might have implications for using self-adaptive mutation rates in other Genetic Algorithm applications and might clarify why self-adaptation in Genetic Algorithms is less successful than in Evolutionary Strategies.

REFERENCES

• 1: Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
• 2: Thomas Bäck , Martin Schütz, Intelligent Mutation Rate Control in Canonical Genetic Algorithms, Proceedings of the 9th International Symposium on Foundations of Intelligent Systems, p.158-167, June 09-13, 1996
• 3: R. Breukelaar , Th. Bäck, Using a genetic algorithm to evolve behavior in multi dimensional cellular automata: emergence of behavior, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068024]
• 4: Eiben, A.E., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms Evolutionary Computation, IEEE Transactions on Evolutionary Computation' Volume 3, Issue 2, Jul (1999), pages:124--141
• 5: Mitchell, M., Crutchfield, J.P.: The Evolution of Emergent Computation. Proceedings of the National Academy of Sciences (1994), SFI Technical Report 94-03-012
• 6: 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]
• 7: Wolfram, S.: Statistical mechanics of Cellular Automata. Reviews of Modern Physics volume 55 (1983)
• 8: Wolfram, S.: 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, Theory

Keywords:
cellular automata, genetic algorithms, self adaptation