Natural selection for computers: nature provides the model for a speedy computer search.

Natural Selection for Computers

Randomly stringing together a handful of resistors, capacitors and transistors hardly seems the way to design and build a radio. But that's one way of picturing the starting point for a novel computer-based method used to design jet engines, establish schedules and cope with situations offering a wide range of choices.

The idea is to start with several random arrangements of components that each represent a complete but unorganized system. Most of these chance designs would fare very poorly, but some are bound to be better than others. The superior designs are then "mated" by combining parts of different arrangements to produce "offspring" with characteristics derived from both their "parents."

From this second generation, the computer selects the best or most efficient designs for further "breeding" and rejects the rest. The process continues until an acceptable design or solution to a specific problem emerges.

Methods that incorporate this kind of strategy are known as genetic algorithms. Rooted in the mechanics of natural selection and evolution, they represent a sophisticated kind of search that combines blind groping with precise bookkeeping. Once it has the criteria in hand, the computer itself picks its way through in trial-and-error fashion, recording and building on its best guesses, eventually to find a good answer.

Pioneered more than 25 years ago by computer scientist John H. Holland of the University of Michigan at Ann Arbor, genetic algorithms constitute a field of computer science inspired by biological models and strewn with biological terms. In essence, Holland links the question of how biological systems adapt to their environments with the problem of programming computers so they can learn and solve problems.

The genetic algorithm approach to problem-solving has developed slowly. Only in recent years have researchers begun to appreciate and exploit its flexibility and versatility, especially for designing complex systems or finding near-optimal solutions to problems. Engineers are beginning to use genetic algorithms for such applications as designing integrated-circuit chips, scheduling work in a busy machine shop, operating gas-pipeline pumping stations and recognizing patterns.

"People are finding that genetic algorithms work well in lots of different problems," says engineer David E. Goldberg of the University of Alabama at Tuscaloosa. "It's the combination of reasonable efficiency over a broad spectrum of environments that makes genetic algorithms interesting."

The first step in using a genetic algorithm to find a good design for, say, an integrated-circuit chip is to express all the chip's major components as a string of digits, or "chromosome," in which small groups of digits (somewhat analogous to genes on a chromosome) correspond to different components. The list of all possible chromosomes -- different random arrangements of the components -- would correspond to all available design choices. In addition, the designer must specify a way of numerically evaluating the efficiency or quality of any given design.

Because trying every combination to find the best one would take too long, the genetic algorithm approach offers a way of narrowing and thereby speeding up the process of selecting a suitable design. The trick lies in starting with a small selection of chromosomes. In each succeeding generation, the method creates a new set of chromosomes using the best pieces of the previous generation -- a kind of survival of the fittest.

Such an approach turns out surprisingly efficient, partly because it builds on previous "answers," making it unnecessary to search the entire field of possible designs. Each trial after the first becomes less and less random. Once it eliminates bad parent strings, the method automatically eliminates their offspring, the offspring of their offspring, and so on. That allows a genetic algorithm to rapidly zero in on a good solution.

Initially criticized as little more than a random search with a fancy name, the genetic algorithm strategy is just starting to come into its own. Holland and his collaborators have developed a firm mathematical foundation for the method that clearly demonstrates its efficiency. "Genetic algorithms are not just random processes," he insists.

To keep the algorithm from getting stuck at a significantly less-than-optimal answer (perhaps because of an unfortunate choice of starting configurations), genetic algorithms also include a "mutation" operation. Used sparingly, this operation randomly changes a digit in the string of digits that make up a chromosome.

However, the mutation operation plays a minor role compared with the key part played by the process of splitting chromosomes and then piecing together various fragments. "It's recombination, not mutation, that's the driving

force," Holland says.

That insight has encouraged biologists to take a closer look at the comparative importance of mutation and genetic recombination in biological evolution. Evolution governed strictly by random mutation seems too slow a process to account for the present-day diversity of life forms. According to Holland's model, mutation's only real function may be to restart an evolutionary process that has momentarily stalled.

Although only a few hundred researchers worldwide presently work with genetic algorithms, they have already come up with a wide variety of applications. Earlier this year, a conference on genetic algorithms featured papers on topics ranging from scheduling the movements of robots in an automated manufacturing plant to developing a strategy for picking winning horses at the racetrack.

Simple genetic algorithms can handle such basic engineering tasks as designing a minimum-weight truss--a framework of struts meant to support a roof or some other structure. Although engineers have many methods for working out such problems, a genetic algorithm approach developed by Goldberg and graduate student Manohar P. Samtani proved astonishingly quick in narrowing the choices for constructing a suitable 10-section truss.

In their computer program, a string of 10 numbers (a chromosome) -- with each number describing the diameter of a particular strut--represents the 10-member truss. A computer initially generates from 50 to 100 chromosomes and then proceeds to weed out the weaklings while reproducing, splitting and recombining the superior combinations. It takes only about 40 generations to arrive at a near-optimal design.

