An evolutionary approach has the same difficulties in dealing with local optima. There are techniques (like simulated annealing) that transform the nasty optimization problem into a nice (convex, or at least, single optimum) optimization problem such that the global optima of the two problems are identical. Then, the nice, solved optimization problem can be slowly transformed back into the original, nasty problem in such a way that you can find that global minimum.

Tomorrow Never Dies...