On the local performance of simulated annealing and the (1+1) evolutionary algorithm

ABSTRACT

Simulated annealing and the (1+1) EA, a simple evolutionary algorithm, are both general randomized search heuristics that optimize any objective function with probability converging to 1. But they use very different techniques to achieve this global convergence. The (1+1) EA applies global mutations than can reach any point in the search space in one step together with an elitist selection mechanism. Simulated annealing restricts its search to a neighborhood but employs a randomized selection scheme where the probability for accepting a move to a new point in the search space depends on the difference in function values as well as on the current time step. Otherwise, the two algorithms are equal. It is known that the different philosophies of search implemented in the two heuristics can lead to exponential performance gaps between the two algorithms with respect to the expected optimization time. Even for very restricted classes of objective functions where the differences in function values between neighboring points are strictly limited the performance differences can be huge. Here, a more local point of view is taken. Considering obstacles in the fitness landscapes it is proven that the local performance of the two algorithms is remarkably similar in spite of their different search behaviors.

REFERENCES

• 1: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 2: J. R. Cruz and C. C. Y. Dorea. Simple conditions for the convergence of simulated annealing type algorithms. Journal of Applied Probability, 35(4):885--892, 1998.
• 3: Stefan Droste , Thomas Jansen , Ingo Wegener, Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization, Theory of Computing Systems, v.39 n.4, p.525-544, July 2006 [doi>10.1007/s00224-004-1177-z]
• 4: W. Feller. An Introduction to Probability Theory and its Applications I. Wiley, 1968.
• 5: Bruce Hajek, Cooling schedules for optimal annealing, Mathematics of Operations Research, v.13 n.2, p.311-329, May 1988 [doi>10.1287/moor.13.2.311]
• 6: Thomas Jansen, On the Analysis of Dynamic Restart Strategies for Evolutionary Algorithms, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.33-43, September 07-11, 2002
• 7: T. Jansen. A comparison of simulated annealing with a simple evolutionary algorithm. In A. H. Wright, M. D. Vose, and K. A. De Jong, editors, Foundation of Genetic Algorithms 8 (FOGA 2005), pages 37--57. Springer, 2005. LNCS 3469.
• 8: 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
• 9: T. Jansen and I. Wegener. Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Transactions on Evolutionary Computation, 5(6):589--599, 2002.
• 10: T. Jansen and I. Wegener. On the analysis of a dynamic evolutionary algorithm. Journal of Discrete Algorithms, 2006. To appear. Available online via Science Direct. http://dx.doi.org/10.1016/j.jda.2005.01.002.
• 11: M. Jerrum and G. Sorkin. Simulated annealing for graph bisection. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 1993), pages 94--103. IEEE Press, 1993.
• 12: S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science, 220:671--680, 1983.
• 13: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21:1087--1092, 1953.
• 14: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 15: G. Rudolph. Convergence Properties of Evolutionary Algorithms. Kovac, 1997.
• 16: I. Wegener. Simulated annealing beats metropolis in combinatorial optimization. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), pages 589--601. Springer, 2005. LNCS 3580.
• 17: Ingo Wegener , Carsten Witt, On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics, Combinatorics, Probability and Computing, v.14 n.1, p.225-247, January 2005 [doi>10.1017/S0963548304006650]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Performance, Theory

Keywords:
evolutionary algorithms, local performance, mutation, run time analysis, selection, simulated annealing