PROGRAMMING WITH Useful software begins
crawl out of digital gene pools
Computer programmers ascended the economic food chain by inventing
clever algorithms to make manufacturing and service laborers redundant.
But some programmers may one day find themselves automated out of a job.
In university labs, scientists are teaching computers how to write their
own programs. Borrowing from the principles of natural selection, the
researchers have built artificial ecosystems that, for a few problems at
least, can evolve solutions better than any yet devised by humans. Someday
such systems may even be able to design new kinds of computers.
The idea of evolving rather than inducing algorithms is not new. John
H. Holland of the University of Michigan worked out the method 21 years
ago. But Holland's strategy, based on a rigorous analogy to chromosomes,
is limited to problems whose solutions can be expressed as mathematical
formulas. It works well only if a human programmer figures out how many
numbers the computer should plug into the formula.
In 1992 John R.
Koza, a computer scientist at Stanford University, extended Holland's
method to evolve entire programs of virtually any size and form. A field
was born, and this past July several hundred disciples gathered at the
first Genetic Programming Conference to show off their latest creations.
Jaime J. Fernandez of Rice University, for example, reported evolving a
program to help control a prosthetic hand. The software analyzes the
erratic nerve signals picked up by three electrodes taped around a
subject's wrist and can tell, with perfect accuracy, which way he moved
his thumb. Fernandez's team is now collecting data from amputees missing a
hand to see whether the technique can be applied to them.
Brian Howley of Lockheed Martin Missiles and Space guided the evolution
of a program that can figure out how to maneuver a spacecraft from one
orientation to another within 2 percent of the theoretical minimum
time--10 percent faster than a solution hand-crafted by an expert. And
researchers at University College in Cork, Ireland, grew a system that can
convert regular programs, which execute instructions one at a time, into
parallel programs that carry out some instructions simultaneously.
To create their software, Fernandez and Howley did not have to divine
insights into neurophysiology or rocket science. The task of the genetic
programmer is simpler. First, build an environment that rewards programs
that are faster, more accurate or better by some other measure. Second,
create a population of seed programs by randomly combining elements from a
"gene pool" of appropriate functions and program statements. Then sit back
and let evolution take its course. Artificial selection works just like
the natural variety: each program is fed data and then run until it halts
or produces a result. The worst performers in each generation are deleted,
whereas the best reproduce and breed--that is, swap chunks of code with
other attractive programs. Occasionally, a random mutation changes a
variable here or adds a command there.
The technique can generate solutions even when the programmers know
little about the problem. But there is a price: the evolved code can be as
messy and inscrutable as a squashed bug. Fernandez's gesture-predicting
program consists of a single line so long that it fills an entire page and
contains hundreds of nested parenthetical expressions. It reveals nothing
about why the thumb moves a certain way--only that it does.
Just as in the real world, evolution is not necessarily the fastest
process either. Howley's speedy workstation churned for 83 hours to
produce a satellite-control program that beat human ingenuity in eight
test cases. And when it was presented with situations it had never
encountered, the program failed, a common problem with evolved software.
(Of course, the human expert's program failed on the new cases as well.)
To address some of these limitations, computer scientists are extending
their technique. Lee
Spector of Hampshire College in Amherst, Mass., allows the programs in
his ecosystems to share a common memory as they compete to demonstrate
their fitness. "This means that a 'good idea' developed by any individual
may be preserved for use by all others," Spector says--essentially, it
allows the community of programs to evolve a culture. He reports that the
innovation reduced the computational effort required to solve a tricky
mathematical problem by 39 percent.
"It is possible," Spector says, "to use genetic programming to produce
programs that themselves develop in significant, structural ways over the
course of their 'life spans'"--a strategy he calls ontogenetic
programming. He demonstrated one such system that can predict the next
value in a sequence of numbers so complicated that it has stumped regular
genetic programming systems.
Ultimately, evolved software may lead to evolved hardware, thanks to
the recent invention of circuit boards that can reconstruct their circuit
designs under software control. Adrian Thompson of the University of
Sussex turned a genetic programming system loose on one such board to see
whether it could produce a circuit to decode a binary signal sent over an
analog telephone line. Using just 100 switches on the board, the system
came up with a near-perfect solution after 3,500 generations. Although the
task is simple, "it would be difficult for a designer to solve this
problem in such a small area and with no external components," Thompson
"Hardware evolution demands a radical rethink of what electronic
circuits can be," he argues, because evolution exploits the idiosyncratic
behavior that electrical engineers try to avoid. Although genetic programs
are largely still fermenting in their primordial ooze, it seems just a
matter of time until they crawl out to find their niche.
--W. Wayt Gibbs in San Francisco