Abstract
In this work we investigate the use of prediction mechanisms in Evolutionary Algorithms for dynamic environments. These mechanisms, linear regression and Markov chains, are used to estimate the generation when a change in the environment will occur, and also to predict to which state (or states) the environment may change, respectively. Different types of environmental changes were studied. A memory-based evolutionary algorithm empowered by these two techniques was successfully applied to several instances of the dynamic bit matching problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments: a survey. IEEE Transactions on Evolutionary Computation 9(3), 303–317 (2005)
Yang, S.: Explicit memory schemes for evolutionary algorithms in dynamic environments. In: Yang, S., Ong, Y.S., Jin, Y. (eds.) Evolutionary Computation in Dynamic and Uncertain Environments, pp. 3–28. Springer, Heidelberg (2007)
Simões, A., Costa, E.: Evolutionary algorithms for dynamic environments: prediction using linear regression and markov chains. Technical Report TR 2008/01, CISUC (2008)
Branke, J., Mattfeld, D.: Anticipation in dynamic optimization: The scheduling case. In: Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Merelo, J., Schwefel, H.P. (eds.) PPSN VI 2000. LNCS, vol. 1917, pp. 253–262. Springer, Heidelberg (2000)
Stroud, P.D.: Kalman-extended genetic algorithm for search in nonstationary environments with noisy fitness evaluations. IEEE Transactions on Evolutionary Computation 5(1), 66–77 (2001)
van Hemert, J., Hoyweghen, C.V., Lukshandl, E., Verbeeck, K.: A futurist approach to dynamic environments. In: GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pp. 35–38 (2001)
Bosman, P.: Learning, anticipation and time-deception in evolutionary online dynamic optimization. In: Yang, S., Branke, J. (eds.) GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization (2005)
Bosman, P.A.N.: Learning and anticipation in online dynamic optimization. In: Yang, S., Ong, Y.S., Jin, Y. (eds.) Evolutionary Computation in Dynamic and Uncertain Environments. Springer, Heidelberg (2007)
Bird, S., Xiaodong, L.: Using regression to improve local convergence. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pp. 592–599. IEEE Press, Los Alamitos (2007)
Norris, J.R.: Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (1997)
Branke, J.: Memory enhanced evolutionary algorithms for changing optimization problems. In: IEEE Congress on Evolutionary Computation (CEC 1999), pp. 1875–1882. IEEE Press, Los Alamitos (1999)
Simões, A., Costa, E.: Improving memory’s usage in evolutionary algorithms for changing environments. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007). IEEE Press, Los Alamitos (2007)
Simões, A., Costa, E.: An immune system-based genetic algorithm to deal with dynamic environments: Diversity and memory. In: Proc. of the 6th Int. Conf. on Artificial Neural Networks, pp. 168–174. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Simões, A., Costa, E. (2008). Evolutionary Algorithms for Dynamic Environments: Prediction Using Linear Regression and Markov Chains. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds) Parallel Problem Solving from Nature – PPSN X. PPSN 2008. Lecture Notes in Computer Science, vol 5199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87700-4_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-87700-4_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87699-1
Online ISBN: 978-3-540-87700-4
eBook Packages: Computer ScienceComputer Science (R0)