Spring 2008.
Table of Contents.
Modern Prometheus.
Still Standing.
Charting a Path to the Planets.
Instructional Incentive.
Bright Innovations.
Bad to the Bone.
New & Now.
Profile.
Publisher's Column.
Topics.
Past Issues.
Contact Us.

MU Homepage.

 

Illumination magazine.
  Page 1. Page 2. Page 3. Page 4.
 Text size small. Text size medium. Text size large.  Email this article.  Print this article.

Image courtesy of Courtesy NASA/JPL-Caltech/T. Pyle

What computer scholars refer to as "differential evolution" is a relatively simple computing methodology -- at least for engineers -- that uses concepts of reproduction, random mutation and natural selection to solve problems. Think of it as a form of digital Darwinism, one that MU mechanical and aerospace engineering professor Craig Kluever and his former MU graduate students Aaron Olds and Michael Cupples are using to teach an old theory new tricks.

"With any space mission, you want to put as many instruments or as many people as possible on board. That can take a lot of fuel," says Kluever, who holds a James C. Dowell professorship. "Our differential evolution algorithm can find the route that takes the least time or the least fuel, or that maximizes the amount of payload a spacecraft can carry."

In evolutionary computation, the scientists say, Darwin's theory has found one of its least controversial, most successful applications.

The process bears a remarkable resemblance to DNA transcription and replication, where, instead of 1s and 0s that make up the binary language of computer programming, nature uses four chemical bases represented by the first letters of adenine, cytosine, guanine and thymine.

Just as biological evolution forces new combinations of A, G, C and T to compete with old combinations until a fitter organism emerges, digital evolution puts new combinations of 1s and 0s in competition until an optimal solution emerges. In short, solving by evolving.

The idea of solution evolution began germinating in the 1950s. Faced with complex problems in space flight, bridge engineering, skyscraper construction and other minutely detailed, step-by-step processes, scientists began using computers to randomly test potential solutions, letting the machines weed out those that failed to make the grade. Over time, researchers noted the process was beginning to look like something out of Darwin's Origin of Species.

In the 1960s, American computer scientists Lawrence J. Fogel and John Henry Holland formalized the science of evolutionary computing with their work on what they described as "genetic algorithms." Mapping the most fuel-efficient route from Columbia to Los Angeles provides a simple example of Fogel and Holland's method.

To start, one would develop an algorithm with a "population" of various routes along different highways. The algorithm would next cycle through dozens of "fitness functions," checking each for "efficiency parameters." One fitness function would test for the number of mountains along a particular route; another might check for routes with the fewest stops; a third could seek routes with the optimal average speed limit. The algorithm then uses evolutionary programming to select, mutate and recombine these fitness function findings in ways that, eventually, produce the most efficient route.

As in natural selection, mutation plays a key role in this digital Galapagos. To visualize a digital mutation, imagine strings of 1s and 0s merging to form new strings, each representing a new solution. The string 011110111101111 might represent a road trip from Columbia to Los Angeles that uses 75 gallons of unleaded gasoline. But, like nature, computers can make mistakes. A digital mutation -- an accidental combination that produces a slight variation of that string, say, 011110111101100 -- might represent a 74-gallon road trip. After a round of fitness checks, the computer's evolutionary algorithm would save the mutation, adding it to the digital mix until the fittest solution emerges.

Page 1. Page 2. Page 3. Page 4. Forward one page.

Published by the Office of Research.

©2009 Curators of the University of Missouri. Click here to contact the editor.

 

Illumination home. Fall 2007 Table of Contents.