Researchers at the Catholic University of Nijmegen in the Netherlands are studying the possibility of using genetic algorithms for analyzing chemical data. One potential application involves determining the three-dimensional structure of DNA molecules dissolved in water by interpreting nuclear magnetic resonance measurements.

At Vanderbilt University in Nashville, J. Michael Fitzpatrick and his colleagues have developed a genetic algorithm to help physicians looking for arterial damage to align images when matching two different X-ray photographs of the same artery, one taken before the injection of dye into the artery and the other taken after. Often, because the patient may move a little between photographs, the two images do not register perfectly. The genetic algorithm finds a set of equations that mathematically transforms one image so that it fits the other.

The speed with which a genetic algorithm can find solutions allows it to "learn"--to adapt to changes in the problem it's trying to solve in a way that conventional expert systems, which rely on a complicated web of rules to specify responses, can't match. In general, expert systems embody attempts to put knowledge in a form that allows machines to mimic human reasoning within a limited context. The trouble is that conventional expert systems are too rigid or "brittle," Holland says. "The minute you try to do anything outside [an expert system's] domain, you get non-sense as answers," says Holland. "That's very troubling. You can't have intelligence without learning."

By showing that a search can proceed efficiently without any prior knowledge about a problem, the genetic algorithm approach provides a possible answer to the question of how machines can learn--an alternative to neural-network models, which may mimic the way neurons in the brain develop connections as the brain accumulates knowledge. Whereas neural networks seem suitable for tasks such as pattern recognition and responding to immediate conditions, they often fail when they need to look ahead and anticipate some action -- the kinds of things a human being does to play chess or other games, for example. Various systems based on genetic algorithms have managed to learn simple tasks such as negotiating a maze and playing draw poker.

On a more practical level, one genetic-algorithm-based program developed by Goldberg copes with the ever-changing demands on a gas-pipeline pumping station. Faced with fluctuating input -- because of pump breakdowns, line leaks and daily and seasonal pressure changes -- the operator of the system must learn how to adjust the pumping equipment to maintain a steady output.

Goldberg's computer program for running a pumping station finds a combination of pumps and pressures that achieves the desired output. As the input changes, the algorithm automatically searches for a new combination that keeps the flow as steady as possible and minimizes the amount of natural gas used to run the pumps. The system essentially trains itself.

Some of the most promising systems are hybrids, combining genetic algorithms with conventional expert systems and traditional optimization methods in a computer-aided design procedure. David J. Powell of the General Electric Corporate Research and Development Center in Schenectady, N.Y., and his colleagues have developed just such a tool for engineers involved in designing mechanical components, from simple cooling fans to fuel-efficient aircraft turbine engines. Powell says the technique improves the quality of engineering designs and, by allowing the investigation of a greater number of potential designs in a shorter time, increases engineers' productivity by at least a factor of 10.

The hybrid method has already yielded a jet-engine design that GE intends to build and test. "The design system tried things an engineer would never have thought to try," Powell says.

Comments computer scientist Michael M. Skolnick of the Rensselaer Polytechnic Institute of Troy, N.Y., "The [hybrid] technique is interesting because it uses genetic algorithms for things that the genetic algorithm does well, which is mainly exploration." That adds the flexibility an expert system needs to cope with even slight changes in the problem at hand.

Holland himself is exploring a possible role for his ideas in economic models. Last year, working with economists at the Santa Fe (N.M.) Institute, he constructed a mathematical model to simulate a miniature stock market. A genetic algorithm allows the system to generate new rules for trading money for stocks. The idea is to show that a market starting with only a few simple rules can organize itself into a very complicated state. Such a model would demonstrate that stock-price fluctuations represent much more than responses to financial data such as interest rates.

Genetic algorithms, in all their variations, can produce good solutions to a wide variety of problems. But the field is still in its infancy. "In many ways, we're still early on in understanding genetic algorithms," Holland says.

That leaves many unresolved issues concerning how best to use the new approach. Practitioners get into long debates over technical details on exactly how to code specific problems into a suitable form, how to split and rejoin chromosomes, and when to stop the procedure, which theoretically can continue indefinitely. Moreover, simple genetic algorithms, which work with chromosomes of a fixed length, often seem too limited to solve many types of problems. At the same time, problems that need to be expressed in the form of lengthy chromosomes sometimes prove unwieldy.

In fact, large genetic algorithm systems behave more like ecologies, showing complicated, hard-to-predict interactions. "For instance, things like parasites emerge," Holland says. "We have an awful lot to learn about how systems behave when they're large and run over long periods of time."

There's also lots of room for new ideas, and nature points the way. "Perhaps one day our methods will contain artificial analogs of DNA, RNA, jumping genes, inverted segments, and a host of other genetic paraphernalia," Goldberg writes in his book Genetic Algorithms in Search, Optimization, and Machine Learning (1989, Addison-Wesley).

"Natural evolution has found all kinds of interesting organisms to fill many different niches," Goldberg says. "Genetic algorithms are broad in the same way. Although they may not be tailored for solving a particular problem in the best possible way, they work well for many different problems."