11. Nonstationary and Noisy Function Optimisation

Unlike most of the examples we have used so far, real-world environments typically contain sources of uncertainty. This means that if we measure the fitness of a solution more than once, we will not always get the same result. Of course, biological evolution happens in just such a dynamic environment, but there are also many EA applications in environments featuring change or noise when solutions are evaluated.

In these nonstationary situations the search algorithm has to be designed so that it can compensate for the unpredictable environment by monitoring its performance and altering some aspects of its behaviour. An objective of the resulting adaptation is not to find a single optimum, but rather to select a sequence of values over time that maximise or minimise some measure of the evaluations, such as the average or worst. This chapter discusses the various sources of unpredictability, and describes the principal adaptations to the basic EA in response to them.

Contents:

11.1 Characterisation of Nonstationary Problems …………….185
11.2 The Effect of Different Sources of Uncertainty……………187
11.3 Algorithmic Approaches ……………………………189
11.3.1 Approaches That Increase Robustness or Reduce Noise . 189
11.3.2 Pure Evolutionary Approaches to Dynamic
Environments . . . . . . . . . . . . . .. . . . . . . . . . . . . 189

11.3.3 Memory-Based Approaches for Switching or Cyclic Environments . . . . . . . . . . . . . . . . 190
11.3.4 Explicitly Increasing Diversity in Dynamic Environments190
11.3.5 Preserving Diversity and Resampling: Modifying Selection and Replacement Policies ………………191
11.3.6 Example Application: Time-Varying Knapsack Problem 193

Suggested Reading

Exercises

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

The on-line accompaniment to the book Introduction to Evolutionary Computing