1 Introduction

Telecommunications, infrastructures, services and, in general, all the aspects concerning the information society, give raise to a set of complex problems where several objectives may need to be satisfied, that may vary with time, or where uncertainty of diverse types may exist in the values of the variables, coefficients, or even in the objectives. Also, alternatives that were bad in the past can be good nowadays or vice versa; criteria that were important before become irrelevant now, etc., and moving in this dynamic scenarios is a challenge. The development of solving strategies in the area of intelligent systems that may work in such dynamic and imprecise scenarios raises new challenges that are being addressed from different points of view by the international scientific community.

Many problems in this context can be modeled as dynamic optimization problems (\(\hbox{DOPs}\)) in which some elements of the underlying model change over the course of the optimization. Here, we will consider \(\hbox{DOP}\) defined as follows:

$$ \hbox{DOP} = \left\{ \begin{array}{ll} \hbox{optimize} &f(x,t) \\ \hbox{s.t.} & x \in F(t) \subseteq S, t \in T \\ \end{array}\right\} $$

where:

  • \(S \in R^{n}\), \(S\) is the search space.

  • \(t\) is the time.

  • \(f:S \times T \to R\), is the objective function that assigns a numerical value (\(f(x,t) \in R\)) to each possible solution (\(x \in S\)) at time \(t\).

  • \(F(t)\), is the set of feasible solutions \(x \in F(t) \subseteq S\) at time \(t\).

In other words, a \(\hbox{DOP}\) is a problem where the objective function or the restrictions change with time. The simplest method for solving these problems is ignoring dynamics, considering each change as the arrival of a new optimization problem and re-optimizing, but it is often impractical, as illustrated in Branke (2001). Therefore, the goal of the methods for dealing with \(\hbox{DOPs}\) is no longer to locate a stationary optimal solution, but to track its movement through the solution and time spaces as closely as possible. Classic algorithms have been adapted to cope with such dynamic scenarios enhancing their ability for tracking moving optima.

Since the first known reference to evolutionary algorithms (EAs) applied to dynamic optimization by Fogel et al. (1966), and the paper by Goldberg and Smith (1987) almost 20 years later, EAs have been the most common approach used to solve this kind of problems. Recently, other optimization techniques have been adapted to dynamic environments: particle swarm optimization, cooperative strategies (Pelta et al. 2009b), immune-based algorithms (Trojanowski and Wierzchon 2009), stochastic diffusion search (Meyer et al. 2006), ant colony optimization (Guntsch et al. 2001), and so on.

The topic of dynamic optimization was partly reviewed in the past. For example, it was covered in the books by Branke (2001), Weicker (2003), Morrison (2004), Yang et al. (2007a, b) and in the survey by Jin and Branke (2005). These works were mainly related to Evolutionary Optimization. Some special issues were devoted to the topic, considering other kind of methods, like Branke (2005), Branke and Jin (2006a, b), and Yang et al. (2006).

A reference websiteFootnote 1 on the application of evolutionary algorithms to DOP was maintained by Branke; other methods were later added, but the site seems to be inactive since 2007.

In our opinion, the research field is getting mature and it becomes necessary to stop and carefully look at what (and how) has been done in the past decade in order to avoid “re-inventing the wheel”, establish good research practices regarding for example proper evaluations of methods, and detect opportunities to go beyond “artificial” problems to real-world applications.

We claim that this work can be considered as a step towards these goals and we focus on two specific aims: (1) to provide an overview of the related works on dynamic optimization problems on the last decade; (2) to present a new repository about this topic that goes beyond a simple collection of bibliographic entries, providing an organized and “curated” view of the field.

The contribution is organized as follows: Sect. 2 describes the web repository and the process to classify the references of the papers collected. Section 3 describes the most used dynamic optimization problems. Section 4 describes the methods used to tackle DOPs. Then, Sect. 5 explains the measures and tests that have been used to assess the performance of a single method or to analyze and compare the results of several different methods. Finally, in Sect. 6 a brief summary and some suggestions for future research are provided.

2 Bibliography search and repository details

The first step in constructing the review was to define what to search, where the search should be conducted and how the search should be defined (search terms).

The search was conducted using the engines described in Table  1, using terms like “dynamic optimization”, “optimization AND uncertain environments”, “dynamic scenarios”, “metaheuristics AND dynamic optimization”, “metaheuristics AND time varying”, etc. First, just journal articles were considered, but as the number of results was small, we decided to extend the search to consider book chapters (from books published by prestigious publishing companies) and conference papers (from respected conferences). All the process was done during the last semester of 2009. It is important to notice that some of the search engines provide results considering also “In press” or “Online First” articles, so the publication year appearing in the website may not match the “physical” publication.

