Machines that Think

Which of the following can computers now do better than humans? Write advanced software Design other machines Predict who will pay their bills Evolve and adapt All of the above and more

By Brad Lemley|Monday, January 01, 2001
RELATED TAGS: COMPUTERS


From cave paintings to canticles to Corvettes, brilliant, creative designs have always been the products of brilliant, creative people— until now. Consider these examples of nonhuman design:
  • At Brandeis University in Waltham, Massachusetts, a pyramid-shaped plastic robot hops across the carpet, propelled by a single thrusting leg. Its companions, shaped like inchworms, arrows, and spirochetes, wriggle and undulate alongside. These robots look like the creations of wildly inventive engineers, but human beings did not design them. And while the synthetic creatures sport a myriad of configurations, they share a strength— they cover ground quite efficiently.
  • At tony art galleries in Hong Kong and London, patrons gladly pay up to $4,500 for photographs of images that evoke seashells, ferns, bacteria, and other organic shapes. No human invented these forms. The glossy prints aren't beautiful in the traditional sense— some disturbing ones evoke extraterrestrial parasites— but they are assuredly art.
  • Each week throughout Scotland, burly workers muscle 20,000 barrels of whisky out of 49 warehouses into bottling factories according to a complex plan that factors in age, malt numbers, and wood types.


Doing this efficiently is so mind-numbingly complex, the problem makes chess look like rock-scissors-paper. But the plan these workers are following is brilliant and original beyond the artifice of any flesh-and-bone inventory manager and, compared to the one human beings used to cobble together, has nearly doubled cask-handling efficiency.

Each of these triumphs was cooked up by a computer. Human beings wrote the programs but then, essentially, just pushed a button and waited for silicon and software to dream up the creative, surprising result.

That's revolutionary. For most of their existence, computers have been little more than complex adding machines, tabulating data and spitting out useful but prosaic results. Now, employing a new kind of programming based on biological evolution, computers are invading what we thought was among the last uniquely human spheres— true, original, even artful creativity. "We're not used to computers creatively solving problems," says David Goldberg, chairman of the International Society for Genetic and Evolutionary Computation. "But it's happening."

The engine behind the revolution is called evolutionary computation. Its basic premise is that the most capable and efficient things on the planet came into being through evolution— not as the brainchild of an individual designer. After all, the human hand makes the most dexterous robotic claw look like nothing more than a pair of rusty pliers. A cat is far nimbler than any off-road vehicle could possibly be. Trees can self-assemble, self-repair, run for centuries on water and sunlight, and make little copies of themselves, tricks outside the ken of any human-crafted machine.

So while many of us marvel at human ingenuity, a few researchers have ventured to ask: Why, compared to living creatures, are robots and other man-made things so stupid, clumsy, and otherwise second-rate? The emerging answer: We designed them. To get true, original excellence, the argument goes, we need to harness the creative power of natural selection, the same process that spawned the best things on Earth— humans, animals, and plants. While no programmer can stuff a computer with all the variables that go into real-world evolution, skilled ones can define a specific problem and prod the computer to evolve the solution. And computers have a unique advantage: While biological evolution takes eons, computerized evolution takes hours.

It was in the 1960s that computer science professor John Holland, working with his students at the University of Michigan, created the first genetic algorithms, which lie at the heart of many types of evolutionary computation. An algorithm is a set of steps for solving a particular problem: The recipe for baking a cake is a simple example. Holland and his group made algorithms that mimicked the behavior of genes and chromosomes. They allowed sets of variables to "mate," "give birth," and improve from generation to generation.

Over the last decade— and with increasing frequency over the last two years— evolutionary computation has evolved from an academic exercise to a real-world tool that solves problems in fields ranging from robotics to software design to finance to aerospace, and the benefits are both impressive and concrete. The technology has been used to design new antibacterial cleaners for Unilever, help the Marshall & Ilsley Corporation target American banking customers, advise Ford regarding the best potential dealership locations in the United Kingdom, boost efficiency in oil extraction for British Petroleum, diagnose breast cancer among Wisconsin women, even play jazz: Trumpeter Al Biles, who is also an undergraduate program coordinator at the Rochester Institute of Technology in Rochester, New York, records and performs with the Al Biles Virtual Quintet. He is the only human member of the ensemble. The rest, who improvise on a variety of instruments, are virtual musicians produced by a genetic algorithm that resides in his Macintosh Powerbook.

