John Koza Has Built an Invention Machine

The key was mating bits of computer programs together, not just strings of numbers. The old genetic algorithms worked to optimize specific parameters; Koza's leap in genetic programming allowed for open-ended evolutions of basic structure and so produced more novel and sophisticated designs. "If you're trying to breed a better racehorse, you could take a herd of horses out into a field and irradiate them and hope that, through random mutation, you get a better horse," Koza explains. "Or you could mate a champion with another champion."

His breakthrough moment came in October 1995. Working with only the most rudimentary information, he watched his computer evolve a circuit. Unlike the gas pipelines bred by genetic algorithms, his circuit didn't start with an inferior design that was optimized. Beginning from a pile of unconnected components-assorted resistors, capacitors and the like-his computer devised a complex electronic circuit.

Koza made a drawing of his new circuit and showed it to a colleague, who told him that it was a low-pass filter-a circuit used for cleaning up the signal passing through an amplifier. He also learned that someone had taken out a patent on it, which made him wonder whether genetic programming could evolve other patented circuits from scratch. He programmed the machine to design circuits with the attributes of other patented devices and started churning out infringements by the dozen. "That's when we began to see that genetic programming could be human-competitive," he says. "If you remake a patented circuit, you're doing something that people consider inventive."

NASA Signs On

January 25, 2005, looms large in the history of computer science as the day that genetic programming passed its first real Turing test: The examiner had no idea that he was looking at the intellectual property of a computer. This is especially significant because the U.S. Patent and Trademark Office requires a "non-obvious step"-a break from established practices or what someone might deduce from them-to grant an invention intellectual-property protection. The machine was demonstrably creative.

And that was just the start. Every day now, genetic programs continue to create the unexpected, the counterintuitive or the just plain weird. Take, for example, the antenna that was set to launch on NASA's Space Technology 5 mission, a test platform for new technologies, as this magazine went to press. Several years ago, Koza protg Jason Lohn took a job as a computer scientist at NASA Ames Research Center, which had taken an interest in evolutionary approaches to problem solving, including genetic algorithms. "Antenna design has a black-art quality to it," Lohn says. "A lot of it is intuition."

Lohn got his hands on the antenna specs for the Space Technology 5 mission. He plugged in an antenna's basic requirements and let the software run. What he got, several hundred generations later, appeared to be a mistake. "It looked like a bent paper clip," he remembers. Lohn had no background in antenna design, but that was beside the point. "There's no chapter in the textbooks on crooked wire antennas," he says. He had his bent paper clip prototyped and put it in a test chamber. Sure enough, it provided the tricky combination of wide bandwidth and wide beam that NASA required. Like the duck-billed platypus, it looked preposterous but proved perfectly suited to its niche.

John Holland has lately been researching what such ingenuity might tell us about the creative process in humans. He believes that revolutionary ideas don't come at random but are "new combinations of fairly standard parts with which we're already familiar." He cites as examples the internal combustion engine and the airplane, for which all the components were available long before the invention came along, lacking only someone with adequately broad knowledge, deep resources and the temperament to combine them. "Evolution is good at recombining building blocks to get innovations," Holland says. The machine has inspired a new way to think about our own creative process: Perhaps extraordinary thinking is simply the product of gradual refinements and serendipitous recombinations. Darwin's combination of mutation, sex and selection creates not just new species, or antennas: It spawns creativity itself.

The Search for Problems

As genetic programming becomes pervasive over the next decade, the process of finding good solutions to difficult engineering problems will become efficient in the way that once-arduous tasks such as 3-D rendering have become routine. But, as with 3-D rendering, the real challenge will lie in deciding what to create. This is no trivial matter-to invent a car, even with an invention machine, you must be able to conceive of wanting a horseless carriage in the first place. In the future, as solutions become plentiful and cheap, the real test of creativity will come in the search for problems.

Meanwhile, Koza thinks he has already found a good one to solve, although it will require more than just an invention machine. Confident as ever in the power of rational thought (and in himself), he has undertaken the mission of reengineering U.S. elections. More specifically, he has developed a strategy to effectively eliminate the American electoral college. Here's how it works:Since the Constitution allows each state to assign its electors any way it chooses, a critical mass of states could pledge to assign its electors to vote for the winner of the nationwide popular vote. In theory, as few as 11 states could make this work. The plan is slowly gaining traction among politicians and pundits, and a bill was recently introduced in the Illinois legislature that would make that state the first to back the plan.

As Koza waits for the machinations of politics to grind, he has his sights set on one more goal, perhaps genetic programming's ultimate Turing test: an invention that succeeds in the marketplace. (Passing muster with a patent examiner is nothing compared to nabbing a couple million customers.) That means finding a problem serious enough that people will pay to have it solved. Alas, figuring out what people really need is one thing genetic programming can't do. Koza will have to invent that for himself.

Jonathon Keats is writing a collection of fables called The Book of the Unknown.