Table 1 Search engines where the bibliography was collected
Full size table

Then, a carefully hand-made categorization along several dimensions was performed for each selected reference. The categories were type of publication, dynamism, methods, models, performance measures, and applications. Their meaning and potential values for each category are described below:

  • type of publication: book, book chapter, journal article, conference paper, thesis, etc.

  • type of dynamism: where the dynamism is present in the problem formulation (objective function, and/or restrictions).

  • \(methods\): evolutionary algorithms, ant colony optimization, cooperative strategies, etc.

  • performance measures: which measures were used to evaluate the algorithms.

  • \(applications\): which problem is solved by the proposed method.

  • publication year.

The repository has filters that allow searching information using the above advanced classification with an appropriate search form. Data such as title, authors, abstract, keywords, etc., and links to the paper are also shown. Besides, the site have a section dedicated to additional Resources and Links where relevant information is being included, like other researchers, software, problems, congresses, and competitions. Figure 1 shows the number of publications collected and the number of visits in the past 15 months. Most of the visits came from Europe and that is also the reason for the noticeable decrease in August 2009, which is summer holidays time in most European universities.

Fig. 1
figure 1

Number of contributions available in the repository (top) and number of visits from April, 2009 to March, 2010 (bottom)

Full size image

We should also remark that the repository has a wider scope, including also information about “uncertainty”. Although one may argue that dynamism represents a type of uncertainty, the meaning here is more related with imprecision or noise that can be managed with probabilities, fuzzy sets, and systems techniques, etc. This analysis is out of the scope of this review.

3 Dynamic optimization problems

The review performed allows to confirm that most of the research done up to this date on \(\hbox{DOPs}\) is based on synthetic or test problems, where the degree of dynamism and the complexity of the objective function is controllable. Table 2 shows a summary of the main problems in dynamic optimization and their references.

Table 2 Dynamic optimization problems (\(\hbox{DOPs}\)) and corresponding references
Full size table

Many of these synthetic problems can be understood as \(\hbox{DOPs}\) generators that, departing from a predefined fitness landscape, allow to control the severity, the correlation or the type of the changes as well as to use different function types in some cases.

From the search results, it can be observed that one of the most widely used synthetic problems nowadays is still the Moving Peaks Benchmark (MPB) (Branke 1999). The idea is to have an artificial multi-dimensional landscape consisting of several peaks, where the height, width, and position of each peak is altered slightly every time a change in the environment occurs.

As many of the artificial problem generators rely on pretty similar ideas, we include here a complete description.

The cost function for \(n\) dimensions and \(m\) peaks has the following form:

$$ F(\mathop x\limits^ \to ,t) = \mathop{\max}\limits_{i = 1,\ldots, m} \frac{{H_i (t)}}{{1 + W_i (t)\sum\nolimits_{j = 1}^n {(x_j - X_{ij}(t))^2 } }} $$

where \(\mathop x\limits^ \to \in \Re^{n}\) is a particular solution, \(\overrightarrow{X} \in \Re^{m \times n}\) is the set of \(m\) peaks locations (we need \(n\) values for locating a peak) and \(\overrightarrow{H}, \overrightarrow{W} \in \Re^m\) are vectors storing the height and width of every peak. Figure 2 shows a scenario with \(n=1\) and \(m=5\).

Fig. 2
figure 2

An example of the error landscape created with the moving peaks benchmark

Full size image

The coordinates, the height \(H_i\) and the width \(W_i\) of each peak are randomly initialized. Then, at certain time steps, the height and width of every peak are changed by adding a random Gaussian variable multiplied by a specific “severity” factor (\(h_{\rm sev},w_{\rm sev}\), respectively). The location of every peak is moved by a vector \(\mathbf{v}\) of fixed length \(s\) in a random direction for \(\alpha = 0\) or a direction depending on the previous direction for \(\alpha > 0\). Thus \(\alpha\) is a correlation coefficient allowing to control whether the changes exhibit a trend or not.

More formally, given \(\sigma \in N(0,1)\) a change can be described as

$$ \begin{aligned} H_i (t) &= H_i (t - 1) + h_{\rm sev} \times \sigma \\ W_i (t) &= W_i (t - 1) + w_{\rm sev} \times \sigma \\ \mathbf{X}_i (t) &= \mathbf{X}_i (t) + \mathbf{v} \end{aligned} $$

The complexity of the problem can be augmented by increasing the number of dimensions or the number of peaks and by overlaying the whole landscape with a high-frequency noise.

Departing from this idea, a natural way for generating \(\hbox{DOPs}\) has been to introduce environment changes on a known stationary problem. In this sense, interesting benchmarks are obtained when the “peak” function from MPB is replaced by “cones” [as in the DF1 generator from Morrison and De Jong (1999) and Morrison (2004)] or more complex functions like Sphere, Griewank, Rastrigin, etc. that are typical test problems in continuous optimization. Dynamic versions of combinatorial problems also exist, like dynamic knapsack problem (Branke et al. 2006a, b; Dasgupta and Mcgregor 1992; Goldberg and Smith 1987; Rohlfshagen and Yao 2009a, b), moving parabola (Angeline 1997), dynamic bit-matching (Droste 2003; Stanhope and Daida 1999), or dynamic scheduling problems (Mattfeld and Bierwirth 2004).

The way the dynamism is included into a stationary problem is well exemplified in Yang (2003, 2005). The idea is to depart from a binary-encoded stationary function \(f(\mathbf{x})\) (\(\mathbf{x} \in \{0,1\}^l)\) and use a bitwise exclusive-or (\(\hbox{XOR}\)) operator in the fitness calculation. This technique was tested on One-Max problem and plateau, royal road, and deceptive functions.

Assuming that the environment changes every \(\tau\) generations, for each environmental period \(k\) the XOR-ing mask \(\mathbf{M}(k)\) is incrementally generated as follows:

$$ \mathbf{M}(k) = \mathbf{M}(k - 1) \oplus \mathbf{T}(k) $$

where \(\oplus\) is the bitwise exclusive-or (XOR) operator (i.e. \(1\oplus 1 = 0\), \(1 \oplus 0 = 1\), \(0 \oplus 0 = 0\)) and \(\mathbf{T}(k)\) is an intermediary binary template randomly created with \(\rho \times l\) ones for environmental period \(k\) (cyclic or cyclic with noise changes were also considered). For the first period \(k = 1\), \(\mathbf{M}(1)\) is set to a zero vector. Then, the population at generation \(t\) is evaluated with the formula

$$ f(\mathbf{x}, t) = f(\mathbf{x} \oplus \mathbf{M}(k)) $$

where \(k = \lceil t / \rho \rceil\) is the environmental period index. With the XOR generator defined in this way, the parameter \(\tau\) controls the speed of change while \(\rho \in (0.0, 1.0)\) controls the severity of environmental changes. Bigger values of \(\rho\) mean more severe environmental changes. The above procedure allows to change the fitness landscape while keeping certain properties of the original landscape, like the total number of optima and their values despite their locations are shifted.

Tinos and Yang (2007c) extend the XOR technique to real-valued optimization problems and applied it to a problem where the fitness function uses Sphere model and Generalized Griewank function. Also, Rohlfshagen et al. (2009a, b) using the XOR technique analyzed the effects of the magnitude and frequency of changes in a dynamic evolutionary optimization on a set of artificially designed pseudo-boolean functions.

Rohlfshagen and Yao (2009a, b) recently proposed a dynamic combinatorial optimization benchmark based on 0-1 knapsack problem instances that are generated using a small set of real-valued parameters. These parameters are varied over time by some set of differential equations so it is possible to model different types of transitions by controlling the shape and degree of interactions between the trajectories of the parameters.

Another interesting idea was proposed by Yin and Sendhoff (2004), where they suggest to construct dynamic optimization test problems using multi-objective optimization (MOO) concepts. A typical MOO problem consists on minimizing a set of objectives:

$$ \min_{x \in S} (f_1(x), f_2(x), \ldots , f_m(x)) $$

where \(x\) is a candidate solution, \(m\) is the number of objectives and \(S\) is the search space. One “simple” way to deal with multiobjective problems, is to aggregate the individual objectives as

$$ \hbox{min}\;F(x) = \sum_{i=1}^m w_i \times f_i(x) $$

where \(0 \leq w_i \leq 1, \; i=1,\ldots, m, \sum w_i = 1.\)

Using this idea, one can change the weights \(w_i\) dynamically to construct dynamic single objective and multi-objective test problems systematically.

Finally, Li and Yang (2008a) proposed the Generalized Dynamic Benchmark Generator. It was designed with the idea of constructing dynamic environments across binary, real, and combinatorial solution spaces. To do this the authors defined a DOP as

$$ F = f(x, \theta , t) $$

where \(F\) is the optimization problem, \(f\) is the cost function, \(x\) is a feasible solution in the solution set X, \(t\) is the real-world time, and \(\theta\) are the system control parameters, which determine the solution distribution in the fitness landscape. The search space is constructed from a composition of base functions and the dynamism is obtained by tuning the system control parameters. There are six change types of this system: small step change, large step change, random change, chaotic change, recurrent change, and recurrent change with noise. Thus, GDBG can present different dynamic properties using these change types. The authors also propose, for real coded landscapes, to rotate the landscape instead of shifting the positions of base functions. It should also be remarked that GDBG was used as a benchmark in CEC’2009 competition on dynamic optimization.

