7.2.1 Multi‐Population Methods with a Fixed Number of Populations

The main idea of these methods is to divide the task of optimization among a number of fixed‐size populations. One way to do this is by establishing a mutual repulsion among a predefined number of sub‐populations to place them over different promising areas of the search space. The representative work in this category is that of Blackwell and Branke [37]. They proposed two multi‐swarm algorithms based on the particle swarm optimization (PSO), namely mCPSO and mQSO. In mCPSO, each swarm is composed of neutral and charged particles. Neutral particles update their velocity and position according to the principles of pure PSO. On the other hand, charged particles move in the same way as neutral particles, but they are also mutually repelled from other charged particles residing in their own swarm. Therefore, charged particles help to maintain the diversity inside the swarm. In mQSO, instead of having charged particles, each swarm contains quantum particles. Quantum particles change their positions around the center of the best particle of the swarm according to a random uniform distribution with radius r_cloud . Consequently, they never converge and provide a suitable level of diversity to swarm in order to follow the shifting optimum. The authors also introduced the exclusion operator, which prevents populations from settling on the same peak. In another work [23], the same authors proposed a second operator referred to as anti‐convergence, which is triggered after all swarms converge and reinitializes the worst swarm in the search space. After the introduction of mQSO, a lot of work has been done to enhance its performance by modifying various aspects of its behavior.

A group of studies analyzed the effect of changing the number and the distribution of quantum particles on the performance of mQSO. For instance, Trojanowski [38] proposed a new class of limited area distribution for quantum particles in which the uniformly distributed candidate solutions within a hyper‐sphere with radius r_cloud are wrapped using von Neumann's acceptance‐rejection method. In another work [39], the same author introduced a two‐phased method for generating the cloud of quantum particles in the entire area of the search space based on a direction vector θ and the distance d from the original position using an α‐stable random distribution. This approach allows particles to be distributed equally in all directions. The findings of both studies revealed that changing the distribution of quantum particles has a significant effect on the performance of mQSO. del Amo et al. [40] investigated the effect of changing the number of quantum and neutral particles on the performance of mQSO. The three major conclusions of their study can be summarized as follows: (i) an equal number of quantum and neutral particles is not the best configuration for mQSO, (ii) configurations in which the number of neutral particles is higher than the number of quantum particles usually perform better, and (iii) quantum particles are most helpful immediately after a change in the environment.

Some researchers borrowed the general idea of mQSO and developed it using other ECs. The main purpose of these approaches is to benefit from intrinsic positive characteristics of other algorithms to reach a better performance than the mQSO. For instance, Mendes and Mohais [41] introduced a multi‐population differential evolution (DE) algorithm, called DynDE. In DynDE several populations are initialized in the search space and explore multiple peaks in the environment incorporating exclusion. DynDE also includes a method for increasing diversity, which enables the partially converged population to track the shifting optimum.

One of the technical drawbacks of the exclusion operator in mQSO is that it ignores the situations when two populations stand on two distinct but extremely close optima (i.e. within the exclusion radius of each other). In these situations, the exclusion operator simply removes the worst population and leaves one of the peaks unpopulated. A group of studies tried to address this issue by adding an extra routine to the exclusion which is executed whenever a collision is detected between two populations. For example, Du Plessis and Engelbrecht [42] proposed re‐initialization midpoint check (RMC) to detect whether different peaks are located within the exclusion radius of each other. In RMC, once a collision occurs between two populations, the fitness of the midpoint on the line between the best individuals in each population is evaluated. If the fitness of the midpoint has a lower value than the fitness value of the best individuals of both populations, it implies that the two populations reside on distinct peaks and that neither should be reinitialized. Otherwise, the worst‐performing population will be reinitialized in the search space. Although RMC is effective, as pointed by the authors, it is unable to correctly detect all extremely close peaks. In another work, Xiao and Zuo [43] applied hill‐valley detection with three checkpoints to determine whether two colliding populations are located on different peaks. In their approach, three points between the best solutions of the collided populations x and y are examined. Thereafter, if there exists a point z = c · x + (1 − c) · y for which f(z) <  min {f(x), f(y)}, where cϵ{0.05, 0.5, 0.95}, then two populations are on different peaks and they remain unchanged. Otherwise, they are on the same peak.

Another interesting approach for improving the performance of mQSO is to spend more FEs around the most promising areas of the search space. In this regard, Novoa‐Hernández et al. [44] proposed a resource management mechanism, called swarm control mechanism, to enhance the performance of the mQSO. The swarm control mechanism is activated on the swarms with low diversity and bad fitness, and stops them from consuming FEs. In another work, Du Plessis and Engelbrecht [45] proposed an extension to the DynDE referred to as favored populations DE. In their approach, FEs between two successive changes in the environment are divided into three phases: (i) all populations are evolved according to normal DynDE for ζ1 generations in order to locate peaks, (ii) the weaker populations are frozen and stronger populations are executed for another ζ2 generations, and (iii) frozen populations are put back to the search process and all populations are evolved for ζ3 generations in a normal DynDE manner. This strategy adds three parameters ζ1, ζ2, and ζ3 to DynDE, which must be tuned manually.

