Using Linear Regression to Predict Changes in Evolutionary Algorithms dealing with Dynamic Environments

Authors

Abstract

Many real-word problems change over time and usually, the moment when next change will happen is unknown. Evolutionary Algorithms have been widely used to deal with changing environments and the algorithm is constantly monitoring for alterations and just after detecting one some action is taken. Nevertheless, some of the studied environments are characterized by the periodicity of the change. In these cases it is possible to predict when the next change will occur and start using some mechanisms before the change take place. In this report we carried out an investigation in cyclic changing environments with periodic changes, using linear regression to predict when next change will occur. Based on the predicted value, the algorithm starts preparing the population for the near change. This idea is tested in a memory-based EA using a population and memory of variable sizes previously studied with considerable success. We assume that the predicted moment can have a small error. Before the change occurs two different actions can be taken in order to avoid the decrease of the algorithm's performance under the new conditions. The results show that prediction is useful for cyclic environments when the period between changes is small and when more different states can appear in the environment.

Keywords

Evolutionary Algorithms, Dynamic Environments, Prediction, Memory, Statistics, Linear Regression

Subject

Evolutionary Optimization

TechReport Number

TR2007/005