Differential Evolution: Population Topologies,
Ensemble Strategies and Adaptation
Dr. P. N. Suganthan, EEE, NTU, Singapore
Some Software Resources Available from:http://www.ntu.edu.sg/home/epnsugan
IEEE CEC 2017, Donostia - San Sebastián, Spain, 5thJune 2017

Overview
I.

Introduction to Real Variable Optimization & DE

II.

Single Objective Optimization

III.

Constrained Optimization

IV. Dynamic Optimization
V.

Multi-objective Optimization

VI. Large Scale Optimization
VII. Multimodal Optimization

But, first a little publicity.

S. Das, S. S. Mullick, P. N. Suganthan, "Recent Advances in Differential Evolution An Updated Survey," Swarm and Evolutionary Computation, Vol. 27, pp. 1-30, 2016.
S. Das and P. N. Suganthan, “Differential Evolution: A Survey of the State-of-theArt”, IEEE Trans. on Evolutionary Computation, 15(1):4 – 31, Feb. 2011.

2

Optimization Benchmark Test Problems, Surveys,
Codes of several of our research publications
Are available fromhttp://www.ntu.edu.sg/home/epnsugan(limited to our own publications & CEC Competitions)
Ensemble / Adaptive Methods for Evolutionary Algorithms:
http://www.ntu.edu.sg/home/epnsugan/index_files/EEAs-EOAs.htm
3Consider submitting to
SWEVO journal
dedicated to the EC-SI
fieldsSCI Indexed from Vol. 1,
Issue 1.
2016 IFs:
2 years = 2.9
5 years= 5.7

Overview
I.

Introduction to Real Variable Optimization & DE

II. Single Objective Optimization
III. Multimodal Optimization
IV. Dynamic Optimization
V. Multi-objective Optimization
VI. Large Scale Optimization
VII. Constrained Optimization
5

General Thoughts: NFL (No Free Lunch Theorem)•

Glamorous Name for Commonsense?
–

Over a large set of problems, it is impossible to find a single best algorithm–

DE with Cr=0.90 & Cr=0.91 are two different algorithms Æ Infinite algos.

–

Practical Relevance: Is it common for a practicing engineer to solve several
practical problems at the same time? (NO)–Academic Relevance: Very High

Other NFL Like Commonsense Scenarios
Panacea: A medicine to cure all diseases (No need for doctors), Amrita the nectarof immortal perfect life …
Silver bullet: in politics … (you can search these on internet)
Jack of all trades, but master of none
If you have a hammer all problems look like nails

6General Thoughts: Convergence•

What is exactly convergence in the context of EAs & SAs ?
––The whole population reaching a single point (within a tolerance)
Single point based search methods & convergence …

•

In the context of real world problem solving, are we going to reject agood solution because the population hasn’t converged ?

•Good to have all population members converging to the global
solution OR good to have high diversity even after finding the
global optimum ? (Fixed Computational budget Scenario)•

What we do not want to have:
For example, in the context of PSO, we do not want to have chaotic oscillations

c1 + c2 > 4.1+
7

General Thoughts: Algorithmic Parameters
•
•
•
•

•

Good to have many algorithmic parameters / operators ?
Possible to be robust against parameter / operator variations ?
What are Reviewers’ preferences ?
Or good to have several parameters that can be adaptively
tuned on the fly to achieve top performance on diverse
problems?
If NFL says that a single algorithm is not the best for eachproblem in a large set of problems, then good to have manyalgorithmic parameters & operators to be adapted for different
problems !!

CEC 2015 Competitions: “Learning-Based Optimization”
8

Similar Literature: Thomas Stützle, Holger Hoos, …

Differential Evolution• A stochastic population-based algorithm for continuous function
optimization (Storn and Price, 1995)• Finished 3rd at the First International Contest on Evolutionary
Computation, Nagoya, 1996 (icsi.berkley.edu/~storn)• Outperformed several variants of GA and PSO over a wide variety ofnumerical benchmarks over past several years.
• Continually exhibited remarkable performance in competitions on
different kinds of optimization problems like dynamic, multi-objective,
constrained, and multi-modal problems held under IEEE congress on
Evolutionary Computation (CEC) conference series.
• Very easy to implement in any standard programming language.
• Very few control parameters (typically three for a standard DE) andtheir effects on the performance have been well studied.
• Spatial complexity is very low as compared to some of the mostcompetitive continuous optimizers like CMA-ES.
9

DE is an Evolutionary Algorithm
This Class also includes GA, Evolutionary
Programming and Evolutionary Strategies

Initialization

Mutation

Recombination

Basic steps of an Evolutionary Algorithm

10

Selection

Representation
Max

&
X

x1

x2

x D-1

xD

Min
Solutions are represented as vectors of size D with eachvalue taken from some domain.
May wish to constrain the values taken in each domain
above and below.

11

Maintain Population - NP
We will maintain a population of size NP

&
X1
&
X2

x1,1

x2,1

x D-1,1

xD,1

x1,2

x2,2

xD-1,2

xD,2

&
X NP

x1,NP

x2,NP

x D-1,NP

xD, NP

12

The population size NP
1) The influence of NP on the performance of DE is yet to be extensively studied andfully understood.
2)

Storn and Price have indicated that a reasonable value for NP could be chosen
between 5D and 10D (D being the dimensionality of the problem).

3) Brest and Maučec presented a method for gradually reducing population size of
DE. The method improves the efficiency and robustness of the algorithm and canbe applied to any variant of DE.
4) But, recently, all best performing DE variants used populations ~50-100 for
dimensions from 50D to 1000D for the following scalability Special Issue:
F. Herrera M. Lozano D. Molina, "Test Suite for the Special Issue of Soft Computing
on Scalability of Evolutionary Algorithms and other Metaheuristics for Large Scale
Continuous Optimization Problems". Available: http://sci2s.ugr.es/eamhco/CFP.php.

13

Initialization

Mutation

Recombination

Selection

Max
0.42

0.22

0.78

0.83

Min

&
Xi

x1,i,0x2,i,0x D-1,i,0

xD,i,0x j ,i ,0 = x j ,min + randi , j [0,1] ⋅ ( x j ,max − x j ,min )Different randi , j [0,1] values are instantiated for each i and j.

14

Initialization

Mutation

Recombination

Selection¾For each vector select three other parameter vectors randomly.
¾Add the weighted difference of two of the parameter vectors to thethird to form a donor vector (most commonly seen form ofDE-mutation):&&&&
Vi ,G = X r i ,G + F ⋅ ( X r i ,G − X r i ,G ).
1

2

3¾The scaling factor F is a constant from (0, 2)¾Self-referential Mutation
15

Example of formation of donor vector over twodimensional constant cost contours

Constant cost contours of
Sphere function

16

Initialization

Mutation

Recombination

Selection

Binomial (Uniform) Crossover:
Components of the donor vector enter into the trial offspring vector in
the following way:
Let jrand be a randomly chosen integer between 1,...,D.

17

An Illustration of Binomial Crossover in 2-D Parametric Space:Three possible trial vectors:

18

Exponential (two-point modulo) Crossover:First choose integers n (as starting point) and L (number of components thedonor actually contributes to the offspring) from the interval [1,D]

where the angular brackets

Ddenote a modulo function with modulus D.

Pseudo-code for choosing L:

Exploits linkages among neighboring decision variables. If benchmarks have thisfeature, it performs well. Similarly, for real-world problems with neighboring linkages.
19

Example: Let us consider the following pair of donor and target vectors
3.82
4.78
&
X i ,G = −9.34
5.36
−3.77

8.12
&
Vi ,G =

10
−10
−3.22
−1.12

Suppose n = 3 and L= 3 for this specific example. Then the exponential
crossover process can be shown as:

20

Initialization

Mutation

Recombination

Selection¾“Survival of the fitter” principle in selection: The trial
offspring vector is compared with the target (parent)
vector and the one with a better fitness is admitted to thenext generation population.

&&&&
X i ,G +1 = U i ,G , if f (U i ,G ) ≤ f ( X i ,G )&&&= X i ,G , if f (U i ,G ) > f ( X i ,G )
¾Importance of parent-mutant crossover & parentoffspring competition-based selection
21

An Example of Optimization by DE
Consider the following two-dimensional function

f (x, y) = x2+y2

The minima is at (0, 0)

Let’s start with a population of 5 candidate solutions randomly initiated in therange (-10, 10)

X1,0 = [2, -1]
X5,0= [6,-7]

X2,0 = [6, 1]

X3,0 = [-3, 5]

X4,0 = [-2, 6]

For the first vector X1, randomly select three other vectors say X2,
X4 and X5
Now form the donor vector as, V1,0 = X2,0+F. (X4,0 – X5,0)6+ 0.8 ×V1,0 =
1

−2
6
−
−7
6

−0.4
=
10.4
22

Now we form the trial offspring vector by exchanging
components of V1,0 with the target vector X1,0

Let rand[0, 1) = 0.6. If we set Cr = 0.9,
since 0.6 < 0.9, u1,1,0 = V1,1,0 = - 0.4
Again next time let rand[0, 1) = 0.95 > Cr
Hence u1,2,0 = x1,2,0 = - 1−0.4
So, finally the offspring is U1,0 =−1Fitness of parent:

Fitness of offspringf (2, -1) = 22 + (-1)2 = 5

f (-0.4, -1) = (-0.4)2 + (-1)2 = 1.16

Hence the parent is replaced by offspring at G = 1
23Population
at G = 0

Fitness
at G = 0

Donor vector
at G = 0

Offspring Vector
at G = 0

Fitness ofoffspring at
G=1

Evolvedpopulation at
G=1

X1,0 =[2,-1]

5

V1,0=[-0.4,10.4]

U1,0=[-0.4,-1]

1.16

X1,1
=[-0.4,-1]

X2,0=[6, 1]

37

V2,0=[1.2, -0.2]

U2,0=[1.2, 1]

2.44

X2,1
=[1.2, 1]X3,0=[-3, 5]34

V3,0=[-4.4, -0.2]

U3,0=[-4.4, -0.2]

19.4

X3,1
=[-4.4, -0.2]

X4,0=[-2, 6]40

V4,0=[9.2, -4.2 ]U4,0=[9.2, 6 ]120.64

X4,1=[-2, 6 ]X5,0=[6, 7]

85

V5,0=[5.2, 0.2]

U5,0=[6, 0.2]

