1 Introduction

Most real-world engineering, economic and information technology problems change over time (i.e. experience uncertain and dynamic changes). The interest in improving the performance of EAs in dynamic environments continues to increase so as to identify promising techniques capable of addressing more complex DOPs. Many studies (such as Nelson et al. (2009) and Gongora et al. (2009) and many more) have demonstrated that the standard EA is good at finding the optimum of complex multi-modal functions when the promising region of the search space remains stationary during an optimization process. However, when solving DOPs, the standard EA is not suitable because the algorithm is expected to not only find the optimum, but also track the optimum with respect to time. In fact, realistic applications are more likely to experience uncertain or dynamic changes, in the sense that one or more of the problem specifications (i.e. the target function, constraints and parameters) may vary over time. In such environment, optimization algorithms are not only required to optimize the problem in its actual state, but also adapt to the new optima whenever an environmental change is detected and then to continuously track the moving optima throughout the whole optimization process.

In EAs, diversity in the population is useful for adapting in a changing environment, since members of the population represent potential solutions that can be applied to different environmental circumstances (Branke et al. 2000; Yang 2008). Standard EAs have been successful in solving optimization problem in static environments, e.g. Deb et al. (2002), Juang (2004) and Passow et al. (2008), but when confronted with DOPs the algorithms performance is limited (see Yang and Tinós (2007)). Also the standard EAs employ a strong selection policy based on feedback which gradually reduces diversity during an optimization process (Cobb and Grefenstette 1993). In typical applications, the function representing the environment remains static so that the algorithm is mainly limited to finding a solution. If the environment changes, the performance of the standard EA is not guaranteed as it is unable to redirect its region of concentration in the search space (Grefenstette et al. 1992).

Recently, Uzor et al. (2014a) investigated a compact genetic algorithm (cGA) for DOPs known as adaptive-mutation cGA (amcGA). They introduced a mechanism whereby the mutation rates are directly linked to the detected rate of change (i.e degree of change determines the probability of mutation). In Uzor et al. (2014b), the amcGA was evaluated using a real-world dynamic optimization control problem with some preliminary results. In this paper, variants of the amcGA are presented and further investigated to improve the algorithms adaptability in a dynamic environment. These variants are denoted as amcGA1 (Uzor et al. 2014a), amcGA2, amcGA3, amcGA4 and amcGA5. In amcGA2 and amcGA3, a scaled mutation rate (based on the degree of change) is used to regulate the amount a mutation operation alters the probability vector within the algorithm. The amcGA4 and amcGA5 make use of change patterns exhibited by the current working probability vector to mutate the probability vector held in memory so as to boost the algorithms response to dynamic change.

The rest of this paper is organized as follows; Sect. 2 reviews existing EAs for dynamic environments, Sect. 3 introduces a background knowledge of the cGA and details the amcGA as well as its variants, and Sect. 4 describes the set-up scene for all experiments and performance analysis. Finally, Sect. 5 concludes this paper with discussions on future direction.

2 EAs for DOPs

In real-world applications, certain problems arise which can be a search or optimization problem (e.g. Higuchi et al. (1999) and Bektas (2006)). These problems normally require the consideration of multiple performance criteria and non-proportional control variables. Optimization problems can be found everywhere in science, technology and even daily life activities, e.g. planning (Bui et al. 2012), tuning of controllers (Pedersen and Yang 2006) and many more. For more than 20 years, static optimization has been an active area of research. However, the inclusion of time dependency by Goldberg and Smith (1987) created a distinct degree of difficulty. Most real-world optimization problems are often influenced by uncertain and dynamic factors (Jin and Branke 2005), and it is unlikely that a solution found for a particular problem would remain valid for a long period of time. In order to counter these dynamic and uncertain factors, an adaptive mechanism is required to introduce changes to the current solution. These types of optimization problems can be referred to as a dynamic optimization problem.

The nature of DOPs presents challenges to traditional optimization algorithm because these problems usually require the tracking of the changing environment with respect to time. In general, addressing DOPs using EAs can be grouped into four categories:

  • Using implicitly or explicitly defined memory to store and reuse useful information so as to adapt the EA whenever a change occurs (Goldberg and Smith 1987; Dasgupta and McGregor 1993, 1992; Yang and Yao 2008).

  • Creating a multi-population to distribute the search force in the search space (Branke et al. 2000; Zhu et al. 2006).

  • Promote diversity by inserting random immigrants back in the population (Grefenstette et al. 1992; Yu et al. 2008) and

  • Adjusting genetic operators adaptively (Morrison and De Jong 2000; Eiben et al. 2006).

Apart from the approaches mentioned above, for an EA to function properly the genetic operators need to be tuned/defined properly as it affects performance and is problem dependent. This can be achieved in three ways: (1) Deterministic method, which involves adjusting the value of the strategy parameter using a deterministic rule which is fixed. (2) Adaptive method, which makes use of feedback from the optimization process to determine when to change the strategy parameter, which can be in form of an IF–THEN rule and may involve a credit assignment which defines the quality of the solution discovered. (3) Self-adaptive method, where the mechanism for updating the strategy parameter is implicitly defined (see Eiben et al. (1999) and Eiben and Smit (2012)).

