Prediction in evolutionary algorithms for dynamic environments using markov chains and nonlinear regression

ABSTRACT

The inclusion of prediction mechanisms in Evolutionary Algorithms (EAs) used to solve dynamic environments allows forecasting the future and this way we can prepare the algorithm to the changes. Prediction is a difficult task, but if some recurrence is present in the environment, it is possible to apply statistical methods which use information from the past to estimate the future. In this work we enhance a previously proposed computational architecture, incorporating a new predictor based on nonlinear regression. The system uses a memory-based EA to evolve the best solution and a predictor module based on Markov chains to estimate which possible environments will appear in the next change. Another prediction module is responsible to estimate when next change will happen. In this work important enhancements are introduced in this module, replacing the linear predictor by a nonlinear one. The performance of the EA is compared using no prediction, using predictions supplied by linear regression and by nonlinear regression. The results show that this new module is very robust allowing to accurately predicting when next change will occur in different types of change periods.

REFERENCES

• 1: P. A. N. Bosman and H. La Poutr´e. Computationally Intelligent Online Dynamic Vehicle Routing by Explicit Loa Prediction in Evolutionary Algorithm. In T. P. Runarsson, H.-G. Beyer, E. Burke, J. Merelo-Guervós, L. D. Whitley and X. Yao, editors, Proceedings of Parallel Problem Solving from Nature (PPSN IX), Lecture Notes in Computer Science, volume 4193, pages 312--321. Springer-Verlag, 2006.
• 2: P. A. N. Bosman and H. La Poutré. Inventory Management and the Impact of Anticipation in Evolutionary Stochastic Online Dynamic Optimization. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 268--275. IEEE Press, 2007.
• 3: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 2001
• 4: 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
• 5: D. S. Moore and G. P. McCabe. Introduction to the Practice of Statistics (4th edition). Freeman and Company, 2003.
• 6: Z. Pan, Y. Chen, L. Kan and Y. Zhang. Parameter Estimation by Genetic Algorithms For Nonlinear Regression. In Proceedings of the International Conference on Optimization Techniques and Applications, pages 946--953. World Scientific, 1995.
• 7: 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]
• 8: G. A. F. Seber and C. J. Wild. Nonlinear Regression. Wiley&Sons, Inc, 2003.
• 9: A. Simões and E. Costa. Evaluating Predictor's Accuracy in Evolutionary Algorithms for Dynamic Environments. In Proceedings of GECCO-2009. ACM, 2009.
• 10: A. Simões and E. Costa. Improving Memory's Usage in Evolutionary Algorithms for Changing Environments. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 276--283. IEEE Press, 2007.
• 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: 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]
• 14: A. Simões and E. Costa. Prediction in Evolutionary Algorithms for Dynamic Environments Using Markov Chains and Nonlinear Regression. Technical Report TR 2009/01, ISSN 0874-338X, CISUC, 2009.
• 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.

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, markov chains, nonlinear regression, prediction