Creating Life in a Computer

Andrew Singleton

THE GARDEN IN THE MACHINE, Claus Emmeche, Princeton University Press, ISBN 0-691-03330-7, $24.95

GENETIC PROGRAMMING, John R. Koza, MIT Press, ISBN 0-262-11170-5, $60

GENETIC PROGRAMMING 2, John R. Koza, MIT Press, ISBN 0-262-11189-6, $45

ADVANCES IN GENETIC PROGRAMMING, Kenneth L. Kinnear Jr., MIT Press, ISBN 0-262-11188-8, $45

ARTIFICIAL LIFE II, Edited by Christopher G. Langton, Charles Taylor, J. Doyne Farmer, and Steen Rasmussen, Addison-Wesley, ISBN 0-201-52571-2, $36.75

GENETIC ALGORITHMS IN SEARCH, OPTIMIZATION, AND MACHINE LEARNING, David E. Goldberg, Addison-Wesley, ISBN 0-201-15767-5, $48.50

GENETIC ALGORITHMS (FOURTH INTERNATIONAL CONFERENCE), Richard K. Belew and Lashon B.Booker, Morgan Kaufmann, ISBN 1-55860-208-9, $4 4.95

GENETIC ALGORITHMS (FIFTH INTERNATIONAL CONFERENCE), Stephanie Forrest, Morgan Kaufmann, ISBN 1-55860-299-2, $44.95

Artificial life (AL) burst on the scene as a science, a technology, a philosophy, and a group of personalities during the first AL conference in 1987. Now, with Claus Emmeche's book The Garden in the Machine, we have a concise guide to all the various threads, tied together with Emmeche's own philosophical analysis.

AL researchers explore "the biology of the possible." They believe that we can use computers to explore the world not of BL (biological life) but of many possible alternative life-forms. They define life not by its material substance but by its organization, which can include the patterns of information in a computer. The researchers believe life in all its forms has mechanisms for processing energy and information that emerge from some fundamental order in the universe, a new natural law that shapes those forms out of chaos.

If life can have alternate forms, what is life? With that question, we plunge into the zoology of AL, including its history, its technologies, and its personalities, all in only 166 pages. We learn about exobiology, biochips, artificial chemistry, genetic algorithms, animats, cellular automata, computational ecology and thermodynamics, the edge of chaos, and the riddle of morphogenesis.

The history lesson begins with Aristotle, who proposed "psyche," the force that gives animals independent motivations, and continues through John von Neumann, who drew up a detailed plan for a "self-reproducing automaton." Emmeche introduces biologists such as Louis-Jean-Marie Daubenton, C. H. Waddington, and Jay Gould. We meet Tom Ray, creator of evolving AL creatures, and Christopher G. Langton, the organizational father of AL, author of the "seven commandments" of AL, and originator of the "edge of chaos" theory of computation.

We see the influence of Stephen Wolfram, who explored the space of cellular automata, and Edward Fredkin, who believes the universe is a cellular automaton. We get a quick explanation of the evidence behind Stuart Kauffman's claim to have found mathematical principles for the organization of life, and an even quicker review of John H. Holland's genetic algorithms.

This book does not require a knowledge of computer science. The description of cellular automata and the game of Life recounts how John Conway's first experiments involved moving dishes around on his floor tiles. To his infinite credit, Emmeche does not oversimplify the science or the philosophy that he is describing, and his paraphrase of technical points is accurate.

Emmeche writes that AL research is a shadow world that exists mostly in theories. They won't bring forth a slimy snail or a nightingale. As a biologist, Emmeche has come to terms with the capabilities and limitations of AL in relation to his chosen field. But he stops short of exploring the larger cultural and ethical implications of AL.

AL imitating BL relies on bottom-u p evolution. BL starts with relatively simple organisms and builds more complex behavior through evolution and emergence. This principle, applied to the creation of AI, is the motivation for genetic programming. Starting with thousands of simple, randomly generated programs, genetic programmers attempt to cull out the ones with useful behavior. They apply a genetic algorithm to select the best candidates, modify them with mutation and crossover (or mating), and create a new population of candidates. A refined version of this process might build up software with powerful capabilities. At the very least, we know that a similar mechanism can yield surprising results in the realm of BL.