When solving DOPs, evolutionary algorithms are considered a good choice because they are inspired from the principles of biological evolution, which takes place in a dynamic environment (Goldberg 1989). But when using classic EAs, once converged, they are unable to adapt to changes in a dynamic environment. In DOPs, values of the optima change with time, thus rendering the problem of optimum finding to optimum tracking. This means that the fitness landscape of a given problem is dynamic with possibly both the search space and fitness being time dependent. In Yang and Tinos (2008), a hyperselection scheme in dynamic environment was proposed for a genetic algorithm (GA) to address DOPs, where the selection pressure is increased whenever an environment change occurs. In standard GAs, individuals in the population converge to an optimal solution in static environments due to selection pressure, but in dynamic environments, converging to an optimum becomes a problem for the standard GAs since it does not encourage genetic diversity and hence makes it hard to adapt to a new environment whenever a change occurs. Although the scheme discussed in Yang and Tinos (2008) demonstrated the effects of selection pressure for GAs in dynamic environment, adjusting the selection pressure adaptively during an optimization/search process still remains an open question. A forward-looking approach for solving dynamic multi-objective optimization problems using EA was proposed in Hatzakis and Wallace (2006). They implemented a forecasting method where the location in variable space of the optimal solution is estimated. The optimization algorithm exploits past information and prepares for the change before it arrives instead of reacting to the change.

In Yang (2008), a memory and elitism-based immigrants approach for GAs in dynamic environment were presented. The best individual during an optimization process is stored in memory (or elite from previous generation) and is retrieved as a base to create new individuals by mutation so as to ensure diversity and also adapt to a new environment. In general, certain techniques are suitable for certain environments. Memory-based approaches are suitable for periodic optima. Self-adaptation and mutation approaches are suitable for landscapes with fast changes. Multi-population approaches are suitable for competing peaks and maintaining diversity is suitable for continuously moving peaks (Woldesenbet and Yen 2009).

Although these algorithms have been successful in tackling DOPs, none of the authors have considered linking change severity with a diversity scheme such that the degree of change is directly proportional to the diversity scheme. Numerous dynamic techniques have been proposed to tackle dynamic problems effectively (Nguyen et al. 2012). However, the complex structure of some the existing dynamic optimization algorithms makes them unsuitable for solving real-time DOPs on-board embedded hardware system with limited memory. Therefore, a compact dynamic approach is investigated in this paper.

3 cGA for DOPs

There are some optimization problems that limit the application of traditional optimization algorithm due to hardware limitations. This is as a result of the complex structure employed by population-based approach (which makes them computationally expensive). In order to overcome hardware limitations, a compact algorithm is required. The compact genetic algorithm (cGA) offers the advantage of being computationally efficient (i.e requires less memory and execution time) (see Harik et al. (1999) and Mininno et al. (2008)).

The compact genetic algorithm as proposed by Harik et al. (1999) is an estimation of distribution algorithm (EDA) (Larraanaga and Lozano 2001; Pelikan et al. 2000) that generates offspring population according to an estimated probability model of the parent population. The cGA makes use of a real-valued probability vector \(\overrightarrow{P}\) to represent the bit probability of 0 or 1 which models the distribution of the population:

$$\begin{aligned} \overrightarrow{P} = \{P_{1},\ldots ,P_{l}\} \end{aligned}$$
(1)

where l is the binary-encoding or chromosome length and \(P{i} \in \{0, 1\}\), \((i = 1,\ldots ,l)\). The probability vector is initially assigned 0.5 to represent a randomly generated population. In every generation, competing solutions are generated based on the current probability vector and the probabilities \(P_{i}\) are updated to favour a better solution. In a simulated population of size s, the probability of each gene increases or decreases by \(\frac{1}{s}\) based on the gene of the best solution, i.e.

figure a

The cGA maintains a probability vector and evolves it towards the best sample solution created from it. The driving force for cGA to solve an optimization problem lies in the update mechanism of the probability vector towards the best sample created from it iteratively. The probability vector of the cGA usually converges to either 0.0 or 1.0 in each element which will produce the optimal solution when sampled in static environments. The performance of the cGA in a dynamic environment is not guaranteed since once the probability vector converges it is unable to adapt to the changed environment (Ahn and Ramakrishna 2003). As a result, modifications to the original algorithm have been proposed so as to enable it to tackle DOPs.

To address the convergence problem, several approaches have been developed to reintroduce diversity after a change occurs, e.g. the restart scheme which resets the optimization algorithm back to the default setting when a change occurs (Harik et al. 2006; Sastry et al. 2005), the hypermutation scheme (Cobb 1990; Morrison and De Jong 2000) where the probability of mutation is raised from a low mutation rate to a high mutation rate when the environment changes and many more. The hypermutation creates an adaptive EA with small incremental memory and computational cost, but requires the mutation factor to be picked a priori.

Although these algorithms have been successful in tackling DOPs, to the best of the authors knowledge none has considered an adaptive method for controlling the mutation factor and none has tried to link together the mutation scheme with a change severity scheme (i.e. measuring the degree of change) such that the degree of change is directly proportional to the mutation factor. This section describes the amcGA as well as variants.

3.1 Change detection

