Skip to main content
main-content
Top

About this book

Evolutionary Algorithms (EAs) have grown into a mature field of research in optimization, and have proven to be effective and robust problem solvers for a broad range of static real-world optimization problems. Yet, since they are based on the principles of natural evolution, and since natural evolution is a dynamic process in a changing environment, EAs are also well suited to dynamic optimization problems. Evolutionary Optimization in Dynamic Environments is the first comprehensive work on the application of EAs to dynamic optimization problems. It provides an extensive survey on research in the area and shows how EAs can be successfully used to continuously and efficiently adapt a solution to a changing environment, find a good trade-off between solution quality and adaptation cost, find robust solutions whose quality is insensitive to changes in the environment, find flexible solutions which are not only good but that can be easily adapted when necessary. All four aspects are treated in this book, providing a holistic view on the challenges and opportunities when applying EAs to dynamic optimization problems. The comprehensive and up-to-date coverage of the subject, together with details of latest original research, makes Evolutionary Optimization in Dynamic Environments an invaluable resource for researchers and professionals who are dealing with dynamic and stochastic optimization problems, and who are interested in applying local search heuristics, such as evolutionary algorithms.

Table of Contents

Frontmatter

Brief Introduction to Evolutionary Algorithms

Chapter 1. Brief Introduction to Evolutionary Algorithms

Abstract
Evolutionary algorithms are randomized heuristic search methods based on the principles of natural evolution, or more specifically, on Darwin’s theory of survival of the fittest.
Jürgen Branke

Enabling Continuos Adaptation

Frontmatter

Chapter 2. Optimization in Dynamic Environments

Abstract
Whenever a change in a dynamic optimization problem occurs i.e. when the optimization goal, the problem instance, or some restrictions change, the optimum to that problem might change as well. If this is the case, an adaptation of the old solution is necessary.
Jürgen Branke

Chapter 3. Survey: State of the Art

Abstract
The following subsections survey methods that have been proposed to make EAs suitable for dynamic environments. Some widely used approaches, like restart mechanisms, adaptive mutation, or the addition of memory are treated in separate subsections, further approaches are collected in the last subsection.
Jürgen Branke

Chapter 4. From Memory to Self-Organization

Abstract
In the preceding chapter, we have thoroughly reviewed the existing approaches to make evolutionary algorithms more suitable for dynamic optimization problems. Most of these concentrate on either memorization or diversity as a means to facilitate adaptation. In this chapter, two new approaches of applying evolutionary algorithms to dynamic optimization problems are presented. The first one, called “memory/search”, combines the concepts of explicit memory and diversification in a particularly effective way. It is described in Section 1.
Jürgen Branke

Chapter 5. Empirical Evaluation

Abstract
There is no clear consensus on how to best compare the performance of two EA variants, and on dynamic environments that is particularly challenging.
Jürgen Branke

Chapter 6. Summary of Part 1

Abstract
Part 1 started with a brief introduction into the field of optimization in dynamic environments. Since being able to accurately describe the dynamics of a problem is a prerequisite to understanding how an approach reacts to different dynamics and to determine which approaches might be most suitable for a certain environment, in the following section a number of parameters have been identified that might be used to characterize dynamic environments, namely the change frequency, severity of change, predictability of change, cycle length and accuracy.
Jürgen Branke

Considering Adaptation Cost

Frontmatter

Chapter 7. Adaptation Cost vs. Solution Quality: Multiple Objectives

Abstract
In many practical applications, adapting an already implemented solution to changes in the environment incurs some adaptation cost. In these cases, in addition to the solution quality, the “distance” from the old solution respectively the cost to change the old solution into the new solution has to be taken into account when searching for an optimal adaptation.
Jürgen Branke

Robustness and Flexibility — Precaution Against Changes

Frontmatter

Chapter 8. Searching for Robust Solutions

Abstract
So far in this work, it has been assumed that uncertainties and changes of the environment should be treated by continuously adapting the solution to the dynamic environment. However, in many real world situations adaptation is not possible, e.g. because the environment changes too quickly, because the environment cannot be monitored closely enough, or because the changes occur after the commitment to a particular solution has been made.
Jürgen Branke

Chapter 9. From Robustness to Flexibility

Abstract
When searching for robust solutions in the previous chapter, the underlying assumption always was that the solution will not be changed, but instead should promise high quality even if the environment changes.
Jürgen Branke

Chapter 10. Summary and Outlook

Abstract
Most common heuristics are restricted to static optimization problems, i.e. problems that are completely known to the optimization algorithm from the beginning. However, many real-world optimization problems are stochastic and change over time. Therefore, powerful heuristics are needed that are not only capable of finding good solutions to a single static problem, but that account for the dynamics and the uncertainty present in real world problems.
Jürgen Branke

Backmatter

Additional information