3.1 Real-world dynamic problems

Some interesting works about real-world problems showing dynamic environment behavior have started to appear in the very last years. The lower part of Table 2 shows a summary of the main “real world” problems in dynamic optimization and their references.

For example Mack et al. (2007) solve an aerospace design problem applying genetic algorithms (NSGA-II) and surrogate modeling. They tried the response surface-based multi-objective optimization of a radial turbine for an expander cycle-type liquid rocket engine. Three problems, a pollution control system, path planning of ships, and a car distribution system for “off-lease” cars, were solved by Michalewicz et al. (2007) using Adaptive Business Intelligence. Risk in financial optimization problems was studied by Tezuka et al. (2007) using a genetic algorithm.

There are also some works on dynamic vehicle routing problem made by different researchers (Hanshar and Ombuki-Berman 2002; Pankratz 2005) that could be applied to real-world problems modeled as instances of this problem. Rossi et al. (2008) worked on the pose problem where there is a need to know the pose of a moving object using evolutionary algorithms and Kalman filters. Dam et al. (2007) solved the task of performing evolutionary online data mining in a dynamic environment applying XCS, a genetics-based learning classifier system (GBLCS). Tumer and Agogino (2007) evolved evaluation functions for a multi rover system in a dynamic and noisy environment using evolutionary algorithms. Handa et al. (2007) optimized salting truck routes based on real-world data from the South Gloucestershire council in England, with dynamic optimization using a memetic algorithm that was able to achieve a \(10\%\) improvement over the available solutions in terms of the distances traveled by the trucks.

Neri and Mäkinen (2007) solved two structural optimization problems using evolutionary algorithms: the optimal design of a grounding grid and the optimal design of an elastic structure. Ling et al. (2007) studied the design of recording optics of varied-line-spacing holographic grating (VLSHG) in the National Synchrotron Radiation Laboratory by applying an standard crowding genetic algorithm. Quintão et al. (2007) controlled energy consumption and quality of service aspects on Wireless Sensor Networks applying Dijkstra Shortest Path and Prim Minimum Spanning Tree algorithms together with evolutionary algorithms, and mixed linear integer programming. More recently, Yang et al. (2010) tackled a dynamic shortest path routing problem on mobile ad hoc networks (MANETs) using genetic algorithms.

4 Methods for solving DOPs

As it was stated before, the goal of the methods for dealing with \(\hbox{DOP}\)s is no longer to locate a stationary optimal solution, but to track their progression through the space and time as closely as possible.

It is somehow obvious to think that this “tracking” would be better performed using a group of solutions/searchers than a single individual, and this idea is also reflected in the kind of methods that are being applied to deal with DOPs. The so-called population-based methods, like evolutionary algorithms or particle swarm optimization, showed themselves as clear alternatives for this domain.

The methods reviewed and categorized on the web repository are presented in Table 3. Observing the results, it is clear that the class of Evolutionary Techniques and their variants have been the most widely used methods to solve these DOPs. Nevertheless, other approaches are gaining more and more attention in the past years.

Table 3 Methods applied to dynamic optimization and references to papers where they are used
Full size table

If we look at the methods used as a whole, we can see that despite using quite different motivations there are several important frequently used components or mechanisms that can be considered as building blocks for the majority of dynamic optimization methods. These components are needed to properly adapt the classic methods to dynamic scenarios, tackling the diversity loss and outdated memory problems. According to classic categories by Blackwell and Branke (2006) these building blocks can be grouped as

Maintenance of diversity It is essential to keep certain level of diversity as it is expected that a diverse population can adapt more easily to changes than a fully converged one. Random Immigrants GA (RIGA) (Grefenstette 1992; Tinós and Yang 2007b; Yang 2008) is an example of this strategy. Every generation RIGA replaces part of the population by randomly generated individuals. This introduces new genetic material in every time step and avoids the convergence of the whole population to a narrow region of the search space.

For PSO this may be achieved by integrating a sort of repulsion. There are several techniques such as charged PSO (CPSO) (Blackwell 2003) based on mutually repelling particles that orbit chaotically a nucleus of neutral particles, quantum particles (Blackwell and Branke 2004) based on a quantum rather than classical picture of an atom, the replacement of global by local neighborhoods (Li 2004) or hierarchical neighborhood structures (Janson and Middendorf 2004).

