Technology: Special lines of computer code mate and mutate like living organisms. Called 'genetic algorithms,' they solve problems no human can. The John Deere Factory in Moline to inspire visions of that old "I Love Lucy" episode-the one in which the only way Lucy, working at a candy plant, could keep up with the assembly line was to stuff the sweets into her mouth. You can't exactly do that with the 90 models of tractor-size seed planters that Deere makes. But the general idea was tempting: production at Moline often hit logjams as a longer-to-assemble model made newly arriving customer orders bunch up. Finding a smoother production schedule was daunting: there are about 1.5 million possible ways Deere could schedule production of the 90 models. Finally, last year, Deere hired Optima Systems Corp. of Cambridge, Mass., to develop software that discovered the best schedule in the same way that nature finds, say, the best bird wing: through natural selection. Just as the criteria for wings include "light enough to flap," so the criteria for the assembly line included "make units for the same shipment within a certain time of each other." Quickly, the computer found a "genetically fit" schedule. "It used to take us a day to generate a [week's] schedule," says Deere's Joe Mausser. "But now it's literally a zap of the screen."
The technique is called a genetic algorithm. It's a new method of "machine learning," in which software bootstraps itself from dumb and dumber to smarter and smarter. The algorithms themselves are lines of code that act like living organisms. Like all organisms, they are subject to Darwin's rules of evolution. Through chance matings and a process called "crossover," different sections of code come together, producing novel combinations. Through mutations, in which some bits are randomly altered, the algorithm is continually modified. The chunks of code compete, and even go extinct: in the survival of the cyberfit, only code approaching the desired solution remains. For instance, one genetic algorithm worked out positions for cellular-telephone towers that provide the maximum coverage with no overlap. The algorithm kept mating and mutating the positions of the towers until it arrived at the ideal placement, explains Lawrence Davis, founder of Tica Associates in Cambridge, Mass.
Genetic algorithms were invented in the 1960s at the University of Michigan by John Holland, who won a MacArthur Foundation "genius grant" for the work. For a long time they "remained cloistered in universities and research institutes," says computer scientist David Goldberg of the University of Illinois. But now they're "graduating from college . . . into industrial-strength applications." Already, the field's Internet USENET newsgroup (comp.ai.genetic) is chockablock with ways to use the mating, mutating programs, from creating "genetic music" to scheduling production at a sugar-beet factory. A software package called Evolver, from Axcelis Inc. in Seattle, applies genetic algorithms to a spreadsheet. "We've gone from maybe a dozen applications five years ago to hundreds today." says Tica's Davis. Some recent successes:
Texas Instruments wanted to design a computer chip on the smallest piece of silicon possible. A genetic algorithm came up with a circuit design that took up 18 percent less space, using a strategy of cross connections that no human had thought of. "A genetic algorithm will usually come up with something very different from what a human would," says Illinois's Goldberg. "Then you have this 'aha' moment."
One genetic algorithm discovered a design for a gas turbine that went on to become the engine for the Boeing 777, made by General Electric. It is almost I percent more efficient in its use of fuel than previous engines. In a mature field like gas turbines, 1 percent is a windfall.
US West had to lay a huge network of fiber-optic cable, something usually done by a designer relying on intuition and experience. But the company instead unleashed a genetic algorithm. After mating and mutating, code that produced networks with less cable survived; code that produced networks with more died. Design time for new networks has fallen from two months to two days and saves US West $1 million to $10 million each.
First Quadrant, an investment firm in Pasadena, Calif. that manages a $10 billion portfolio of pension funds, uses genetic algorithms not merely to save money but to make it. A lot of it--more than $30 million since 1993, mostly by taking advantage of differences in a stock, bond or curreney's price in various markets. The company uses genetic algorithms that encode general models for investing, by taking into account such variables as inflation and unemployment. Thousands of different models compete; each one has a different set of rules (one model might say buy stocks when price/earnings ratios are below 15, another might say to buy when the P/E is dropping). By testing the models against historical market data, First Quadrant learned which ones were the most "genetically fit," explains First Quadrant president Robert Arnott. Models that make money live; those that buyhigh and sell low go extinct. The models built by genetic algorithms made $255 for every $100 invested over six years, compared with $205 for a model that didn't undergo the rigorous testing of natural selection.
Success stories shouldn't obscure the difficulty of creating a genetic algorithm. Inventing one that is effective against many diverse problems, rather than tailor-making them to a single one, "is a design challenge as stiff as the most difficult this century," warns Goldberg. Most fundamentally,computer scientists don't fully "understand what problems genetic algorithms work on and what ones they don't," says mathematician Raymond Greenwell of Hofstra University in New York. Greenwell is trying to discover the ideal mutation rate for the algorithms, a fundamental unknown. Still, genetic algorithms have going for them something that no other computer technique does: they have been field-tested, by nature, for 3.5 billion years.