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.
|