36.04

X5,1
=[6, 0.2]

24

Locus of the fittest solution: DE working on 2D Sphere Function

25

Locus of the fittest solution: DE working on 2D Rosenbrock Function

26

Five most frequently used DE mutation schemes&&&&“DE/rand/1”: Vi (t ) = X r i (t ) + F ⋅ ( X r i (t ) − X r i (t )).
1

2

3

&
&
&
&
“DE/best/1”: Vi (t ) = X best (t ) + F .( X r i (t ) − X r i (t )).
1

2

&
&
&
&
&
&
“DE/target-to-best/1”: Vi (t ) = X i (t ) + F .( X best (t ) − X i (t )) + F .( X r i (t ) − X r i (t )),
1

2

&
&
&
&
&
&
“DE/best/2”: Vi (t ) = X best (t ) + F .( X r1i (t ) − X r2i (t )) + F .( X r3i (t ) − X r4i (t )).

&
&
&
&
&
&
“DE/rand/2”: V (t ) = X i (t ) + F .( X i (t ) − X i (t )) + F .( X i (t ) − X i (t )).
i
1
2
r
r
r
r
r
1

2

3

4

5

The general convention used for naming the various mutation strategies is
DE/x/y/z, where DE stands for Differential Evolution, x represents a string
denoting the 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 (exp: exponential; bin: binomial)

27

The Crossover Rate Cr:
1)
2)

The parameter Cr controls how many parameters in expectation, are changed in a population member.
Low value of Cr, a small number of parameters are changed in each generation and the stepwise
movement tends to be orthogonal to the current coordinate axes
Good for separable problems

3) High values of Cr (near 1) cause most of the directions of the mutant vector to be inherited prohibiting thegeneration of axis orthogonal steps
Good for non-separable problems
Empirical distribution of trial vectors for three different values of Cr has been shown. The plots wereobtained by obtained by running DE on a single starting population of 10 vectors for 200 generations withselection disabled.

(a) Cr = 0(b) Cr = 0.5(c) Cr = 1.0

For schemes like DE/rand/1/bin the performance is rotationally invariant only when Cr = 1.
At that setting, crossover is a vector-level operation that makes the trial vector a pure mutant i.e.

&&&&
U i ,G = X r i ,G + F ⋅ ( X r i ,G − X r i ,G ).
1

2

3

28

Overview
I.

Introduction to Real Variable Optimization & DE

II. Future of Real Parameter Optimization
III. Single Objective Optimization
IV. Multimodal Optimization
V. Dynamic Optimization
VI. Multi-objective Optimization
VII. Large Scale Optimization
VIII.Constrained Optimization

29

Importance of Population Topologies• In population based algorithms, population members exchange
information between them.
• Single population topology permits all members to exchange
information among themselves – the most commonly used.
• Other population topologies have restrictions on informationexchange between members – the oldest is island model• Restrictions on information exchange can slow down the
propagation of information from the best member in the population
to other members (i.e. single objective global optimization)• Hence, this approach– slows down movement of other members towards the best member(s)– Enhances the exploration of the search space– Beneficial when solving multi-modal problems
As global version of the PSO converges fast, many topologies were
Introduced to slow down PSO-30-

PSO with Neighborhood Operator
Presumed to be the oldest paper to consider distance basedneighborhoods for real-parameter optimization.
Lbest is selected from the members that are closer (w.r.t.
Euclidean distance) to the member being updated.
Initially only a few members are within the neighborhood (small
distance threshold) and finally all members are in the n’hood.
Island model and other static/dynamic neighborhoods did not
make use of Euclidean distances, instead just the indexes of
population members.
Our recent works are extensively making use of distance basedneighborhoods to solve many classes of problems.
P. N. Suganthan, “Particle swarm optimizer with neighborhood
operator,” in Proc. Congr. Evol. Comput., Washington, DC, pp.1958–
31
1962, 1999.

Two Subpopulations with Heterogeneous
Ensembles & Topologies
 Proposed for balancing exploration and exploitation capabilities
 Population is divided into exploration / exploitation sub-poplns¾¾

Exploration Subpopulation group uses exploration oriented ensembleof parameters and operators
Exploitation Subpopulation group uses exploitation oriented ensembleof parameters and operators.

•

Topology allows information exchange only from explorative subpopulation
to exploitation sub-population. Hence, diversity of exploration popln notaffected even if exploitation popln converges.
• The need for memetic algorithms in real parameter optimization: Memetic
algorithms were developed because we were not able to have an EA or SI to beable to perform both exploitation and exploration simultaneously. This 2-popln
topology allows with heterogeneous information exchange.
32

Two Subpopulations with Heterogeneous
Ensembles & Topologies
 Sa.EPSDE realization (for single objective Global):N. Lynn, R Mallipeddi, P. N. Suganthan, “Differential Evolution with Two
Subpopulations," LNCS 8947, SEMCCO 2014.

 2 Subpopulations CLPSO (for single objective Global)
N. Lynn, P. N. Suganthan, “Comprehensive Learning Particle Swarm
Optimization with Heterogeneous Population Topologies for Enhanced
Exploration and Exploitation,” Swarm and Evolutionary Computation, 2015.

 Neighborhood-Based Niching-DE: Distance basedneighborhood forms local topologies while within each n’hood,
we employ exploration-exploitation ensemble of parameters
and operators.
S. Hui, P N Suganthan, “Ensemble and Arithmetic Recombination-BasedSpeciation Differential Evolution for Multimodal Optimization,” IEEE T.
Cybernetics, Online since Mar 2015. 10.1109/TCYB.2015.2394466
33

Ensemble Methods•

Ensemble methods are commonly used for patternrecognition (PR), forecasting, and prediction, e.g. multiple
predictors.

•

Not commonly used in Evolutionary algorithms ...

There are two advantages in EA (compared to PR):
1. In PR, we have no idea if a predicted value is correct ornot. In EA, we can look at the objective values and makesome conclusions.
2. Sharing of function evaluation among ensembles possible.
34

Adaptations•

Self-adaptation: parameters and operators are evolved bycoding them together with solution vector•

Separate adaptation based on performance: operatorsand parameter values yielding improved solutions are
rewarded.

•

2nd approach is more successful and frequently used inDE.

35

Overview
I.

Introduction to Real Variable Optimization & DE

II. Future of Real Parameter Optimization
III. Single Objective Optimization
IV. Multimodal Optimization
V. Dynamic Optimization
VI. Multi-objective Optimization
VII. Large Scale Optimization
VIII.Constrained Optimization

36

The ‘jDE’ Algorithm (Brest et al., 2006)• Control parameters F and Cr of the individuals are adjusted byintroducing two new parameters τ1 and τ2• The new control parameters for the next generation arecomputed as follows:

Fi ,G +1 = Fl + rand1 * Fu if rand 2 < τ 1= Fi ,G else.
Cri ,G +1 = rand 3 if rand 4 < τ 2= Cri ,Gelse,

τ 1 = τ 2 = 0.1 Fl = 0.1,
The new F takes a value from [0.1, 0.9] while the new Cr takes
a value from [0, 1].
J. Brest, S. Greiner, B. Bošković, M. Mernik, and V. Žumer, “Self-adapting Control parameters
in differential evolution: a comparative study on numerical benchmark problems,” IEEE Trans.
on Evolutionary Computation, Vol. 10, Issue 6, pp. 646 – 657, 200637

Self-Adaptive DE (SaDE) (Qin et al., 2009)• Includes both control parameter adaptation and strategy adaptation
Strategy Adaptation:
Four effective trial vector generation strategies: DE/rand/1/bin, DE/rand-tobest/2/bin, DE/rand/2/bin and DE/current-to-rand/1 are chosen to constitutea strategy candidate pool.
For each target vector in the current population, one trial vector generation
strategy is selected from the candidate pool according to the probability
learned from its success rate in generating improved solutions (that cansurvive to the next generation) within a certain number of previous
generations, called the Learning Period (LP).
First published in CEC 2005
A. K. Qin, V. L. Huang, and P. N. Suganthan, Differential evolution algorithm with strategy
adaptation for global numerical optimization", IEEE Trans. on Evolutionary
Computation, 13(2):398-417, April, 2009.

38

SaDE (Contd..)
Control Parameter Adaptation:
1)
2)
3)
4)

NP is left as a user defined parameter.
A set of F values are randomly sampled from normal distribution
N(0.5, 0.3) and applied to each target vector in the current
population.
CR obeys a normal distribution with mean value CR m and standard
deviation Std =0.1, denoted by N (CR m , Std ) where CR m isinitialized as 0.5.
SaDE gradually adjusts the range of CR values for a given problem
according to previous CR values that have generated trial vectors
successfully entering the next generation.

39

Opposition-based DE (Rahnamayan etal., 2008)• Three stage modification to original DE framework based on
the concept of Opposite Numbers :Let x be a real number defined in the closed interval [a, b]. Thenthe opposite number of x may be defined as:∪

x = a+b− x

ODE Steps:
1) Opposition based Population Initialization: Fittest NP individuals are chosen
as the starting population from a combination of NP randomly generated population
members and their opposite members.
2) Opposition Based Generation Jumping: In this stage, after each iteration,
instead of generating new population by evolutionary process, the opposite
population is calculated with a predetermined probability Jr () and the NP fittest
individuals may be selected from the current population and the corresponding
40
opposite population.

ODE (Contd.)3) Opposition Based Best Individual Jumping: In this phase, at first a
difference-offspring of the best individual in the current population is created
as:

&
&
&
&
X new _ best ,G = X best ,G + F '.( X r1 ,G − X r2 ,G )where r1 and r2 are mutually different random integer indices selected from{1, 2, ..., NP} and& F’ is a real constant. Next the opposite of offspring is
generated as X.
Finally the current best member is replaced
opp _ newbestG

{

&
&
&
by the fittest member of the set X best ,G , X new _ best ,G , X opp _ newbest ,G}

S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Opposition-based differential evolution”, I
EEE Trans. on Evolutionary Computation, Vol. 12, Issue 1, pp. 64-79, Feb. 2008.

41

¾ Introduction of Topological Neighborhood-based mutations in Differential Evolution:
Index-based social neighborhoods in DE for global optimization:
 Removes the exploitative bias of the classical DE mutation
Initially investigated
&
&
&
&
&
&
scheme:only ring topologies:
Vi (t ) = X i (t ) + F .( X best (t ) − X i (t )) + F .( X i (t ) − X i (t )),r1

r2• Reduces attractions towards specific points• Increases information sharing and promotes
explorative search.
Local Mutation Model:

&
&
&
&
&
&
Li (t ) = X i (t ) + α ⋅ ( X n _ besti (t ) − X i (t )) + β ⋅ ( X p (t ) − X q (t ))Global Mutation Model:

&
&
&
&
&
&
g i (t ) = X i (t ) + α ⋅ ( X g _ best (t ) − X i (t )) + β ⋅ ( X r1 (t ) − X r2 (t ))Combined Model for Donor Vector generation:&&&
Vi (t ) = w.g i (t ) + (1 − w).Li (t )Indexed based topologies from PSO domain are faster than Euclidean distance based. But not very
effective.
S. Das, A. Konar, U. K. Chakraborty, and Ajith Abraham, “Differential evolution with aneighborhood based mutation operator: a comparative study”, IEEE Transactions on
Evolutionary Computing, Vol 13, No. 3, June 2009.

42

JADE (Zhang and Sanderson, 2009)
1) Uses DE/current-to-pbest strategy as a less greedy generalization of the DE/current-to-best/ strategy.
Instead of only adopting the best individual in the DE/current-to-best/1 strategy, the current-to-pbest/1
strategy utilizes the information of other good solutions.

&pDenoting X best ,G as a randomly chosen vector from the top 100p% individuals of the current population,
&
&
&p
&
&
&
DE/current-to-pbest/1 without external archive: Vi ,G = X i ,G + Fi ⋅ ( X best ,G − X i ,G ) + Fi ⋅ ( X r i ,G − X r i ,G )122) JADE can optionally make use of an external archive (A), which stores the recently explored inferior&&p&solutions. In case of DE/current-to-pbest/1 with archive, X i , G, X
, and X
are selected from thebest , Gr ,G&current population P, but X
is selected from P ∪ A
r ,G
i
1

i
2

J. Zhang, and A. C. Sanderson, “JADE: Adaptive differential evolution with optional external archive”,
IEEE Transactions on Evolutionary Computation, Vol. 13, Issue 5, Page(s): 945-958, Oct. 2009.

43

JADE (Contd..)3) JADE adapts the control parameters of DE in the following manner:
A) Cr for each individual and at each generation is randomly generated from a normal distribution

N ( µ Cr ,0.1) and then truncated to [0, 1].
The mean of normal distribution is updated as:µ Cr = (1 − c).µ Cr + c.mean A ( S Cr )where SCr be the set of all successful crossover probabilities Cri s at generation GB) Similarly for each individual and at each generation Fi is randomly generated from a Cauchy distributionC ( µ F ,0.1) with location parameter µ F and scale parameter 0.1.
Fi is truncated if Fi > 1 or regenerated if Fi <= 0

The location parameter of the Cauchy distribution is updated as:µ F = (1 − c).µ F + c.meanL ( S F )where SF is the set of all successful scale factors at generation G and meanL is the Lehmer mean:

meanL ( S F ) =

∑F

2

F∈S F

∑F

F∈S F

JADE usually performs best with 1/c chosen from [5, 20] and p from [5%, 20%]44

Success-History based Adaptive DE (SHADE)• An improved version of JADE
• Uses a success-history based adaptation• Based on a historical memory of successful parameter settings that werepreviously used found during the run• A historical memory MCR , MF are used, instead of adaptive parameter ucr , uF
• This improves the robustness of JADE

Fig. Their adaptation behaviors on Rastrigin (30 dimensions)

JADE uses a single pair ucr, uF

SHADE maintains a diverse set ofparameters
in a historical memory MCR , MF

45

SHADE• The weighted Lehmer mean (in CEC’14 ver.) values of SCR and
SF , which are successful parameters for each generation, arestored in a historical memory MCR and MF• CRi and Fi are generated by selecting an index ri randomly from [1,memory size H]• Example: if selected index ri = 2• CRi = NormalRand(0.87, 0.1)
• Fi = CauchyRand(0.52, 0.1)

46

Example of memory update in SHADE• The contents of both memories are initialized to 0.5 and the index counter is set 1• The CRi and Fi values used by successful individuals are recorded in SCR and SF• At the end of the generation, the contents of memory are updated by the mean values of SCR andSF• The index counter is incremented• Even if SCR , SF for some particular generation contains a poor set of values, the parameters stored
in memory from previous generations cannot be directly, negatively impacted• If the index counter exceeds the memory size H, the index counter wraps around to 1 again

47

Deterministic population reduction methods• General Policy for Evolutionary Algorithms• Explorative search is appropriate for estimating the promisingregions• Exploitative search is appropriate for finding the higher
precision solutions• Deterministic population reduction methods• They use a large population size as initial population andreduce its size
• This mechanism makes EA more robust and effective.
“Evaluating the performance of SHADE on CEC 2013 benchmark
problems”, Ryoji Tanabe and Alex Fukunaga, The University ofTokyo, Japan (Codes-Results available, as SHADE_CEC2013)
L-SHADE in CEC 2014: “Improving the Search Performance of SHADE
Using Linear Population Size Reduction,” By Ryoji Tanabe and Alex48
S. Fukunaga

L-SHADE: SHADE with Linear Population Size Reduction• Deterministic Population Size Reduction (DPSR) [Brest 08]• reduces the population by half at predetermined intervals• The frequency of the population reduction has to be tuned to match the initial population
size as well as the dimensionality of the problem…

• Simple Variable Population Sizing (SVPS) [Laredo 09]• is a more general framework in which the shape of the population size reduction scheduleis determined according to two control parameters• Due to its general versatility, tuning the two control parameters is very hard…

• Linear Population Size Reduction (LPSR) [Tanabe CEC 2014]• is a special case of SVPS which reduces the population linearly, and requires only initial
population sizes• L-SHADE is an extended SHADE with LPSR