The SPS, which is the subject of this chapter, falls under this category where the main objective is to distribute FEs among the sub‐populations so as to allocate the greatest amount of FEs to the most successful sub‐populations. Despite the progress achieved in the past, we believe that there is still room for improving this approach. Therefore, this chapter focuses on different ways to suitably assign FEs to each sub‐population using the SPS algorithm.

Different from the above studies, some researchers combined desirable features of various optimization algorithms into a single collaborative method for DOPs. In these methods, each population plays a different role and information can be shared between populations. For example, Lung and Dumitrescu [46] introduced a hybrid collaborative method called collaborative evolutionary‐swarm optimization (CESO). CESO has two equal‐size populations: a main population to maintain a set of local and global optimum during the search process using crowding‐based DE, and a PSO population acting as a local search operator around solutions provided by the first population. During the search process, information is transmitted between both populations via collaboration mechanisms. In another work [47] by the same authors, a third population is incorporated to CESO which acts as a memory to recall some promising information from past generations of the algorithm. Inspired by CESO, Kordestani et al. [48] proposed a bi‐population hybrid algorithm. The first population, called QUEST, is evolved by crowding‐based DE principles to locate the promising regions of the search space. The second population, called TARGET, uses PSO to exploit useful information in the vicinity of the best position found by the QUEST. When the search process of the TARGET population around the best‐found position of the QUEST becomes unproductive, the TARGET population is stopped and all genomes of the QUEST population are allowed to perform an extra operation using hill‐climbing local search. They also applied several mechanisms to conquer the existing challenges in the dynamic environments and to spend more FEs around the best‐found position in the search space.

7.2.2 Methods with a Variable Number of Populations

Another group of studies has investigated the multi‐population schemes with a variable number of sub‐populations. These methods can be further categorized into three groups based on how the sub‐populations are formed from a main population. They are methods with a parent population and variable number of child populations, methods based on population clustering, and methods based on space partitioning.

7.2.3 Methods with an Adaptive Number of Populations

The last group of studies includes methods that control the search progress of the algorithm and adapt the number of populations based on one or more feedback parameters.

The critical drawback of the multi‐swarm algorithm proposed in [23] is that the number of swarms should be defined before the optimization process. This is a clear limitation in real‐world problems where information about the environment might be not available. The very first attempt to adapt the number of populations in dynamic environments was made by [56]. He developed an adaptive mQSO (AmQSO) which adaptively determines the number of swarms either by spawning new swarms into the search space, or by destroying redundant swarms. In this algorithm, swarms are categorized into two groups: (i) free swarms, whose expansion, i.e. the maximum distance between any two particles in the swarm in all dimensions, is larger than a predefined radius r_conv, and (ii) converged swarms. Once the expansion of a free swarm becomes smaller than a radius r_conv, it is converted to the converged swarm. In AmQSO, when the number of free swarms (M_free) is dropped to zero, a free swarm is initialized in the search space for capturing undetected peaks. On the other hand, free swarms are removed from the search space if M_free is higher than a threshold n_excess .

Some researchers adapted the idea of AmQSO and used it in conjunction with other ECs. For instance, Yazdani et al. [57] proposed a dynamic modified multi‐population artificial fish swarm algorithm based on the general principles of AmQSO. In this approach, the authors modified the basic parameters, behaviors and general procedure of the standard artificial fish swarm algorithm to fulfill the requirements for optimization in dynamic environments.

Inspired by AmQSO, a modified cuckoo search algorithm was proposed by Fouladgar and Lotfi [58] for DOPs. Their approach uses a modified cuckoo search algorithm to increase the convergence rate of populations for finding the peaks, and exclusion to prevent populations from converging to the same areas of the search space.

Differing from the above algorithms, which use the expansion of the populations as a feedback parameter to adapt the number of populations, Du Plessis and Engelbrecht [59] proposed the dynamic population differential evolution (DynPopDE), in which the populations are adaptively spawned and removed, based on their performance. In this approach, when all of the current populations fail to improve their fitness, i.e. ∀k ∈ κ → Δf_k (t) = |f_k (t) − f_k (t − 1)| = 0 where κ is the set of current populations, DynPopDE produces a new population of random individuals in the search space.

