Home » Library » Modern Library » Meta Getalife Epgp

Meta Getalife Epgp


 
 
   

Get A-life

Evolutionary Programming

After the unexpected success of Tierra, computer scientists began to explore whether similar techniques could be used to evolve real, useful code. Today, the state of the art is Genetic Programming or Evolutionary Programming, invented (and patented) in 1992 by John R. Koza of Stanford University.

Like Tierra, the “DNA” of Genetic Programming is a set of equations and operations, not just parameters; but instead of reaping the code that crashes and rewarding the code that copies itself in the smallest space, Evolutionary Programming measures how well each program does at solving a particular problem. The programs that do the worst are eliminated, and new strains of program code are bred by recombination, either with or without mutation.

The solutions produced by evolutionary programming resemble the solutions we find in the real world in several ways. To start with, they are very hard (or even impossible) to understand: the code makes no sense whatsoever to a human mind. It may use functions that seemingly have no logical relevance to the problem, like using trigonometry to solve a binary arithmetic problem. Typically evolved programs will consist of one long line of code, with literally hundreds of nested expressions.

Another characteristic of evolved solutions is that they’re messy. They may include obviously unnecessary operations in one part of the code, yet be much more compact than any human programmer can achieve elsewhere. Think of the human eye: it has a far greater sensitivity than the best camera man can build, yet the retina is wired in backwards. The nerve cell wiring is on the inside of the eye, in the way of the light path; the brain processes the gaps out of the sensory data later on. If cameras were built like that, there would be wires going across the film, and you’d paint out the gaps on the prints when you got them back. Intelligent design? Hardly. The very idea is crazy. Yet to the blind process of evolution, it’s perfectly adequate.

A third thing evolutionary solutions have in common is that they’re unpredictable. Because we don’t really understand how the evolved code works, we also don’t know what conditions might make it stop working. A piece of evolved code that computed the best way to drive between two cities in the USA might behave bizarrely if asked about a city a mile across the border in Canada. Yet at the same time, evolved code is often much more robust than programmed code, so long as it has been tested against a wide enough range of sample problems. Because the code is evolved rather than designed, it doesn’t have built into it all the assumptions a human programmer would make–and the Y2K problem is a good example of the value of not making obvious assumptions.

Robustness is good, but the single biggest advantage of Evolutionary Programming is the final thing it has in common with biological evolution: it can solve problems that humans are unable to solve, or come up with solutions better than any human solution. In the biological world, animals can climb stairs, avoid obstacles, catch prey, and do many other things that humans have failed to get a robot to do well. In the a-life world, there are evolved programs like the 22s in Tierra. Lockheed Martin have evolved code that works out how to maneuver spacecraft from one orientation to another. It achieves the goal within 2% of the theoretical minimum time — which is around 10% faster than any human-written code can manage. Imitating nature even more closely may lead to further advances in genetic programming.

One recent innovation is the development of Field-Programmable Gate Arrays, or FPGAs. Whereas a normal computer chip cannot have its design changed once it has been built, FPGAs are completely reprogrammable–you can actually change the wiring of the circuits on the chip. Some researchers are now using this technology to investigate whether it’s possible to evolve hardware, rather than software.

In one experiment, a chip was evolved that would digitally decode a binary signal sent over a telephone line, without using any of the external analog components found in devices such as modems. All digital circuits have “rough edges” where they don’t quite behave exactly like perfect digital components; whereas human engineers try to filter out these irregularities, evolution exploited them. It came up with an almost perfect solution to the problem; it would have been almost impossible for a human electronics expert to build a similar circuit from the same components.

Lessons From A-Life

What, if anything, does all this prove? Is it meaningful to draw a comparison between a-life and real life, or is it a false analogy?

The Game of Life shows us that an incredibly simple system can exhibit complex behavior. All that’s needed are two simple rules inspired by cell biology. Somehow, all of the cell patterns that move across the Life universe, all the machines which breed gliders and glider guns, all the logic gates needed to model a digital computer, they’re all a necessary consequence of those two rules; nobody designed them there. You can play with the hyperreal universe of the Game of Life using a computer, using counters, or just using pen and paper, and the result is the same; but change the rules, and the complex patterns and structures change.

So, complex behavior and elaborate structures don’t require a designer, and don’t even require a complicated explanation. Just two simple mathematical rules might be all it takes. The lesson is shown again in the world of L-plants, where the actual growth of real plants is modeled accurately by repeating the same straightforward operations over and over again.

Biomorphs show us the power of taking that simple iterative system, and adding in selection and mutation. Suddenly the artificial life forms start to act in unexpected ways, and almost seem to exploit the system they live in according to some hidden plan–producing insects in a world built to contain only plants. Tierra more closely resembles the biological world, and as a result the power of evolution is shown even more strongly. Whole new species appear from nowhere, with no human input at all; they evolve ways to reproduce that are better than any human can design.

Finally, Genetic Programming astounds us with solutions so bizarre that they are obviously not the product of any human mind; yet at the same time, they are efficient and often robust, like the biological solutions in the real world which outdo our greatest feats of engineering. All of this is achieved without even hinting to the computer how it should solve the problem.

To put it another way: A sophisticated computer program that is way too complex for humans to understand can now be evolved from random numbers! This completely destroys the Creationist argument that complexity cannot arise without a designer. If evolution can work this way on something as simple as a string of numbers or a chip full of transistors, it clearly ought to work for more complicated systems such as chemical molecules.

In fact, it’s hard to read about all of this A-life research and not be struck by the amazing, almost magical power of evolution. Suddenly life–the real kind–looks a little less inexplicable.

mathew

<mathew>

January 1st, 2000

 

You can send feedback on this article to the Internet Infidels, or continue on to a list of a-life resources on the Internet and suggestions for further reading.

2000.01.01

#01234[5]R

<PRV//NXT>

[Next]