Comparing global and local mutations on bit strings

Evolutionary algorithms operating on bit strings usually employ a global mutation where each bit is flipped independently with some mutation probability. Most often the mutation probability is set fixed in a way that on average exactly one bit is flipped in a mutation. A seemingly very similar concept is a local one realized by an operator that flips exactly one bit chosen uniformly at random. Most known results indicate that the global approach leads to run-times at least as good as the local approach. The draw-back is that the global approach is much harder to analyze. It would therefore be highly useful to derive general principles of when and how results for the local operator extend to the global ones. In this paper, we show that there is little hope for such general principles, even under very favorable conditions. We show that there is a fitness function such that the local operator from each initial search point finds the optimum in small polynomial time, whereas the global operator for almost all initial search points needs a weakly exponential time.