DynPopDE starts with a single population and gradually adapts to an appropriate number of populations. On the other hand, when the number of populations surpasses the number of peaks in the landscape, redundant populations can be detected as those which are frequently reinitialized by the exclusion operator. Therefore, a population k will be removed from the search space when it is marked for restart due to exclusion, and it has not improved since its last FEs (Δf_k (t) ≠ 0).

Recently, Li et al. [60] proposed an adaptive multi‐population framework to identify the correct number of populations. Their framework has three major procedures: clustering, tracking, and adapting. Moreover, they have employed various components to further enhance the overall performance of the proposed approach, including a hibernation scheme, a peak hiding scheme, and two movement schemes for the best individuals. Their method was empirically shown to be effective in comparison with a set of algorithms.

7.4.1 Fixed Structure Learning Automaton

A fixed structure learning automaton (FSLA) is a quintuple 〈α, Φ, β, F, G〉 where:

• α = (α₁, ⋯, α_r) is the set of actions that it must choose from.
• Φ = (Φ₁, ⋯, Φ_s) is the set of states.
• β = {0, 1} is the set of inputs where 1 represents a penalty and 0 represents a reward.
• F : Φ × β → Φ is a map called the transition map. It defines the transition of the state of the automaton on receiving input, F may be stochastic.
• G : Φ → α is the output map and determines the action taken by the automaton if it is in state Φ_j .

A very well‐known example of FSLA is the two‐state automaton (L_{2, 2}). This automaton has two states, Φ₁ and Φ₂ and two actions α₁ and α₂. The automaton accepts input from a set of {0, 1} and switches its states upon encountering an input 1 (unfavorable response) and remains in the same state on receiving an input 0 (favorable response). An automaton that uses this strategy is referred as L_{2, 2}, where the first subscript refers to the number of states and the second subscript is the number of actions.

7.4.2 Variable Structure Learning Automaton

A variable structure learning automaton (VSLA) is represented by a quadruple 〈β, α, p, T〉, where β = {β₁, β₂, …, β_m } is the set of inputs, α = {α₁, α₂, …, α_r } is the set of actions, p = {p₁, p₂, …, p_r } is the probability vector which determines the selection probability of each action, and T is learning algorithm which is used to modify the action probability vector, i.e. p(n + 1) = T [α(n), β(n), p(n)]. Let α(n) and p(n) denote the action chosen at instant n and the action probability vector on which the chosen action is based, respectively. The recurrence equations shown by Eq. (7.4) and Eq. (7.5) is a linear learning algorithm by which the action probability vector p is updated as follows:

(7.4)

when the taken action is rewarded by the environment (i.e. β(n) = 0), and

(7.5)

when the taken action is penalized by the environment (i.e. β(n) = 1). In the above equations, r is the number of actions. Finally, a and b denote the reward and penalty parameters and determine the amount of increases and decreases of the action probabilities, respectively. If a = b, the recurrence Eqs. (7.4) and (7.5) are called a linear reward–penalty (L_R – P) algorithm, if a ≫̸ b the given equations are called linear reward–εpenalty (L_{R – εP} ), and finally if b = 0 they are called linear reward–inaction (L_R – I ). In the latter case, the action probability vectors remain unchanged when the taken action is penalized by the environment.

A learning automaton has been shown to perform well in parameter adjustment [64–66], networking [67], social networks [67], etc.

7.5.1 Round Robin SPS

The most common and simplest method for scheduling sub‐populations, which is currently used in majority of multi‐population methods, is using the round robin (RR) strategy. In this strategy, all sub‐populations are executed one by one in a circular queue (Figure 7.2). This way, FEs are equally distributed among the sub‐populations.

At each time, the sub‐population that should be executed is determined as follows:

(7.6)

where % is the modulo operation which returns the remainder after division of one number by another, and N is the number of sub‐populations.

7.5.2 Random SPS

The second SPS method is to execute the sub‐populations in a random manner. In this method, called random (RND) SPS, at each time, a sub‐population is chosen randomly according to the following equation:

(7.7)

where is the index of the sub‐population that should be executed at time t, and randi is a function that returns a random integer in the range 1 and N, and N is equal to the number of sub‐populations.

7.5.3 Pure‐Chance Two Action SPS

Another option for random SPS is choosing between executing the current sub‐population or executing the next sub‐population based on pure chance (PC). Let R be a random variable following the discrete uniform distribution over the set {current sub − population, next sub − population}. At each iteration, the algorithm randomly decides to execute the current sub‐population or the next sub‐population as follows:

(7.8)

where rand is a random number in [0, 1]. Again, N is the number of sub‐populations.

At the beginning of the optimization process, the current sub‐population is set to the first sub‐population.

7.5.4 SPS Based on Competitive Population Evaluation

As stated before, one way for scheduling the sub‐populations is based on receiving one or more feedback parameters from the search progress of the sub‐populations. The fourth SPS method, called competitive population evaluation (CPE) [42], uses the combination of the current fitness of the best individual in the sub‐populations and the amount that the error of the best individual was reduced during the previous evaluation of the sub‐populations as a feedback parameter for SPS. In this method, a performance measure is first calculated for all sub‐populations as follows:

(7.9)

In the above equation, N is the number of sub‐populations and is the improvement amount of the best individual during the previous evaluation of the sub‐population i, which is computed as:

(7.10)

is also calculated as follows:

(7.11)

Finally, the sub‐population to be executed is selected as follows:

(7.12)

Regarding Eq. (7.12), at each iteration, the best‐performing sub‐population takes the FEs and evolves itself until its performance drops below that of another sub‐population, where the other one takes the FEs, and this process continues during the run. Figure 7.3 summarizes the working mechanism of CPE.

7.5.5 SPS Based on Performance Index

Another way for adaptive SPS is taking other types of feedbacks into account. In [29], the authors combined the success rate and the quality of the best solution found by the sub‐populations in a single criterion called performance index (PI). The success rate (⊖) determines the portion of improvement in the individuals of a sub‐population which is defined as:

(7.13)

For function maximization, the PI ψ_i for each sub‐population i is computed as:

(7.14)

where is the success rate of the sub‐population i at time t. exp is a mathematical function which returns Euler's number e raised to the power of , and represents the fitness value of the best solution found by sub‐population i at time t.

For function minimization, one must convert the function minimization problem into a fitness maximization in which a fitness value is used. Here, is the maximum value of the fitness function, while is the fitness value of the best‐found position by sub‐population i.

The FEs at each stage are then allocated to the sub‐population with the highest PI, which is selected as follows:

(7.15)

It is easy to see that the best‐performing population will be the population with the highest fitness and success rate.

The pseudo code for the SPS based on the PI is shown in Figure 7.4.

7.5.6 SPS Based on VSLA

Another interesting approach for SPS is by using decision making tools like learning automata. One way to model the SPS using learning automata is by applying an N‐action VSLA, where its actions correspond to different sub‐populations, i.e. n₁, n₂, …, n_N [29]. In order to select the next sub‐population for execution, the learning automaton LA_{sub − pop} selects one of its actions, e.g. α_i, randomly based on its action probability vector. Then, depending on the selected action, the corresponding sub‐population is executed.

After execution of the selected sub‐population, the automaton LA_{sub − pop} updates its probability vector based on the reinforcement signal received in response to the selected action. Based on the received reinforcement signal, the automaton determines whether its action was a right or wrong, updating its probability vector accordingly. To monitor the overall progress of the SPS process, the reinforcement signal is generated as follows:

(7.16)

where f is the fitness function, and is the global best individual of the algorithm at time step t. According to Eq. (7.16), if the quality of the best‐found solution by the algorithm improves, then a favorable signal is received by the automaton LA_{sub − pop} . Afterwards, the probability vector of the LA_{sub − pop} is modified based on the learning algorithm of the automaton. The structure of the VLSA‐based SPS method is given in Figure 7.5.

7.5.7 SPS Based on FSLA

Apart from the above VSLA approach, one can model the SPS with FSLA. The seventh SPS algorithm is modeled by an FSLA with N states Φ = (Φ₁, Φ₂, …, Φ_N ), the action set α = (α₁, ⋯, α_N ), and the environment response β = {0, 1} which is related to reward and penalty. Figure 7.6 illustrates the state transition and action selection in the proposed model.

Initially, the automaton is in state i = 1. Therefore, the automaton selects action α₁ which is related to evolving the sub‐population n₁. Generally speaking, when the automaton is in state i = 1, …, N, it performs the corresponding action α_i which is executing the sub‐population n_i . Afterwards, the FSLA receives an input β according to Eq. (7.16). If β = 0, FSLA stays in the same state, otherwise it goes to the next state.

Qualitatively, the simple strategy used by FSLA‐based scheduling implies that the corresponding multi‐population EC algorithm continues to execute whatever sub‐population it was evolving earlier as long as the response is favorable but changes to another sub‐population as soon as the response is unfavorable. Figure 7.7 shows the different steps of the FSLA model for SPS.

7.5.8 SPS Based on STAR Automaton

Finally, the last SPS method is based on STAR with deterministic reward and deterministic penalty [68]. The automaton can be in any of N + 1 states Φ = (Φ₀, Φ₁, Φ₂, …, Φ_N ), the action set is α = (α₁, ⋯, α_N ), and the environment response is β = {0, 1}, which is related to reward and penalty. The state transition and action selection are illustrated in Figure 7.8.

