STANDING 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.
Advertisement
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
żěè¶ĚĘÓƵ, 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
±č˛ąłŮ±đ˛ÔłŮ.”
Time, perhaps, to get that massively parallel supercomputer to evolve an even
fitter form of genetic programming.