Human-competitive results produced by genetic programming (Open Access)

springerlink.com

7 points·sadiq··2 comments

These results are always impressive.

The main problem in my opinion is that most genetic algorithms perform a kind of local search in the genotype space. A large part of the problem is therefor to find a way of encoding which makes the target function smooth with respect to the target function being optimized.

That in itself is a significant intelectual feat in many cases. So one should not be fooled into thinking we can now just plug any given problem into a GA and get brilliant results. Human input is still very much required.

Not sure what you mean by "local search", but GAs (/GP) are used precisely when the target function is unsmooth (otherwise basic hill-climbing algorithms such as backpropagation in neural nets could be used). The search heuristic of GAs (mutation, crossover, fitness-proportionate reproduction) is pseudo-random and very analogous to simulated annealing, where we start out very random then coalesce on our best guesses.

However I do agree that the smoothness of a target function under a particular encoding is key to evolutionary methods. I think the No Free Lunch Theorem implies that for every target fitness function, there is an encoding that makes it smooth and an encoding that makes it purely random, and everything in between.

Reply on news.ycombinator.com