When the automaton is in any state i = 1, …, N, it performs the corresponding action α_i which is related to evolving the sub‐population n_i . On the other hand, the state Φ₀ is called the “neutral” state: when in that state, the automaton chooses any of the N actions with equal probability .

Both reward and penalty cause deterministic state transitions, according to the following rules [68]:

1. When in state Φ₀ and chosen action is i (i = 1, …, N), if rewarded go to state Φ_i with probability 1. If punished, stay in state Φ₀ with probability 1.
2. When in state Φ_i, i ≠ 0 and chosen action is i (i = 1, …, N), if rewarded stay in state Φ_i with probability 1. If punished, go to state Φ₀ with probability 1.

With these in mind, the STAR‐based SPS can be described as follows. At the commencement of the run, the automaton is in state Φ₀. Therefore, the automaton chooses one of its actions, say α_r, randomly. The action chosen by the automaton is applied to the environment, by evolving the corresponding sub‐population r, which in turn emits a reinforcement signal β according to Eq. (7.16). The automaton moves to state Φ_r if it has been rewarded and it stays in state Φ₀ in the case of punishment. On the other hand, when in state Φ_i ≠ 0, the automaton chooses an action based on the current state it resides in. That is, action α_i is chosen by the automaton if it is in the state Φ_i ≠ 0.

Consequently, sub‐population i is evolved. Again, the environment responds to the automaton by generating a reinforcement signal according to Eq. (7.16). On the basis of received signal β, the state of the automaton is updated. If β = 0, STAR stays in the same state, otherwise it moves to Φ₀. The algorithm repeats this process until the terminating condition is satisfied. Figure 7.9 shows the details of the proposed scheduling method.

A summary of various SPS strategies is given in Table 7.1.

7.6.1 Differential Evolution

DE [69, 70] is a well‐known EC paradigm which is one of the most powerful stochastic real‐parameter optimization algorithms. Over the past decade, DE has gained much popularity because of its simplicity, effectiveness, and robustness.

The main idea of DE is to use spatial difference among the population of vectors to guide the search process toward the optimum solution. The rest of this section describes the main operational stages of DE in detail.

7.6.1.1 Initialization of Vectors

DE starts with a population of NP randomly generated vectors in a D‐dimensional search space. Each vector i, also known as genome or chromosome, is a potential solution to an optimization problem which is represented by . The initial population of vectors is simply randomized into the boundary of the search space according to a uniform distribution as follows:

(7.17)

where iϵ[1, 2, …, NP] is the index of ith vector of the population, jϵ[1, 2, …, D] represents the jth dimension of the search space, and rand_j [0, 1] is a uniformly distributed random number corresponding to the jth dimension. Finally, lb_j and ub_j are the lower and upper bounds of the search space corresponding to the jth dimension of the search space.

7.6.1.2 Difference‐vector‐based Mutation

After initialization of the vectors in the search space, a mutation is performed on each genome i of the population to generate a donor vector corresponding to target vector . Each component of donor vector , using a DE/rand/1 mutation strategy, is given by:

(7.18)

where is the scaling factor used to control the amplification of difference vector, and r₁, r₂ and r₃ are uniformly distributed random integers on the interval [1, NP] such that r₁ ≠ r₂ ≠ r₃ ≠ i.

Different mutation strategies have been outlined in [71]. If the generated mutant vector is out of the search boundary, a repair operator is used to bring back to the feasible region.

7.6.1.3 Crossover

To introduce diversity to the population of genomes, DE utilizes a crossover operation to combine the components of target vector and donor vector , to form the trial vector . Two types of crossover are commonly used in the DE community, which are called binomial crossover and exponential crossover. Binomial crossover is the underlying crossover in DynDE which is defined as follows:

(7.19)

where rand_ij [0, 1] is a random number drawn from a uniform distribution between 0 and 1, CR ∈ (0, 1) is the crossover probability which is used to control the approximate number of components that are transferred to the trial vector. jrand is a random index in the range [1, D], which ensures the transmitting of at least one component from the donor to the trial vector.

7.6.1.4 Selection Finally, a selection approach is performed on vectors to determine which vector ( or ) should survive in the next generation. The most fitted vector is chosen to be the member of the next generation.

Different extensions of DE can be specified using the general convention DE/x/y/z, where DE stands for “Differential Evolution,” x represents a string denoting the base vector to be perturbed, y is the number of difference vectors considered for perturbation of x, and z stands for the type of crossover being used, i.e. exponential or binomial, [71]. Figure 7.10 shows a sample pseudo‐code for canonical DE.

DE has several advantages that make it a powerful tool for optimization tasks. Specifically, (i) DE has a simple structure and is easy to implement; (ii) despite its simplicity, DE exhibits a high performance; (iii) the number of control parameters in the canonical DE [69] are very few (i.e. NP, F, and CR); (iv) due to its low space complexity, DE is suitable for handling large‐scale problems.