"Industry has gotten the message: Either use these tools or your technology will be left behind," says David Goldberg.

Yet despite its broad use and applications, evolutionary computation is unfolding largely under the public's radar. Removing human beings from the creative loop could be promising or disturbing, depending on your point of view, but researchers agree on one point: Evolutionary computation is the future, and people should know more about its awesome potential. "What the human race is always trying to do, in any field, is develop the best possible solution," says Akeel Al-Attar, managing director of Attar Software in Lancashire, England, a leading software firm in the field. "Evolutionary computation can help you do that."

Take, for instance, United Distillers and Vintners in Scotland, the world's largest and most profitable spirits company, accounting for more than a third of global grain whisky production. The company's inventory and supply department must manage the flow of 7 million casks that contain 60 different whisky recipes and are distributed throughout an enormous system of warehouses and distilleries— and must do so weekly in rapid response to ever-changing market demands.

Five full-time employees used to craft this vast deployment of casks, and because the variables were numerous beyond counting, their method was as much art as science. In fact, the task required creativity, traditionally defined as "to produce through imaginative skill." That's why, explains Al-Attar, "traditional computing systems could not offer solutions. The problem was too complex for even the most powerful system."

Today one person, employing software from Al-Attar and a few keystrokes, prods the computer to make a plan every week that factors in current inventory and market conditions. Warehouse efficiency nearly doubled. It works like this: Genetic algorithms start with a basic "population" of possible solutions to a problem, roughly analogous to unevolved bugs at the very bottom of the evolutionary ladder. In the whisky warehouse problem, for example, the process of moving groups of casks A, B, and C from warehouses D, E, and F— but only if the needed casks are not stored behind more than x other casks— would represent one "individual" in the population. A different cask-movement plan would represent another individual.

Why start with a limited set of solutions? Why not have the computer whip up every possible cask-movement scheme on its own, then pick the winner? Because the scenario is so complicated, brute-force computation just won't work. "In problems like these, you very quickly get to a point where you literally need years, even centuries of computer time," says Konrad Feldman of Searchspace Corp., a New York City software firm. Genetic algorithms, he says, "are a wonderful mechanism for narrowing the search space."

After defining the population, the algorithm pits the individuals against the demands of the problem— in this case, how to move around casks so that each one arrives when and where it should, while minimizing the taxing chore of manhandling unneeded barrels out of the way. So a genetic algorithm "mates" the first population of individual-solutions, combining them in artfully randomized ways to "breed" slightly varying offspring-solutions. A so-called fitness function then evaluates the progeny by "looking" for a combination that is nearly optimal in cost, simplicity, speed, or any other collection of qualities the programmer desires. The fitness function then kills off the parents (silicon evolution turns out to be as merciless as its biological counterpart) and picks the best solutions from the offspring's ranks. Those solutions mate, the fitness function sizes up their children, weeds the losers and mates the winners, they have children, and so on.

The task ends when the offspring all start to look alike. That means the best solution this particular starting population and fitness function can whelp is either here, or near enough. In the cask problem, this happens after about 200 generations of digital breeding. "There are situations where running the program for many more hours will yield a .5 percent increase in efficiency. At that point, it's not worth it. The curve has flattened, and it's time to call it a day," says Al-Attar.