Fig. Comparison of population
resizing schedule between LPSR andDPSR (# of reduction = 4)

L-SHADE’s C++ and Matlab/Octave code can be downloaded from
Ryoji Tanabe’s site (https://sites.google.com/site/tanaberyoji/)49

SPS-L-SHADE-EIG• A self-optimization approach and a new successhistory based adaptive differential evolution withlinear population size reduction (L-SHADE) which isincorporated with an eigenvector-based (EIG)
crossover and a successful-parent selecting (SPS)
frameworkSPS-L-SHADE-EIG• The EIG crossover is a rotationally invariant
operator• Very good performance on numerical optimization
problems with highly correlated variables• The SPS framework provides an alternative of theselection of parents to prevent the situation ofstagnation

SPS-L-SHADE-EIG• The experiment evaluates the performance of theself-optimized SPS-L-SHADEEIG in CEC 2015 realparameter single objective optimizationcompetition. Winner of CEC 2015
• The parameters of SPS-L-SHADE-EIG are self
optimized in terms of each function under IEEE
Congress on Evolutionary Computation (CEC)
benchmark set in 2015

LSHADE-Epsin•

JADE Æ SHADE Æ L-SHADE Æ LSHADE-EpSin (joint winner in CEC’16)•

An enhanced version of L-SHADE using:••

An ensemble sinusoidal parameter adaptation and
A local search based on a Gaussian walk•

In this ensemble approach, a pool of two different sinusoidal adjustments
along with Cauchy distribution are used to adapt the scaling factor foreach individual•

The proposed approach falls in the first class which uses an ensemble
pool of two sinusoidal waves to adapt F, and also proposes an adaptive
scheme to control the settings of freq parameter in the sinusoidal
formula.

Noor H. Awad, Mostafa Z. Ali, Ponnuthurai N. Suganthan, Robert G. Reynolds, An Ensemble Sinusoidal Parameter Adaptation incorporated
with L-SHADE for Solving CEC2014 Benchmark Problems, in Proc. IEEE Congr. Evol. Comput., WCCI 2016, Jul. Vancouver, Canada

LSHADE-Epsin- Control Parameter Settings
Ensemble of parameter settings to adapt scaling factor Fi , g :Sinusoidal pool

Cauchy distribution• Activated for the first half ofgenerations g ∈ [1, Gmax ]• Activated for the second half ofgenerations g ∈ ( Gmax , Gmax ]• Two different sinusoidal adjustments• The key advantage of using the sinusoidal
formula at first generations is its ability tochange the search direction• Since the parameter value increases
and decrease periodically, thanks tothe periodicity of the sine function• Hence, the efficiency in exploring thesearch space is enhanced• As proposed by L-SHADE

22• The reason behind using
Cauchy at later generations isin its ability to generate values
that are best to invoke theexploitation phase• Hence, the exploitation
phase will be enhanced tosearch around the bestsolutions

As a result, our proposed control parameter settings Æ Provides a good balance
between exploration and exploitation

LSHADE-Epsin- Sinusoidal Pool
Non-adaptive Sinusoidal Decreasing Adjustment

Adaptive Sinusoidal Increasing Adjustmen

Random Selection
Non-adaptive
Sin Decreasing
Adaptive Sin
Increasing

Fi , g =1
2* sin(2π * freq * g + π ) *Gmax − gGmax+1

Fi , g =1
2* sin(2π * freqi , g * g ) *gGmax

freqi , g

is auto-adjusted using a Cauchy distribution as shown in the following
freqi , g = Cauchy ( µ freq , 0.1)
equation:
At each generation, the successful frequencies are stored in S freq and µ freq is
updated at the end of each generation using the usual arithmetic mean of S freq

+1

Ensemble of Parameters and Mutation and Crossover
Strategies in DE (EPSDE )¾ Motivationo Empirical guidelines
o Adaptation/self-adaptation (different variants)
o Optimization problems (Ex: uni-modal & multimodal)o Fixed single mutation strategy & parameters – may not be the best always¾

Implementationo Contains a pool of mutation strategies & parameter valueso Compete to produce successful offspring population.
o Candidate pools must be restrictive to avoid unfavorable influenceso The pools should be diverse

R. Mallipeddi, P. N. Suganthan, Q. K. Pan and M. F. Tasgetiren, “Differential Evolution
Algorithm with ensemble of parameters and mutation strategies,” Applied Soft Computing,11(2):1679–1696, March 2011.
56

Ensemble of Parameters and Mutation and Crossover
Strategies in DE (EPSDE )o Selection of pool of mutation strategies
1. strategies without crossover (DE/current-to-rand/1/bin)
2. strategies with crossover
1. individuals of mutant vector randomly selected (DE/rand/1/bin)
2. rely on the best found so far (DE/best/2/bin)o Selection of pool of parameters
F = {0.4, 0.5,0.6,0.7,0.8,0.9} Cr = {0.1,0.2,0.3,0.4, 0.5,0.6,0.7,0.8,0.9}

ADAPTIVE EPSDEo Initial population randomly assigned with a mutation & crossoverstrategies and respective parameterso Success rate of each parameter or operator is recorded and future usage is
proportional to each one’s success rate over a few recent past generations.

57

Differential Evolution With Multi-population Based
Ensemble Of Mutation Strategies (MPEDE)• The most efficient mutation strategy is problem dependent• Even for one specific problem, the required best mutation strategy may varyduring the optimization process• Different mutation strategy have different exploitation and exploration
capabilities and could support each other
Wu, G., Mallipeddi, R., Suganthan, P. N., Wang, R., & Chen, H. (2016). Differential
evolution with multi-population based ensemble of mutation strategies. Information
Sciences, 329, 329-345.

MPEDE – Motivation• Constituent mutation strategies should have respective advantages• Each constituent mutation strategy has its minimum resources• The constituent mutation strategy that historically performed well should be
rewarded with more resources in the closely successive generations• Resource is represented by the amount of population taken by one mutation
strategy

MPEDE – Implementation• Three well-investigated mutation strategies are included“current-to-pbest/1”

 i )Vi ,G = X i ,G + F ⋅ ( X pbest ,G − X i ,G + X ri ,G − X
r ,G
1

2

“current-to-rand/1”
U i ,G = X i ,G + K ⋅ ( X r i ,G − X i ,G ) + F ⋅ ( X r i ,G − X r i ,G )12

“rand/1”

Vi ,G = X ri ,G + F ⋅ ( X ri ,G − X ri ,G )
1

2

3

3

MPEDE – Implementation• Each constituent mutation strategy has a minimum population
resources named indicator sub-population denoted by pop1, pop2
and pop3, respectively.
• Recently best performed mutation strategy is rewarded by an extra
population resources named reward sub-population denoted by pop4
Remarks:• Three indicator sub-populations have relatively small size
• The reward sub-population has larger size.

MPEDE – Implementation• At the beginning, pop1, pop2 and pop3, are assigned to threeconstituent mutation strategies, respectively.
• pop4 is randomly assigned to one constituent mutation strategy.
• After every ng generations, the performance of each mutation
strategy is evaluated by the metric∆f j∆FES j• The determined best-performed mutation strategy will occupy the
reward population resource in the following ng generations.

MPEDE – Implementation• The control parameters of each mutation strategy are adapted
independently, which is similar to that used in JADE.

We eventually realize that better mutation strategies obtained
more computational resources in an adaptive manner during theevolution.

Experiments on CEC 2005 benchmark suit show that MPEDE outperforms several
other peer DE variants including JADE, jDE, SaDE, EPSDE, CoDE and SHADE.

Overview
I.

Introduction to Real Variable Optimization & DE

II. Single Objective Optimization
III. Constrained Optimization
IV. Dynamic Optimization
V. Multiobjective Optimization
VI. Large Scale Optimization
VII. Multimodal Optimization
64

Single Objective Constrained Optimization
Currently DE with local Search and Ensemble of Constraint
handling are competitive.
CEC'06 Special Session / Competition on Evolutionary Constrained Real Parameter
single objective optimization
CEC10 Special Session / Competition on Evolutionary Constrained Real Parameter
single objective optimization

E Mezura-Montes, C. A. Coello Coello, "Constraint-handling in nature-inspired
numerical optimization: Past, present and future", Vol. 1, No. 4, pp. 173-194, Swarmand Evolutionary Computation, Dec 2011.
-65-

Constraint Handling Methods• Many optimization problems in science and engineering involve
constraints. The presence of constraints reduces the feasible
region and complicates the search process.
• Evolutionary algorithms (EAs) always perform unconstrained
search.
• When solving constrained optimization problems, they require
additional mechanisms to handle constraints-66-

Constrained Optimization• In general, the constrained problems can be transformed into thefollowing form:• Minimize
subjected to:f (x), x = [ x1 , x2 ,..., xD ]gi (x) ≤ 0, i = 1,..., qh j (x) = 0, j = q + 1,..., mq is the number of inequality constraints and m-q is the number of
equality constraints.

-67-

Constrained Optimization• For convenience, the equality constraints can be transformed into
inequality form:| h j (x) | −ε ≤ 0where ε is the allowed tolerance.
• Then, the constrained problems can be expressed as
Minimizesubjected tof (x), x = [ x1 , x2 ,..., xD ]G j (x) ≤ 0, j = 1,..., m,
G1,..., q (x) = g1,...q (x), Gq +1,..., m (x) = hq +1,...m (x) − ε-68-Constraint-Handling (CH) Techniques• Penalty Functions:• Static Penalties (Homaifar et al.,1994;…)• Dynamic Penalty (Joines & Houck,1994; Michalewicz& Attia,1994;…)• Adaptive Penalty (Eiben et al. 1998; Coello, 1999; Tessema & Gary Yen
2006, …)
• …
• Superiority of feasible solutions• Start with a population of feasible individuals (Michalewicz, 1992; Hu &Eberhart, 2002; …)• Feasible favored comparing criterion (Ray, 2002; Takahama & Sakai, 2005; …)• Specially designed operators (Michalewicz, 1992; …)
• …

-69-

Constraint-Handling (CH) Techniques• Separation of objective and constraints• Stochastic Ranking (Runarsson & Yao, TEC, Sept 2000)• Co-evolution methods (Coello, 2000a)• Multi-objective optimization techniques (Coello, 2000b; MezuraMontes & Coello, 2002;… )• Feasible solution search followed by optimization of objective(Venkatraman & Gary Yen, 2005)• …
• While most CH techniques are modular (i.e. we can pick one CH techniqueand one search method independently), there are also CH techniques
embedded as an integral part of the EA.

Constraint Handling in DE¾

Superiority of Feasible (SF)Among Xi and Xj, Xi is regarded superior to Xj if :oBoth infeasible &υ( X i ) < υ( X j )push infeasible solutions to feasible regionoBoth feasible & f(Xi ) < f(Xj) (minimization problems)
improves overall solutionoXi - feasible & Xj – infeasible

Constraint Handling in DE¾

Self-adaptive Penalty
F(X)=d(X) + p(X)d(X ) =f "(X ) =

υ ( X ),f " ( X ) 2 + υ ( X ) 2 , otherwisef ( X ) − f min
f max − f min

M (X ) =ooooif r f = 0

p( X ) = (1 − r f ) M ( X ) + r f N ( X )# feasible individuals
f min , f max - min. & max. of f ( X )rf =irrespective of feasibility
population size0,
if r f = 0
υ ( X ), otherwise

N(X ) =

0,
if X is feasible"f ( X ), if X is infeasible

Amount of penalties - controlled by # of feasible individuals present
Few feasible – high penalty added to infeasible individuals with highconstraint violation.
More feasible – high penalty added to feasible individuals with high fitness
valuesSwitch - more feasible - optimal solution

Constraint Handling in DE¾

Epsilon Constraint (EC)oRelaxation of constraints is controlled by ε parameteroHigh quality solutions for problems with equality constraints

ε (0) = υ ( X θ )X θ - top θ th individual in initial population (sorted w. r. t. υ )ε (k ) =ε (0) 1 −
0,

o

k
Tc

cp

,

0 < k < Tck ≥ TcThe recommended parameter settings are

Tc ∈ [0.1Tmax ,0.8Tmax ]cp ∈ [2, 10]

Constraint Handling in DE¾ Stochastic Ranking (SR)o Balances between objective and υ stochastically (low computational cost)
Basic form of SR

If (no constraint violation or rand < p f )Rank based on the objective value only
else
Rank based on the constraint violation onlyend

Ensemble of Constraint Handling Techniques (ECHT)¾No free lunch theorem (NFL)¾Each constrained problem is unique(feasible /search space, multi-modality and nature of constraint functions)¾Evolutionary algorithms are stochastic in nature.
(same problem & algorithm – diff. constraint handling methods - evolution paths
can be diff.)¾Diff. stages– Diff. constraint handling methods effective(feasible/ search space, multi-modality, nature of constraints, chosen EA)¾To solve a particular problem - numerous trial-and-error runs
(suitable constraint handling technique and to fine tune associated parameters)
R. Mallipeddi and P. N. Suganthan, Ensemble of Constraint Handling Techniques, IEEE Transactions on
Evolutionary Computation, Vol. 14, No. 4, pp.561-579, Aug. 2010.

ECHT: MOTIVATION• Therefore, depending on several factors such as the ratio between feasible search
space and the whole search space, multi-modality of the problem, nature ofequality / inequality constraints, the chosen EA, global exploration/local
exploitation stages of the search process, different constraint handling methods
can be effective during different stages of the search process.
• Hence, solving a particular constrained problem requires numerous trial-and-error
runs to choose a suitable constraint handling technique and to fine tune theassociated parameters. Even after this, the NFL theorem says that one well tuned
method may not be able to solve all problems instances satisfactorily.

-76-

ECHT: MOTIVATION• Each constraint handling technique has its own population and parameters.
• Each population corresponding to a constraint handling method produces its
offspring.
• The parent population corresponding to a particular constraint handling method
not only competes with its own offspring population but also with offspring
population of the other constraint handling methods.
• Due to this, an offspring produced by a particular constraint handling method
may be rejected by its own population, but could be accepted by the populationsof other constraint handling methods.
-77-

ECHT: Flowchart
INITIALIZE POPULATIONS & PARAMETERS ACCORDING TO EP RULESAND EACHCH ( i = 1,..., 4 ) RULES

i

POP1
PAR1

POP2
PAR2

POP4
PAR4

POP3
PAR3

EVALUATE OBJECTIVE & CONSTRAINT FUNCTIONS OF ALL POPULATIONSINCREASE NUMBER OF FUNCTION EVALUATIONS (nfeval)

nfeval ≤ Max_FEs

STEP 1

STEP 2

NO
STOP

YES
UPDATE THE PARAMETERS OF EACH POPULATION CORRESPONDING TO
EACH CONSTRAINT HANDLING METHOD CH i ( i = 1,..., 4 )PRODUCE OFFSi FROM PARi BY EP MUTATION STRATEGIES
OFFS1

OFFS2

COMBINE POPULATIONi WITH ALL OFFSPRING
POP2
OFFS1
OFFS2
OFFS3
OFFS4

POP2

STEP 5

STEP 6
POP4
OFFS1
OFFS2
OFFS3
OFFS4

POP3
OFFS1
OFFS2
OFFS3
OFFS4

SELECT POPULATIONS OF NEXT GENERATION ACCORDING TO THE
RULES OF EP & C H ( i = 1,...,4 )i
POP1

STEP 4

OFFS4

OFFS3

EVALUATE OBJECTIVE & CONSTRAINT FUNCTIONS OF ALL OFFSPRING
INCREASE NUMBER OF FUNCTION EVALUATIONS (nfeval)

POP1
OFFS1
OFFS2
OFFS3
OFFS4

STEP 3

POP4

POP3

-78-

STEP 7

ECHT¾Efficient usage of function calls(evaluation of objective / constraint functions is computationally expensive)¾Offspring of best suited constraint handling technique survive(For a search method and problem during a point in the search process, theoffspring population produced by the population of the best suited constraint
handling method dominates and enters other populations. In subsequent
generations, these superior offspring will become parents in other populations too)

¾No trial and error search¾Performance of ECHT can be improved by selecting diverse andcompetitive constraint handling methods(If the constraint handling methods in ensemble are similar in nature populations
associated may lose diversity and the search ability of ECHT may be deteriorated)
-79-

ECHT
• Therefore, ECHT transforms the burden of choosing a particular constraint
handling technique and tuning the associated parameter values for a particular
problem into an advantage.
• If the constraint handling methods selected to form an ensemble are similar innature then the populations associated with each of them may lose diversity andthe search ability of ECHT may be deteriorated.
• Thus the performance of ECHT can be improved by selecting diverse andcompetitive constraint handling methods.
-80-

ECHT: Implementation• The constraint handling methods used in the ensemble are
1. Superiority of Feasible (SF)
2. Self-Adaptive penalty (SP)
3. Stochastic Ranking (SR)
4. Epsilon Constraint handling (EC)
Detailed Results in:
R. Mallipeddi, P. N. Suganthan, “Ensemble of Constraint Handling Techniques”, IEEE
Trans. on Evolutionary Computation, Vol. 14, No. 4, pp. 561 - 579 , Aug. 2010-81-

ECHT: Results

Problem G01

Problem G10

Convergence Plots-82-

Variable reduction strategy (VRS)• Although EAs can treat optimization problems as black-boxes (e.g., academic
benchmarks), evidences showing that the exploitation of specific problem domain
knowledge can improve the problem solving efficiency.
• Technically, optimization can be viewed a process that an algorithm act on a problem.
To promote this process, we can¾ Enhance the capability of optimization algorithms,¾ Make use of the domain knowledge hidden in the problem to reduce its
complexity.
• We may think¾ Whether there exists general domain knowledge?
¾ How to use such knowledge?
Guohua Wu , Witold Pedrycz, P. N. Suganthan, R. Mallipeddi, “A Variable Reduction Strategy for
Evolutionary Algorithms Handling Equality Constraints,” Applied soft computing, 37 (2015): 774-786 83

VRS: Motivation• We utilize the domain knowledge of equality optimal conditions (EOCs) of
optimization problems.
¾ EOCs are expressed by equation systems;¾ EOCs have to be satisfied for optimal solutions;¾ EOCs are necessary conditions;¾ EOCs are general (e.g. equality constraints in constrained optimization andfirst derivative equals to zero in unconstrained optimization problem with
fist-order derivative).
• Equality constraints are much harder to be completely satisfied when an EA is
taken as the optimizer.
• The equality constraints of constrained optimization problems (COPs) are treatedas EOCs to reduce variables and eliminate equality constraints.

VRS: Motivation• In general, the constrained problems can be transformed into the following form:• Minimize

f (x), x = [ x1 , x2 ,..., xD ]gi (x) ≤ 0, i = 1,..., q

subjected to:h j (x) = 0, j = q + 1,..., m
q: number of inequality constraints & m-q : the number of equality constraints.
• When using EAs to solve COP, the equality constraints are converted into
inequality constraints as:| h j (x) | −ε ≤ 0• To obtain highly feasible solutions, we need small ε. However, evidences showthat a too small ε makes it harder to find feasible solutions, let alone highquality ones.
-85-

VRS: Implementation
Assume Ω j denotes the collection of variables involved in equality constraint h j ( X ) = 0

From h j ( X ) = 0 ( 1 ≤ j ≤ m ), if we can obtain a relationshipxk = Rk , j ({xl | l ∈ Ω j , l ≠ k})xk can be actually calculated by relationship Rk , j and the values of variables in {xl | l ∈ Ω j , l ≠ k}Moreover, equality constraint h j ( X ) is always satisfied.
As a result, both h j ( X ) and xk are eliminated.
86

VRS: Implementation• Some essential concepts:¾ Core variable(s): The variable(s) used to represent other variables in termsof the variable relationships in equality constraints.
¾ Reduced variable(s): The variable(s) expressed and calculated by corevariables.
¾ Eliminated equality constraint(s): The equality constraint(s) eliminatedalong with the reduction of variables due to full satisfaction by all solutions.
The aim of the variable reduction strategy is to find a set of corevariables with minimum cardinality, such that maximum number of equality
constraints and variables are reduced.
87

VRS: Implementation

Variable reduction operate88VRS: Implementation• Naïve example, considering:
min x12 + x2 2
x1 + x2 = 2
0 ≤ x1 ≤ 5, 0 ≤ x2 ≤ 5• We can obtain the variable relationship x2 = 2 − x1 and substituteit into original problem, then we get
min 2 x12 − 4 x1 + 4
0 ≤ x1 ≤ 2
89

VRS: Implementation• Solution space before and after the variable reduction process
4
3.8
3.6
3.4

f

3.2
3
2.8
2.6
2.4
2.2
2

(a) Original solution space

0

0.5

1
x1

1.5

2

(b) Solution after VRS.

VRS: Implementation91

VRS: Implementation• A formal method automatically reducing linear equality constraint and variables.
• Matrix form of linear equality constraint• Expand it and we get

AX = b

a11 x1 + a12 x2 +  + a1n xn = b1
a21 x1 + a22 x2 +  + a2 n xn = b2
am1 x1 + am 2 x2 +  + amn xn = bm

m<n• We can transform the expanded form into

a11 x1 + a12 x2 +  + a1m xm = b1 − ( a1,m +1 xm +1 + a1,m + 2 xm + 2 +  + a1,n xn )a21 x1 + a22 x2 +  + a2 m xm = b2 − ( a2,m +1 xm +1 + a2,m + 2 xm + 2 +  + a2,n xn )

am1 x1 + am 2 x2 +  + amm xm = bm − ( am ,m +1 xm +1 + am ,m + 2 xm + 2 +  + am ,n xn )• Let

a11  a1m
A′ =   
am1  amm

• We haveb1 − ( a1,m +1 xm +1 + a1,m + 2 xm + 2 +  + a1,n xn )x1
X′=

A′X ′ = b′

x2

xm

b′ =

b2 − ( a2,m +1 xm +1 + a2,m + 2 xm + 2 +  + a2,n xn )bm − ( am ,m +1 xm +1 + am ,m + 2 xm + 2 +  + am ,n xn )X ′ = ( A′)−1 b′

X ′ is reduced and all linear equality constraints are eliminated.

VRS: Results• Impact of VRS on the number of variables and equality constraints for
Benchmark COPs

ProblemOriginal COP COP after ECVRS
10
Variables9g03
Equality Const. 1
04
Variables1g05
Equality Const. 30
Variables21
g11
Equality Const. 1
0
Variables
52
g13
Equality Const. 30
Variables
107g14
Equality Const. 30
Variables32
g15
Equality Const. 1
0
Variables
62
g17
Equality Const. 40
Variables
72
g21
Equality Const. 5
0
Variables223
g22
Equality Const. 19
0
Variables
9
5
g23
94
Equality Const. 4
0

VRS: Results
ECHT-DEECVRS
Best-1.0005-1.0000
g03 Mean-1.0005-1.0000
Worst-1.0005-1.0000
Std
2.3930e-10 2.1612e-16
Violation 3.6892e-04 0.0
Best5.1265e+03 5.1265e+03
g05 Mean
5.1265e+03 5.1265e+03
Worst
5.1265e+03 5.1265e+03
Std
2.0865e-12 9.33125e-13
Violation 3.0543e-04 0.0
Best7.4990e-01 7.5000e-01
g11 Mean7.4990e-01 7.5000e-01
Worst
7.4990e-01 7.5000e-01
Std1.1390e-16 0.0
Violation 1.0989e-04 0.0
Best5.3942e-02 5.3949e-02
g13 Mean
1.3124e-01 5.3949e-02
Worst
4.4373e-01 5.3949e-02
Std1.5841e-01 6.3675e-18
Violation 3.9935e-04 0.0
Best-4.7765e+01 -4.7761e+01
g14 Mean-4.7765e+01 -4.7761e+01
Worst-4.7765e+01 -4.7761e+01
Std
2.1625e-05 1.6703e-14
Violation 2.9212e-04 0.0

Problems

ECHT-DEECHT-EP

ECHT-EP-ECVRS-1.0005-1.0000-1.0005-1.0000-1.0000-1.0004
1.6026e-05 8.7721e-14
2.6684e-04 0.0
5.1265e+03 5.1265e+03
5.1265e+03 5.1265e+03
5.1265e+03 5.1265e+03
2.0212e-07 9.3312e-13
4.6534e-04 0.0
7.4990e-01 7.5000e-01
7.4990e-01 7.5000e-01
7.4990e-01 7.5000e-01
1.1390e-16 0.0
1.0000e-05 0.0
5.3942e-02 5.3949e-02
5.3942e-02 5.3949e-02
5.3942e-02 5.3949e-02
5.3942e-02 1.5597e-17
5.0444e-09 0.0-4.7761e+01 -4.7761e+01-4.7703e+01 -4.7761e+01-4.7405e+01 -4.7761e+01
7.8687e-02 2.9722e-12
2.9999e-04 0.0

SF-DE

SF-DE
-ECVRS-1.0005-1.0000-1.0005-1.0000-1.0000-1.00053.3013e-16 2.8816e-16
2.6631e-04 0.0
5.1265e+03 5.1265e+03
5.1265e+03 5.1265e+03
5.1265e+03 5.1265e+03
1.9236e-12 9.3312e-13
8.0598e-04 0.0
7.4990e-01 7.5000e-01
7.4990e-01 7.5000e-01
7.4990e-01 7.5000e-01
1.1390e-16 0.0
1.0539e-04 0.0
5.3942e-02 5.3949e-02
3.5288e-01 5.3949e-02
4.6384e-01 5.3949e-02
1.4745e-01 7.9594e-18
1.0000e-04 0.0-4.7765e+01 -4.7761e+01-4.7765e+01 -4.7761e+01-4.7765e+01 -4.7761e+01
1.8728e-14 3.7355e-14
3.0000e-004 0.0

EC-EP

EC-EP
-ECVRS-1.0005-1.0000-1.0000-1.0005-1.0000-1.0005
1.4728e-06 2.8658e-16
1.0000e-04 0.0
5.1265e+03 5.1265e+03
5.1265e+03 5.1265e+03
5.1266e+03 5.1265e+03
3.2214e−02 9.3312e-13
6.0558e-04 0.0
7.4990e-01 7.5000e-01
7.4990e-01 7.5000e-01
7.4990e-01 7.5000e-01
2.1630e-09 0.0
9.9999e-05 0.0
5.4137e-02 5.3949e-02
5.4375e-02 5.3949e-02
5.6346e-02 5.3949e-02
6.3439e-03 1.2834e-17
2.7237e-02 0.0-4.7765e+01 -4.7761e+01-4.5142e+01 -4.7706e+01-4.3762e+01 -4.7361e+01
7.3651e-01 2.1542e-02 95
2.9999e-04 0.0

Violation 2.9212e 04 0.0
Best9.6172e+02 9.6172e+02
g15 Mean 9.6172e+02 9.6172e+02
Worst 9.6172e+02 9.6172e+02
Std
5.8320e-13 1.1664e-13
Violation 1.9995e-04 0.0Best8.8535e+03 8.8535e+03
g17 Mean 8.8535e+03 8.8535e+03
Worst 8.8535e+03 8.8535e+03
Std
3.7324e-12 1.8662e-12
Violation 3.2953e-04 0.0Best1.9372e+02 1.9379e+02
g21 Mean 1.9984e+02 1.9379e+02
Worst 3.1604e+02 1.9379e+02
Std2.7351e+01 2.8632e-12
Violation 4.0195e-04 0.0Best1.8857e+03 2.3637e+02
g22 Mean 1.0158e+04 2.3637e+02
Worst 1.7641e+04 2.3637e+02
Std
4.2890e+03 1.4580e-13
Violation 4.1562e+03 0.0-3.9072e+02 -4.0000e+02
Best
g23 Mean -3.6413e+02 -4.0000e+02
Worst -2.3426e+02 -4.0000e+02
Std
3.4129e+01 1.1664e-13
Violation 3.5951e-04 0.0

VRS:
Results
3.0000e 004 0.0
2.9999e 04 0.0
9.6172e+02 9.6172e+02
9.6172e+02 9.6172e+02
9.6172e+02 9.6172e+02
6.1830e-13 1.1664e-13
1.9999e-04 0.0
8.8535e+03 8.8535e+03
8.8535e+03 8.8535e+03
8.8535e+03 8.8535e+03
2.0301e-08 1.8662e-12
2.6943e-04 0.0
1.9372e+02 1.9379e+02
1.9498e+02 1.9379e+02
2.0661e+02 1.9379e+02
3.8129e+00 3.8765e-12
4.8585e-04 0.0
3.9184e+02 2.3637e+02
7.7786e+02 2.3637e+02
1.4844e+03 2.3637e+02
3.0970e+02 2.2875e-13
2.7186e+03 0.0-3.4556e+02 -4.0000e+02-3.0952e+02 -4.0000e+02-2.5807e+02 -4.0000e+02
2.5417e+01 4.8217e-09
1.7373e-04 0.0

2.9999e 04 0.0
9.6172e+02 9.6172e+02 9.6233e+02 9.6172e+02
9.6172e+02 9.6172e+02 9.6248e+02 9.6172e+02
9.6172e+02 9.6172e+02 9.6265e+02 9.6172e+02
5.8320e-13 1.1664e-13 7.3719e+01 1.1664e-13
2.0000e-04 0.0
2.1737e-01 0.0
8.8535e+03 8.8535e+03 9.1573e+03 8.8535e+03
8.8757e+03 8.8535e+03 9.1791e+03 8.8535e+03
8.9439e+03 8.8535e+03 9.2005e+03 8.8535e+03
3.8524e+01 1.8662e-12 1.2346e+01 1.8662e-12
1.7744e-04 0.0
3.1295e-04 0.0
1.9372e+02 1.9379e+02 1.9872e+02 1.9379e+02
2.0682e+02 1.9379e+02 2.3474e+02 1.9379e+02
3.2470e+02 1.9379e+02 2.7589e+02 1.9379e+02
4.0314e+01 6.8507e-10 2.6621e+01 3.8625e-129.9999e-05 0.0
3.0432e-03 0.0
3.9643e+03 2.3637e+02 2.2545e+03 2.3637e+02
1.3812e+04 2.3637e+02 1.2854e+04 2.3637e+02
1.9205e+04 2.3637e+02 1.6328e+04 2.3637e+02
5.0860e+03 7.3769e-14 3.2582e+03 1.9875e-13
1.3192e+04 0.0
4.156e+03 0.0-3.9158e+02 -4.0000e+02 −3.8625e+02 -4.0000e+02-2.4367e+02 -4.0000e+02 −3.4864e+02 -4.0000e+02-1.0004e+02 -4.0000e+02 −2.7235e+02 -4.0000e+02
1.9487e+01 0.0
2.3654e+01
1.7496e-13
962.5635e-02 0.0
8.8827e-02 0.0

VRS: Results
Number of function objective evaluations required by each EA with or without
ECVRS to reach the near optimal objective function values
Problem
s
g03
g05
g11
g13
g14
g15
g17
g21
g22
g23

ECHT-DEECHT-DE- ECVRS ECHT-EP
ECHT-EP -ECVRS
FEs
Suc FEs
Suc
FEs
Suc FEs
Suc
80160 25 16630
25
2511828 25 18540
010976 25 400
2511961 25 400
250036810 25 400
2512020 25 400
25089300 18 840
2512660 25 860
25
013959 25 23490
2586720 25 39250
25010346 25 400
2512020 25 400
250010834 25 400
2511564 25 400
250010750 22 6160
25
14856 22 8280
25
0
0
---0
660
25
---0
1860
25
---0
28060
25
---0
37200
25

SF-DE
FEs
22570

SF-DE -ECVRS
Suc FEs
Suc
25
25 6955

EC-EP
FEs
10250

EC-EP -ECVRS
Suc FEs
Suc
25 8555
25

27290

25

200

25

12290

25

400

25

13090

25

200

25

25

400

25

14055
0
46440

5

620

25

12141
0
56000

15

1040

25

25

23650

25

26750

25

200

40860

25

25870
-------

25

82385

25

25

14147
0
----

0

400

25

200

25

----

0

400

25

20

18800

25

13556

12

9580

25

0
0

455
650

25
25

-------

0
0

4526
24630

25
25

97

VRS: Results
Illustration of the convergence process of each EA on the benchmark COPs.
-0.5
ECHT-DEECHT-DE-ECVRS
SF-DE
SF-DE-ECVRS
ECHT-EP
ECHT-EP-ECVRS
EC-EP
EC-EP-ECVRS

-0.55
-0.6

Fitness

-0.65
-0.7
-0.75
-0.8
-0.85
-0.9
-0.95
-1
0

5

10
Function Evaluations

15
x 10

4

VRS: Remarks• It is generally impossible to exactly solve the equation systems
expressing equality optimal conditions of an problem;• We are not to pursue the exact solution of equality optimal
conditions, but to utilize equality optimal conditions to derivevariable relationships and exploit them to reduce the problem
complexities (e.g., reduce variables and eliminate equality
constraints);• General and theoretical approaches to deal with complex andnonlinear equality optimal conditions are needed.

Overview
I.

Introduction to Real Variable Optimization & DE

II. Future of Real Parameter Optimization
III. Single Objective Optimization
IV. Multimodal Optimization
V. Dynamic Optimization
VI. Multi-objective Optimization
VII. Large Scale Optimization
VIII.Constrained Optimization

100

Dynamic Optimization with DE
Optima of the problem to be solved shift with time.
Examples:1) Price Fluctuations
2) Stochastic arrival of new tasks in a scheduling problem
3) Machine breakdown/maintenance during process control
4) Optimal routing with changing traffic conditions

