Comparing global and local mutations on bit strings

ABSTRACT

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.

REFERENCES

• 1: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 2: B. Doerr, E. Happ, and C. Klein. A tight bound for the (1+1)-EA on the single source shortest path problem. In D. Srinivasan and L. Wang, editors, Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC), pages 1890--1895. IEEE Press, 2007.
• 3: Stefan Droste , Thomas Jansen , Ingo Wegener, On the Optimization of Unimodal Functions with the (1 + 1) Evolutionary Algorithm, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.13-22, September 27-30, 1998
• 4: Stefan Droste , Thomas Jansen , Ingo Wegener, On the analysis of the (1+ 1) evolutionary algorithm, Theoretical Computer Science, v.276 n.1-2, p.51-81, April 6, 2002 [doi>10.1016/S0304-3975(01)00182-7]
• 5: Jun He , Xin Yao, A study of drift analysis for estimating computation time of evolutionary algorithms, Natural Computing: an international journal, v.3 n.1, p.21-35, 2004 [doi>10.1023/B:NACO.0000023417.31393.c7]
• 6: Jeffrey Horn , David E. Goldberg , Kalyanmoy Deb, Long Path Problems, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.149-158, October 09-14, 1994
• 7: Thomas Jansen , Ingo Wegener, On the Choice of the Mutation Probability for the (1+1) EA, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.89-98, September 18-20, 2000
• 8: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 9: Günter Rudolph, How mutation and selection solve long-path problems in polynomial expected time, Evolutionary Computation, v.4 n.2, p.195-205, Summer 1996 [doi>10.1162/evco.1996.4.2.195]
• 10: G. Rudolph. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovač, Hamburg, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
analysis, evolutionary computation, mutation, randomized local search