7.6.2 DynDE

DynDE starts with a predefined number of sub‐populations, exploring the entire search space to locate the optimum. Each sub‐population is composed of normal and Brownian individuals.

7.6.2.1 Normal Individuals

Normal individuals follow the principles of the DE. Although various schemes are typically used for DE, according to the authors [41], DE/best/2/bin produces the best results. In this scheme, the following mutation strategy is used:

(7.20)

here, are four randomly selected vectors from the sub‐population. In addition, is the best vector from the sub‐population.

7.6.2.2 Repair Operator

If the generated mutant vector is out of the search boundary, a repair operator is used to bring back to the feasible region. Different strategies have been proposed to repair the out of bound individuals. In this chapter, if the j^th element of the i^th mutant vector, i.e. v_ij, is out of the search region [lb_j, ub_j ], then it is repaired as follows:

(7.21)

Afterwards, the binomial crossover is applied to form the trial vector according to Eq. (7.19).

7.6.2.3 Brownian Individuals

On the other hand, Brownian individuals are not generated according to the DE/best/2/bin scheme. They are created around the center of the best individual of the sub‐population according to the following equation:

(7.22)

where is a Gaussian distribution with zero mean and standard deviation σ. As shown in [41], σ = 0.2 is a suitable value for this parameter.

7.6.2.4 Exclusion

In order to prevent different sub‐populations from settling on the same peak, an exclusion operator is applied. This operator triggers when the distance between the best individuals of any two sub‐populations becomes less than the threshold r_excl, and reinitializes the worst performing sub‐population in the search space. The parameter r_excl is calculated as follows:

(7.23)

where X is the range of the search space for each dimension, and p is the number of existing peaks in the landscape.

7.7.1 Dynamic Test Function

One of the most widely used dynamic test functions in the literature is the Moving Peaks Benchmark (MPB) [17]. MPB is a real‐valued dynamic environment with a D‐dimensional landscape consisting of m peaks, where the height, width, and position of each peak are changed slightly every time a change occurs in the environment [72]. Different landscapes can be defined by specifying the shape of the peaks and some other parameters. A typical peak shape is conical which is defined as follows:

(7.24)

where H_t (i) and W_t (i) are the height and width of peak i at time t, respectively.

In MPB, both position and objective function of the problem are subject to change. The control parameters of the MPB are φ = (H, W, X), that deviate from their current values, every time a change occurs, according to the following equation:

(7.25)

where ∆φ is the deviation of the control parameters, σ denotes a normally distributed random number with mean zero and standard deviation one, and φ_severity is a constant number that indicates the change severity of φ. The coordinates of each dimension j ∈ [1, D] of peak i at time t are expressed by X_t (i, j), while D is the problem dimensionality. A typical change of a single peak can be modeled as follows:

(7.26)

(7.27)

(7.28)

(7.29)

where σ_h and σ_w are two random Gaussian numbers with zero mean and standard deviation one. Moreover, the shift vector is a combination of a random vector , which is created by drawing random numbers in [−0.5, 0.5] for each dimension, and the current shift vector , and normalized to the length s. Parameter λ ∈ [0.0, 1.0] specifies the correlation of each peak's changes to the previous one. This parameter determines the trajectory of changes, where λ = 0 means that the peaks are shifted in completely random directions and λ = 1 means that the peaks always follow the same direction, until they hit the boundaries where they bounce off.

In this chapter we consider the so‐called Scenario 2, which is the most widely used configuration of MPB. Unless stated otherwise, the MPB's parameters are set according to the values listed in Table 7.2 (default values). In addition, to investigate the effect of the environmental parameters (i.e. the change severity, change period, number of peaks, number of dimensions) on the performance of the proposed SPS methods, various experiments were carried out with different combinations of other tested values listed in Table 7.2.

7.7.2 Performance Measure

Several criteria have been already proposed in the literature for measuring the performance of the optimization algorithms in DOPs [73]. In order to validate the efficiency of the tested SPS algorithms, we considered the offline error, which is the most well‐known metric for dynamic environments [74]. This measure [75] is defined as the average of the smallest error found by the algorithm in every time step:

(7.30)

where T is the maximum number of FEs so far and is the minimum error obtained by the algorithm at the time step t. We assume that a FE used by the algorithm corresponds to a single time step.

7.7.3 Experimental Settings

For each experiment of a SPS algorithm on a specific DOP, 50 independent runs with different random seeds were performed. Each run ends when the algorithm has consumed 500 000 FEs. The experimental results are reported in terms of average offline error and standard error, which is computed as standard deviation divided by the squared root of the number of runs.