Where philosophers blaze a trail, engineers follow with paving equipment, and nobody has heavier machinery than John R. Koza. His book Genetic Programming weighs in at 800 pages and contains data from hundreds of experiments. Each experiment required runs from several hours to several days on an aging Lisp machine and inclu des its own statistical charts.

The book contains an introduction to genetic algorithms and a thorough explanation of the mechanism for applying a genetic algorithm to generate S-expressions or Lisp expressions. The appendix contains the complete listing in Lisp code of a simple genetic-programming system and several other tools. The reference material is complete enough to teach you how to do genetic programming and reproduce many of the experiments.

Koza is a pioneer in the field of genetic programming, and he has faced a number of skeptics. The idea of randomly combining computer routines does sound crazy to anyone who has faced the difficulty of debugging even a carefully constructed routine. His book includes a sometimes plodding attempt to justify genetic programming as a systematic and widely applicable method.

The book starts with two claims. One, that many problems can be cast "as requiring the discovery of a program that produces some desired output when presented with particula r inputs," or program induction. Two, that genetic programming is an effective way to do program induction. The book then presents a wide variety of problems and demonstrates how to set them up as program-induction problems. In finding and setting up these problems, Koza shows real ingenuity.

He solves classic control problems, such as cart balancing, and introduces diversions like the optimal feeding strategy for a lizard. Through this all, it is apparent that genetic programming can solve only simplified problems. In an attempt to solve more difficult and more realistic problems, Koza introduces the idea of Automatically Defined Functions, or ADFs. These are evolved subroutines, which add a more complex, hierarchical structure to the evolved programs. ADFs are the subject of a second weighty tome entitled Genetic Programming 2.

It explores the application of ADFs in chapters such as "The Bumblebee Problem" and "Prediction of Omega Loops in Proteins." It examines how ADFs perform as problems ge t harder. It shows how you can force ADFs to take on specialized functions and exploit this specialization. It looks at ADFs with fixed arguments, with no arguments, and with an evolved number of arguments. The book demonstrates that ADFs bring more difficult problems within reach, although it leaves open the question of how genetic programming can be scaled up to produce, for instance, a machine-vision system.

For all their depth, Koza's books are extremely narrow. They present only one particular mechanism for doing genetic programming. A few of Koza's conclusions, like the one that mutation is not useful, are wrong. A more expansive view of genetic programming comes from Kenneth L. Kinnear's Advances in Genetic Programming. This anthology of papers from 22 contributors shows off the exuberance of the new field.

Advances in Genetic Programming contains useful work on theory, representations, and applications. Kinnear compares ADFs to other methods for building hierarchy. Eric Teller shows how genetic programming can evolve the use of memory, or "mental models." Frederick Gruau demonstrates how genetic programming can be applied to generate embryos that expand into neural networks. Peter Nordin applies a genetic algorithm to generate superfast machine-language programs rather than Lisp. The book also contains examples of truly practical genetic-programming applications. Brij Masand used genetic programming to optimize text classification, and Howard Oakley used it to produce a useful stack filter for measuring blood flow. Several authors present approaches to image recognition.

Even if you never have the patience to read academic conference proceedings, you should read Artificial Life II, the proceedings of the second conference on AL held in Santa Fe in 1989. It contains a remarkable concentration of influential and broadminded writing. Christopher Langton examines the conditions that lead to interesting behavior (here called "extended transients") in cellular automata and, by implication, in the crucibles of AL and evolution. Thinking Machines founder W. Daniel Hillis adds to the practice of artificial evolution with the technique of "Co-Evolving Parasites." And Robert J. Collins and David R. Jefferson describe their "Ant Farm" experiments in simulated evolution.

You too can get involved. A practical background for those excited about genetic programming begins with David E. Goldberg's textbook Genetic Algorithms in Search, Optimization, and Machine Learning. The two Genetic Algorithms books suggest some of the several ways that genetic algorithms can be applied. Internet mailing lists and newsgroups track the current action.

---

Andrew Singleton is president of Creation Mechanics (Dublin, NH), a software development company specializing in genetic programming for financial analysis. You can reach him on the Internet or BIX at editors@bix.com or at p0039@psilink.com .