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 a

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.