To determine the differences among tested algorithms, we applied nonparametric tests. First, we applied the Friedman's test (P < 0.05) to verify whether significant differences exist at group level, that is, among all algorithms. In the case that such differences exist, then a Wilcoxon test (α = 0.05) is applied to compare the best‐performing algorithm among DynDE‐RND, DynDE‐PC, DynDE‐CPE, DynDE‐PI, DynDE‐VSLA, DynDE‐FSLA, and DynDE‐STAR with DynDE‐RR, which is the commonly used SPS algorithm for multi‐population methods. The outcomes of the Wilcoxon test revealing that statically significant differences exist between the algorithms are highlighted with an asterisk symbol.

In addition, when reporting the results, the last column(row) of each table includes the improvement rate (%Imp) of the best‐performing DynDE variant vs. the DynDE‐RR. This measure is computed for every problem instance i as follows:

(7.31)

where e_{i, DynDE − RR} is the error value obtained by DynDE‐RR for the problem i. Similarly, e_{i, Best} is the best (minimum) offline error obtained by the other DynDE variants.

The parameters setting of the DynDE, and the reward and penalty factors for the VSLA‐based SPS, are as shown in Table 7.3.

In order to draw valid conclusions regarding the effect of including SPS in DynDE, we have employed the same parameter settings reported by the authors of the algorithm. Moreover, the values for reward and penalty parameters were set according to [29].

7.7.3.3 Experiment 3: Effect of Increasing the Number of Dimensions

In this experiment, the performance of the eight SPS algorithms is investigated on the MPB with different dimensionalities D ∈ {5, 10, 15, 20, 25, 30} and the other dynamic and complexity parameters are the same as the Scenario 2 of the MPB listed in Table 7.2.

As can be clearly observed in Table 7.6, the advantage of using SPS is more marked by increasing the scale of the DOP. As the number of dimensions is increased from 10 to 30, the best rate of improvement values of the SPS methods increases monotonically. This is a further argument to confirm the effectiveness of the SPS.

In order to provide some insights about the performance of the tested algorithms over the all simulated DOPs, a graphical representation using a box plot is presented in Figure 7.12. Each boxplot in the figure corresponds to a DynDE variant with lines at the lower quartile, median as solid black line, and upper quartile data values, where the whiskers are the lines extending from each end of the box to show the extent of the rest of the data. Values outside the range of the box plot are shown as individual points.

m	DynDE‐RR	DynDE‐RND	DynDE‐PC	DynDE‐CPE	DynDE‐PI	DynDE‐VSLA	DynDE‐FSLA	DynDE‐STAR	%Imp
1	3.80 ± 0.17	4.85 ± 0.21	4.88 ± 0.20	2.79 ± 0.16	2.70 ± 0.11	3.07 ± 0.12	2.37 ± 0.10	2.49 ± 0.10	37.63*
2	2.41 ± 0.17	2.64 ± 0.16	2.77 ± 0.12	1.93 ± 0.15	1.63 ± 0.13	1.88 ± 0.14	1.54 ± 0.05	1.53 ± 0.05	36.51*
5	1.64 ± 0.09	1.70 ± 0.07	1.87 ± 0.08	1.55 ± 0.08	1.32 ± 0.09	1.41 ± 0.08	1.32 ± 0.06	1.30 ± 0.07	20.73*
7	1.63 ± 0.08	1.66 ± 0.05	1.82 ± 0.07	1.59 ± 0.06	1.50 ± 0.09	1.32 ± 0.05	1.46 ± 0.08	1.32 ± 0.05	19.01*
10	1.50 ± 0.05	1.64 ± 0.06	1.61 ± 0.05	1.49 ± 0.05	1.47 ± 0.08	1.32 ± 0.06	1.42 ± 0.06	1.31 ± 0.04	12.66*
20	2.74 ± 0.07	2.73 ± 0.06	2.77 ± 0.06	2.66 ± 0.07	2.46 ± 0.08	2.60 ± 0.07	2.58 ± 0.07	2.54 ± 0.07	10.21*
30	3.22 ± 0.10	3.24 ± 0.11	3.31 ± 0.09	3.25 ± 0.11	2.91 ± 0.11	3.05 ± 0.10	3.15 ± 0.10	3.02 ± 0.08	9.62*
40	3.46 ± 0.08	3.54 ± 0.08	3.56 ± 0.09	3.53 ± 0.09	3.28 ± 0.09	3.34 ± 0.07	3.38 ± 0.08	3.41 ± 0.09	5.20
50	3.81 ± 0.10	3.86 ± 0.08	3.90 ± 0.11	3.77 ± 0.09	3.38 ± 0.10	3.56 ± 0.09	3.71 ± 0.10	3.62 ± 0.10	11.28*
100	4.21 ± 0.12	4.15 ± 0.11	4.11 ± 0.09	4.15 ± 0.12	3.78 ± 0.11	3.88 ± 0.11	4.02 ± 0.09	3.97 ± 0.09	10.21*
200	3.99 ± 0.12	3.86 ± 0.09	3.94 ± 0.10	3.98 ± 0.11	3.62 ± 0.09	3.71 ± 0.09	3.77 ± 0.09	3.71 ± 0.09	9.27

