Search Ames

Go

Exploring the Universe

Text Size

Evolvable Systems
 
Exploring the Universe

Computer scientists at NASA are building software programs that design hardware the way 19th century naturalist Charles Darwin might have suggested, by natural selection.

Darwin's theory says that evolution produces better species from organisms best adapted to their environment. The Evolvable Systems Group at NASA Ames Research Center's Computational Sciences Division builds software that mimics Darwin's theory to make new inventions. It's survival of the fittest hardware.

"We're taking our cue and inspiration from nature," said Jason Lohn, who leads the group that captures evolution inside a computer.

With his fingertips Lohn holds what looks like a ball of unwound paper clips. The half dollar-sized piece of metal is a high-tech communications antenna capable of sending and receiving signals while orbiting Earth.

"It's actually a functioning antenna," he said, pointing to its four symmetrical prongs. "This was designed by a computer -- that's the cool thing about it, and it actually works. No human would build an antenna as crazy as this."

Evolutionary algorithms were invented about 40 years ago but just became practical in the 1990s when computers became fast enough to use them. The programs typically run on a supercomputer. This project runs on 35 PCs networked together using Linux. These days, artificial evolution is gaining popularity as an application for building many types of hardware, from engines to circuits as well as antennas.

"It's an area that NASA is very interested in, and it's a growing field," Lohn said. "We wanted to see if computers can do things without telling them how to design them. You tell a computer to do x, y, z -- out spits the design you want."

Evolutionary algorithms start with a set of human-made specifications from which the program will generate populations of hundreds of designs, each encoded in an artificial chromosome. For an antenna, genes might specify its branching structure and the lengths and widths of each wire.

The program's first populations will likely be quite rough, varying among themselves in their makeup, but will produce superior designs by repeatedly taking the best antennas and using them as "parents" to make new ones, said researcher Greg Hornby.

"Just like in the real world you'd breed horses or dogs or plants, the computer program breeds the antennas. After a while the population converges and doesn't get any better. In the natural world, crocodiles and dragonflies are the same they were a hundred million years ago."

Add to Darwin's evolution Mendel's genetics, which says individuals inherit characteristics through the combination of genes from parent cells. Genetic mutation and crossover create new designs called 'children.'

In a broad sense, genetic mutation makes a random change to a chromosome. In the computational world of artificial evolution a program performs genetic mutations by making small changes to the values of the genes in the artificial chromosome. With crossover, the program combines parts from two good designs to make children.

Said Lohn, "The idea is that you want to be able to come up with chromosomes that have a higher performance than their parents so that the kids are better designs than the parent designs."

In a few months the programs will have created hundreds of thousands or even millions of individuals with a few considered best, or genetically fittest.

The Evolvable Systems Group started studying evolvable algorithms in 2001, building what's called a Yagi-Uda, the antennas that commonly topped houses before cable television. Next they did a proof of concept study on optimizing an antenna used by NASA's Mars Odyssey orbiter, launched in 2001 and still returning images of Mars.

The group's most recent design is the antenna Lohn holds, which is undergoing tests that will tell if it's fit to be launched with a set of three miniature satellites scheduled for orbit in the Earth's magnetosphere in 2004. This New Millennium mission, Space Technology 5, will test multiple technologies and mission concepts for future use. Each technology represents a breakthrough in performance, capability or application in a new and unique manner.

If launched the evolved antenna will be the first piece of evolved equipment in space.

New Mexico State University researcher Bruce Blevins said an experienced antenna designer would need 12 years working full time to process 100,000 design evolutions. Blevins works for the university's Physical Science Laboratory, which built the actual mission antenna for ST5. "And there is no guarantee that the person would come up with a design that is as good," he added. "I'm very interested in learning the techniques."

Starting an evolutionary algorithm is like an art form. The computer programmer must set up many parameters and build models that will slow or quicken an evolving system depending on the amount of detail the programmer wants the system to examine.

Conducting objects that are nearby affect an antenna's performance. "If you've ever played with a TV antenna, you realize that every material within the vicinity of the antenna effects its performance," said Hornby. The Ames group mathematically models the environment in which the antenna will operate, a necessary feature for the evolutionary algorithms to work. The software designs the antenna as if it is bolted onto the spacecraft, "and that's not something that's easy for antenna designers to do," Lohn said.

In addition to automated antenna design, the Evolvable Systems Group builds algorithms that design chips that fix themselves, circuits, coevolutionary algorithms and schedules for satellite fleets. But antennas are a big focus because of their importance in NASA missions and because antennas are difficult to design. In the future, evolutionary designs may become a common tool for designers.


Related Links