For cooperative strategies, Pelta et al. (2009a, b) use the grid of solutions per-se as an implicit diversity mechanism. Because there are more solutions than agents, then it is like having a sort of backup of solutions that are not being manipulated by any agent. Such solutions may be helpful in the future to get closer to new optimums. Also, they implement a simple diversification mechanism in two stages: perturbation of a certain percentage of solutions and a random re-positioning of the agents.

A combination of ACO and Estimation of Distribution Algorithm is presented by Fernandes et al. (2008) where a new strategy is able to respond to a change. This method uses vectors that emulate ACOs pheromone maps and act as a kind of memory, allowing to incorporate information from prior distributions into their current parameters.

An important problem in the use of this technique is that the continuous focus on maintenance of diversity can slow down the optimization process.

React on changes The detection of changes is also a key component of most dynamic optimization methods. In general, this detection is performed reevaluating the best solution, the second best or using some solutions as “sentinels”. In any case, when a change in the environment occurs, the best fitness areas are probably others and the proper detection of such changes can allow to track the good solutions or to vary the intensification of the search giving more weight to other areas.

The way in which reaction to change is managed is well exemplified in the following works. For example, Cobb (1990) used hypermutation technique as an adaptive operator in GAs, keeping the whole population after a change but increasing population diversity by drastically increasing the mutation rate for some number of generations.

Abbass et al. (2004) introduced the extended compact genetic algorithm (ECGA) to solve problems in dynamic environments. Their approach is based on random restarts of the population at each change so that diversity in the population can be increased at the beginning of each new environment. Another way of improvement comes through parameter self-adjustment. Tinos and Yang (1823) used a evolutionary programming algorithm with self adaptation of the value of \(q\) parameter that controls the shape of a \(q\)-Gaussian mutation distribution. Parameter \(q\) is increased after environmental changes, which allows for a higher number of long jumps to help the population escape from the local optimum or to converge faster to the global optimum. On the contrary, the latest stages within the same environmental change showed that \(q\) reaches small values which improves the local search and intensification once a good search space location has been found.

Determining the useful amount of diversity is the main problem in these cases: too much diversity will resemble a restart and too little does not solve the convergency.

Use of Memory A natural way to enhance the strategies for DOPs is using memory schemes that work by storing useful information from the current scenario (either implicitly or explicitly) and reusing it at a later stage. Memory can help to preserve good solutions from the past that could be useful again at a later time, to reuse good solution components in newer solutions, to avoid visiting regions of the search space whose fitness is going down, and so on. The use of these techniques is only useful when periodic changes occur. In other words, when what is being observed now, can occur in the future.

An implicit memory scheme, for example, is an algorithm that uses representations containing more information than necessary and basically has some memory where good (partial) solutions may be stored and reused later as necessary. An explicit memory scheme is an algorithm that uses an extra storage space with explicit rules for storing and retrieving information.

Interesting surveys about memory-based evolutionary algorithms approaches for dynamic optimization problems appear in Branke (1999, 2001). Authors suggested the use of explicit memory through a memory population and search population. The memory population is responsible for remembering good solutions, maintaining a minimum quality and initiating jumps. The search population searches for new good solutions and submit these to the memory, but will not retrieve any information from it, and it is re-initialized at random after every change in the environment.

Karaman et al. (2005) propose a memory indexing evolutionary algorithm (MIA) that uses concepts originating from explicit memory-based dynamic evolutionary algorithms, the hyper-mutation mechanism and estimation of distribution approaches. MIA uses a distribution array (DA) that can be seen as a form of an external memory, where DA is a list of ratios representing the frequency of each allele at each gene position in the population.

Richter and Yang (2009) implemented an abstract memory scheme where the abstraction of good solutions is preserved in the memory to improve future problem solving. Abstraction means to select, evaluate, and code information before storing. In this case they use their approximate location in the search space to deduce a probabilistic model for the spatial distribution of good solutions.

Yang et al. (2010) applied a combination of a genetic algorithm with immigrants and an explicit memory scheme to solve Dynamic Shortest Path Routing Problems in wireless Mobile Ad Hoc Networks. They show how the immigrants improve the results in acyclic dynamic environments while the memory schemes outperform other techniques in cyclic environments.

Yang (2006a) presented an associative memory scheme for genetic algorithms where the environmental information is stored and associated with the current best individual of the population, and when the environment changes this information is used to create new individuals.

Pelta et al. (2009b) using cooperative strategies presented a dynamic fuzzy rule that made use of a history of previously seen costs to decide on the quality of solutions leading a successful optimization strategy. The definition of the fuzzy set is static but the domain where it is defined changes over time.

Multiple populations Employing several populations has been one of the most successful strategies to enhance the diversity in dynamic environments.

In EAs, a multi-population algorithm named self organizing scouts (SOS) presented by Branke et al. (2000) showed excellent results in some dynamic test problems. Multi-objective GAs have also been proposed for solving single objective functions. Also Bui et al. (2005b) apply multiobjective GAs for solving single-objective functions to dynamic optimization and test it on the moving peaks benchmark. Mendes and Mohais (2005) experimented with a multi-population approach of differential evolution (DE). Moser and Hendtlass (2007) used a multi-individual version of extremal optimization (EO) applied to the moving peaks benchmark.

For the case of PSO, multi-population means many swarms. In that sense, Parrot and Li (2004) created a speciation-based PSO (SPSO), which dynamically adjust the number and the sizes of swarms through an ordered list of particles. SPSO was tested with good results in the benchmark defined by Morrison and De Jong (1999). Blackwell and Branke inspired by multipopulation EA approaches developed a multiswarm PSO (Blackwell and Branke 2004, 2006) with additional diversity mechanisms. The approaches were evaluated on the moving peaks benchmark showing that they performed well over a wide range of problem characteristics. Li and Yan (2008b) presented a fast multi-swarm algorithm (FMSO) where a parent swarm keeps exploring the entire search space using a global search operator, while many child swarms are dynamically created around the best solutions found by this parent swarm. In the experimental studies conducted for FMSO, the authors observed a greater robustness of this algorithm than that of several instances of MPB. Novoa et al. (2009) also used a multi-swarm PSO algorithm but adding an operator for controlling particle failures (CPF) and tested it on the moving peaks benchmark obtaining very good results.

4.1 Problems and methods

After reviewing problems and methods, it is interesting to analyze the relation between these two aspects. Table 6 shows a matrix where each row is a problem and each column a method. As stated before, genetic algorithms are clearly the most frequent approach while the moving peaks is the usual benchmark (many methods were already used to deal with it).

The most interesting aspect to observe is that the table is sparse, thus indicating that much work could be potentially done using current methods on different problems. This is specially noticeable on “real world” applications where there is a one-to-one relation in most of the cases. However, this situation poses additional challenges that are going to be discussed later.

5 Comparison and analysis of results for DOPs

When solving an optimization problem, there is always a need to assess the quality of solutions (or populations of solutions). This is useful to compare different solutions or to rank different algorithms or different versions of the same algorithm according to their performance. The use of appropriate measures, metrics, and statistical tests is an important part for the usefulness and meaning of this process. It is also a key point for being able to assess the quality of research results and to allow for a comparison of new research data with previously published results.

Therefore, it is important to discuss what measures and metrics have been used for DOPs and which ones are more appropriate for the former purposes.

5.1 Measures and metrics for assessing the results

Regarding what to measure or how to compare the performance of a set of algorithms over \(\hbox{DOPs}\), the review performed indicates that there is no unified criteria. This is illustrated in Table 4 where a summary of the most used measures is presented. These measures range from totally method/problem-specific to some more generic proposals.

Table 4 Measures for dynamic optimization and references to the papers where they are used
Full size table

In a static context when solving a problem instance it is often enough to just report the best solution achieved by a method at the end of its execution. In some cases the costs in terms of memory/time are also considered, but no other factors are normally taken into account. But when we move to DOPs, reporting this simple values is not enough because we are normally interested not only in the solution quality at single points of time but also in many other aspects. These aspects include how well the methods are able to detect the problem changes and move to new better areas of the search space as they appear or how well they can track the existing good solutions as they move through the search space. It may be possible, for instance, that an algorithm is able to find the optimal solution at a given problem state (change) but it is totally lost for the rest of the execution. If we used a simple value like the best solution found, that algorithm may be ranked higher than another algorithm that keeps obtaining near-optimal solutions through all the optimization process and all the problem changes. On the contrary, the user will probably prefer this second algorithm over the occasionally optimal one. These concerns and the complexity of these tasks make the evaluation of the performance of methods in DOPs a research area per se and many different desirable goals and measures have been proposed to evaluate DOP optimization methods.

The usual approach taken in many contributions is depicted in Fig. 3. In a single run (top of the figure), the evolution of the error (calculated with respect to a known optimum) or the best solution found against evaluations (or time) looks like the one depicted in the plot. The small circles represents the “cost” (error or best) of the best solution found before the new change arrived. These costs are collected and some aggregation of the values is performed, typically the mean or median.

Fig. 3
figure 3

Basic schemes for calculating the performance of an algorithm in a dynamic environment. Circles represents the fitness of the best solution found before the new change arrived

Full size image

Usually, several runs are performed, so such values are further averaged as shown in Fig. 3 (bottom)

Many of the typical measures like current best and current average (Weicker 2002), Collective Mean Fitness (Morrison 2003), Off-line performance and offline error (Branke and Schmeck 2003), and Mean Fitness Error (Richter and Yang 2009) are based on similar ideas.

