Evolutionary Computation for Dynamic
Optimization Problems
Shengxiang Yang
Centre for Computational Intelligence
School of Computer Science and Informatics
De Montfort University, United Kingdom
Email: syang@dmu.ac.uk
http://www.tech.dmu.ac.uk/∼syang
Tutorial presented at the 2017 IEEE Congress on Evolutionary Computation(IEEE CEC 2017), Donostia-San Sebastian, Spain, 5-8 June, 2017
Copyright is held by the author/owner(s)Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

1 / 68

Presenter — Shengxiang Yang
Education and career history:
PhD, Northeastern University, China, 1999
Worked at King’s College London, University ofLeicester, and Brunel University, 1999-2012
Joined De Montfort University (DMU) as Professor in
Computational Intelligence (CI) in July 2012
Director of Centre for Computational Intelligence (CCI)

Research interests:
Evolutionary Computation (EC) and nature-inspired computation
Dynamic optimisation and multi-objective optimisation
Relevant real-world applications

Over 230 publications and £2M funding for research
AE/Editorial Board Member for 8 journals, including IEEE Trans Cybern,
Evol Comput, Inform Sci, Neurocomputing, and Soft Comput
Chair of two IEEE CIS Task Forces
EC in Dynamic and Uncertain Environments
Intelligent Network Systems
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

2 / 68

Centre for Computational Intelligence (CCI)
CCI (www.cci.dmu.ac.uk):
Mission: Developing fundamental theoretical and practical solutions toreal-world problems using a variety of CI paradigms
Members: 18 staff, several research fellows, 30+ PhDs, visiting researchers
Themes: EC, fuzzy logic, neural networks, data mining, robotics, game ...

Funding:
Research Councils/Charities: EPSRC, ESRC, EU FP7 & Horizon 2020,
Royal Academy of Engineering, Royal Society, Innovate UK, KTP,
Innovation Fellowships, Nuffield Trust, etc.
Government: Leicester City Council, DTI
Industries: Lachesis, EMDA, RSSB, Network Rail, etc.

Collaborations:
Universities: UK, USA, Spain, and China
Industries and local governments

Teaching/Training:
DTP-IS: University Doctor Training Programme in Intelligent Systems
MSc Intelligent Systems, MSc Intelligent Systems & Robotics
BSc Artificial Intelligence with Robotics

YouTube page: http://www.youtube.com/thecci
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

3 / 68

Outline of the Tutorial

Part I: Fundamentals
Introduction to evolutionary computation (EC)EC for dynamic optimization problems (DOPs): Concept and motivation
Benchmark and test problems
Performance measures

Part II: Approaches, Issues and Future WorkEC enhancement approaches for DOPs
Case studies
Relevant issues
Future work

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

4 / 68What Is Evolutionary Computation (EC)?

EC encapsulates a class of stochastic optimization algorithms, dubbed
Evolutionary Algorithms (EAs)
An EA is an optimisation algorithm that isGeneric: a black-box tool for many problems
Population-based: evolves a population of candidate solutions
Stochastic: uses probabilistic rules
Bio-inspired: uses principles inspired from biological evolution

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

5 / 68Design and Framework of an EA
Given a problem to solve, first consider two key things:
Representation of solution into individual
Evaluation or fitness function

Then, design the framework of an EA:
Initialization of population
Evolve the population
Selection of parents
Variation operators (recombination &mutation)
Selection of offspring into next
generation

Termination condition: a given numberof generations

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

6 / 68EC Applications

EAs are easy-to-use: No strict requirements to problems
Widely used for optimisation and search problems
Financial and economical systems
Transportation and logistics systems
Industry engineering
Automatic programming, art and music design......

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

7 / 68

EC for Optimisation Problems

Traditionally, research on EAs has focused on static problems
Aim to find the optimum quickly and precisely

But, many real-world problems are dynamic optimization problems(DOPs), where changes occur over time
In transport networks, travel time between nodes may change
In logistics, customer demands may change

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

8 / 68What Are DOPs?

In general terms, “optimization problems that change over time” arecalled dynamic problems/time-dependent problems⃗ t)
F = f (⃗x , φ,
⃗ parameter(s); t: time
– ⃗x : decision variable(s); φ:
DOPs: special class of dynamic problems that are solved online by analgorithm as time goes by

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

9 / 68

Why DOPs Challenge EC?

For DOPs, optima may move over time in the search space
Challenge: need to track the moving optima over time

DOPs challenge traditional EAs
Once converged, hard to escape from an old optimum

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

10 / 68

Why EC for DOPs?

Many real-world problems are DOPs
EAs, once properly enhanced, are good choice
Inspired by natural/biological evolution, always in dynamic environments
Intrinsically, should be fine to deal with DOPs

Many events on EC for DOPs recently

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

11 / 68

Relevant Events
Books (Monograph or Edited):
Yang & Yao, 2013; Alba et al., 2013; Yang et al., 2007; Morrison, 2004;
Weicker, 2003; Branke, 2002

PhD Theses:
Jiang, 2017; Mavrovouniotis, 2013; Helbig, 2012; du Plessis, 2012; Li,2011; Nguyen, 2011; Simoes, 2010

Journal special issues:
Neri & Yang, 2010; Yang et al., 2006; Jin & Branke, 2006; Branke, 2005

Workshops and conference special sessions:
EvoSTOC (2004–2017): part of Evo*ECiDUE (2004–2017): part of IEEE CEC
EvoDOP (’99, ’01, ’03, ’05, ’07, ’09): part of GECCOIEEE Symposium on CIDUE (2011, 2013-2017)
IEEE Competitions: within IEEE CEC’09, CEC’12 & CEC’14

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

12 / 68

Benchmark and Test DOPs

Basic idea: change base static problem(s) to create DOPs
Real space:
Switch between different functions
Move/reshape peaks in the fitness landscape

Binary space:
Switch between ≥ 2 states of a problem: knapsackUse binary masks: XOR DOP generator (Yang & Yao’05)

Combinatorial space:
Change decision variables: item weights/profits in knapsack problems
Add/delete decision variables: new jobs in scheduling, nodes
added/deleted in network routing problems

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

13 / 68

The DF1 Generator
Proposed by Morrison & De Jong (1999)
The base landscape in the D-dimensional real space:
#
⎤
⎡
$ D
$&
f (⃗x ) = max ⎣Hi − Ri × % (xj − Xij )2 ⎦i=1,...,pj=1– ⃗x = (x1 , · · · , xD ): a point in the landscape; p: number of peaks– Hi , Ri , Xi = (Xi1 , · · · , XiD ): height, slope, center of peak i
The dynamics is controlled by a logistics function:∆t = A · ∆t−1 · (1 − ∆t−1 )– A ∈ [1.0, 4.0]: a constant; ∆t : step size of changing a parameter

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

14 / 68

Moving Peaks Benchmark (MPB) Problem
Proposed by Branke (1999)
The MPB problem in the D-dimensional space:
Hi (t))D2
i=1,...,p 1 + W (t)ij=1 (xj (t) − Xij (t))

