ORLANDO, Fla. Genetic algorithms and similar evolutionary programming techniques have solved a variety of nondeterministic polynomial time problems (NPs) that proved impossible to crack using conventional techniques. Yet other NPs have proven resistant to genetic algorithms. Ingo Rechenberg of the Technical University of Berlin claimed to know why, at the recent Genetic and Evolutionary Computation Conference.
"A problem is best for solution by evolutionary techniques if it is decomposable into separate pockets of order, each of which follows the rule of strong causality that similar causes produce similar effects," according to Rechenberg.
Rechenberg's experiments led him to create an algebra of evolution, whereby each nested intermediary step parents, grandparents, great-grandparents and so on is represented by separate terms in an "evolutionary equation." The easiest problems to solve, he found, are those that can be broken down into separate, but related, regions.
"The prerequisite to all human action is strong causality that similar causes will produce similar effects. This also turns out to be the prerequisite for the solution of a problem using evolutionary programming techniques," Rechenberg said. His work involved real-life simulations such as wind tunnels, a type of experiment researchers often shun in favor of running a simulation inside a computer.
Yet real-life simulations are often not so arduous as one might imagine, Rechenberg said. Charles Darwin himself ran primitive wind-tunnel experiments to find the optimal shape of an eight-segment pre-airplane "wing." Of 345 million possible configurations, only 300 had to be evaluated before Darwin found the optimal one.
"Why is it so relatively easy to find the optimal solution to some NP problems, and others seem impossible to solve?" asked Rechenberg. To find out, he set up a wind tunnel to find the optimal airflow inside a pipe that must bend around a 90 angle. In a short time, Rechenberg showed that a nonintuitive bend structure, which has a slight reverse bend near its end section, was optimal. In a second experiment that sought to find the optimal 180 bend, Rechenberg found the first clue to the puzzle.
"It appeared from my experiments that these problems were so easily solved because parental information was building up in the offspring," he said. In other words, the genetic programming scheme was discovering the solution a little at a time. In the pipe-bending example, the reverse bend that proved a good solution for the 90 bend was repeated and elaborated upon in the 180 solution. Each offspring that proved to be better than its parent had retained a part of its grandparent, its great-grandparent and all the previous generations, Rechenberg said.
Generation by generation
Further work revealed that evolutionary techniques functioned best when they were "nested." For instance, in all the problems solved, the best genetic algorithm was the one that first found the optimal size of each mutation, then repeated that optimal size each generation to eventually find the overall optimal solution to the problem. Since the optimal-mutation-step size had to be found first, Rechenberg got the idea that perhaps other nested optimal steps housed information that seemed to pass on from grandparent to parent to offspring.
That algebraic approach gave him the clue he needed to solve the puzzle that is, which types of problems can be formulated in his evolutionary equation.
The critical property is the smoothness of the underlying solution space. Starting from a nearby point would lead to closely similar results. In contrast, solution spaces that are chaotically configured could not be solved by genetic algorithms.