What is holding genetic programming back?
Solution 1:
This is something I have been considering in my own research, and I'd say there are many reasons:
The vast majority of research in the GP field has focused on producing formulas rather than the sort of software that gets produced by most programmers. There are plenty of computer scientists in the field, but very few are focused on producing the sort of programs you would expect, so advances have been slow in that area.
There is a significant over emphasis on using LISP because it can produce nice tree structures which are easy to manipulate and unfortunatly imperative programs have been neglected because they involve solving some tricky problems. For GP to be taken seriously by programmers it has to produce imperative programs.
Real programs contain looping constructs, but loops are difficult to implement in GP without all sorts of ugly constraints to prevent infinite looping.
Genetic Programming does not scale well. It is fine for small problems, with a small available language, but as you say in your first point - the search space becomes too large very quickly.
Compared to a human programmer, GP can be very slow. It is however very parallelisable so is likely to benefit substantially as larger numbers of processor cores become the norm.
Another valid answer would be that it is difficult to trust code has been automatically generated. This is true, but in practice I doubt this has much impact because GP is not able to produce the right sort of programs in the first place.
Solution 2:
The hard part about genetic programming is writing a good scoring function:
The scoring function must correctly judge whether the algorithm has the desired properties. This is harder than it sounds -- much harder than writing a test suite. The algorithm may adapt to any quirk of your scoring function and optimize it. Trying to evolve
strcmp? Your algorithm may instead discover a mathematical pattern to the lengths of your pass/fail test cases.The scoring function must be capable of judging whether the algorithm under test is partially working. Genetic programming relies on "hill climbing". A tiny beneficial mutation needs to cause a tiny incremental improvement in score. If your scoring function can only output true/false then you're searching randomly, not genetically.
If you try your hand at it you'll find that genetic programming is the ultimate in lateral thinking: Your program will tend to solve the problem in every way you didn't think of, most of them unexpected and (for serious applications) probably useless. One famous case involved an attempt to evolve an oscillator using basic electronic components. It was judged on the simplicity of the circuit and whether the output oscillated. It produced something so simple the researchers were sure it couldn't work, but it did: It was picking up and amplifying radio waves from the environment.
Edit to cite:
Graham-Rowe, Duncan. "Radio emerges from the electronic soup." New Scientist, vol.175, no.2358, p.19 (August 31, 2002). Available online at http://www.newscientist.com/news/news.jsp?id=ns99992732
However the link now appears to be broken.
New link is http://www.newscientist.com/article/dn2732-radio-emerges-from-the-electronic-soup.html