F (⃗x , t) = max– Wi (t), Hi (t), Xi (t) = {Xi1 · · · XiD }: height, width, location of peak i at t
The dynamics:
Hi (t) = Hi (t − 1) + height_severity ∗ σ
Wi (t) = Wi (t − 1) + width_severity ∗ σs*⃗⃗⃗vi (t) = **⃗r + ⃗vi (t − 1)* ((1 − λ)r + λvi (t − 1))⃗ i (t) = X⃗ i (t)(t − 1) + ⃗vi (t)X– σ ∼ N(0, 1); λ: correlated parameter– ⃗vi (t): shift vector, which combines random vector ⃗r and ⃗vi (t − 1) and isnormalized to the shift length s
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

15 / 68

Dynamic Knapsack Problems (DKPs)
Static knapsack problem:
Given n items, each with a weight and a profit, and a knapsack witha fixed capacity, select items to fill up the knapsack to maximize theprofit while satisfying the knapsack capacity constraint
The DKP:
Constructed by changing weights and profits of items, and/or knapsack
capacity over time as:
Max f (⃗x (t), t) =n!

pi (t) · xi (t), s. t. :

i=1

n
!

wi (t) · xi (t) ≤ C(t)i=1

– ⃗x (t) ∈ {0, 1}n : a solution at time t– xi (t) ∈ {0, 1}: indicates whether item i is included or not– pi (t) and wi (t): profit and weight of item i at t
– C(t): knapsack capacity at t

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

16 / 68

The XOR DOP Generator
The XOR DOP generator can create DOPs from any binary f (⃗x ) by an
XOR operator “⊕” (Yang, 2003; Yang & Yao, 2005)
Suppose the environment changes every τ generations
For each environmental period k = ⌊t/τ ⌋, do:
1

State 1

M(1)=1001011010
M(0) + T(0)State 4...

2

M(1) + T(1)M(0)=0000000000

M(3)=1101000101

