Cheaper than printing it out: buy the paperback book.

Out of Control
Chapter 15: ARTIFICIAL EVOLUTION

David Ackley is a researcher of neural nets and genetic algorithms at Bellcore, the R&D labs for the Baby Bells. Ackley has some of the most original ways of looking at evolutionary systems that I've come across.

Ackley is a bear of a guy with a side-of-the-mouth wisecracking delivery. He broke up 250 serious scientists at the 1990 Second Artificial Life Conference with a wickedly funny video of a rather important artificial life world he and colleague Michael Littman had made. His "creatures" were actually bits of code not too different from a classical GA, but he dressed them up with moronic smiley faces as they went about chomping each other or bumping into walls in his graphical world. The smart survived, the dumb died. As others had, Ackley found that his world was able to evolve amazingly fit organisms. Successful individuals would live Methuselahian lifetimes -- 25,000 day-steps in his world. These guys had the system all figured out. They knew how to get what they needed with minimum effort. And how to stay out of trouble. Not only would individuals live long, but the populations that shared their genes would survive eons as well.

Noodling around with the genes of these streetwise creatures, Ackley uncovered a couple of resources they hadn't taken up. He saw that he could improve their chromosomes in a godlike way to exploit these resources, making them even better adapted to the environment he had set up for them. So in an early act of virtual genetic engineering, he modified their evolved code and set them back again into his world. As individuals, they were superbly fitted and flourished easily, scoring higher on the fitness scale than any creatures before them.

But Ackley noticed that their population numbers were always lower than the naturally evolved guys. As a group they were anemic. Although they never died out, they were always endangered. Ackley felt their low numbers wouldn't permit the species to last more than 300 generations. So while handcrafted genes suited individuals to the max, they lacked the robustness of organically grown genes, which suited the species to the max. Here, in the home-brewed world of a midnight hacker, was the first bit of testable proof for hoary ecological wisdom: that what is best for an individual ain't necessarily best for the species.

"It's tough accepting that we can't figure out what's best in the long run," Ackley told the Artificial Life conference to great applause, "but, hey, I guess that's life!"

Bellcore allowed Ackley to pursue his microgod world because they recognized that evolution is a type of computation. Bellcore was, and still is, interested in better computational methods, particularly those based on distributed models, because ultimately a telephone network is a distributed computer. If evolution is a useful type of distributed computation, what might some other methods be? And what improvements or variations, if any, can we make to evolutionary techniques? Taking up the usual library/space metaphor, Ackley gushes, "The space of computational machinery is unbelievably vast and we have only explored very tiny corners of it. What I'm doing, and what I want to do more of, is to expand the space of what people recognize as computation."

Of all the possible types of computation, Ackley is primarily interested in those procedures that underpin learning. Strong learning methods require smart teachers; that's one type of learning. A smart teacher tells a learner what it should know, and the learner analyzes the information and stores it in memory. A less smart teacher can also teach by using a different method. It doesn't know the material itself, but it can tell when the learner guesses the right answer -- as a substitute teacher might grade tests. If the learner guesses a partial answer the weak teacher can give a hint of "getting warm," or "getting cold" to help the learner along. In this way, a weaker teacher can potentially generate information that it itself doesn't own. Ackley has been pushing the edge of weak learning as a way of maximizing computation: leveraging the smallest amount of information in, to get the maximum information out. "I'm trying to come up with the dumbest, least informative teacher as possible," Ackley told me. "And I think I found it. My answer is: death."

Death is the only teacher in evolution. Ackley's mission was to find out: what can you learn using only death as a teacher? We don't know for sure, but some candidates are: soaring eagles, or pigeon navigation systems, or termite skyscrapers. It takes a while, but evolution is clever. Yet it is obviously blind and dumb. "I can't imagine any dumber type of learning than natural selection," says Ackley.

In the space of all possible computation and learning, then, natural selection holds a special position. It occupies the extreme point where information transfer is minimized. It forms the lowest baseline of learning and smartness, below which learning doesn't happen and above which smarter, more complicated learning takes place. Even though we still do not fully understand the nature of natural selection in coevolutionary worlds, natural selection remains the elemental melting point of learning. If we could measure degrees of evolution (we can't yet) we would have a starting benchmark against which to rate other types of learning.

Natural selection plays itself out in many guises. Ackley was right; computer scientists now realize that many modes of computation exist -- many of them evolutionary. For all anyone knows, there may be hundreds of styles of evolution and learning. All such strategies, however, perform a search routine through a library or space. "Discovering the notion of the 'search' was the one and only brilliant idea that traditional AI research ever had," claims Ackley. A search can be accomplished in many ways. Natural selection -- as it is run in organic life -- is but one flavor.

Biological life is wedded to a particular hardware: carbon-based DNA molecules. This hardware limits the versions of search-by-natural-selection that can successfully operate upon it. With the new hardware of computers, particularly parallel computers, a host of other adaptive systems can be conjured up, and entirely different search strategies set out to shape them. For instance, a chromosome of biological DNA cannot broadcast its code to DNA molecules in other organisms in order for them to receive the message and alter their code. But in a computer environment you can do that.

David Ackley and Michael Littman, both of Bellcore's Cognitive Science Research Group, set out to fabricate a non-Darwinian evolutionary system in a computer. They chose a most logical alternative: Lamarckian evolution -- the inheritance of acquired traits. Lamarckism is very appealing. Intuitively such a system would seem deeply advantageous over the Darwinian version, because presumably useful mutations would be adopted into the gene line more quickly. But a look at its severe computational requirements quickly convinces the hopeful engineer how unlikely such a system would be in real life.

If a blacksmith acquires bulging biceps, how does his body reverse- engineer the exact changes in his genes needed to produce this improvement? The drawback for a Lamarckian system is its need to trace a particular advantageous change in the body back through embryonic development into the genetic blueprints. Since any change in an organism's form may be caused by more than one gene, or by many instructions interacting during the body's convoluted development, unraveling the tangled web of causes of any outward form requires a tracking system almost as complex as the body itself. Biological Lamarckian evolution is hampered by a strict mathematical law: that it is supremely easy to multiply prime factors together, but supremely hard to derive the prime factors out of the result. The best encryption schemes work on this same asymmetrical difficulty. Biological Lamarckism probably hasn't happened because it requires an improbable biological decryption scheme.

But computational entities don't require bodies. In computer evolution (as in Tom Ray's electric-powered evolution machine) the computer code doubles as both gene and body. Thus, the dilemma of deriving a genotype from the phenotype is moot. (The restriction of monolithic representation is not all that artificial. Life on Earth must have passed through this stage, and perhaps any spontaneously organizing vivisystem must begin with a genotype that is restricted to its phenotype, as simple self-replicating molecules would be.)

In artificial computer worlds, Lamarckian evolution works. Ackley and Littman implemented a Lamarckian system on a parallel computer with 16,000 processors. Each processor held a subpopulation of 64 individuals, for a grand total of approximately one million individuals. To simulate the dual information lines of body and gene, the system made a copy of the gene for each individual and called the copy the "body." Each body was a slightly different bit of code trying to solve the same problem as its million siblings.

The Bellcore scientists set up two runs. In the Darwinian run, the body code would mutate over time. By chance a lucky guy might become code that provides a better solution, so the system chooses it to mate and replicate. But in Darwinism when it mates, it must use its original "gene" copy of the code -- the code it inherited, not the improved body code it acquired during its lifetime. This is the biological way; when the blacksmith mates, he uses the code for the body he inherited, not the body he acquired.

In the Lamarckian run, by contrast, when the lucky guy with the improved body code is chosen to mate, it can use the improved code acquired during its lifetime as the basis for its mating. It is as if a blacksmith could pass on his massive arms to his offspring.

Comparing the two systems, Ackley and Littman found that, at least for the complicated problems they looked at, the Lamarckian system discovered solutions almost twice as good as the Darwinian method. The smartest Lamarckian individual was far smarter than the smartest Darwinian one. The thing about Lamarckian evolution, says Ackley, is that it "very quickly squeezes out the idiots" in a population. Ackley once bellowed to a roomful of scientists, "Lamarck just blows the doors off of Darwin!"

In a mathematical sense, Lamarckian evolution injects a bit of learning into the soup. Learning is defined as adaptation within an individual's lifetime. In classical Darwinian evolution, individual learning doesn't count for much. But Lamarckian evolution permits information acquired during a lifetime (including how to build muscles or solve equations) to be incorporated into the long-term, dumb learning that takes place over evolution. Lamarckian evolution produces smarter answers because it is a smarter type of search.

The superiority of Lamarckism surprised Ackley because he felt that nature did things so well: "From a computer science viewpoint it seems really stupid that nature is Darwinian and not Lamarckian. But nature is stuck on chemicals. We're not." It got him thinking about other types of evolution and search methods that might be more useful if you weren't restricted to operating on molecules.

continue...