A step beyond was proposed by Weicker (2002) who presented an in-depth analysis on this topic, mainly focusing on EAs for dynamic environments; he considered the evaluation of three characteristics in a dynamic optimization process:

  • Accuracy: The optimization accuracy at time \(t\) is defined as

    $$ \hbox{accuracy}^t=\frac{\hbox{{best}}^t - \hbox{{Min}}^t}{\hbox{Max}^t - \hbox{Min}^t} $$

    where \(\hbox{bes}t^{t}\) is the fitness of the best candidate solution in the population at time \(t\), \({\hbox{Max}^t \in \mathbb{R}}\) is the best fitness value in the search space and \({\hbox{Min}^t \in \mathbb{R}}\) is the worst fitness value in the search space.

  • Stability: In the context of dynamic optimization, an adaptive algorithm is called stable if changes in the environment do not affect the optimization accuracy severely. Even in the case of drastic changes an algorithm should be able to limit the respective fitness drop. The stability of an optimization algorithm at time \(t\) is defined as

    $$ \hbox{stability}^t=\hbox{max}\left\{ 0,\hbox{accuracy}^t - \hbox{accuracy}^{(t-1)}\right\} $$

  • The stability cannot be relied as the only criterion to compare two algorithms since it makes no statement on the accuracy level. It can be seen as a consistency index of how reliably the algorithm keeps getting good results through the whole optimization process.

  • Reactivity: An additional aspect that can be considered as a goal in a dynamic optimization process is the ability of an adaptive algorithm to react quickly to changes. The \(\varepsilon\)-reactivity of an algorithm at time \(t\) is

    $$ \begin{aligned} \hbox{react}_{\varepsilon}^{(t)} &= \hbox{min}\left\{ (t'- t)\ \left \vert \ \frac{\hbox{accuracy}^{t'}}{\hbox{accuracy}^t} \right. \geq(1-\varepsilon)\right\} \\ &\quad \cup \ \{\hbox{maxgen}-t\} \end{aligned} $$

    where \({t, t'\in\mathbb{N}}\) and \(t<t'\leq \hbox{maxgen}\), with \(\hbox{maxgen}\) referring to the number of generations in generation-based algorithms such as evolutionary algorithms. Lower values for the reactivity mean a better and faster reaction to changes.

While these proposals were mainly oriented to evaluate EAs, they are usually applicable to any other type of algorithm, or they are easily modifiable to be adapted to other algorithms. In this way, the best of the population could be a single algorithm solution if the algorithm does not use populations, or the generations can be substituted by other progression steps like the number of problem changes or fitness function evaluations.

Despite the insights that the analysis of the last two characteristics may provide, most authors have focused only on accuracy measures, not considering at all the stability or the reactivity. The accuracy is always a useful value but if the overall best fitness is not known the accuracy cannot be computed. Since the best fitness value changes there is no common basis for assessment of the quality of a solution, because a good fitness value at one time may be bad at another. Therefore, there is a need for alternative performance/quality measures so a different knowledge is required such as the position of the optimum (usually only available in academic benchmarks), the knowledge of the best fitness values or even no global knowledge at all.

5.2 Statistical tests

Given a set of algorithms and their corresponding performance values, there is a need to assess which is the “best” alternative. From the pioneer works of Hooker (1995) or Golden and Stewart (1985) until recent papers (García et al. 2009; Rardin and Uzsoy 2001) the use of statistical tests are advocated as a way of introducing validation into empirical investigations of algorithms.

When dealing with static problems, proper statistical validations is nowadays a sine qua non condition for further consideration of the work.

In dynamic optimization papers, the situation is similar to the one observed in the early days of optimization with metaheuristics. After analyzing the papers in the repository, we find that many works make a comparison of results using only mean and standard deviation values while others resort to parametric tests (like Student’s t-test) without assessing if the set of performance values follows a normal distribution. It should also be remarked that several authors are starting to consider non-parametric statistical test in order to confirm if the observed differences in performance can be obtained by chance. Table 5 provides a small showcase of papers and the test they have applied to compare the algorithms.

Table 5 Tests for dynamic optimization and references to the papers where they are used
Full size table
Table 6 Dynamic optimization problems (\(\hbox{DOPs}\)) and methods cross-references to the papers where they are used
Full size table

In our opinion, if one wants to compare the behavior of a set of algorithms over a dynamic optimization problem, and the performance obtained by a single algorithm in an individual run is resumed as a single value denoting its performance, then the comparison should be performed using non-parametric statistical testing. Of course, parametric tests can also be applied whenever the conditions for their application are verified first. See, for example, Sheskin (2004) for a general discussion on testing. In the context of dynamic optimization as understood here, we can suggest to follow the guidelines and indications provided in (García et al. 2009), where the authors discuss how to made single-problem analysis and multiple-problem analysis in the context of evolutionary algorithms for real parameter optimization.

6 Summary and suggestions for future research

This paper presents an overview of the related works on dynamic optimization problems emphasizing what has been done in the past decade. A large number of papers were first collected from several search engines and then carefully analyzed and categorized. The result is now available at http://www.dynamic-optimization.org where the information can be explored through several dimensions. Three points of view were mainly considered: methods, measures, and problems.

Regarding the methods analyzed, the use of population-based techniques represents the most usual approach. From an almost exclusive use of evolutionary algorithms in the beginning, there is now an increasing interest in other optimization techniques such as particle swarm optimization, ant colony optimization, cooperative strategies, immune based algorithms, etc. It is clear that, besides more or less appealing names, the way to go are self-adaptive systems that can “sense” the environment and react properly, doing some self-tuning or even reconfiguring (changing components) by themselves. As stated in Plexousakis (2006) regarding software intensive systems:

The challenge is to develop algorithms, methods, tools, and theoretical foundations that enable effective design of adaptive systems which harness and control properties that emerge through the interaction of systems and their environment.

Regarding the problems, it is clear that many synthetic test problems and \(\hbox{DOPs}\) generators are available but what is not clear at all is what features of “real world” these generators should model. In this sense, it is interesting to note that most of the research is done considering dynamism in the objective function. We are not aware of other works considering time varying restrictions, or dimensionality changes that may perfectly represent real world problem features.

We should also highlight that there is a clear drawback with the reproducibility of published experiments and results as the concept of “problem instance” is not as clear as in the static optimization case. The “dynamic” part is lost from the definition of the problem instance and, being true that the type of change is perfectly defined in artificial problems, this fact would be critical in other scenarios.

For example, in the so-called “real-world” problems, the main open question is if one wishes to apply a new algorithm to such problem, what information about it should be provided? In other words, how the dynamism of the problem should be represented? For example, if we consider a dynamic vehicle routing problem with time windows, where the customers can be added or deleted dynamically from the schedule, we will have both a hard problem to solve and no simple way to share such information about timing. This could be an interesting line of research.

In terms of the measures and tests, we observed that most of the used measures need a precise knowledge of the problem at hand, and they reduce a whole dynamic run to a single value. The use of proper statistical testing to compare different results/algorithms, instead of simple comparisons based on reported means and standard deviations, should be promoted. In particular, non-parametric tests should be applied whenever the conditions for the application of their parametric versions do not hold. The literature on the topic is wide and there is no reason for not using them.

In our opinion, there is a need for new measures that take into account what happens “during” the run. In this sense, perhaps the field of time series theory may provide some ideas. At the end, we will want to observe and be able to compare temporal patterns (or averages of them).

After this review, we consider that the following aspects should deserve further consideration:

  • On problems:

    • Consider other types of dynamism, like dimensionality change.

    • Further explore multi-objective dynamic optimization.

  • On methods:

    • Explore self-adaptive algorithms as well as other successful population-based algorithms like scatter search, that could also perform well on DOPs.

    • The assumption that trajectory methods will not work well for DOPs should be reconsidered. The results on González et al. (2010) where several trajectory solvers are coupled with a cooperative strategy suggest that these methods could greatly outperform evolutionary like algorithms on some cases. This approach combined with some sort of cooperation could possibly lead to very good results on some DOPs.

    • Suggest the authors to provide their algorithms source code or executables for checking and reproducibility purposes as it is done in other areas, like bioinformatics.

  • On analyzing performance:

    • Define a computational experimentation protocol.

    • Development of new measures beyond “single valued” ones.

    • Promote the use of non-parametric testing.

Moreover, it will be very interesting to have a broader experimentation done on the different issues described on this paper (methods, problems, measures, tests, and so on) as well as the interactions between them. This could start to provide insights into how to select a good algorithm for a given DOP or which measures to use for a given problem with respect to its severity of change, if the optimum is known or not, the shape of the search landscape or any other problem characteristics. A good understanding of the interactions between all these issues will surely be helpful for tackling more complex real-world problems and to focus the research into the most promising topics while reducing the efforts on the less promising ones.

To conclude, we would like to recognize that this review has been a hard task. Any review process is also a filtering process, so we would like to apologize to the readers and researchers for any possible omissions. We will be happy to receive their feedback in order to improve the resources available in our web repository. If this study motivates students and researchers to use and investigate on these problems, then the aim of the paper will be fulfilled.