Improving prediction in evolutionary algorithms for dynamic environments

ABSTRACT

The addition of prediction mechanisms in Evolutionary Algorithms (EAs) applied to dynamic environments is essential in order to anticipate the changes in the landscape and maximize its adaptability. In previous work, a combination of a linear regression predictor and a Markov chain model was used to enable the EA to estimate when next change will occur and to predict the direction of the change. Knowing when and how the change will occur, the anticipation of the change was made introducing useful information before it happens. In this paper we introduce mechanisms to dynamically adjust the linear predictor in order to achieve higher adaptability and robustness. We also extend previous studies introducing nonlinear change periods in order to evaluate the predictor's accuracy.

REFERENCES

• 1: Peter A. N. Bosman, Learning, anticipation and time-deception in evolutionary online dynamic optimization, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102264]
• 2: P. A. Bosman. Learning and Anticipation in Online Dynamic Optimization. In S. Yang, Y.S. Ong and Y. Jin, editors, Evolutionary Computation in Dynamic and Uncertain Environments. Springer-Verlag, 2007.
• 3: J. Branke. Memory Enhanced Evolutionary Algorithms for Changing Optimization Problems. In IEEE Congress on Evolutionary Computation (CEC 1999), pages 1875--1882. IEEE Press, 1999.
• 4: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 2001
• 5: J. Branke, T. Kaußler and C. Schmidt, A Multi-Population Approach to Dynamic Optimization Problems. In I. Parmee, editor, Adaptive Computing in Design and Manufacture (ACDM 2000), pages 299--308. Spriger-Verlag, 2000.
• 6: Jürgen Branke , Dirk C. Mattfeld, Anticipation in Dynamic Optimization: The Scheduling Case, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.253-262, September 18-20, 2000
• 7: H. G. Cobb. An Investigation into the Use of Hypermutation as an Adaptive Operator in Genetic Algorithms having Continuous, Time-Dependent Nonstationary Environment. Technical Report TR AIC-90-001, Naval Research Laboratory 1990.
• 8: D. S. Moore and G. P. McCabe. Introduction to the Practice of Statistics (4th edition). Freeman and Company, 2003.
• 9: Y. Jin and J. Branke. Evolutionary Optimization in uncertain Environments: a survey. IEEE Transactions on Evolutionary Computation, 9(3): 303--317, 2005.
• 10: Claudio Rossi , Mohamed Abderrahim , Julio César Díaz, Tracking moving optima using kalman-based predictions, Evolutionary Computation, v.16 n.1, p.1-30, Spring 2008 [doi>10.1162/evco.2008.16.1.1]
• 11: A. Simões and E. Costa. Using Linear Regression to Predict Changes in Evolutionary Algorithms dealing with Dynamic Environments. Technical Report TR 2007/005, ISSN 0874-338X, CISUC, 2007.
• 12: Anabela Simões , Ernesto Costa, Variable-Size Memory Evolutionary Algorithm to Deal with Dynamic Environments, Proceedings of the 2007 EvoWorkshops 2007 on EvoCoMnet, EvoFIN, EvoIASP,EvoINTERACTION, EvoMUSART, EvoSTOC and EvoTransLog: Applications of Evolutionary Computing, April 11-13, 2007, Valencia, Spain [doi>10.1007/978-3-540-71805-5_68]
• 13: A. Simões and E. Costa. Evaluating Prediction's Accuracy in Evolutionary Algorithms for Dynamic Environments. Technical Report TR 2008/04, ISSN 0874-338X, CISUC, 2008.
• 14: Anabela Simões , Ernesto Costa, Evolutionary Algorithms for Dynamic Environments: Prediction Using Linear Regression and Markov Chains, 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_31]
• 15: P. D. Stroud. Kalman-extended Genetic Algorithm for Search in Nonstationary Environments with Noisy Fitness Evaluations. IEEE Transactions on Evolutionary Computation, 5(1): 66--77, 2001.
• 16: J. van Hemert, C. Van Hoyweghen, E. Lukshandl and K. Verbeeck. A Futurist Approach to Dynamic Environments. In GECCO EvoDOP Workshop, pages 35--38, 2001.
• 17: S. Yang. Explicit Memory Schemes for Evolutionary Algorithms in Dynamic Environments. In S. Yan, Y-S. Ong and Y. Jin, editors, Evolutionary Computation in Dynamic and Uncertain Environments, pages 3--28. Springer-Verlag, 2007.
• 18: Shengxiang Yang , Xin Yao, Experimental study on population-based incremental learning algorithms for dynamic optimization problems, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.11, p.815-834, November 2005 [doi>10.1007/s00500-004-0422-3]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation, Performance

Keywords:
dynamic environments, evolutionary algorithms, linear regression, markov chains, prediction