A Gaussian function is employed to detect and determine the degree of change \(C_{\mathrm{d}}\) in the environment:

$$\begin{aligned} C_{\mathrm{d}}= & {} \hbox {e}^{-a}\end{aligned}$$
(3)
$$\begin{aligned} a= & {} \frac{(\Delta f - c)^2}{2\sigma ^2} \end{aligned}$$
(4)

where c is the mean (and is set to 1.0), \(\sigma \) represents standard deviation of the change detection and \(\Delta f\) is the change in fitness or fitness difference between the elite solution at generation t and same elite solution re-evaluated at generation \(t+1\):

$$\begin{aligned} \Delta f = f(E_{\mathrm{s}},t) - f(E_{\mathrm{s}}, t+1) \end{aligned}$$
(5)

It is important to note that change in fitness of the elite solution is considered in this study as a sign of change in the environment (i.e. the algorithm monitors the performance of the elite solution). The algorithm employs the elitism approach, where the best solution from a previous generation is transferred and evaluated in subsequent generations. In order to adaptively control the mutation rate (i.e. probability of mutation) \(p_{\mathrm{m}}\), \(C_{\mathrm{d}}\) is converted to the mutation rate such that a high degree of change results in a high mutation rate and a low degree of change results in a low mutation rate, but when no change occurs, the algorithm proceeds as a normal cGA. The probability of mutation \(p_{\mathrm{m}}\) is defined as follows:

$$\begin{aligned} p_{\mathrm{m}} = m_{\mathrm{l}} + (C_{\mathrm{d}} - d_{\mathrm{l}})\times \left( \frac{m_{\mathrm{h}} - m_{\mathrm{l}}}{d_{\mathrm{h}} - d_{\mathrm{l}}}\right) ,\quad p_{\mathrm{m}} \in [0.01, 0.5] \nonumber \\ \end{aligned}$$
(6)

where \(m_{\mathrm{l}} = 0.01\) is low probability of mutation, \(m_{\mathrm{h}} = 0.5\) is high probability of mutation, \(d_{\mathrm{l}} = 0.0\) is low degree of change and \(d_{\mathrm{h}} = 1.0\) is high degree of change.

3.2 Mutation schemes

Unlike the mutation scheme adopted by most cGA variants where mutation is applied directly to candidate solutions to create another solution for selection, the mutation scheme discussed in this paper is applied directly to the probability vector that generated the best solution (i.e. elite) since the probability vector represents a distribution of the population.

Suppose at generation t an elite solution \(E_{\mathrm{s}}\) with fitness \(f(E_{\mathrm{s}},t)\) was obtained, the probability vector that generated the solution is held in a temporary memory \(\overrightarrow{mP}\) . At generation \(t+1\), the elite solution is re-evaluated and a new fitness value is obtained, i.e. \(f(E_{\mathrm{s}},t+1)\). If the fitness difference \(\Delta f\) is greater than a defined threshold (e.g. \(\Delta f\>{0}\)), then a change is said to have occurred which triggers the mutation scheme, which is applied directly to \(\overrightarrow{mP}\) to generate a mutated version of the elite solution \(E_{\mathrm{m}}\) to compete with \(E_{\mathrm{s}}\).

The cGA makes use of a real-valued probability which generates two solutions when sampled. In order to apply the mutation scheme to the probability vector, a random number \(r = \hbox {rand}(0.0, 1.0)\) is generated and then compared with \(p_{\mathrm{m}}\) and \(\overrightarrow{mP}\) is mutated as follows:

amcGA1

figure b

amcGA2

figure c

amcGA3

figure d

The diversity techniques by Vavak et al. (1996) differ in that it makes use of a variable local search around the locations in the search space which are represented by chromosomes before a change occurs. It is triggered when the time-average best performance of the population falls below a defined threshold. When triggered, all mutation and crossover operations are suspended.

However, the amcGA detects and measures the degree of change whenever there is a drop in the fitness of an elite solution. Then, the probability of mutation is directly linked to the measured degree of change. The amcGA has been design to be suitable for systems and applications with limited computational resources and time constraints. This is because the amcGA maintains the small footprint of the cGA without a significant increase in memory requirements, unlike the algorithm presented by Vavak et al. (1996), which is not efficient in such systems and applications.

