Dynamic evolutionary optimisation: an analysis of frequency and magnitude of change

ABSTRACT

In this paper, we rigorously analyse how the magnitude and frequency of change may affect the performance of the algorithm (1+1) EA_dyn on a set of artificially designed pseudo-Boolean functions, given a simple but well-defined dynamic framework. We demonstrate some counter-intuitive scenarios that allow us to gain a better understanding of how the dynamics of a function may affect the runtime of an algorithm. In particular, we present the function Magnitude, where the time it takes for the (1+1) EA_dyn to relocate the global optimum is less than n²log n (i.e., efficient) with overwhelming probability if the magnitude of change is large. For small changes of magnitude, on the other hand, the expected time to relocate the global optimum is e^Ω(n) (i.e., highly inefficient). Similarly, the expected runtime of the (1+1) EA_dyn on the function Balance is O(n²) (efficient) for a high frequencies of change and n^Ω(√n) (highly inefficient) for low frequencies of change. These results contribute towards a better understanding of dynamic optimisation problems in general and show how traditional analytical methods may be applied in the dynamic case.

REFERENCES

• 1: Thomas Bäck, Optimal Mutation Rates in Genetic Search, Proceedings of the 5th International Conference on Genetic Algorithms, p.2-8, June 01, 1993
• 2: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 2001
• 3: S. Droste. Analysis of the (1+1) EA for a dynamically changing objective function. Technical Report CI-113/01, Universitt Dortmund, 2001.
• 4: S. Droste. Analysis of the (1+1) EA for a dynamically changing onemax-variant. In Congress on Evolutionary Computation, pages 55--60. IEEE Press, 2002.
• 5: 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]
• 6: Stefan Droste , Thomas Jansen , Ingo Wegener, A rigorous complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with boolean inputs, Evolutionary Computation, v.6 n.2, p.185-196, Summer 1998 [doi>10.1162/evco.1998.6.2.185]
• 7: 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]
• 8: 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, 2001.
• 9: Y. Jin and J. Branke. Evolutionary optimization in uncertain environment -- a survey. IEEE Transactions on Evolutionary Computation, 9(3):303--317, 2005.
• 10: Ronald W. Morrison, Designing Evolutionary Algorithms for Dynamic Environments, SpringerVerlag, 2004
• 11: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 12: H.Müuhlenbein. How genetic algorithms really work -- i. mutation and hillclimbing. In Proceedings of the Second Conference on Parallel Problem Solving from Nature, pages 15--26. Elsevier, 1992.
• 13: Pietro S. Oliveto , Carsten Witt, Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_9]
• 14: Philipp Rohlfshagen , Xin Yao, Attributes of Dynamic Combinatorial Optimisation, Proceedings of the 7th International Conference on Simulated Evolution and Learning, December 07-10, 2008, Melbourne, Australia [doi>10.1007/978-3-540-89694-4_45]
• 15: S.A. Stanhope and J.M. Daida. (1+1) genetic algorithm fitness dynamics in a changing environments. In Congress on Evolutionary Computation, volume 3, pages 1851--1858. IEEE, 1999.
• 16: R. Tinos and S. Yang. Continuous dynamic problem generators for evolutionary algorithms. In Proceedings of the 2007 IEEE Congress on Evolutionary Computation, pages 236--243, 2007.
• 17: S. Yang. Non-stationary problem optimization using the primal-dual genetic algorithms. In R. Sarker, R. Reynolds, H. Abbass, K.-C. Tan, R. McKay, D. Essam, and T. Gedeon, editors, Proceedings of the 2003 IEEE Congress on Evolutionary Computation, volume 3, pages 2246--2253, 2003.
• 18: Shengxiang Yang, Memory-based immigrants for genetic algorithms in dynamic environments, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068196]
• 19: S. Yang. Memory-enhanced univariate marginal distribution algorithms for dynamic optimization problems. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation, volume 3, pages 2560--2567, 2005.
• 20: S. Yang and X. Yao. Population-based incremental learning with associative memory for dynamic environments. IEEE Transactions on Evolutionary Computation, 12(5):542--561, Oct. 2008.

INDEX TERMS

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

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

General Terms:
Algorithms, Theory

Keywords:
dynamic evolutionary computation, evolutionary algorithms, runtime analysis