State 0 (Initial State)M(2) + T(2)⃗ ) incrementally
Create a mask M(k⃗M(0)= ⃗0 (the initial state)⃗⃗ )⊕T⃗ (k )M(k+ 1) = M(kState 3

M(2)=0111010011

Create a template Tk with ρ ∗ l ones

3

Evaluate an individual:⃗ ))f (⃗x , t) = f (⃗x ⊕ M(kState 2
T(0)=1001011010 T(1)=1110001001

T(2)=1010010110

τ and ρ controls the speed and severity of change respectively

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

17 / 68

Constructing Cyclic Dynamic Environments
Can extend the XOR DOP generator to create cyclic environments:
1

Partition Templates: T(0)=1001011010 v T(1)=0110100101

Form a partition of the search space
Each contains ρ × l = l/K ones

Base State 1
M(1)=1001011010
2

Base State 0(Initial State)

M(0) T(0)M(0)=0000000000

M(1) T(1)Base State 2⃗ + 1) = M(i)⃗⃗ (i%K ), i = 0,· · · , 2K −1
M(i⊕T

M(2) T(0)M(3)=0110100101
Base State 3⃗
Create 2K masks M(i)as base states⃗M(0)= ⃗0 (the initial state)

M(2)=1111111111
M(3) T(1)⃗ (0),· · · ,T⃗ (K −1)
Construct K templates T

3⃗
Cycle among M(i)’severy τ generations⃗ t )) = f (⃗x ⊕ M(k⃗ %(2K )))f (⃗x , t) = f (⃗x ⊕ M(I– k = ⌊t/τ ⌋: environmental index– It = k %(2K ): mask index

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

18 / 68

Constructing Cyclic Environments with Noise
We can also construct cyclic environments with noise:
Each time before a base state is entered, it is bitwise changed with asmall probability
Base State 1
M(1)=1001011011
Base State 0(Initial State)M(0)=0000000000

Bit 10 changed
by noise

Base State 2
M(2)=0111111111

Bit 6 changed
by noise
M(3)=0110110101

Bit 1 changed
by noise

Base State 3

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

19 / 68

Dynamic Traveling Salesman Problems
Stationary traveling salesman problem (TSP):
Given a set of cities, find the shortest route that visits each city once andonly once

Dynamic TSP (DTSP):
May involve dynamic cost (distance) matrix
D(t) = {dij (t)}n∗n– dij (t): cost from city i to j; n: the number of cities
The aim is to find a minimum-cost route containing all cities at time t
DTSP can be defined as f (x, t):f (x, t) = Min(n!

dxi ,xi+1 (t))

i=1where xi ∈ 1, · · · , n. If i ̸= j, xi ̸= xj , and xn+1 = x1

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

20 / 68

Dynamic Permutation Benchmark Generator
The dynamic benchmark generator for permutation-encoded problems(DBGP) can create a DOP from any stationary TSP/VRP by swapping
objects:
1

Generate a random vector ⃗r (T ) that
contains all objects every f iterations

2

Generate another randomly re-order vectorr⃗′ (T ) that contains only the first m × n
objects of ⃗r (T )3

Modify the encoding of the problem instancewith m × n pairwise swaps

More details: M. Mavrovouniotis, S. Yang, & X. Yao (2012). PPSN XII, Part II,
LNCS 7492, pp. 508–517

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

21 / 68Effect on Algorithms
Similar with the XOR DOP generator, DBGP shifts the
population of an alg. to new location in the fitness landscape
The individual with the same encoding as before a change will have a
different cost after the change

Can extend for cyclic and cyclic with noise environments
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

22 / 68

Generalized DOP Benchmark Generator (GDBG)
Proposed by Li & Yang (2008), GDBG uses the model below:

In GDBG, DOPs are defined as:
F = f (x , φ, t),– φ: system control parameter
Dynamism results from tuning φ of the current environmentφ(t + 1) = φ(t) ⊕ ∆φ
– ∆φ: deviation from the current control parameter(s)The new environment at t + 1 is as follows:f (x , φ, t + 1) = f (x , φ(t) ⊕ ∆φ, t)
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

23 / 68

GDBG: Dynamic Change Types

Change types:
1
Small step: ∆φ = α · ∥φ∥ · rand()2
Large step: ∆φ = ∥φ∥ · (α + (1 − α)rand())
3
Random: ∆φ = ∥φ∥ · rand()4
Chaotic: φ(t + 1) = A · φ(t) · (1 − φ(t)/∥φ∥)5
Recurrent: φ(t + 1) = φ(t%P)
6Recurrent with nosy: φ(t + 1) = φ(t%P) + α · ∥φ∥ · rand()7......
More details:
C. Li & S. Yang (2008). SEAL’08, LNCS 5361, pp. 391–400

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

24 / 68

DOPs: Classification

Classification criteria:
Time-linkage: Does the future behaviour of the problem depend on thecurrent solution?
Predictability: Are changes predictable?
Visibility: Are changes visible or detectable
Cyclicity: Are changes cyclic/recurrent in the search space?
Factors that change: objective, domain/number of variables, constraints,
and/or other parameters

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

25 / 68

DOPs: Common Characteristics

Common characteristics of DOPs in the literature:
Most DOPs are non time-linkage problems
For most DOPs, changes are assumed to be detectable
In most cases, the objective function is changed
Many DOPs have unpredictable changes
Most DOPs have cyclic/recurrent changes

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

26 / 68Performance Measures
For EC for stationary problems, 2 key performance measures
Convergence speed
Success rate of reaching optimality

For EC for DOPs, over 20 measures (Nguyen et al., 2012)
Optimality-based performance measures
Collective mean fitness or mean best-of-generation
Accuracy
Adaptation
Offline error and offline performance
Mean distance to optimum at each generation......

Behaviour-based performance measures
Reactivity
Stability
Robustness
Satisficability
Diversity measures......

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

27 / 68Performance Measures: Examples
Collective mean fitness (mean best-of-generation):F BOG =

!i=G 1!j=N
1×( ×
FBOGij )
i=1 N
j=1
G

– G and N: number of generations and runs, resp.
– FBOGij : best-of-generation fitness of generation i of run j

Adaptation performance (Mori et al., 1997)
Ada =

1 !
(fbest (t)/fopt (t))
T
t=1..T

Accuracy (Trojanowski and Michalewicz, 1999)
Acc =

1 !
(fbest (i) − fopt (i))
K
i=1..K– fbest (i): best fitness for environment i (best before change)

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

28 / 68

Part II: Approaches, Issues and Future WorkEC enhancement approaches for DOPs
Case studies
Relevant issues
Future work

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

29 / 68

EC for DOPs: First Thinking

Recap: traditional EAs are not good for DOPs
Goal: to track the changing optimum
How about restarting an EA after a change?
Natural and easy choice
But, not good choice because:
1
2

It may be inefficient, wasting computational resources
It may lead to very different solutions before and after a change.
For real-world problems, we may expect solutions to remain similar

Extra approaches are needed to enhance EAs for DOPs

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

30 / 68

EC for DOPs: General Approaches

Many approaches developed to enhance EAs for DOPs
Typical approaches:
Memory: store and reuse useful information
Diversity: handle convergence directly
Multi-population: co-operate sub-populations
Adaptive: adapt generators and parameters
Prediction: predict changes and take actions in advance

They have been applied to different EAs for DOPs

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

31 / 68

Memory Approaches
Cyclic DOPs: change cyclically among a fixed set of states

Memory works by storing and reusing useful information
Two classes regarding how to store information
Implicit memory: uses redundant representations
Multiploidy and dominance (Ng & Wong, 1995; Lewis et al., 1998)
Dualism mechanisms (Yang, 2003; Yang & Yao, 2005)

Explicit memory: uses extra space to store information

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

32 / 68

Implicit Memory: Diploid Genetic Algorithms
Encoding

Dominance Scheme

Genotype

Genotype−to−Phenotype
Mapping

0

o

1

i

0

0

0/1

0

o

0

0

1

0/1

1

0/1

1

1

1

i

0

0/1

1

1

Chromosome 10Chromosome 2

Dominance Scheme

Ng & Wong (1995)
Phenotype
Same PhenotypicAlleles
Evaluating

External Environment

Fitness
Genotypic Alleles:
Phenotypic Alleles:

A

B

C

D

A

0

0

0

1

B

0

0

0

1

C

0

0

1

1

D

1

1

1

1

Lewis et al. (1998)

Each individual has a pair of chromosomes
Dominance scheme maps genotype to phenotype
Dominance scheme may change or be adaptive (Uyar & Harmanci,
2005)
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

33 / 68

Explicit Memory Approaches

Basic idea: use extra memory
With time, store useful information of the pop into memory
When a change occurs, use memory to track new optimum

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

34 / 68

Explicit Memory: Direct vs Associative
Direct memory: store good solutions (Branke, 1999)
Associative memory: store environmental information + good solutions(Yang & Yao, 2008)
Main Population

Update memory

Main Population

2. Select

Update memory
3. Replace

1. Extract
env info

1. Select best
pop member

2. Associate+ 1. Merge

2. Replace one
memory solution

2. Create

3. Replace
1. Associate
Retrieve memory

Retrieve memory

MemoryMemoryEnvironment information

Direct Memory

Shengxiang Yang (De Montfort University)

Solution

Associative Memory

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

35 / 68

Associative Memory Based Genetic Algorithm⃗ to represent environmental info.
Idea: Use allele distribution (AD) D⃗ S> pairs
Use memory to store <D,
Main Population

Update memory
3. Replace

1. Extract allele
distribution vector
2. Associate

2. Create

3. Replace
1. Associate
Retrieve memory

Update memory by similarity policy
Re-evaluate memory every generation. Ifchange detected⃗M
Extract best memory AD: D⃗M
Create solutions by sampling D
Replace them into the pop randomly

Details:
S. Yang (2006). EvoWorkshops’06, pp. 788–799

MemoryAllele distribution vector

Solution

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

36 / 68

Diversity Approaches: Random Immigrants

Convergence is the key problem in metaheuristics for DOPs
Random immigrants:
Each generation, insert some random individuals (called random
immigrants) into the population to maintain diversity
When optimum moves, random immigrants nearby take action to draw the
pop to the new optimum

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

37 / 68

Memory-Based Immigrants
Random immigrants maintain the diversity while memory adapts analgorithm directly to new environments
Memory-based immigrants: uses memory to guide immigrants
towards current environment
Re-evaluate the memory every generation
Retrieve the best memory point BM (t) as the base
Generate immigrants by mutating BM (t) with a prob.
Replace worst members in the population by these immigrants
current best memory point

random immigrants

current
optimum

memory−based immigrants

memory points

Search Space

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

38 / 68

Experimental Results: Immigrants Based GAs
Cyclic Dynamic OneMax Function, τ = 25, ρ = 0.1

Random Dynamic OneMax Function, τ = 25, ρ = 0.1

100

100
SGA
RIGA
MEGA
MRIGA
MIGA

90

95
Best-Of-Generation Fitness

Best-Of-Generation Fitness

95

85
80
75
70

90

SGA
RIGA
MEGA
MRIGA
MIGA

85
80
75
70

65
4500

4600

4700

4800

4900

5000

65
4500

4600

Generation

4700

4800

4900

5000

Generation

Memory-based immigrants GA (MIGA) significantly beats other GAs
More details:
S. Yang (2008). Evol. Comput., 16(3): 385–416

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

39 / 68

Hybrid Immigrants Approach
Combines elitism, dualism and random immigrants ideas
Dualism: Given ⃗x = (x1 , · · · , xl ) ∈ {0, 1}l , its dual is defined as⃗x d = dual(⃗x ) = (x1d , · · · , xld ) ∈ {0, 1}lwhere xid = 1 − xi
Each generation t, select the best individual from previous generation,E(t − 1), to generate immigrants
Elitism-based immigrants: Generate a set of individuals by mutatingE(t − 1) to address slight changes
Dualism-based immigrants: Generate a set of individuals by mutating thedual of E(t − 1) to address significant changes
Random immigrants: Generate a set of random individuals to address
medium changes
Replace these immigrants into the population

More details:
S. Yang & R. Tinos (2007). Int. J. of Autom. & Comp., 4(3): 243–254

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

40 / 68

Experimental Results: Hybrid Immigrants GA
Royal Road, τ = 1060500.05 0.2 0.5 0.6 0.95 1.0

ρ

ρ

90
80
70
60

Royal Road, τ = 100

Deceptive, τ = 100
100

95

90

95

85
80

Offline Performance

100
Offline Performance

100

90

80
70
60

Offline Performanceρ

70

Offline Performanceρ

Offline Performance

Offline Performance50
0.05 0.2 0.5 0.6 0.95 1.080

Knapsack, τ = 10
1300
SGA
1250
RIGA
1200
EIGA
1150
ERIGA
1100
HIGA
1050
1000
950
900
850
0.05 0.2 0.5 0.6 0.95 1.0

100

90
80
70
60
50
40
30
20
0.05 0.2 0.5 0.6 0.95 1.0

90

OneMax, τ = 100

Offline Performance

Deceptive, τ = 10100

Knapsack, τ = 100
1350

SGA
RIGA
EIGA
ERIGA
HIGA

1300
Offline Performance

OneMax, τ = 10
100

90
85

50

80

75
0.05 0.2 0.5 0.6 0.95 1.0

400.05 0.2 0.5 0.6 0.95 1.0

750.05 0.2 0.5 0.6 0.95 1.0

ρ

ρ

ρ

1250
1200
1150
1100
1050

1000
0.05 0.2 0.5 0.6 0.95 1.0

ρHybrid immigrants improve GA’s performance for DOPs efficiently
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

41 / 68

Multi-Populations: Shifting Balance
Multi-population scheme uses co-operating sub-populations
Shifting Balance GA (Oppacher & Wineberg, 1999):
A core population exploits the promising area
Several colonies explore the search spacecolonymigration

Core
Population
migration

migrationcolonycolonyShengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

42 / 68

Multi-Populations: Self-Organizing Scouts
Self-organizing scouts (SOS) GA (Branke et al., 2000)
The parent population explores the search space
A child population is split under certain conditions
Child populations search limited promising areas
ParentPopulation

evolveParentPopulation

split

child
population 1

evolveevolveParentPopulation

Shengxiang Yang (De Montfort University)

split

child
population 2

Tutorial: EC for DOPs

child
population 1

IEEE CEC 2017, 05/06/2017

43 / 68

Adaptive Approaches

Aim: Adapt operators/parameters, usually after a change
Hypermutation (Cobb & Grefenstette, 1993): raise the mutation rate
temporarily
Hyper-selection (Yang & Tinos, 2008): raise the selection pressure
temporarily
Hyper-learning (Yang & Richter, 2009): raise the learning rate forPopulation-Based Incremental Learning (PBIL) temporarily

Combined: Hyper-selection and hyper-learning with re-start or
hypermutation

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

44 / 68

Prediction Approaches

For some DOPs, changes exhibit predictable patterns
Techniques (forecasting, Kalman filter, etc.) can be used to predict
The location of the next optimum after a change
When the next change will occur and which environment may appear

Some relevant work: see Simões & Costa (2009)

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

45 / 68

Remarks on Enhancing Approaches

No clear winner among the approaches
Memory is efficient for cyclic environments
Multi-population is good for tracking competing peaks
The search ability will decrease if too many sub-populations

Diversity schemes are usually useful
Guided immigrants may be more efficient

Different interaction exists among the approaches
Golden rule: balancing exploration & exploitation over time

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

46 / 68

Case Study: GA for Dynamic TSP
Dynamic TSP:
144 Chinese cities, 1 geo-stationary saterllite, and 3 mobile satellites
Find the path that cycles each city and satellite once with the minimum
length over time

Solver: A GA with memory and other schemes
More details:
C. Li, M. Yang, & L. Kang (2006). SEAL’06, LNCS 4247, pp. 236–243

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

47 / 68

Case Study: GAs for Dynamic Routing in MANETs – 1

Shortest path routing problem (SPRP) in a fixed network:
Find the shortest path between source and destination in a fixed topology

More and more mobile ad hoc networks (MANETs) appear where thetopology keeps changing
Dynamic SPRP (DSPRP)in MANETs:
Find a series of shortest paths in a series of highly-related network
topologies

We model the network dynamics as follows:
For each change, a number of nodes are randomly selected to sleep orwake up based on their current status

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

48 / 68

Case Study: GAs for Dynamic Routing in MANETs – 2

A specialized GA for the DSPRP:
Path-oriented encoding
Tournament selection
Path-oriented crossover and mutation with repair

Enhancements: Immigrants and memory approaches
Experimental results:
Both immigrants and memory enhance GA’s performance for the DSPRP
in MANETs.
Immigrants schemes show their power in acyclic environments
Memory related schemes work well in cyclic environments

More details:
S. Yang, H. Cheng, & F. Wang (2010). IEEE Trans SMC Part C: Appl. &Rev., 40(1): 52–63

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

49 / 68

Case Study: PSO for Continuous DOPs

Particle Swarm Optimization (PSO):
Inspired by models of swarming and flocking
First introduced by Kennedy and Eberhart in 1995
PSO has been applied for many static optimization problems

Recently, PSO has been applied for continuous DOPs
Two aspects to consider for DOPs:
Outdated memory. Two solutions:
Simply set pbest to the current position
Reevaluate pbest and reset it to the current position if current position is better

Diversity loss. Three solutions:Introduce diversity after a change
Maintain diversity during the run
Use multi-swarms

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

50 / 68

Multi-swarm PSO for DOPs
Clustering PSO (CPSO):
Training: Move particles toward different promising regions
Clustering: Single linkage hierarchical clustering to create sub-swarms
Local search: Each sub-swarm will search among one peak quickly
Overlapping and convergence check
Strategies to response to changes
Details: Li & Yang, CEC’09; Yang & Li, IEEE Trans Evol Comput, 14(6),2010

Adaptive Multi-Swarm Optimizer (AMSO):
Use single linkage hierarchical clustering to create populations
An overcrowding scheme to remove unnecessary populations
A special rule to decide proper moments to increase diversity withoutchange detection
An adaptive method to create a proper number of populations needed
Details:
Li, Yang & Yang (2014), Evol Comput, 22(4): 559–594
Li et al. (2016), IEEE Trans Evol Comput, 20(4): 590–605

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

51 / 68Demo: CPSO & AMSO for DOPs

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

52 / 68

Case Study: Ant Colony Optimization (ACO) for DOPs

ACO mimics the behaviour of ants searching for food
ACO was first proposed for TSPs (Dorigo et al., 1996)
Generally, ACO was developed to be suitable for graph optimization
problems, such as TSP and VRP
The idea was to let ants “walk” on the arcs of the graph while “reading”
and “writing” pheromones until they converge into a path
Standard ACO consists of two phases:
Forward mode: Construct solutions
Backward mode: Pheromone update

Conventional ACO cannot adapt well to DOPs due to stagnation
behaviour
Once converged, it is hard to escape from the old optimum

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

53 / 68

ACO for DOPs: General Comments
ACO transfers knowledge via pheromone
Make sense on slight changes; otherwise, may misguide the search
For severe changes, a global restart is a better choice
A global restart of ACO ⇒ pheromone re-initialization

Moreover, ACO has to maintain adaptability, instead of stagnation
behaviour, to accept knowledge transferred
Recently, many approaches developed with ACO for DOPs
(Mavrovouniotis, Li, & Yang 2017)
Pheromone modification after a change (Guntsch & Middendorf, 2001,
Eyckelhof & Snoek, 2002)
Memory-based schemes (Guntsch & Middendorf, 2002)
Hybrid and memetic algorithms (Mavrovouniotis, Muller & Yang, 2017)
Pheromone modification during execution (Mavrovouniotis & Yang, 2013a)
Multi-colony schemes (Mavrovouniotis, Yang & Yao, 2014)

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

54 / 68

ACO with Pheromone Strategies: Adapting Evaporation

Pheromone evaporation is an adaptation mechanism in ACO
Different evaporation rates perform better for different DOPs
Solution ⇒ Adaptive pheromone evaporation rate
Starts with an initial ρ and modifies it as follows:
When stagnation behaviour is detected, increase ρ to help ants forget
current solution; otherwise, decrease ρ to avoid randomization
A λ-branching method is used to detect stagnation behaviour

Performs better than fixed evaporation rate
However, a restart strategy performs better for severe changes

More details:
Mavrovouniotis & Yang (2013a) for both DTSP and DVRP

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

55 / 68

ACO with Pheromone Strategies: Immigrants
Integrate immigrants schemes to ACO
A short-term memory is used to store the best k ants and generated
immigrant ants
The memory is updated every iteration
No ant can survive in more than one iteration

Pheromone trails are synchronized with short-term memory
Any changes to the memory applied also to pheromone trails

Pheromone evaporation is not used because pheromone trails are
removed directly
More details:
Mavrovouniotis & Yang (2013b) for DTSPs
Mavrovouniotis & Yang (2015) for DVRPs
Eaton, Mavrovouniotis & Yang (2016) for the dynamic railway junction
rescheduling problem

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

56 / 68

Theoretical Development
So far, mainly empirical studies
Theoretical analysis has just appeared
Runtime analysis:
Stanhope & Daida (1999) first analyzed a (1+1) EA on the dynamic bit
matching problem (DBMP)
Droste (2002) analyzed the first hitting time of a (1+1) ES on the DBMP
Rohlfshagen et al. (2010) analyzed how the magnitude and speed ofchange may affect the performance of the (1+1) EA on two functions
constructed from the XOR DOP generator

Analysis of dynamic fitness landscape:
Branke et al. (2005) analyzed the changes of fitness landscape due tochanges of the underlying problem instanceRichter (2010) analyzed the properties of spatio-temporal fitness
landscapes constructed from Coupled Map Lattices (CML)
Tinos and Yang (2010, 2014) analyzed the properties of the XOR DOP
generator based on the dynamical system approach of a GA

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

57 / 68

EC for Dynamic Multi-objective Optimization
So far, mainly dynamic single-objective optimization
Dynamic multi-objective optimization problems (DMOPs): even morechallenging
Recently, rising interest in studying EC for DMOPs
Farina et al. (2004) classified DMOPs based on the changes on the Pareto
optimal solutions
Goh & Tan (2009) proposed a competitive-cooperative coevolutionary
algorithm for DMOPs
Zeng et al. (2006) proposed a dynamic orthogonal multi-objective EA(DOMOEA) to solve a DMOP with continuous decision variables
Zhang & Qian (2011) proposed an artificial immune system to solve
constrained DMOPs
Jiang & Yang (2017a) proposed a new benchmark MDOP generator
Jiang & Yang (2017b) proposed a Steady-Generational EA (SGEA) for
DMOPs
Ruan et al. (2017) analyzed the effect of diversity maintenance on
prediction for DMOPs
Eaton et al. (2017) applied ACO for the dynamic multi-objective railway
junction rescheduling problem
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

58 / 68

Challenging Issues

Detecting changes:
Most studies assume that changes are easy to detect or visible to analgorithm whenever occurred
In fact, changes are difficult to detect for many DOPs

Understanding the characteristics of DOPs:
What characteristics make DOPs easy or difficult?
The work has started, but needs much more effort

Analysing the behaviour of EAs for DOPs:
Requiring more theoretical analysis tools
Addressing more challenging DOPs and EC methods
Big question: Which EC methods for what DOPs?

Real world applications:
How to model real-world DOPs?

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

59 / 68

Future WorkThe domain has attracted a growing interest recently
But, far from well-studied

New approaches needed: esp. hybrid approaches
Theoretical analysis: greatly needed
EC for DMOPs: deserves much more effort
Real world applications: also greatly needed
Fields: logistics, transport, MANETs, data streams, social networks, ...

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

60 / 68

Summary

EC for DOPs: challenging but important
The domain is still young and active:
More challenges to be taken regarding approaches, theory, andapplications

More young researchers are greatly welcome!

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

61 / 68

Acknowledgements
Two EPSRC funded projects on EC for DOPs
“EAs for DOPs: Design, Analysis and Applications”
Linked project among Brunel Univ. (Univ. of Leicester before 7/2010),
Univ. of Birmingham, BT, and Honda
Funding/Duration: over £600K / 3.5 years (1/2008–7/2011)
http://gtr.rcuk.ac.uk/project/B807434B-E9CA-41C7-B3AF-567C38589BAC“EC for Dynamic Optimisation in Network Environments”
Linked project among DMU, Univ. of Birmingham, RSSB, and Network Rail
Funding/Duration: ∼£1M / 4.5 years (2/2013–8/2017)
http://gtr.rcuk.ac.uk/project/C43F34D3-16F1-430B-9E1F-483BBADCD8FA

Research team members:
Research Fellows: Dr. Hui Cheng, Dr. Crina Grosan, Dr. Changhe Li,
Dr. Michalis Mavrovouniotis, Dr. Yong Wang, etc.
PhD students: Changhe Li, Michalis Mavrovouniotis, Shouyong Jiang,
Jayne Eaton, Hongfeng Wang, etc.

Research cooperators:
Prof. Xin Yao, Prof. Juergen Branke, Prof. Jinliang Ding, Dr. Renato Tinos,
Dr. Hendrik Richter, Dr. Trung Thanh Nguyen, etc.
Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

62 / 68

Relevant Information

IEEE CIS Task Force on EC in Dynamic and Uncertain Environments
http://www.tech.dmu.ac.uk/~syang/IEEE_ECIDUE.html
Maintained by Shengxiang Yang
Source codes:
http://www.tech.dmu.ac.uk/~syang/publications.html

IEEE Competitions:2009 Competition on EC in Dynamic & Uncertain Environments:
http://www.cs.le.ac.uk/people/syang/ECiDUE/ECiDUE-Competition09

2012 Competition on EC for DOPs:
http://people.brunel.ac.uk/~csstssy/ECDOP-Competition12.html

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

63 / 68

References – 1
1
2
3
4
5
6
7
8
9
10

11
12

E. Alba, A. Nakib, & P. Siarry (2013). Metaheuristics for Dynamic Optimization. Springer
J. Branke (1999). Memory enhanced evolutionary algorithms for changing optimization
problems. CEC’99, pp. 1875–1882
J. Branke (2002). Evolutionary Optimization in Dynamic Environments. Kluwer Academic
Publishers
J. Branke, E. Salihoglu, S. Uyar (2005). Towards an analysis of dynamic environments.
GECCO’05, pp. 1433–1439
H.G. Cobb, J.J. Grefenstette (1993). Genetic algorithms for tracking changing
environments. Proc. ICGA, pp. 523–530
C. Cruz, J. Gonzanlez, D. Pelta (2011). Optimization in dynamic environments: A survey
on problems, methods and measures. Soft Comput., 15: 1427–1448
M. Dorigo, V. Maniezzo, A. Colorni (1996). Ant system: Optimization by a colony ofcooperating agents, IEEE Trans SMC-Part B: Cybern 26(1): 29–41
S. Droste (2002). Analysis of the (1+1) EA for a dynamically changing onemax-variant.
CEC’02, pp. 55–60
J. Eaton, S. Yang, M. Gongora (2017). Ant colony optimization for simulated dynamic
multi-objective railway junction rescheduling. IEEE Trans Intell Transport Syst, in press
J. Eaton, S. Yang, M. Mavrovouniotis (2016). Ant colony optimization with immigrants
schemes for the dynamic railway junction rescheduling problem with multiple delays. Soft
Comput, 20(8): 2951–2966
C. Eyckelhof, M. Snoek (2002). Ant systems for a dynamic TSP, Proc 3rd Int Workshop on
Ant Algorithms, LNCS 2463, pp. 88–99
M. Farina, K. Deb, P. Amato (2004). Dynamic multiobjective optimization problems: test
cases, approximations, and applications. IEEE Trans Evol Comput, 8(5): 425–442

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

64 / 68

References – 2
13
14
15
16
17
18
19
20
21
22
23

C. Goh, K.C. Tan (2009). A competitive-cooperative coevolutionary paradigm for dynamic
multiobjective optimization. IEEE Trans Evol Comput, 13(1): 103–127
M. Guntsch, M. Middendorf (2001). Pheromone modification strategies for ant algorithms
applied to dynamic TSP, EvoWorkshops 2001, LNCS 2037, pp. 213–222
M. Guntsch, M. Middendorf (2002). Applying population based aco to dynamic optimization
problems, Proc. 3rd Int. Workshop on Ant Algorithms, LNCS 2463, pp. 111–122
M. Guntsch, M. Middendorf, H. Schmeck (2001). An ant colony optimization approach to
dynamic TSP, GECCO 2001, pp. 860–867
S. Jiang, S. Yang (2017a). Evolutionary dynamic multi-objective optimization: benchmarks
and algorithm comparisons. IEEE Trans Cybern, 47(1): 198-211
S. Jiang, S. Yang (2017b). A steady-state and generational evolutionary algorithm for
dynamic multi-objective optimization. IEEE Trans Evol Comput, 21(1): 65-82.
Y. Jin, J. Branke (2005). Evolutionary optimization in uncertain environments–A survey.
IEEE Trans Evol Comput, 9(3): 303–317
R.W. Morrison (2004). Designing Evolutionary Algorithms for Dynamic Environments.
Springer
E.H.J. Lewis, G. Ritchie (1998). A comparison of dominance mechanisms and simple
mutation on non-stationary problems. PPSN V, pp. 139–148
C. Li, S. Yang, M. Yang (2014). An adaptive multi-swarm optimizer for dynamic optimization
problems. Evol Comput, 22(4): 559–594
C. Li, T.T. Nguyen, M. Yang, M. Mavrovouniotis, S. Yang (2016). An adaptive
multi-population framework for locating and tracking multiple optima. IEEE Trans Evol
Comput, 20(4): 590–605

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

65 / 68

References – 3
24
25

26
27

28
29
30
31
32
33
34

M. Mavrovouniotis, C. Li, S. Yang (2017). A survey of swarm intelligence for dynamic
optimization: Algorithms and applications. Swarm & Evol Comput, 33: 1–17
M. Mavrovouniotis, F.M. Muller, S. Yang (2017). Ant colony optimization with local searchfor dynamic travelling salesman problems. IEEE Trans Cybern, in press (DOI:
10.1109/TCYB.2016.2556742)
M. Mavrovouniotis, S. Yang (2013a). Adapting the pheromone evaporation rate in dynamic
routing problems, EvoApplications 2013, LNCS 7835, pp. 606–615
M. Mavrovouniotis, S. Yang (2013b). Ant colony optimization with immigrants schemes forthe dynamic travelling salesman problem with traffic factors, Appl. Soft Comput, 13(10):4023–40376.
M. Mavrovouniotis, S. Yang (2015). Ant algorithms with immigrants schemes for the
dynamic vehicle routing problem. Inform Sci, 294: 456–477
M. Mavrovouniotis, S. Yang, X. Yao (2012). A benchmark generator for dynamic
permutation-encoded problems, PPSN XII, LNCS 7492, pp. 508–517
M. Mavrovouniotis, S. Yang, X. Yao (2014). Multi-colony ant algorithms for the dynamic
travelling salesman problem, IEEE SSCI 2014, pp. 9–16
R. Montemanni, L. M. Gambardella, A. E. Rizzoli, A. V. Donati (2005). Ant colony system
for a dynamic vehicle routing problem, Combinat Optim, 10: 327–343
R.W. Morrison, K.A. De Jong (1999). A test problem generator for non-stationary
environments. CEC’99, pp. 2047–2053
K.P. Ng, K.C. Wong (1995). A new diploid scheme and dominance changemechanism for non-stationary function optimisation. ICGA 6, pp. 159–166
T.T. Nguyen, S. Yang, J. Branke (2012). Evolutionary dynamic optimization: A survey of thestate of the art. Swarm & Evol Comput, 6: 1–24

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

66 / 68

References – 4
35
36
37

38
39
40
41
42
43
44

45

F. Oppacher, M. Wineberg (1999). The Shifting balance genetic algorithm: Improving the
GA in a dynamic environment. GECCO’99, vol. 1, pp. 504–510
G. Ruan, G. Yu, J. Zheng, J. Zou, S. Yang (2017). The effect of diversity maintenance on
prediction in dynamic multi-objective optimization. Appl Soft Comput, 58: 631–647.
H. Richter (2010). Evolutionary optimization and dynamic fitness landscapes: Fromreaction-diffusion systems to chaotic cml. Evolutionary Algorithms and Chaotic Systems,
Springer, pp. 409–446.
P. Rohlfshagen, P.K. Lehre, X. Yao (2009). Dynamic evolutionary optimisation: An analysis
of frequency and magnitude of change. GECCO’09, pp. 1713–1720
S.A. Stanhope, J.M. Daida (1999). (1+1) genetic algorithm fitness dynamics in a changing
environments. CEC’99, vol. 3, pp. 1851–1858
R. Tinos, S. Yang (2010) An analysis of the XOR dynamic problem generator based on the
dynamical system. PPSN XI, LNCS 6238, Part I, pp. 274–283
R. Tinos, S. Yang (2014). Analysis of fitness landscape modifications in evolutionary
dynamic optimization. Inform Sci, 282: 214–236
A. Simões, E. Costa (2009). Improving prediction in evolutionary algorithms for dynamic
environments. GECCO’09, pp. 875–882
K. Trojanowski, Z. Michalewicz (1999). Searching for optima in non-stationary
environments. CEC’99, vol. 3, pp. 1843–1850
A.S. Uyar, A.E. Harmanci (2005). A new population based adaptive domination changemechanism for diploid genetic algorithms in dynamic environments. Soft Comput, 9:803–814
S. Yang (2003). Non-stationary problem optimization using the primal-dual
genetic algorithm. CEC’03, pp. 2246–2253

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

67 / 68

References – 5
46
47
48
49
50
51
52
53
54
55
56

S. Yang, Y. Jiang, T.T. Nguyen (2013). Metaheuristics for dynamic combinatorial
optimization problems. IMA J of Management Math, 24(4): 451–480
S. Yang, C. Li (2010). A clustering particle swarm optimizer for locating and tracking
multiple optima in dynamic environments. IEEE Trans Evol Comput, 14(6): 959–974
S. Yang, Y.-S. Ong, Y. Jin (2007). Evolutionary Computation in Dynamic and Uncertain
Environments. Springer
S. Yang, H. Richter (2009). Hyper-learning for population-based incremental learning in
dynamic environments. CEC’09, pp. 682–689
S. Yang, R. Tinos (2008). Hyper-selection in dynamic environments. CEC’08,
pp. 3185–3192
S. Yang, X. Yao (2005). Experimental study on population-based incremental learningalgorithms for dynamic optimization problems. Soft Comput, 9: 815–834
S. Yang, X. Yao (2008). Population-based incremental learning with associative memoryfor dynamic environments. IEEE Trans Evol Comput, 12: 542–561
S. Yang, X. Yao (2013). Evolutionary Computation for Dynamic Optimization Problems.
Springer
K. Weicker (2003). Evolutionary Algorithms and Dynamic Optimization Problems. Der
Andere Verlag
S. Zeng et al. (2006). A dynamic multi-objective evolutionary algorithm based on an
orthogonal design. CEC’06, pp. 573–580
Z. Zhang, S. Qian (2011). Artificial immune system in dynamic environments solving
time-varying non-linear constrained multi-objective problems. Soft Comput, 15(7):1333–1349

Shengxiang Yang (De Montfort University)

Tutorial: EC for DOPs

IEEE CEC 2017, 05/06/2017

68 / 68