PROGRAMMING WITH
PRIMORDIAL OOZE
Useful software beginsto 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 says.
"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
No comments:
Post a Comment