- author = "Lorenz Huelsbergen",
- title = "Learning Recursive Sequences via Evolution of Machine-Language Programs",
- booktitle = "Genetic Programming 1997: Proceedings of the Second Annual Conference",
- editor = "John R. Koza and Kalyanmoy Deb and Marco Dorigo and David B. Fogel and Max Garzon and Hitoshi Iba and Rick L. Riolo",
- year = "1997",
- month = "13-16 " # jul,
- keywords = "genetic algorithms, genetic programming, MLGP",
- pages = "186--194",
- address = "Stanford University, CA, USA",
- publisher_address = "San Francisco, CA, USA",
- publisher = "Morgan Kaufmann",
-
URL = "
http://bell-labs.co/who/lorenz/papers/gp97.pdf",
-
URL = "
http://cm.bell-labs.com/cm/cs/who/lorenz/papers/gp97.ps",
- size = "9 pages",
-
abstract = "We use directed search techniques in the space of
computer programs to learn recursive sequences of
positive integers. Specifically, the integer sequences
of squares, x^2; cubes, x^3; factorial, x!; and
Fibonacci numbers are studied. Given a small finite
prefix of a sequence, we show that three directed
searches, machine-language genetic programming with
crossover, exhaustive iterative hill climbing, and a
hybrid (crossover and hill climbing), can automatically
discover programs that exactly reproduce the finite
target prefix and, moreover, that correctly produce the
remaining sequence up to the under lying machine
precision.
Our machine-language representation is generic, it contains instructions for arithmetic, register manipulation and comparison, and control flow. We also introduce an output instruction that allows variable-length sequences as result values. Importantly, this representation does not contain recursive operators; recursion, when needed, is automatically synthesised from primitive instructions.
For a fixed set of search parameters (e.g., instruction set, program size, fitness criteria), we compare the frequencies of the three directed search techniques on the four sequence problems. For this parameter set, an evolutionary-based search always out performs exhaustive hill climbing as well as undirected random search. Since only the prefix of the target sequence is variable in our experiments, we posit that this approach to sequence induction is potentially quite general.",
- notes = "GP-97. Comparison with random search",