The robotic life-forms designed by Jordan Pollack, a computer scientist, and Hod Lipson, a mechanical engineer, both of Brandeis University, are perhaps the most vivid example of evolutionary computation's potential to innovate without interference from humans. Their computer program evolved an initial population of simple creatures made from plastic bars. Some bars were rigid, like bones; others could expand and contract, like muscle fibers. The fitness function selected for designs that could move swiftly across a horizontal surface. Evolved inside the computer over several hundred generations, then built by a rapid-prototyping machine, the resulting cyber species, consisting of extraordinarily diverse shapes, scooted along with impressive efficiency. In a similar experiment, Laurent Keller of the University of Lausanne in Switzerland programmed antlike robots to collect plastic cylinders simulating food and then to communicate with one another about a virtual food source. These "antbots" were more successful than another group of loners who banged around on their own through solo trial and error. Keller's antbots, in other words, evolved successfully to mimic the behavior of real ants.

While programmers can design evolutionary computation software to run independently, systems can also be set up to include human beings as collaborators. Indeed, some expect that this will profoundly change the nature of creativity itself. Soon, creative tasks may consist primarily of picking from a menu of choices offered by a computer. British artist William Latham is one of many pioneers of evolutionary computation exploring this concept. Using a computer program called Mutator that he helped design, he selects a basic shape, which then spawns nine variants. He picks the one he likes best, that one births nine more, and so on, until he declares an overall winner and halts the evolution. When he began experimenting in 1987, Latham was fascinated— and shocked— to discover that the forms that grew on his screens almost invariably looked like products of nature. "People would think they were seeing real shells, but a type of shell they had never seen on Earth. That something completely synthetic could look so natural came as a complete surprise.

"The central idea," continues Latham, whose works sell in art galleries around the world, "is that the artist comes to resemble a gardener. Rather than cultivating these forms from scratch, you decide which ones live, which ones you weed out, and which of them you breed together. You don't really need to be an artist in the traditional sense. You just need to be able to make selections." He believes the approach will soon pervade all fields in which aesthetics matter. "Eventually, you may not need an architect to do architecture. The computer will present you with a choice of building designs. You'll keep selecting the variant you like until you're satisfied." David Goldberg, who is also the director of the Illinois Genetic Algorithms Laboratory, believes this sort of interactive evolutionary computation is one of its most promising avenues. "We are headed into an era in which genetic algorithms can work as a sophisticated aid to people," he says.

Melanie Mitchell, a leading researcher at the Santa Fe Institute and author of An Introduction to Genetic Algorithms, believes evolutionary computation may prove particularly useful in the Internet age. "Increasingly, instead of sorting through thousands of documents yourself, you'll have software agents that have learned your preferences, go out on the Internet, bid in auctions on your behalf— do things for you." While such agents already exist in rudimentary form— so-called shoppingbots are an example— one that evolved via evolutionary computation would be uncannily like its master, doing exactly what he would do were he logged on. And instead of a simple text search, Mitchell has worked on a genetic algorithm that could learn to find images on the Web. "You would show it several photos of a person's face, and say, 'Here is one example. Here is another example. Now, find the same thing.' " A human operator would weed out mistakes and feed back "hits" into the evolutionary loop until the search program got the knack of what the user was looking for. For a computer to grasp that "the same thing" could include a photo taken from a different angle— so that it shared no data points with any photo the computer had already seen— would indeed represent a major leap in digital discrimination.

Of course, like real-world evolution, the computer variety is only as good as the initial population and the fitness function. Evolutionary computation results are seldom perfect, but they're certainly good enough to tackle the task. "I don't see it as a panacea. I see it as a technology," says Mitchell. Researchers generally agree that this tool works best for extremely complex problems that need some method to truncate the universe of possible solutions. "Other kinds of algorithms will continue to be best for other kinds of problems," says Mitchell.

Nonetheless, she is convinced that evolutionary computation is "closing the gap between living systems and machines. If computer systems can evolve and adapt, it does become harder and harder to say there is some fundamental difference between biological life and machines. This technology is moving from science fiction to reality."

"We need to start engaging in a dialogue about the dangers of these tools over time," warns Bill Joy, chief scientist of Sun Microsystems. In just 30 years, he argues, our machines may surpass us in intelligence, then realize they no longer need us.