An EA should track the changing optima as closely as possible.
T. T. Nguyen, S. Yang, J. Branke, "Evolutionary dynamic optimization: A survey ofthe state of the art", Swarm and Evolutionary Computation, Vol. 6, Oct 2012, pp. 1–24.
101Requirements for adopting an EA in Dynamic Environments¾ Boost-up diversity after an environmental change (e.g. hypermutation, variablelocal search).
¾ Maintain diversity throughout the runs with a hope that a well spread-out
population can cope with dynamic changes more easily (e.g. random immigrants,
thermodynamic GA).
¾ Memory based approaches (particularly useful when the optimum repeatedly
returns to its previous locations).
¾ Multi-population approach – Use of different subpopulations that can maintain
information about several promising regions of the search space – act as a
distributed and adaptive memory (e.g. multinational GAs)

Reuse of information from previous generations may help is the environmental
change is not too severe.
102

The GDBG System Benchmarks-proposed under IEEE CEC 2009 Competition and Special Session on Dynamic optimization&

DOP expression: F = f ( X , ϕ , t ),Parametric variation to introduce dynamicity: ϕ (t + 1) = ϕ (t ) ⊕ ∆ϕ ,GDBG change types

CEC’09 Dynamic Optimization Benchmark
Functions∆φ = α ⋅ || φ || ⋅r ⋅ φ severity ,T1

