From Toys to Tools
Reproducing in microseconds on a computer a process that takes millions of years in nature is an idea that long predates the ability to realize it. John H. Holland, a 76-year-old computer science professor at the University of Michigan, says he first came up with the notion while browsing through the Michigan math library’s open stacks in the early 1950s.
“Every once in a while I’d pick up a book that looked interesting and just read it,” he says. That habit led him to The Genetical Theory of Natural Selection, a 1930 book by British mathematician-turned-biologist Ronald Fisher. Inspired by the pea plant experiments of 19th-century Austrian monk Gregor Mendel, Fisher worked out mathematical descriptions of natural selection at the level of individual genes. While researchers wouldn’t crack the biochemistry behind that process until the 1950s, Fisher’s work nevertheless jibed with what farmers and shepherds had known for centuries: sexual reproduction ensures variation and novelty.
“That’s really where the genetic algorithms came from,” says Holland. “I began to wonder if you could breed programs the way people would, say, breed good horses and breed good corn.”
Holland wrote his first paper on “adaptive algorithms” in 1962. But it wasn’t until the late 1970s that he and his graduate students had amassed the computational resources to put the idea into play. Holland credits one of his students, Edward Codd, with convincing his former employer, IBM, to sell the Michigan research group a low-cost mainframe. (Codd would go on to win the A. M. Turing Award, computer science’s equivalent of the Nobel Prize, for designing the first relational databases.) Even then, however, the computer’s paltry 32 kilobytes of memory limited the size and scope of the researchers’ initial experiments.
One of the first scientists to give evolutionary algorithms a serious test drive was Goldberg, who worked under Holland as a PhD student in the early 1980s. Goldberg resurrected a problem that he had faced during his days in the natural-gas industry: minimize the power consumption of a long-distance pipeline, given variations in regional demand. His evolutionary algorithms yielded solutions as efficient as those produced by the existing fluid mechanics software used by pipeline designers. But as Goldberg fed his algorithms bigger and more complicated problems, they began to stumble: they got stuck exploring evolutionary dead ends or spitting out hopelessly wild solutions. “I understood the problems I was solving better than the tools I was using to solve them, and that bothered me,” Goldberg says.
Goldberg focused his dissertation and then another half-decade of work on making genetic algorithms more predictable. He found that adjusting the parameters of each new algorithm – the starting population size or the rate of mutation, for example – smoothed out a few wrinkles. But for the most part, his research left him with a sobering realization: evolutionary algorithms were often more complex than the problems they tried to solve. Eventually, Goldberg learned to steer clear of what he calls “needle in the haystack” problems, which demand a single, best solution; these tended to cause evolutionary algorithms to spin out of control. Instead, he aimed at friendlier problems that had a range of viable solutions, depending on how you approached them. “If there are dozens of needles scattered around in such a way that the [evolutionary algorithm] can break the haystack down into smaller haystacks, you at least guarantee yourself a shot at a better outcome,” Goldberg says.
Goldberg documented his work in a 1989 textbook, a volume that would inspire other computer-savvy engineers to begin their own tinkering. By the mid-1990s, engineers at General Electric Research Center in Niskayuna, NY, had built evolutionary methods into an in-house design tool called EnGENEous, which was used to find the most efficient shape for the fan blades in the GE90 jet engines used on Boeing’s 777 aircraft. EnGENEous allowed the GE90 team to eliminate one stage of the engine’s compressor, which meant a reduction in engine weight and manufacturing costs without any sacrifice in aerodynamic performance. “After this initial success, the floodgates opened to use these types of tools in many different applications across all of GE’s businesses,” says Pete Finnigan, laboratory manager for advanced mechanical-design applications at the research center. Engineers at Rolls Royce, Honda, and Pratt and Whitney have followed suit, incorporating genetic algorithms into their own design processes.