GOT A TOUGH NUT TO CRACK? TRY 'GENETIC' PROGRAMMING

Saturday, September 27, 2003

The idea that the human brain is like a computer isn't as popular as it used to be, mostly because its behavior doesn't much resemble that of any computer we've yet designed.

Brains and other biological systems work rather well in the environments in which they evolved, however, which suggests that perhaps the metaphor would be more fruitful the other way round. Why not let biological models inspire how we expect computer systems to work?

That was the subject of a talk given by John Koza, a consulting professor at Stanford University and president of Genetic Programming Inc., at the Accelerating Change Conference held Sept. 13-14 at Stanford. The aim: instead of writing a program that accomplishes a specific task, design a way of grading how well a program accomplishes that task.

Start with a lot of very simple programs (individuals) generated at random. In each generation, let the chance that an individual program will reproduce depend on how high a grade it gets (a measure of fitness, in the biological sense). Let individuals exchange parts of their instructions (their programming DNA). Throw in a bit of mutation, and let the system run until it produces individual programs that are very good at doing whatever the original task was.

Why would anyone go to so much trouble instead of just writing a suitable program in the first place? Because there are a lot of important problems for which no one has any idea how to write a suitable program.

When this line of research began, not much more than 15 years ago, it couldn't do much more than solve toy problems, the kind where you already know the answer and are tweaking the evolutionary process to make sure it can find a solution.

But since then the amount of available computer power has increased by several orders of magnitude. Now, Koza says, genetic programming is ``an automated invention machine'' that routinely delivers results competitive with human intelligence (for more information, see www.genetic-programming.com).

Take an example from the early decades of telephony; design a ``low-pass filter,'' one that allows low frequencies to get through but blocks high frequencies. Genetic programming may produce different outcomes on different runs, and in this case it evolved several known solutions. One was a Campbell filter, named for George Campbell, who patented it in 1917 for AT&T. Another was a Zobel filter, after Otto Zobel, 1925 AT&T patent.

But as the computers get more powerful, the patents get more recent. In fact -- still talking about circuits -- Koza has examples of at least six inventions patented since 2000.

Of course, it's not much use rediscovering things that other people have patented. Koza assured the audience that genetic programming has advanced far enough to invent new patentable things. But the process can also be tuned to avoid rediscovering known solutions.

The fitness measure evaluates how well evolved programs solve a particular problem. But fitness can be altered to take away points from programs that too closely resemble, for example, an existing patent, and the eventual survivors won't infringe it.

This will perhaps remind you that new species are more likely to evolve in ecological niches not already occupied by competitor species.

I don't mean to imply that Koza and his company are the only ones working in this field, though he has written several books and innumerable articles about it. He mentioned, among other real-world applications, that General Electric used a genetic algorithm as part of its effort to improve the design of Boeing's 777 jet engines. Curious about the details, I asked the search engine Google for ``GE jet engines genetics algorithm'' and turned up a 1996 article by Christopher Meyer that illustrates how the tuning works. The engineers wanted to improve the compressor, so after describing what it had to do, they introduced a new rule: Design a compressor with six stages instead of seven. The result not only met the design criteria, it was lighter than existing designs so it yielded more fuel savings.

Koza sees promise for genetic programming in, for example, solving problems that involve many variables that are densely interconnected in ways that are not well understood, or where human beings have no clue as to how to find a solution, but a fairly clear idea of what it needs to accomplish. There's no shortage of problems like that.

I don't intend to come over all theological about this, but there are parallels here that go beyond biology. Genetic programming is a program too, which creates and sustains the virtual universe in which the individual programs evolve, but does not itself evolve. It establishes the mechanics for evolution but doesn't know what the eventual survivors will look like. And, of course, humans determine the measure of fitness the genetic programming will use.