In an intriguing role reversal, some computer engineers, faced with tough problems-how to optimally pack grocery bags, for example, or fractionate petroleum for best yield, or schedule assembly line operations-have tried to ape nature by devising programs that generate computer simulations of evolution by natural selection. The much ballyhooed success of these "genetic algorithms" has been taken as yet more support for natural selection's power.
But before you plunk down a few hundred dollars for a genetic algorithm, be sure to heed the "under construction" signs. While genetic algorithms continue to have strong advocates, the gap between promise and delivery looms large. Last year, Carnegie-Mellon computer scientists and genetic algorithm advocates Shameet Baluja and Rich Caruana carried out the most careful bake-off to date: They ran genetic algorithms and other optimization methods (like linear programming) through a standard optimization problem gauntlet, including shopping-bag packing. The standard genetic algorithms never seemed to do as well as other known methods, and only came close when the problem could be carved into several non-interacting factors, with no tradeoffs needed. No surprise, because genetic algorithms really do amount to sending out alpine teams simultaneously in several directions-but again independently, that neat linear assumption. In short, genetic algorithms aren't really "optimizing," and they are good at what they are defined to be good at: taking baby-steps one direction at a time in a space that's easy to hill-climb.
But there was an even bigger surprise: subtracting the biology helped. When Baluja and Caruana removed a biological mirror-"sexual" recombination, the gene-shuffling arising after male and female cells unite-the genetic algorithms did better. Since this "simulated sex" was supposed to be one way in which genetic algorithms gained a lot of their optimizing power-by analogy with nature, testing many possible feature combinations "in parallel" and assembling good partial solutions-this result was a shocker. Even so, there's yet another way in which genetic algorithms fail a biological litmus test: they usually assume a known goal to shoot for-which mountain top to plant the flag on. But natural selection has no "action at a distance." It can't be prospective; it doesn't know that wings will be useful at some future point.
Besides, if there really were such a "universal acid" that could cut through such tough problems, one can be sure that we would have seen a mass stampede in that direction. Why? Because a whole host of the hardest nuts would crack. We would be able to predict next year's interest rates better than George Soros, factor huge prime numbers, and optimally drill oil wells. But we can't do any of these things well. Nor is this argument simply an appeal to Personal Incredulity. If genetic algorithms really worked that well, we could solve all hard problems by first boiling them down-reducing them-to the form of an optimization problem, and then running a genetic algorithm. Perhaps it can be done-but the jury's still out.
-Robert C. Berwick