May 1, 2006

Part I: Is Evolution Sufficient?

Accelerating Problem Solving by Combining
Machine Learning and Human Learning
David Fogel, Natural Selection, Inc.
28 min. (slideshow requires QCShow Player)
Audio only (mp3 format)
View as a webpage (quicktime, real player) (notes)

The most salient aspect of Darwinian evolutionary theory is that it is a learning algorithm, no different in effect than the learning that we imply to individuals.

If a process is well understood, it can be exploited for engineering purposes, and indeed evolutionary theory is likely to become the dominant algorithm in computer engineering in the coming decades, providing it with an economic worth comparable to biology's contribution to medicine and agriculture.

But can evolution design anything of quality in any reasonable time? The common perception is that the evolutionary process is both excruciatingly slow and random. Engineers are not only an impatient bunch, they're picky about the quality of their solutions.

In this talk, presented to an engineering audience at Stanford a few months ago, David Fogel talks about this promise, but in the short time available speeds by two attributes of his work that are of profound philosophical importance to biology: (i) the speed of evolution and (ii) the credit-assignment problem.

The Speed of Evolution

Engineering has its common lab problems too, just as biology has Drosophila and Arabidopsis. Among these are the traveling salesman problem (TSP), checkers and chess.

The TSP is easily stated: determine the shortest possible path to visit a specified list of cities, visiting each city only once, and then return home. It is however a problem that grows in complexity amazingly quickly. If there are only 4 cities on the list, there are only 3 possible paths. But if there are 16 cities, then 653,000,0000,000 paths need to be examined to determine the shortest path, and if there are 100 cities, 10¹⁵⁵ possible paths arise.

It's the 100-city problem that is of interest here. Could we find the solution by simple enumeration (that is, by trying every possibility)? It only takes a quick calculation to demonstrate that the answer is no.

If we were to presume that we could evaluate one trial in a femtosecond (10^-15 s), the fastest that any known physical process operates, and if we were to evaluate a million million of these solutions per femtosecond for the length of the age of the galaxy, 10 billion years, then only 10⁴⁴ trials could have been examined. This still leaves 10¹⁵⁵ solutions to be examined. Clearly, if we were to employ this procedure, we would make no headway at all, and thus this simple calculation becomes prevalent in the creationist literature, denying any possibility of unguided evolution.

But this isn't of course the way that evolution operates. It doesn't explore the entirety of the experiential state space. Rather, it merely retains the best of the current phenotypes at each generation, no matter how poor they are. Nonetheless, when this simple process is repeated generation after generation, it quickly generates solutions of astounding quality.

In David's example, which he demonstrates in real-time, a population of only 100 individuals is iterated over 10,000 generations and yet creates a solution within 2% of the expected best path. The procedure takes less than one second on his 1 GHz laptop. This short time doesn't afford you sufficient time to understand the profundity of what happened without first understanding the difficulty of the problem.

The Credit-Assignment Problem

It only seems intuitive to reward good behavior and punish the bad, and thus "weights" are commonly assigned to optimization problems: in manufacturing, where a machinist is paid by the number of widgets he produces per hour, in mathematical genetics, where individual genes are given selection coefficients, and in chess, where the pieces are assigned relative worths.

But this process is also known to generate such poor solutions that it's been given a name, the credit-assignment problem. If weights are in effect, the factory fills up with widgets it can't use.

This too is not how evolution operates. It does a species no good to produce individuals with intestines of extraordinary quality but with defective hearts. The competitiveness of the species' phenotypes is judged by the whole of their responses, not by their individual parts.

In the second half of David's talk, his checkers game experiments are specifically programmed to eliminate the credit-assignment problem. Not only do his evolving populations of neural nets not know the rules of the game that they're playing, he doesn't even tell them if they've won or lost individual games so as to miminize any sense of credit or blame being assigned to individual moves.

Nevertheless, in a relatively short time, with the neural nets competing among themselves on a single, slow machine, they evolved into structures that can outcompete 99.5% of all human contestants.

Perhaps of even greater interest, if the physics of the game should suddenly change, so that red becomes black and vice versa, the evolved structures would for a time do exceptionally poorly under the new rules, but they would also immediately begin to re-evolve, adapting to the new rules and eventually once again become exceptionally competitive.

— Wirt Atmar

About the Speaker

David B. Fogel is the Chief Executive Officer of Natural Selection, Inc. David's experience includes over 19 years of applying computational intelligence methods and statistical experimental design to real-world problems in industry, medicine, and defense.

Dr. Fogel has over 200 publications in the technical literature, the majority treating the science and application of evolutionary computation. He is the author of six books, including Blondie24: Playing at the Edge of AI.

David served as the founding editor-in-chief of the IEEE Transactions on Evolutionary Computation (1996-2002). He was the founding president of the Evolutionary Programming Society (1991-1993) and was elected a Fellow of the IEEE in 1999. He serves as the editor-in-chief of BioSystems, is on the editorial boards of several other technical journals, and is Vice President of Membership Activities for the IEEE Computational Intelligence Society.

David has received a number of honors and awards, including the 2002 Sigma Xi Southwest Region Young Investigator Award, the 2003 Sigma Xi San Diego Section Distinguished Scientist Award, the 2003 SPIE Computational Intelligence Pioneer Award, and most recently the 2004 IEEE Kiyo Tomiyasu Technical Field Award.

Subscribe to the Weekly Notice

If you wish to receive a weekly notice of the current lecture, please send a blank email to: