Discovery of Rewrite Rules in Lindenmayer Systems and State Transition Rules in Cellular Automata via Genetic Programming
John R. Koza, Margaret Jacks Hall · 2004
: It is difficult to write programs for both Lindenmayer systems and cellular automata. This paper demonstrates the possibility of discovering the rewrite rule for Lindenmayer systems and the state transition rules for cellular automata by means of genetic programming. Genetic programming is an extension of the genetic algorithm in which computer programs are genetically bred to solve problems. We demonstrate the use of genetic programming to discover the rewrite rules for a Lindenmayer system for the quadratic Koch island using a pattern matching measure as the driving force for the evolutionary process. We also demonstrate the use of genetic programming to discover the state transition rules for a one-dimensional and two-dimensional cellular automata using entropy as the driving force for the evolutionary process. 1 Introduction and Overview Interesting behavior often emerges from the repetitive application of seemingly simple rules. Both Lindenmayer systems and cellular automata o...