Sometimes, changes in dynamic environments may exhibit some trends (or pattern). In such case, it might be beneficial to try to use these change trends to improve the algorithms response to subsequent changes in such dynamic environment. Some studies have been made following this idea by exploiting the predictability of dynamic environments (e.g. Simões and Costa (2009b, (2009a)).

Memory approaches (Branke 1999; Yu and Suganthan 2009), which were originally proposed to deal with periodical changes, can also be considered as a type of prediction method. Algorithms following the prediction approach make use of memory scheme to cope with various types of changes (e.g. cyclic, noisy and random), but require the use of accurate training data and dedicated memory allocation, which makes the respective algorithm computationally expensive.

In this study, the change trend \(T_{\mathrm{chg}}\) is used to boost the amcGAs performance whenever a change occurs by applying the change trend to \(\overrightarrow{mP}\) such that \(\overrightarrow{mP}\) learns from past dynamic changes and adapts to future dynamic changes instead of explicitly using stored training data. The change trend \(T_{\mathrm{chg}}\) is defined as follows:

$$\begin{aligned} {\overrightarrow{T_{\mathrm{chg}}}} = {\overrightarrow{{mP}_{t}}} - {\overrightarrow{P}_{t+1}} \end{aligned}$$
(10)

where \(\overrightarrow{P}_{t+1}\) is the current working probability vector at generation \(t+1\). The amcGA4 and amcGA5 make use of the change trend approach described above and are defined as follows:

amcGA4

figure e

amcGA5

figure f

where \(s = \left( n - \frac{p_{\mathrm{m}}}{2}\right) \) and l is the binary string length. It is important to state that the change trend scheme was applied to amcGA2 and amcGA3 (which yields amcGA5 and amcGA4, respectively) to study the effect of \(T_{\mathrm{chg}}\) on the performance of the algorithm. This way, the mutation strategy updates itself based on the change pattern exhibited by the probability vector. Also \(T_{\mathrm{chg}}\) controls the amount a mutation operation alters the value of each element in \(\overrightarrow{mP}\).

After the mutation operation, a mutated version of the elite solution \(E_{\mathrm{m}}\) is generated using the mutated temporary probability vector (i.e. \(\overrightarrow{mP^{'}}\)) to compete with the current elite solution \(E_{\mathrm{s}}\). If the mutated elite solution performs better than the current elite, it replaces the elite solution and the mutated probability vector replaces the current probability vector. The mutation scheme is repeated for a defined number of generations similar to the hypermutation scheme. After the mutation operation, the algorithm continues as a standard cGA unless another change occurs.

The adaptive mutation scheme presented in this section is somewhat similar to the well-established covariance matrix adaptation evolution strategy (CMA-ES) (Hansen and Ostermeier 2001, 1996; Hansen and Kern 2004), which is a de facto standard in continuous domain evolutionary optimization (in static environments). Both algorithms share same idea of storing information about a candidate solution which is used to update/bias the solution sampling process. However, in the CMA-ES evolution cycle, after the evaluation and ranking of the solutions, their relative steps are used to update the parameters of the sampling distribution. This process is repeated through out the evolution cycle until a termination criterion is met. On the other, the amcGA only updates \(\overrightarrow{mP}\) when an elite is discovered and samples a mutated elite from it when a dynamic change occurs. This sampling and update process is only repeated for a defined number of iterations. Also, the amcGA is developed for combinatorial optimization problems and the embedded adaptive mutation scheme can be considered as an improved form of the popular hypermutation scheme.

4 Experiments

4.1 Dynamic benchmark generator

For the experiments, the DOP generator proposed in Yang and Yao (2005) which constructs a dynamic environment was chosen to test the efficiency of the amcGA variants. The generator can construct a DOP from any binary-encoded static function \(f(\overrightarrow{x})\). Given a static optimization problem f(x) (\(x \in \{0,1\}^l\)) where l is the binary string length, the dynamic environment is generated by applying a binary XORing mask \(\overrightarrow{M}\) to each solution before evaluating at every \(\tau \) generations.

$$\begin{aligned} f(x, t) = f(x \oplus {\overrightarrow{M}}(k)) \end{aligned}$$
(13)

where f(x, t) is the fitness of solution x, \(k = t/\tau \) is the period index at time t, \(\oplus \) is a bitwise exclusive-or (XOR) operator which is applied to the x and M(k) according to the following principle:

figure g

For each environment k, \(\overrightarrow{M}(k)\) is incrementally generated as follows:

$$\begin{aligned} {\overrightarrow{M}} (k) = {\overrightarrow{M}} (k - 1) \oplus {\overrightarrow{T}} (k) \end{aligned}$$
(15)

where \(\overrightarrow{T}(k)\) is an intermediate binary template generated for environment k. \(\overrightarrow{T}(k)\) is generated with \(\rho \) x l (\(\rho \in (0.0, 1.0]\)) random loci set to 1 while the remaining loci set to 0. \(\rho \) controls the intensity or severity of change. If \(\rho \) is set to 0, the environment is considered stationary since \(\overrightarrow{T}\) will contain only 0s and no change will occur. On the other hand, \(p = 1\) guarantees a high degree of change (i.e. high change severity). Also a small \(\tau \) means faster environment change while a large \(\tau \) means slow environment change.

4.2 Dynamic test problem

The dynamic test problems used in the experiments are presented in this section. Three 100-bit binary-encoded problems are selected as stationary functions and are described below:

4.2.1 Decomposable unitation-based functions (DUFs)

The decomposable unitation-based functions have been used as benchmark functions by the EA community in an attempt to understand what constructs difficult optimization problems for EAs (Goldberg 2002). These type of functions return the number of ones in a binary string (i.e. unitation function of binary string). Two decomposable unitation-based functions denoted as DUF1 and DUF2 are used as static functions to construct dynamic test environments, in order to compare the performance of algorithms discussed in this paper.

The DUF1 is simply a Onemax function which aims to maximize the number of \(1's\) in a binary string. The fitness of a binary string is the number of \(1's\) contained in the string.

$$\begin{aligned} f_{\mathrm{DUF}1}(x) = u(x) \end{aligned}$$
(16)

where u(x) is number of \(1's\) in a building block.

DUF2 is a fully deceptive function (Goldberg 2002), which is considered hard problems for EAs because the low-order building blocks inside the functions do not combine to form the higher-order optimal building block. Instead, they combine to form deceptive suboptimal building block (Whitley 1991). This property makes it much more difficultly for EAs to solve DUF2 than DUF1.

figure h

Using the dynamic benchmark generator discussed in Sect. 4.1, dynamic test environments are constructed from the DUFs and are referred to as dynamic DUFs (i.e. denoted as DDUF1 and DDUF2). The DDUFs consists of 25 copies of 4-bit building blocks. Each building block of the two DDUFs contributes a maximum value of 4 to the total fitness. The fitness of a bit string is the sum of contributions from all building blocks which gives an optimal fitness of 100 (for DDUF1 and DDUF2).

4.2.2 Dynamic knapsack problem

The knapsack problem is a classic NP-complete combinatorial optimization problem that has been rigorously studied by the EA community in the last few decades (Branke et al. 2006; Wang et al. 2009; Rohlfshagen and Yao 2009). The main aim of this problem is to fill a knapsack with the best subset of items among a larger set to maximize the value of contents in the knapsack without exceeding the knapsack capacity. This benchmark problem has been studied in both static (e.g. Shah and Reed (2011), Martins et al. (2014)) and dynamic environments (e.g. Yang et al. (2013) with different modifications. The dynamic property of the knapsack problem is achieved when the problem parameters (such as item weight, value and sack capacity) are time dependent and subject to variation.

Given n items, each of which has a weight \(w_{i}(t)\) and a value \(v_{i}(t)\) and a knapsack of capacity C. The main goal of the knapsack problem is to load the items that guarantees maximum value without exceeding the knapsack capacity C. A dynamic test environment is constructed for the knapsack problem and is denoted as DKP. Mathematically DKP can be described as follows:

$$\begin{aligned} \hbox {Maximize}\,f_{\mathrm{DKP}}(x,t) = \sum \limits _{i=1}^{n} p_{i}(t)x_{i}(t) \end{aligned}$$
(18)
figure i

where \(x_{i}\) is the binary decision variable used to indicate if item i is included or discarded. In this study, all values and weights are positive, also all weights are less than the knapsack capacity \(C = 500\). A knapsack problem with 100 items using randomly generated data was constructed as follows:

$$\begin{aligned} w_{i}= & {} {\hbox {uniformly random integer}}{[2,20]} \end{aligned}$$
(20)
$$\begin{aligned} p_{i}= & {} {\hbox {uniformly random integer}}{[1,30]} \end{aligned}$$
(21)

The sum of the profits of the selected items is used as the fitness of a candidate solution if the sum of item weight is within the knapsack capacity. However, if a candidate solution selects too many items such that the summed weight exceeds the knapsack capacity, then a penalty function is used to judge how much the candidate solution exceeds the knapsack capacity. The penalty function is defined as follows:

figure j

where \(l_{f} = 7 \times \left( \sum \limits _{i=1}^{n} w_{i}x_{i} - C\right) \) and \(n = 100\).

These dynamic test problems have been chosen to evaluate the performance of the amcGA in different dynamic scenarios. Specifically the DDUFs and DKP are academic combinatorial problems suitable for evaluating dynamic (binary-encoded) optimization algorithms. The DDUFs has an increasing difficulty for the amcGA in the order from DDUF1 to DDUF2. This is due to the deceptive property inherent in DDUF2 which makes it a difficult problem for dynamic EAs (Whitley 1991; Goldberg 2002). The DKP is another difficult problem, because the profit and weight of each item selected change over time based on the XOR mask (i.e. \(\overrightarrow{M}\)) in Eq. 13.

4.3 Parameter settings and performance measures

Experiments were carried out on the selected DOPs to investigate the effect of the change detection, change trend and mutation schemes on the performance of the amcGA. An additional experiment was carried out to compare the performance of the schemes presented in Sect. 3 with a probability-based incremental learning algorithm with hypermutation (denoted as PBILm) (Yang and Richter 2009) and a cGA with hypermutation (denoted as cGAm). The hypermutation scheme embedded in cGAm generates a mutated version of an elite solution for tournament selection whenever a dynamic change occurs. The elite solution is replaced if it is outperformed by the mutated elite. This way the \(\overrightarrow{P}\) in cGAm is only updated by the elite solution.

For all algorithms, some common parameters were set as follows; the population size \(n = 100\), speed of change \(\tau = 20, 60\) and 100, and change ratio \(\rho = 0.1, 0.2, 0.5\) and 1.0. While the sensitivity level for detecting change \(\Delta f \>\) 0 for the scheme described in Sect. 3, probability of mutation (for the PBILm) \(p_{\mathrm{m}} = 0.05\) with mutation shift \(\delta = 0.05\). Also all algorithms use the elitism approach (in the case of the PBIL an elite of size 1 was used). For the PBILm, the probability of mutation was set to a base level \(p_{\mathrm{m}}^l\) = 0.05 for normal generations and a high value \(p_{\mathrm{m}}^h = 0.3\) for interim generations when the hypermutation scheme is triggered due to change in environment and this lasts for five generations, i.e. \(g_{hm} = 5\). Three kinds of dynamic environments were constructed (i.e. cyclic, cyclic with noise and random) using the dynamic problem generator discussed in Sect. 4.1.

For each experiment using all algorithms on the DOP, 30 independent runs were executed and for each run 20 environmental changes were allowed, which are equivalent to 400, 1200 and 2000 generations for \(\tau = 20, 60\) and 100, respectively. Best-of-generation fitness was recorded every generation, and the overall offline performance of all algorithms on each DOP is defined as:

$$\begin{aligned} {{\overline{F}}}_{{\mathrm{BOG}}} = \frac{1}{G} \sum \limits _{i = 1}^{G} \frac{1}{N} \sum \limits _{j= 1}^{N} F_{\mathrm{BOG}_{ij}} \end{aligned}$$
(23)

where \(F_{\mathrm{BOG}_{ij}}\) expresses the fitness value of the best solution at generation i of run j, \(G = 20 \times \tau \) is the total number of generation for a run, \(N = 30\) is the total number of runs and \({\overline{F}}_{\mathrm{BOG}}\) is the overall offline performance, which is the best-of-generation fitness averaged over N and then over the data gathering period.

Experimental results of all algorithms on the selected DOPs based on \({\overline{F}}_{BOG}\) are presented in Figs. 1, 2, 3 and 4, respectively. The corresponding statistical tests are shown in Tables 1 and 2, where Kruskal–Wallis tests were applied followed by pairwise comparisons using Wilcoxon rank-sum tests with the Bonferroni correction. In Tables 1 and 2, the result regarding Alg. 1–Alg. 2 is shown as “\(+\)”, “−” and “\(\sim \)” when Alg. 1 is significantly better than, significantly worse than or statistically equivalent to Alg. 2. The dynamic performance of all algorithms regarding the best-of-generation fitness against generations on the dynamic problems is plotted in Figs. 1, 2 and 3 (with \(\tau = 60\) and \(\rho = 0.2\)).

From Figs. 1, 2, 3 and 4, Tables 1, 2, 3, several behaviours can be observed and are discussed in next section from two aspects: (1) regarding performance based on \({\overline{F}}_{\mathrm{BOG}}\) and (2) algorithms behaviour on the selected DOPs (i.e. the effect of environmental dynamics on algorithms performance).

Fig. 1
figure 1

Dynamic behaviour of all algorithms on DDUF1 with \(\tau = 60\) and \(\rho = 0.2\) in different dynamic environment, i.e. a cyclic, b cyclic with noise and c random environments

Full size image
Fig. 2
figure 2

Dynamic behaviour of all algorithms on DDUF2 with \(\tau = 60\) and \(\rho = 0.2\) in different dynamic environment, i.e. a cyclic, b cyclic with noise and c random environments

Full size image
Fig. 3
figure 3

Dynamic behaviour of all algorithms on DKP with \(\tau = 60\) and \(\rho = 0.2\) in different dynamic environment, i.e. a cyclic, b cyclic with noise and c random environments

Full size image
Fig. 4
figure 4

Experimental results of all algorithms on DOPs in different dynamic environments (i.e. cyclic, cyclic with noise and random) with \(\tau = 60\)

Full size image

4.4 Experimental study regarding overall performance

First, PBILm shows a constant performance across all DOPs regardless of the dynamics of the environment. This is because the PBILm evaluates 100 candidate solutions (every generation) and has a greater chance of finding better solutions than the cGAm and amcGAs which only evaluates two candidate solutions every generation. With the increasing \(\tau \), PBILm has more time to search for solutions with higher fitness before the next change. However, in some environment change ratio \(\rho \), PBILm was outperformed by the amcGA (variants) as can be observed from Fig. 4 and Table 1. This is due to the lack of information transfer from the last environment of the last dynamic change. Also, PBILm applies the mutation scheme to the current working \(\overrightarrow{P}\) which has no information of the previous environment and this means the PBILm is focused more on preventing premature convergence of \(\overrightarrow{P}\). The performance of the PBILm was expected to be better than that of the amcGA and cGAm. Due to its algorithmic structure, the PBILm generates series of solutions (population) every generation until a solution with better fitness is discovered. Therefore, it is important to state that this comparison was carried out in order to see which of the competing algorithm was less behind the PBILm in terms of the overall performance (see Table 3).

Second, cGAm outperforms some of the amcGA variants in some of the DOPs (see Fig. 1b, c). This is due to the fact that whenever a change occurs, the cGAm tries to find a better solution for the current environment (i.e. which is the effect of rapid increase in probability of mutation \(p_{\mathrm{m}}\)), but does not ensure diversity as can be seen in Fig. 1a. Also for some dynamic settings, cGAm shows similar performance to some of the amcGA variants (see Figs. 1c, 2a). It must be noted that the cGAm and amcGAs are modified variants of the cGA suitable for solving DOPs.

Third, among the five variants of the amcGA, amcGA1 and amcGA3 exhibit better performance (see Table 2). From Figs. 1, 2 and 3, it can be observed that amcGA3 performs better than amcGA1. This is as a result of how the mutation scheme within both algorithms alters \(\overrightarrow{mP}\). The amcGA3 mutation scheme either increase or decrease \(\overrightarrow{mP}\) at a reduced scale (see Eq. 9), while amcGA1 is a randomized mutation based on the current values of elements of \(\overrightarrow{mP}\) and the degree of change \(C_{\mathrm{d}}\) [see Eq. (7)]. Also, amcGA3 shows stable performance across different environment dynamics. Performance of all amcGA variants based on \({\overline{F}}_{\mathrm{BOG}}\) is shown on Figs. 1, 2 and 3 for different environment dynamics. Although figures show general performance of all algorithms, it is difficult to draw out conclusions about the final result of the compared algorithms by just visual inspection of the performance curves. Using the Kruskal–Wallis tests followed by pairwise comparisons using Wilcoxon rank-sum tests with the Bonferroni correction, several results can be observed. On several environment dynamics, the performance of the amcGA1 and amcGA3 is better than that of the cGAm (see Tables 1 and 2). Also when the \(\rho \) is low and \(\tau \) is low to medium, most of the amcGA variants outperformed the cGAm (and the PBILm in some environment dynamics). This behaviour is as a result of how the amcGA handles its probability vector.

Table 1 Statistical results regarding the offline performance of the amcGA variants against other algorithms
Full size table

The amcGA3 maintains a moderate convergence rate as it explores the search space (see Figs. 1b, c, 3a). The amcGA not only carries information from one stage of the problem to the next stage, but also retains these information in the form of \(\overrightarrow{mP}\), which represents properties and dynamics of a particular environment. Also since the mutation scheme is only applied to \(\overrightarrow{mP}\), it ensure that the current working \(\overrightarrow{P}\) maintains its diversity unless a solution generated by the mutated \(\overrightarrow{mP}\) (whenever a change is detected) outperforms the current best solution generated by \(\overrightarrow{P}\), thereby replacing \(\overrightarrow{P}\) with \(\overrightarrow{mP}\). This can be considered as an advantage over the hypermutation scheme. The \(\overrightarrow{P}\) in cGAm is mainly updated based on the solutions sampled from it. This implies that genetic diversity is encouraged at individual level since the mutation scheme is applied directly to a candidate solution to create another for selection.

Table 2 Statistical results regarding the offline performance of the amcGA variants
Full size table

Finally, performance of the amcGA4 and amcGA5 in the cyclic environment is better than (or same as) that of the cGAm on some of the DOPs, i.e. cyclic DDUF1 and DKP (with respective environment dynamics). This behaviour is as a result of the change trend scheme within the algorithm. Although this scheme does not make use of any external training data, it has a positive effect on the performance of the amcGA4 and amcGA5. The change trend scheme ensures that the amcGA retains information about past environment (i.e. \(\overrightarrow{mP}\)) while searching for promising region (using \(\overrightarrow{P}\)) in the search space of a new environment. This can be observed when \(\tau = 100\) and \(\rho \) is between 0.1 and 0.5 (see Table 1) and the algorithms are given more time to search before the next environmental change, but experience slow convergence rate. On the other hand, convergence deprives cGAm of the adaptability to changing environments because the \(\overrightarrow{P}\) within cGAm learns from the best hypermutated solution whenever a change occurs. However, the mutation mechanism and change trend scheme embedded in amcGA4 and amcGA5 grants more diversity than cGAm (and PBILm in some environment) and hence better adaptability to environmental changes (see Fig. 3a, b). The change trend scheme within amcGA4 and amcGA5 makes use of change patterns exhibited by the current working probability vector (i.e. \(\overrightarrow{P}\)) to mutate/alter \(\overrightarrow{mP}\). This way, both amcGA4 and amcGA5 respond to dynamic changes based on how often new elites are obtained. One limitation of the amcGA4 and amcGA5 is the lack of an explicitly defined memory allocation to store change trends such that various change patterns can be reused. This means the performance of the amcGA4 and amcGA5 is problem dependent. In addition, the structure of the amcGA4 and amcGA5 permits their application to DOPs with limited computational resources specifically limited in the amount of available memory.

4.5 Experimental analysis of algorithms behaviour on selected DOPs

In order to better understand the experimental results, we need to look deeper into the dynamic behaviour of all algorithms. The dynamic behaviour all different algorithms on the selected DOPs is shown in Fig. 4, where the data were averaged over 30 runs, \(\tau \) is set to 60, \(\rho = 0.1, 0.2, 0.5\) and 1.0. Several behaviours can be observed when examining the effect of the dynamic environments on the performance of the algorithms investigated.

From Fig. 4, it can be observed that for a fixed \(\tau \) with increasing value of \(\rho \), PBILm outperforms other algorithms on several cases and maintains almost the same performance across the three DOPs. The behaviour is a result of the high adaptability brought in by the hypermutation scheme (and population-based structure) within PBILm. However, the performance of PBILm decreases on the cyclic DDUF2 and random DDUF2. This is due to the fact that, when the environment changes, the deceptive building blocks inside DDUF2 will draw the population into the new environment slowly. This means the deceptive attractors are not globally optimal, but they are suboptimal with relatively high fitness.

Table 3 Overall offline fitness difference of the cGAm and amcGAs against the PBILm when \(\tau = 60\) and \(\rho = 0.1,0.2,0.5\) and 1. The table shows how far off the performance of the cGAm and amcGAs is from the PBILm
Full size table

An interesting behaviour is that on DDUF1, the performance of the amcGA variants drops when \(\rho \) is between 0.1 and 0.5, but soon stabilizes. This is because when \(\rho = 1.0\), the environment switches between two landscapes and the algorithm may wait during one environment for the return of the other environment to which they converged well. Also, among the amcGA variants, the amcGA3 shows better performance in DDUF1. The reason lies in the way the mutation scheme operates within amcGA; it ensures that the amcGA3 adapts to the changing environment regardless of the change severity. Also, the mutation scheme only increases (or decreases) \(\overrightarrow{mP}\) by \((n - \frac{p_{\mathrm{m}}}{2})\) which is determined by a random number r unlike the mutation scheme in PBILm which is determined by the probabilities in \(\overrightarrow{P}\).

In Fig. 4, it can be observed that on the cyclic DDUF2 (with and without noise), all amcGA variants show low performance when \(\rho = 0.1\) to 0.5, but exhibit rapid increase in performance when \(\rho =1.0\). This is due to the deceptive nature of DDUF2, since low-order building block inside the function does not clearly lead to a high-order building block and the amcGAs seems to be sensitive to low \(\rho \). However, all amcGA variants cope well with high \(\rho \) (i.e. when \(\rho = 1.0\)) because the environment switches between two states which in turn gives more time for the algorithm to obtain a better solution suitable for the environment before the next change occurs.

Looking at DKP (bottom) of Fig. 4, it can be observed that for all dynamic environments, the performance of all variants of the amcGA reduces as \(\rho \) increases. This can be considered normal, since an increase in \(\rho \) implies more severe environment changes. When the cyclic nature of the dynamic environment increases from cyclic to cyclic with noise, the performance of all amcGA variants (and cGAm) increases slightly. Despite the fact that a cyclic environment with noise is relatively more difficult than a cyclic environment, the amcGA variants showed better performance. But in the random environment, the performance of some of the amcGA variants dropped (i.e. when \(\rho = 0.5\) and 1.0). This implies that even though the existence of noise in a cyclic environment may over weigh randomness (i.e. in terms of difficulty), it favours the performance of all amcGA variants.

Finally, from Figs. 1, 2, 3 and 4, it can be observed that the amcGA variants (i.e. amcGA to amcGA5) performed better on the DDUF2 problem, especially when \(\tau \) is large (see Table 1). This implies that the performance of the amcGA not only depends on the dynamics of the environment but also on the DOP being considered. Generally speaking, the experimental results indicate the amcGA variants can be considered when solving DOPs with deceptive properties. These are functions in which low-order building block does not combine to form higher-order building block. Instead, low-order building block may mislead an optimization algorithm towards local optima (Whitley 1991; Fernandes et al. 2009).

5 Conclusion and future work

Mutation is a double-edged sword; it ensures diversity and improves an algorithm’s ability to respond to changes in a dynamic environment. However, mutation can reduce the performance of an optimization algorithm if the mutation rate is too high and not controlled appropriately. The effect of change trend and different mutation schemes on the performance of the amcGA in dynamic environments was studied in this paper. From experimental results, several conclusions can be drawn on the overall performance of the algorithms:

First, the mutation schemes have a positive effect on the performance of the amcGA in dynamic environments as it ensures that information about an environment is retained and reused whenever the environment changes (instead of using a dedicated memory space and/or training data).

Second, on all but a very small niche of the DOPs with extreme environmental change, the proposed amcGA algorithms were statistically significantly outperformed by the PBILm. On several cases, the change in environment had minimal effect on the performance of the amcGA variants while the algorithms try to find a suitable solution. Also, the interaction between the change trend and mutation depends on the DOP (see Fig. 4; Tables 1, 2, 3).

Third, the addition of a change trend scheme to the amcGA improves the algorithms performance in dynamic environments. The change trend scheme ensures that the amcGA responds to dynamic changes based on the change pattern exhibited by the current working probability. Also, it allows the algorithm to update its mutation strategy using the change pattern. However, the effect may not be as strong as the effect of the hypermutation on the performance of the PBILm.

Finally, the mutation scheme embedded within all amcGA variants promotes diversity in dynamic environments, i.e. it ensures that the population maintains its diversity while tackling the DOP and gradually moves towards the optimal solution.

In general, this paper investigated the effects of the change trend and adaptive mutation schemes for the amcGA in dynamic environments. Based on results obtained, there are several future works relevant to this paper:

All amcGA variants are relatively easy to implement, especially in memory-constrained application since all variants of the amcGA retain the small footprint of the cGA. This allows direct implementation on memory-constrained devices, thus overcoming the limitations related to typical population-based dynamic optimization algorithms (e.g. PBILm).

The results obtained may be used to guide the design of compact dynamic optimization algorithms for tackling DOPs and compare the algorithms obtained with the amcGA variants as well as other EAs for DOPs. Further research will focus on using the schemes developed in this paper to solve real-world DOPs (implemented in memory-constrained applications and embedded hardware) which include further experimentations to identify possible limitations of the algorithms.