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.