Article Preview
Top1. Introduction
Recently, optimization in dynamic environments has attracted a growing interest, due to its practical relevance. Many real-world problems are dynamic optimization problems (DOPs), i.e. their objective function changes over time: typical examples are in vehicle routing (Larsen, 2000), inventory management (Minner, 2003) and scheduling (Branke & Mattfeld, 2005). For dynamic environments, the goal is not only to locate the optimum, but to follow it as closely as possible. A dynamic optimization problem can be expressed by:
(1) where
is the objective function of the problem,
denotes the
equality constraint and
denotes the
inequality constraint. Both of them may change over time, denoted by
. In this paper, we focus on a dynamic optimization problem with time constant constraints.
The main approaches to deal with DOPs can be classified into the following five groups (Jin & Branke, 2005):
- 1.
Generated diversity after a change: When a change in the environment is detected, explicit actions are taken to increase diversity and to facilitate the shift to the new optimum.
- 2.
Maintained diversity throughout the run: Convergence is avoided all the time and it is hoped that a spread-out population can adapt to change more efficiently.
- 3.
Memory-based approaches: These methods are supplied with a memory to be able to recall useful information from the past. In practice, they store good solutions in order to reuse them when a change is detected.
- 4.
Multipopulation approaches: Dividing up the population into several subpopulations, distributed on different optima, allows tracking of multiple optima simultaneously and increases the probability to find new ones.
- 5.
Future prediction: Recently, another kind of methods, trying to predict future changes, has attracted much attention (Rossi, Abderrahim, & Diaz, 2008), (Rossi, Barrientos, & Cerro, 2007), (Simoes & Costa, 2008). This approach is based on the fact that in a real problem, changes can follow some pattern that could be learned.
We focus on population-based metaheuristics, which are global search, generally bio-inspired, algorithms. We can roughly classify them in four categories: evolutionary algorithms (EAs), particle swarm optimization (PSO), ant colony optimization (ACO) and hybrid methods. We will now describe dynamic metaheuristics that have been proposed in the literature in each of these categories.