Small step:T2

Large step: ∆φ =|| φ || ⋅(α ⋅ sign(r ) + (α max − α ) ⋅ r ) ⋅ φseverity ,T3

F1

Rotation peak function

Random:∆φ = N (0,1) ⋅ φ severity ,F2Composition of Sphere functions

T4

Chaotic:φ (t + 1) = A ⋅ (φ (t ) − φ min ) ⋅ (1 − (φ (t ) − φ min ) / || φ ||),

F3

Composition of Rastrigin’s functions

T5

Recurrent:φ (t + 1) = φ min + || φ || (sin( 2π t + ϕ ) + 1) / 2,

F4

Composition of Griewank’s functions

T6

Recurrent with noise:

F5

Composition of Ackley’s functions

F6

Hybrid Composition function

T7

P

2π
φ (t + 1) = φ min + || φ || (sin( t + ϕ ) + 1) / 2 + N (0,1) ⋅ noisy severity ,P

Dimensional change: D(t + 1) = D(t ) + sign ⋅ ∆D,

103

The GDBG System Benchmarks (Contd..)(b) Example plot of Composition of Spherefunctions (F2) [inverted](c) Example plot of Composition of
Rastrigin’s function (F3) [inverted](e) Example plot of Composition of Ackley’sfunction (F5) [inverted](f) Example plot of Hybrid Composition
function (F6) [inverted](a) Example plot of Rotation Peak function (F1)(d) Example plot of Composition of
Griewank’s function (F4) [inverted]104Performance Metrics:
Mean offline error: eoff =

1

where

rrks =&f ( X best (r , k , s ))&*,f ( X (r , k ))&f ( X * (r , k ))&,f ( X best (r , k , s ))K

where R = no. of runs, K = no. of environmental
changes per run andlast∑ ∑ er , k ,R × K r =1 k =1

Standard deviation: STD =Mark obtained by analgorithm in i-th test case:R

last∑ rR=1 ∑ kK=1 (er , k − eoff )R × K −1

wi R K
marki =∑∑
R × K r =1 k =1

&
&*
last
er , k = f ( X best ( r , k )) − f ( X ( r , k )),rrklast
1 S
1 + .∑ (1 − rrks )S s =1for f = F1,
for f ∈ F 2, F 3, F 4, F 5, F 6.

Overall performance of an algorithm calculated as: performance = 100 ×49∑ mark .
i =1

i

105

Overview
I.

Introduction to Real Variable Optimization & DE

II. Future of Real Parameter Optimization
III. Single Objective Optimization
IV. Multimodal Optimization
V. Dynamic Optimization
VI. Multi-objective Optimization
VII. Large Scale Optimization
VIII.Constrained Optimization

106

Non-Domination Sorting• Multi-objective optimization
Minimize:F ( x) = ( f ( x), f ( x),..., f ( x))T1

Subject to:2mxiL ≤ xi ≤ xiU• Non-domination sorting: x1 dominates x2 if
The solution x1 is no worse than x2 in all objectives.
The solution x1 is strictly better than x2 in at least one objective.
• Most current MOEAs are based on non-domination sorting. The
standard DE algorithm (i.e. xover & mutation) is used withdifferent MOEA-tuned selection mechanisms.
• Recently, decomposition method was proposed which
decomposes an MOP into a large number of single objective
problems.
A. Zhou, B-Y. Qu, H. Li, S-Z. Zhao, P. N. Suganthan, Q. Zhang, "Multiobjective
Evolutionary Algorithms: A Survey of the State-of-the-art", Swarm andEvolutionary Computation, Vol. 1, No. 1, pp. 32-49, Mar 2011.
107

Techbycheff Approach in MOEA/D
In this approach, the scalar optimization problems are in
the form:

where m is the number of objectives. λ is a set of well-spreadweight vectors (λ1… λN) and zi* is the reference/best fitness ofeach objective. The problem of approximation of the PF is
decomposed into N scalar optimization subproblems. Solvethese N subproblems one by one. The distribution of final
solutions could be uniform if g( ) and λ are properly chosen.
108

Neighborhood relationship in MOEA/D• These sub-problems are related to each other:If λi and λj are close, g(x,λi) and g(x,λj) areneighbors. Neighboring problems should have
similar solutions.
• N agents are used for solving these N subproblems.

X1

X2

XN

Min
g(x,λ1)Ming(x,λ2)Ming(x,λN)• During the search, neighboring agents collaborate witheach other.
109

MOEA/D framework• Agent i records xi, the best solution found so far forthis particular subproblem.
• At each generation, each agent i does the following:
9 Select several neighbors and obtain their bestsolutions.
9 Apply genetic operators (mutation & crossover in
MOEA/D-DE) on these selected solutions andgenerate a new solution y’.
9 Apply single objective local search on y’ to optimize
its objective g(x,λi) and obtain y.
9 Replace xi by y if g(y,λi)<g(xi,λi).
9 If not replaced, let one of its neighbors replace its
best solution by y, if y is better than the current bestsolution (measured by its own weighted objective).
110

ENS-MOEA/D• For effective performance of MOEA/D, neighborhood size(NS) parameter has to be tuned:– A large NS promotes collaboration among dissimilar subproblems, which
advances the information exchange among the diverse subproblems, andthus it speeds up the convergence of the whole population– While a small NS encourages combination of similar solutions and is good
for local search in a local neighborhood, which maintains the diversity for
the whole population.

• However, in some cases, a large NS can also beneficial fordiversity recovery; while a small NS is also able tofacilitate the convergence:– For instance, during the evolution, some subproblems may gettrapped in a locally optimal regions. In order to force those
subproblems escape from the premature convergence, a large NS
is required for the exploration.
– On the other hand, if the global optima area is already found, a111
small NS will be favorable for local exploitation.

ENS-MOEA/D
Neighborhood sizes (NS) are a crucial control parameter in MOEA/D.
An ensemble of different neighborhood sizes (NSs) with online selfadaptation is proposed (ENS-MOEA/D) to overcome the difficulties
such as1) tuning the numerical values of NS for different problems;2) specifications of appropriate NS over different evolution stages
when solving a single problem.

S. Z. Zhao, P. N. Suganthan, Q. Zhang, "Decomposition BasedMultiobjective Evolutionary Algorithm with an Ensemble of
Neighborhood Sizes", IEEE Trans. on Evolutionary Computation, DOI:
10.1109/TEVC.2011.2166159, 2012.
112

ENS-MOEA/DIn ENS-MOEA/D, K fixed neighborhood sizes (NSs) are used as apool of candidates. During the evolution, a neighborhood size will
be chosen for each subproblem from a pool based on thecandidates’ previous performances of generating improved
solutions. In ENS-MOEA/D, the certain fixed number of previous
generations used to store the success probability is defined as
the Learning Period (LP). At the generation G>LP-1 , theprobability of choosing the kth (k = 1, 2, , K) NS is updated by:113

ENS-MOEA/D Experimental results• ENS-MOEA/D is tested on the 10 unconstrained test instances in
CEC 2009 MOEA Competition which includes two and threeobjective problems (Latest benchmark on MO problems).
• The IGD performance measure is used as in the CEC 2009 MOEA
competition.
• The four different NSs for the two-objective problems are 30, 60, 90
and 120, where NS=60 is the original parameter setting in the
MOEA/D in the NSs for the three-objective problems are 60, 80, 100,
120 and 140, where 100 is the original parameter setting for NS in
the MOEA/D.

114

ENS-MOEA/D Experimental results• We conducted a parameter sensitivity investigation of LP
for ENS-MOEA/D using four different values (10, 25, 50 and75) on the 10 benchmark instances. By observing the meanof IGD values over 25 runs we can conclude that the LP is
not so sensitive to most of the benchmark functions, and it
is set as LP=50.
• The mean of IGD values over 25 runs among all the variantsof MOEA/D with different fixed NS and ENS-MOEA/D are
ranked. Smaller ranks, better performance.

115

116

Overview
I.

Introduction to Real Variable Optimization & DE

II. Future of Real Parameter Optimization
III. Single Objective Optimization
IV. Multimodal Optimization
V. Dynamic Optimization
VI. Multi-objective Optimization
VII. Large Scale Optimization
VIII.Constrained Optimization

118

Large Scale Optimization• Optimization algorithms perform differently whensolving different optimization problems due to their
distinct characteristics. Most optimization algorithms
lose their efficacy when solving high dimensional
problems. Two main difficulties are:
– The high demand on exploration capabilities of the
optimization methods. When the solution space of a problem
increases exponentially with increasing dimensions, more
efficient search strategies are required to explore all promisingregions within a given time budget.
– The complexity of a problem characteristics may increase withincreasing dimensionality, e.g. unimodality in lower
dimensions may become multi-modality in higher dimensions
for some problems (e.g. Rosenbrock’s)
119Large Scale Optimization• Due to these reasons, a successful searchstrategy in lower dimensions may no longer becapable of finding good solutions in higher
dimension.
• Four LSO algorithms based on DE with the best
performances – MOS, jDElscop, SaDE-MMTS andmDE-bES• From the special issue of the Soft Computing
Journal on Scalability of Evolutionary Algorithms
and other Meta-heuristics for Large Scale
Continuous Optimization Problems.
120

SaDE-MMTS – Two levels of selfadaptation
SaDE benefits from the self-adaptation of trial vector generation
strategies and control parameter adaptation schemes by learningfrom their previous experiences to suit different characteristic of the
problems and different search requirements of evolution phases.
 Every generation, a selection among the JADE mutation strategy
with two basic crossover operators (binomial crossover andexponential crossover) as well as no crossover option is also
adaptively determined for each DE population member based on theprevious search experiences.

S. Z. Zhao, P. N. Suganthan, and S. Das, “Self-adaptive differential evolution
with multi-trajectory search for large scale optimization”, Soft Computing,15, pp. 2175-2185, 2011.

121

SaDE-MMTS – Two levels of selfadaptation
Low Level Self-adaptation in MMTS:
An adaptation approach is proposed to adaptively
determine the initial step size parameter used in the
MMTS. In each MMTS phase, the average of all
mutual dimension-wise distances between current
population members (AveDis) is calculated, one of
the five linearly reducing factors (LRF) from 1 to 0.1,
5 to 0.1, 10 to 0.1, 20 to 0.1 and 40 to 0.1 is selectedbased on the performance, and this LRF is applied
to scale AveDis over the evolution.

122

