Evolutionary Optimization in Non-Stationary Environments


Krzysztof Trojanowski
Zbigniew Michalewicz
Institute of Computer Science, Polish Academy of Sciences, ul.
Ordona 21, 01-237 Warsaw, Poland
Department of Computer Science, University of North Carolina,
Charlotte, NC 28223, USA

As most real-world problems are dynamic, it is not sufficient to ``solve'' the problem for the some (cur- rent) static scenario, but it is also necessary to modify the current solution due to various changes in the environment (e.g., machine breakdowns, sickness of employees, etc). Thus it is important to investigate properties of adaptive algorithms which do not require re-start every time a change is recorded. In this paper such non-stationary problems (i.e., problems, which change in time) are considered. We describe different types of changes in the environment. A new model for non-stationary problems and a classification of these problems by the type of changes is proposed. We apply evolutionary algorithms to non-stationary problems. We extend evolutionary algorithm by two mechanisms dedicated to non-stationary optimization: redundant genetic memory structures and a diversity maintenance technique --- random immigrants mechanism. We report on experiments with evolutionary optimization employing these two mechanisms (separately and together); the results of experiments are discussed and some observations are made.