Evolutionary Algorithms for Dynamic Environments: Prediction using Linear Regression and Markov Chains

Authors

Abstract

In this work we investigate the use of prediction mechanisms in Evolutionary Algorithms for dynamic environments. These mechanisms 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. Our study is made using environments where some pattern can be observed. Environments can change in two ways: periodically, following a fixed change period, or according to a repeated pattern of change. Markov Chains are applied to model the characteristics of the environment and we use that model to predict about possible future states. To forecast when a change will probably arise, we employ a linear regression predictor. Both predictions modules use information from the past to estimate the future. Knowing à priori when a change will take place and which state(s) will appear next, we can introduce useful information in the population before change happens, avoiding the performance's decrease usually observed with standard evolutionary algorithms. The techniques are applied to several instances of the dynamic bit matching problem and the obtained results prove the effectiveness of the proposed mechanisms.

Keywords

Evolutionary Algorithms, Dynamic Environments, Prediction, Markov chains, Linear Regression

Subject

Evolutionary Optimization

TechReport Number

TR 2008/001