The ideas machineHuman inventiveness has reached the end of the road. Something far smarter is about to take over, says Robert MatthewsSTANDING outside the law courts in London, James Dyson triumphantly brandished a DC01 vacuum cleaner. This was the product whose revolutionary bag-free design had brought Dyson from the edge of bankruptcy to dominance of the European market. It had taken him 14 years and 5000 prototypes to perfect, so when deadly rival Hoover brought out a strikingly similar bagless cleaner in 1999, Dyson was surprised, then suspicious-and finally incensed.
In a legal battle that lasted over a year and finally ended last October, Dyson claimed that in bringing out a rival bagless cleaner Hoover had infringed patents on features that Dyson had perfected through years of trial and error. The court agreed, forcing Hoover to withdraw its machine from sale and pay Dyson substantial damages. It is a case widely hailed as a victory for the lone genius against the faceless forces of big business.
Don't expect many more of them, though. For the dog-eat-dog world of modern business is about to see the advent of a terrifying new predator, a positive tyrannosaur of a technology that threatens the survival of all but the fittest commercial behemoths. It is the spawn of an unearthly mating of Darwin's theory of evolution with ultra-fast computers.
Called genetic programming (GP), it involves creating thousands of virtual products inside a computer, and letting them fight for survival, with the fittest being allowed to breed. It sounds like
Toy Story on acid, but a squad of computer scientists led by John Koza of Stanford University in California has brought it to life. Using GP it took them a matter of hours to breed products that human experts would need years to develop-and which dodge round all existing patents.
The idea was mooted more than half a century ago by Alan Turing. In 1948, he suggested it might one day be possible to breed intelligent machines through the Darwinian approach of survival of the fittest. Two years later, he explored the idea further, showing how mutations in the design of the machines could lead to ever better ones, with a human watching over the evolutionary process like some omnipotent deity.
With computers in 1950 barely able to add, let alone simulate Darwinian evolution, there was no immediate chance of Turing's vision becoming reality. But by the mid-1970s, computerised Darwinian evolution was back on the agenda. It was put there by John Holland, a computer scientist at the University of Michigan. For years, he had been thinking about using computers to breed solutions to problems. His idea was to start with a random set of guesses to the answer, test each of them out, and kill off all but the best guesses in a bout of Darwinian competition. These would then be combined and mutated and allowed to breed a new-and hopefully somewhat better-set. Repeat that evolutionary process over and over again, thought Holland, and perhaps the truly "fittest" solution would emerge.
One of the questions that can be tackled this way is the "travelling salesman problem". Suppose you're a salesman planning to make calls on cities dotted around the country. You want to find the shortest route. If the cities are identified as letters of the alphabet, then one route would be (A, W, D, B, E...), while another would be (A, M, U, B, K...). The problem is that there are so many possible routes to test. With
N cities, the number of possible routes is
N-factorial-that is,
N multiplied by all the whole numbers below it. So, for example, if there are 20 cities, there are 20-factorial or about 2.4 billion billion possible routes.
Trying to find the single shortest route by checking each possibility in turn will soon bring even the fastest supercomputer to its knees-and the more cities there are, the worse it becomes. A machine powerful enough to solve a 10-city problem in 1 second would take around 21,000 years to find the answer for the 20-city case.
So Holland took a different approach. He started with just a handful-a few thousand, say-of these zillions of possible route sequences. The computer measured each one, and "bred" just the shortest ones, by combining different elements from pairs of them. So, for example, (A, W, D, B, E...) and (A, M, U, B, K...) might have a child (A, M, D, B, K...). In addition to this virtual sex, Holland added in virtual mutation, randomly flipping a letter from time to time.
The result was a brood of somewhat fitter possible route sequences, which were themselves tested and allowed to breed. Doing the whole thing a few hundred times, the Darwinian process of selection started to work its magic, leading eventually to the emergence of the shortest route.
This technique is an example of a "genetic algorithm" (GA), and as computer power has increased, so has the reputation of GAs. They are now routinely used to solve tough commercial problems ranging from designing the fastest routing circuitry for microchips to optimising airlines' flight schedules (see
New Scientist, 28 October 1995, p 40).
It was while pondering the power of GAs in the late 1980s that John Koza at Stanford had a brainwave. Why stop at breeding the best one-off solution to a problem? Why not go one better, and evolve not just the best answer, but the best method for finding the best answer: a formula that solves a whole raft of related problems, rather than just the one in hand? This is the essence of genetic programming-a kind of meta-GA. And as Koza quickly discovered, it is an idea of stunning power.
Making connections
Instead of starting with random collections of answers, such as the various routes in the travelling salesman problem, GP begins with random collections of mathematical operations and inputs: add,
x, sine, multiply,
y, and so on. These it then arranges to produce mathematically meaningful formulas, before testing each one to see how well it does in giving sensible answers to the problem in hand.
Looking for a challenge to test GP, Koza turned to our Solar System. Given data on planetary orbits, conventional GA could only perform mundane tasks like sorting them into ascending order of diameter. If Koza's ideas were right, however, genetic programming would be able to evolve more than just an orderly list of data. It should be able to evolve a series of mathematical operations that reveal the connections between, say, the time taken for a planet to orbit the Sun and its distance from the Sun. In other words, it should provide a method for predicting how different planets behave.
Starting from a random jumble of mathematical operations, Koza's computer rapidly homed in on a formula it reckoned did the best job of relating planetary distances to their periods. Sure enough, the formula turned out to be Kepler's Third Law of Planetary Motion, named after the astronomer who discovered it in 1618, after years of toil.
Back in the 1980s, room-sized supercomputers could manage a few billion calculations a second. But GP is a hungry beast, eating gigaflops at a fearsome rate, so it is only now beginning to come into its own. In 1998, Koza and his colleagues used GP to evolve a soccer-playing algorithm that beat half the human-devised entries in a robotic football contest. Meanwhile, a team led by Lee Spector at Hampshire College in Massachusetts has used GP to evolve new algorithms for quantum computers which could perform tasks such as database searching far faster than ordinary computers.
With quantum computers still years away and robotic football unlikely to change the course of history, there's little about these achievements to suggest that big business has much to fear from GP. But just wait. A paper published last year by Koza and his colleagues shows that GP is ready to move out of academia and into the hard-nosed world of commercial product design.
In the inaugural issue of the journal
Genetic Programming and Evolvable Machines, the team described more than a dozen products-electronic thermometers, analogue-to-digital converters, amplifiers and filters-created using nothing more than a basic specification of what they wanted the products to do, plus the mighty power of GP.
Some have turned out to be rediscoveries of world-beating products such as the Yagi-Uda antenna. Invented in the late 1920s by the eponymous pair of Japanese engineers, these ladder-shaped antennas are plugged into millions of TVs across the world. Koza and his team used GP to evolve the design from nothing more than some performance demands, such as the frequencies it should operate at, and the requirement that it fit into a rectangle no bigger than 40 centimetres by 265 centimetres. Each GP-driven attempt was tested using software that could gauge how well these demands had been met, allowing the best to be taken and bred from. "The thing is, unlike Yagi and Uda, we got to this design without knowing anything about antennas," says Koza. "We just specified the performance we wanted and got a box of simulation software from Berkeley to test each attempt. GP did the rest."
The idea of amateurs armed with GP rediscovering design classics is worrying enough. Much more disturbing is the fact that many of the products in Koza's list meet their spec in completely new ways, and sometimes outperform the very best efforts of human designers.
Fast feedback
Some of their most impressive results have emerged from the search for new types of process controller, arrangements of electronic components that can look after tasks such as altering the temperature in a room as people come and go. Because such controllers often involve non-linear feedback, human designers have to use all their ingenuity to avoid erratic circuit behaviour, where the controller either over or under-compensates for any changes in circumstances.
Designing circuits that avoid such problems is difficult, however, because it calls for components whose behaviour is hard to analyse mathematically. But, Koza points out, all this complexity is irrelevant in GP: all it needs is the properties of various possible components of a controller; evolution does the rest. Two controller designs evolved by GP turned out to be better than anything devised by human engineers. They use components that human designers find hard to deal with because their effects are mathematically complex. "But of course GP doesn't know that-it just goes ahead and uses them anyway," says Koza.
Perhaps most worrying of all for believers in the supremacy of human inventiveness is the ease with which GP can create products that evade the safeguard relied on by inventors for centuries: patents.
Whereas human design departments constantly have to check that their new product ideas don't duplicate the features of existing products, GP can do it all automatically. It's simply a matter of including the key features of existing patents in the original spec and checking each generation of progeny against it. Any offending offspring are then killed off, and the Darwinian process is then allowed to proceed on its way up the evolutionary ladder.
Having got GP to handle the key issue of patent infringement, Koza and his colleagues now think their technology is ready to form the basis of an invention machine, able to turn out new, top-performing and patentable products to order.
Anyone planning to buy an invention machine faces a steep entry price, however: the most computing power you can lay your hands on. To evolve their electronic controller circuit, Koza and his colleagues required hundreds of generations of tens of thousands of offspring, and even with their computer packing 66 DEC Alpha micro-chips zipping along at 533 megahertz, it took around two days to finish the job.
Moreover, the first products to emerge from the GP production line-electronic filters, amplifiers, antennas-are not exactly high-street eye-catchers. Using GP to evolve a complex 3D product such as a new vacuum cleaner makes circuit design look like child's play. "We can't do it at present. With current computing power, it would take years," says Koza. "But the amount of available power is increasing at least as fast as Moore's law, doubling every 18 months or so," he points out. "Within maybe as little as seven to ten years we could be handling full three-dimensional product design."
So is the day coming when everything from circuits to vacuum cleaners to supertankers is evolved by computer-propelled Darwinian evolution? Is the human art of invention about to be made redundant by multinationals wielding teraflop invention machines?
It's a prospect that Dyson finds depressing. "It will mean the end of so many of those wonderful stories of how people made great inventions by accident." Even so, he is convinced that human ingenuity and intuition will remain crucial in making a success of any product. He cites the example of the transparent casing of the DC01-a seemingly minor feature which many retailers insisted was a blunder because it showed the dirt accumulating inside the machine. In fact, it has turned out to be a big selling point. "I knew customers would love it, because it allowed them to see the cleaner working," says Dyson.
Dyson sees much bigger implications for GP in the future of patents themselves. "The original idea of patents was to give innovators time to benefit from the fruits of their ingenuity," he says. "This new technology would ruin that. Companies could just get hold of the patent, see what it does, check which claims they mustn't infringe, and just press the button."
But as Dyson points out, the first patent was granted in 1449, so maybe it's time for a bit of a shake-up. One way forward, he says, might be to grant patents to whoever is first to bring a commercially viable product to market. "That's the real challenge in innovation," he says. "Not just dreaming it up, but actually turning it into a marketable product."
Koza agrees that GP needn't make human ingenuity redundant. After all, the process of evolution works much better and faster if a gifted human can feed in a good first generation of ideas. Koza cites Dyson's own billion-pound success: "Just thinking that a radically new type of vacuum cleaner design was even possible is a big creative leap."
He also agrees that patent law may be due for an overhaul. In fact, the issue of patent protection is proving crucial for Koza himself. He patented the GP concept back in the 1980s. But he has yet to make any money out of it, and time is fast running out. "I said at the time that serious genetic programming wasn't really feasible with the computing power then available," he recalls. "It's getting there now, but there's only five years left to run on my original patent."
Time, perhaps, to get that massively parallel supercomputer to evolve an even fitter form of genetic programming.
Robert Matthews is science correspondent of New Scientist 20 January 2001.