Best values are shown in bold.

Method	Number of dimensions (D)
	5	10	15	20	25	30
DynDE‐RR	1.50 ± 0.05	4.41 ± 0.22	6.75 ± 0.23	9.05 ± 0.29	11.37 ± 0.29	14.30 ± 0.46
DynDE‐RND	1.64 ± 0.06	4.56 ± 0.24	7.00 ± 0.25	9.27 ± 0.28	11.75 ± 0.34	14.49 ± 0.45
DynDE‐PC	1.61 ± 0.05	4.52 ± 0.22	7.18 ± 0.28	9.26 ± 0.27	11.96 ± 0.35	14.87 ± 0.45
DynDE‐CPE	1.49 ± 0.05	4.25 ± 0.21	6.21 ± 0.23	8.43 ± 0.28	10.34 ± 0.33	12.93 ± 0.51
DynDE‐PI	1.47 ± 0.08	4.03 ± 0.23	5.87 ± 0.26	7.33 ± 0.25	8.90 ± 0.33	10.30 ± 0.36
DynDE‐VSLA	1.32 ± 0.06	3.99 ± 0.23	5.60 ± 0.25	6.95 ± 0.23	8.11 ± 0.25	9.43 ± 0.29
DynDE‐FSLA	1.42 ± 0.06	4.05 ± 0.21	5.60 ± 0.23	7.23 ± 0.23	8.53 ± 0.25	9.64 ± 0.28
DynDE‐STAR	1.31 ± 0.04	3.94 ± 0.22	5.73 ± 0.23	7.22 ± 0.25	8.29 ± 0.25	9.65 ± 0.30
%Imp	12.66*	10.65*	17.03*	23.20*	28.67*	34.05*

Best values are shown in bold.

Regarding Figure 7.12, some general observations can be made as follows:

1. The boxplots for PI, VSLA, FSLA, and STAR are comparatively shorter than the other SPS methods. This suggests that PI, VSLA, FSLA, and STAR hold different performances compared to RR, RND, PC, and CPE.
2. The boxplots for PI, VSLA, FSLA, and STAR are comparatively lower than RR, RND, PC, and CPE. This suggests a difference between the two groups of methods.

Moreover, Figure 7.13 shows the mean offline error of each SPS method with 95% confidence intervals for all the reported results from Table 7.4 to Table 7.6. The circles represent the mean offline error obtained by each SPS algorithm and error bars represent 95% confidence intervals for the mean. In addition, the means for every method are connected by a line. From Figure 7.13, it is observed that the results of PI, VSLA, FSLA, and STAR are significantly better than those of RR, RND, PC, CPE. Besides, while PI, VSLA, FSLA, and STAR show a similar performance, the mean error of FSLA is lower than the others.

Finally, in order to fully support the above conclusions, we performed pairwise comparisons with the eight algorithms using the Wilcoxon's rank sum test at 0.05 level (p < 0.05) of significance using all the reported means from the previous experiments. Table 7.7 presents whether pairwise performance comparisons between the algorithms are statistically significant or not. Each result given at the Xth row (AX) and the Yth column (AY) is marked with symbols “S+,” “S‐,” “+” or “−” to indicate that the algorithm on the Xth row is significantly better than, significantly worse than, insignificantly better than, and insignificantly worse than the algorithm on the Yth column, respectively. The rightmost column of the Table 7.7 shows the mean rank of each SPS algorithm using Friedman's multiple comparisons test with p < 0.05. It is important to note that the lower the rank the better is the algorithm performance.

From Table 7.7, it is realized that a sophisticated scheduling mechanism can efficiently enhance the performance of multi‐population methods for DOPs.

	RR	RND	PC	CPE	PI	VSLA	FSLA	STAR	Mean Rank
RR		S+	S+	S‐	S‐	S‐	S‐	S‐	6.1000
RND	S‐		S+	S‐	S‐	S‐	S‐	S‐	6.9833
PC	S‐	S‐		S‐	S‐	S‐	S‐	S‐	7.7000
CPE	S+	S+	S+		S‐	S‐	S‐	S‐	5.2167
PI	S+	S+	S+	S+		+	−	−	2.6000
VSLA	S+	S+	S+	S+	−		−	−	2.8667
FSLA	S+	S+	S+	S+	+	+		+	2.2667
STAR	S+	S+	S+	S+	+	+	−		2.2667