SaDE-MMTS
High Level Self-adaptation between SaDE & MMTS:
The MMTS is used periodically for a certain
number of function evaluations along with SaDE,
which is determined by an adaptive manner.
At the beginning of optimization procedure, theSaDE and the MMTS are firstly conductedsequentially within one search cycle by using thesame number of function evaluations. Then the
success rates of both SaDE and MMTS arecalculated. Subsequently, function evaluations are
assigned to SaDE and MMTS in each search cycle
proportional to the success rates of both searchmethods.

123

Experiments Results• Algorithms were tested on 19 benchmark functions
prepared for a Special Issue on Scalability of
Evolutionary Algorithms and other Metaheuristics
for Large Scale Continuous Optimization Problems.
(http://sci2s.ugr.es/eamhco/CFP.php)• The benchmark functions are scalable. The
dimensions of functions were 50, 100, 200, 500, and1000, respectively, and 25 runs of an algorithm wereneeded for each function.
• The optimal solution results, f (x*), were known for
all benchmark functions.

124mDE-bES• We boost the population diversity while preserving
simplicity by introducing a multi-population DE to solve
large-scale global optimization problems– the population is divided into independent subgroups, each withdifferent mutation and update strategies– A novel mutation strategy that uses information from either thebest individual or a randomly selected one is used to produce
quality solutions to balance exploration and exploitation.
• Mostafa Z. Ali, Noor H. Awad, Ponnuthurai N. Suganthan “Multipopulation differential evolution with balanced ensemble ofmutation strategies for large-scale global optimization” Appl.
Soft Comput. 33: 304-327 (2015)125mDE-bES• At the end of each epoch, individuals between thesubgroups are exchanged to facilitate informationexchange at a slow pace.
• The only link between these subgroups is the sharing ofindividuals’ experiences through the migration ofindividuals at constant intervals to restore balance of thesearch direction affording a higher probability ofescaping basin of attraction of locally optimal solutions.

126

Migration phase
The structure for the migration has several possibilities

Migration with ring topology.
Migration with custom neighborhood topology.

Migration with complete net topology (free form).

127

Choice of mutation strategies
for groups in mDE-bES• DE/rand/1/exp• DE/current-to-best/1/exp• DE/best/1/exp• Modified base vector in mutation strategy– This modified mutation uses one of two
schemes based on the difference between
current best Xbest(t) and the best from theprevious generation Xbest(t − 1).
128Experiments Results• Algorithms were tested on 19 benchmark functions
prepared for a Special Issue on Scalability of
Evolutionary Algorithms and other Metaheuristics
for Large Scale Continuous Optimization Problems.
(http://sci2s.ugr.es/eamhco/CFP.php)• The benchmark functions are scalable. The
dimensions of functions were 50, 100, 200, 500, and1000, respectively, and 25 runs of an algorithm wereneeded for each function.
• The optimal solution results, f(x*), were known for
all benchmark functions.

129

Overview
I.

Introduction to Real Variable Optimization & DE

II. Future of Real Parameter Optimization
III. Single Objective Optimization
IV. Constrained Optimization
V. Dynamic Optimization
VI. Multi-objective Optimization
VII. Large Scale Optimization
VIII.Multimodal Optimization
S. Das, S. Maity, B-Y Qu, P. N. Suganthan, "Real-parameter evolutionary
multimodal optimization — A survey of the state-of-the-art", Vol. 1, No.
2, pp. 71-88, Swarm and Evolutionary Computation, June 2011.
130

Niching and Multimodal Optimization with DE•••

Traditional evolutionary algorithms with elitist selection are suitable to locate asingle optimum of functions.
Real problem may require the identification of optima along with several optima.
For this purpose, niching methods extend the simple evolutionary algorithms
by promoting the formation of subpopulations in the neighborhood of thelocal optimal solutions.
Global EA

Niching EA
131

Multi-modal Optimization Methods¾ Some existing Niching TechniquesoSharingo

Clearingo

CrowdingoRestricted Tournament SelectionoClusteringoSpecies BasedoAdaptive Neighborhood Topology based DE

B-Y Qu, P N Suganthan, J J Liang, "Differential Evolution with Neighborhood
Mutation for Multimodal Optimization," IEEE Trans on Evolutionary
Computation, Doi: 10.1109/TEVC.2011.2161873, 2012.
132

Adaptive Neighborhood Mutation Based DE

Compared with about 15 other algorithms on about 27 benchmark problems
including IEEE TEC articles published in 2010-2012 period.
B-Y Qu, P N Suganthan, J J Liang, "Differential Evolution with Neighborhood Mutation for
Multimodal Optimization," IEEE Trans on Evolutionary Computation, Doi:
133
10.1109/TEVC.2011.2161873, Oct. 2012.

Classical Speciation Technique
Step 1: Initialize at random a population of size N within the range of [XLower, XUpper] in D dimensions
Step 2: Compute Euclidean distance for all members
distij=√∑(xi,j)2, j=1, …D, i=1,2…N
Step 3: Sort all individuals in descending order of fitness
Step 4:Set species number S=1

WHILE sorted population is not empty
1. Identify the fittest member from sorted population and remove it as the species seed for species number S.
2. Mark all members within the speciation radius rspecies as members of the same species as S
3. Remove the speciated members from the sorted population
4. Check the number of members within species. If the specie size exceeds that of specified, remove the excess members in order of weakest
fitness. On the other hand if insufficient members are in the same species, randomly initialize members within rspecies of the species seed.
5. Increment S until all members classified into species.
END WHILE
Step 5:

Perform normal DE process within each species

Step 6:

Repeat Steps 2 to 5 until a termination criterion• Fixed speciation radius, Rspecies• Removes population members from niches without regard for local fitness
environment

Arithmetic Recombination

Search region covered by line Arithmetic Recombination for
K= [-0.5, 0.5, 1.5]
135

Neighborhood Arithmetic Recombination-basedSpeciation DE (based on DoI: .
10.1109/TCYB.2015.2394466)• Classical niching and clustering methods highly sensitive toparameter settings and initial population distribution in addition
to niche size
– e.g Speciation radius Rspecies, Fitness-sharing radius Rsharing, Crowding factor, CF• Difficult to separate the initial population into niches in unevenand rugged regions,– i.e when niching radius contains more than one peak.

• A guaranteed way to identify separate niches: detecting fitness
valleys and peaks• Arithmetic Recombination interpolates and extrapolates between
neighbors from niche centers (local fittest member)• Self-adaptive generalization across different fitness terrains• Reduction of multiple niching parameters to only neighborhood
136
popln size, mInterpolating and Extrapolating members using
Arithmetic RecombinationX – popln member ;Star: solutions generated Arith. Recomb.

Neighborhood Arithmetic
Recombination-based Speciation DE
Step 1: Initialize a randomly distributed population of size N within the range of [XLower, XUpper] in D dimensions
Step 2: Compute Euclidean distance for all members
distij=√∑(xi,j)2, j=1, …D, i=1,2…N
Step 3: Sort all individuals in descending order of their fitness values. This is the speciation pool.
Step 4:
Set niches number S=1
WHILE sorted population is not empty, execute steps 4.1 to 4.6:
1. Identify the fittest member (lbest) from speciation pool and remove it as the specie seed for specie number S.
2. Extract m nearest neighbors to the lbest from speciation pool for arithmetic recombination.
3. Detect the presence of fitness valleys and better fitness between lbest and the neighbors in the specie using 0<K<1.
a) Reject neighbors that are separated by fitness valleys from the lbest of the current specie. Rejected neighbors are
returned to the speciation pool.
b) Check for existence of better fitness between lbest and neighbors and store these as new members of the same
species
4. Explore regions beyond lbest and the remaining neighbors using K>1 and K<0. Solutions with K>1 are included into
the common speciation pool while K<0 are included in the current specie S. These solutions will be subjected to steps
4.3 & 4.4 in the next iteration.
5. Check the number of members within specie. If the population size exceeds that of specified, remove the excess
members in order of weakest fitness. On the other hand if insufficient members are in the same species, randomly
initialize members within Euclidean distance of the furthest specie member (or nearest non-specie neighbor) from thespecie seed.
6. Increment S until all members are classified into species.
END WHILE
Step 5:
Perform Ensemble-DE operations within every specie separately.
Step 6:
Repeat Steps 2 to 5 until a termination criterion.

S. Hui, P N Suganthan, “Ensemble and Arithmetic Recombination-Based Speciation Differential
Evolution for Multimodal Optimization,” IEEE T. Cybernetics, Online. 10.1109/TCYB.2015.2394466

Ensemble Parameters of EARSDE••••

Neighborhood size, m = 6
Scaling factor Fi ∈[0.3, 0.5, 0.9].
Crossover probability Ci ∈[0.1, 0.5].
Binomial Crossover•

Mutation Strategies
1. DE/rand/1
viG = xrand1,iG + F(xrand2,iG – xrand3,iG)
2. DE/ best/1
viG = xbestG + F(xrand1,iG – xrand2,iG)
Arithmetic Recombination scaling factor,
K = [-0.5, 0.5, 1.5] with additive variable, ±∆∆ ϵ [0, 0.1]

•
•

139

Speciation process in EARSDE in 2D Vincent problem•••

Initial population - ‘X’, initial pop-size = 60, neighborhood size = 6
Fittest regions are represented by the darkest contours.
Fittest member is first selected as the species seed for AR operations

140

Speciation process in EARSDE in 2D Vincent problem

New peakdiscovered

•
•
•
•

species seed is highlighted with a red square ‘□‘
5 nearest neighbors are highlighted with red circle ‘o’
AR (K=0.5) applied to check for any fitness valleys.
Midpoints represented with red plus signs ‘+’

141Speciation process in EARSDE in 2D Vincent problem

Randomly initialized
species members•••

Newly peaks survive to
evolve in next iteration

Existing neighbors of the species seed could not be grouped into the same species due tofitness valleys or doubled peaks
Random initialization executed around original species seed within 0.5 of the distance to142
the nearest neighbor separated by fitness valley.
New random members are represented by the red circles ‘●‘Speciation process in EARSDE in 2D Vincent problem

New peakdiscovered••

Next speciesseed

A neighbor rejected by the previous species now selected for speciation. Repeat process
Dotted black lines to indicate association to species
143

Speciation process in EARSDE in 2D Vincent problem

Next species
seed

•
•

New peaks (highlighted by a red square ‘□‘ with red plus signs ‘+’) would only
enter speciation process in the next iteration
Random members populated around new peaks.
144

THANK YOU
Q&A

145