Automatic Bug Repair with Genetic Programming (source code) | Hacker News Reader

Automatic Bug Repair with Genetic Programming (source code)

genprog.adaptive.cs.unm.edu

22 pointsunignorant9 comments

I see genetic programming as an interesting solution to lots of different problems, but I don't think debugging is one of them.

Bugs in my code usually reflect errors in my thinking (or typos). The genetic program would likely come up with the quickest hack that will get the code working, not the correct redesign that will be easiest to read and maintain for humans.

Genetic approaches will get you whatever you design them to do - in cell biology, we call that "you get what you evolve for". If you want code to do a particular task, and write a fitness score that only reflects that, you'll get a hack that does that. If you want readability, you add constraints to the mutation parameters that enforce that requirement at every generation, and you'll get readability.

The hard part becomes writing those constraints, not writing the actual solution.

"The hard part becomes writing those constraints, not writing the actual solution."

Yes, writing constraints can be difficult, as can figuring out which constraints you need, and coming up with fitness functions for figuring out how good a given solution is.

Other difficulties include tweaking the various parameters of the GP to perform well enough to get reasonable solutions in a reasonable amount of time, and making sure you're not overoptimizing, etc...

The other thing I'd mention is that one should always take the results of AI research with a big grain of salt. Often the problems they work on are unrealistic toy problems that have little relevance to anything you'd actually do in the real world, and their statistical methods leave a lot to be desired.

There's huge pressure to get funding, so many papers tend to be unrealistically optimistic and misleading (but get published anyway).

Why are programmers constantly trying to program themselves out of having jobs? While I am joking here, it is interesting to consider that debugging is one of the most complex aspects of programming, and if you took that away from programmers, they might spend their time actually doing something useful... like creating software.

Evolution is too inefficient

Before you get downvoted for sounding glib, allow me to elaborate on what you said: "The search space for evolving bug fixes in a program is likely to be extraordinarily large. Furthermore there will be places of sharp division in the fitness landscape between working programs and nonworking programs. Therefore I'm skeptical whether evolving bug fixes is likely to be computationally tractable in the general case."

Well said.

I'd add that evolution works for organisms because they have evolved evolvability. By this I mean that the source code isn't fragile, so that you can take the source code from two organisms of the same (sexually reproducing) species, mix and match them together, and the resulting DNA codes for a viable organism. This even works for closely related species as the existance of mules demonstrates.

Programs written by humans in the sort of programming languages we use do not have this characteristic of robustness.

Genetic programming would work better using languages specifically designed to be robust in this sense.

But if we can speed up evolution several thousand folds...

It might be inefficient in absolute time, but in terms of programmer effort genetic algorithms can be tremendously efficient.

I used a genetic algorithm to optimize a signal processing routine in my research (I'm a grad student in biological engineering, the project is sizing nanoparticles). It took me 3 days to write and debug a mutation algorithm, a fitness score, and a backbone that iterates breeding a new generation of code and keeping the most fit offspring. I started running the code on a Friday and by Monday morning, at around 500 generations, the fitness score had improved 60%. Colleagues of ours working on a very similar problem spent 3 months doing the same thing manually and only got to about 55% improvement.

I spent that weekend sailing and thinking, I'm glad my computer is doing my work for me right now.

Reply on news.ycombinator.com