Mitchell shares that very same concern. "It won't happen in the near future, but for computers to eventually become lifelike and intelligent, they will need to have bodies that are similar to ours, and they will have to want some of the things that we want." Given that such cyber beings will grow exponentially smarter and stronger with each and every passing hour, they could quickly become as intellectually superior to human beings as we are to bacteria.Perhaps we could instill in such supremely intelligent machines an enduringly protective attitude toward their primitive progenitors. Then again, perhaps not.

Goldberg offers a more upbeat vision. "In biology, there's something called the niche exclusion principle," he says. "In a given niche of resources, there will be one winner. Carbon-based organisms and silicon-based organisms live in different niches, using different resources. There's not much one has that the other wants. I think we'll be symbiotic. We'll supply the silicon; they'll supply the things we need. We'll become increasingly free, able to think and do greater and greater things."

But creativity, of course, begets unpredictability. No one knows where evolutionary computation will lead— which, given the risks attendant, may be reason enough to at least start tapping the brakes. Yet the promise is so provocative, it's likely the field itself will evolve whether we like it or not. As it does, human beings will just have to adapt.

Which leads Goldberg to the inevitable conclusion, "There is no corking this genie back in the bottle."


The Origin of a Species


At Brandeis University, a computer created blueprints (a) and then constructed robots (b) with the aid of a rapid prototyping machine. The designs evolved over hundreds of generations with almost no intervention by project directors Hod Lipson and Jordan Pollack. The project's success, says Lipson, brings us closer to the reality of "self-replicating artificial life systems." Pollack insists we have nothing to fear from unleashing creative computers. "Programs that create won't stop us from creating," he says.


The Computer as Artist


William Latham relies on his Mutator program to create the pricey art he sells in London galleries. Latham views the more disturbing images as "a comment on the dangers of genetic engineering. Since I helped develop the program, I tend to think I have control." Yet as Mutator spawns new images, Latham finds that pleasing forms can "instantly, dramatically go awry."






Evolution of a Cyber Ant Colony


A group of "antbots" (below) at the Swiss Federal Institute of Technology was programmed to search for virtual food (red plastic cylinders, below) whenever the colony's energy level fell too low. The antbots that worked collectively gathered more food than loners— mimicking the cooperative success of biological insects such as waggle-dancing bees and scent-trailing ants.










For further information on the work of researchers Hod Lipson and Jordan Pollack at Brandeis University, see the Golem Project Web site at www.demo.cs.brandeis.edu/golem.

"EvoNet, the Network of Excellence in Evolutionary Computing," at http://evonet.dcs.napier.ac.uk/evoweb/, tracks EC progress worldwide, with an emphasis on European efforts.

David E. Goldberg, director of the Illinois Genetic Algorithms Laboratory and chairman of the International Society for Genetic and Evolutionary Computation, has put his introductory course in genetic algorithms online at online.cen.uiuc.edu/webcourses/ge485/video/teaser/event.htm.

The International Society for Genetic and Evolutionary Computation maintains a Web site that contains archives from the two leading journals in the field, Evolutionary Computation Journal and Genetic Programming and Evolvable Machines Journal: www.isgec.org.

The Leiden Institute of Advanced Computer Science in the Netherlands has put up one of the most comprehensive evolutionary computing sites on the Web: www.wi.leidenuniv.nl/~gusz/Flying_Circus/.

For an amusing and thoroughly readable introduction to evolutionary computing, check out "The Hitch-Hiker's Guide to Evolutionary Computing" at ftp://ftp.cerias.purdue.edu/pub/doc/EC/Welcome.html.

If you really can't get enough of evolutionary computing, see the Navy Center for Applied Research in Artifical Intelligence's Genetic Algorithm Archive: www.aic.nrl.navy.mil/galist, which includes plenty of links.


Comment on this article
ADVERTISEMENT

Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

ADVERTISEMENT
ADVERTISEMENT
Collapse bottom bar
DSCNovCover
+

Log in to your account

X
Email address:
Password:
Remember me
Forgot your password?
No problem. Click here to have it emailed to you.

Not registered yet?

Register now for FREE. It takes only a few seconds to complete. Register now »