Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

TPAM:
A Simulation-Based Model for Quantitatively
Analyzing Parameter Adaptation Methods
Ryoji Tanabe (SUSTech, CHN) and Alex Fukunaga (U. Tokyo, JP)

The first quantitative analysis of PAMs in isolation
Parameter Adaptation Methods (PAMs) are poorly understood
We propose a Target function-based PAM simulation (TPAM)
framework for analyzing PAMs in adaptive DE
TPAM measures the ability of PAMs to track predefined target
parameters and enables quantitative analysis of PAMs
E.g., PAM-JADE tracks this particular target behavior
1.4 times better than PAM-SHADE

1 / 21Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

Diﬀerential Evolution (DE) [Storn 97]
The two main control parameters of DE are:1. Scale factor F ∈ (0, 1]:
F controls the magnitude of the diﬀerential mutation
2. Crossover rate C ∈ [0, 1]:
C controls the number of inherited variables from xt ← 1, initialize the population P t = {x1,t , ..., xN,t };2 while The termination criteria are not met do3for i ∈ {1, ..., N } do
4v i,t ← diﬀerentialMutation(P t , Fi,t );5ui,t ← crossover(xi,t , v i,t , Ci,t );18for i ∈ {1, ..., N } doif f (ui,t ) ≤ f (xi,t ) then xi,t+1 ← ui,t ;else xi,t+1 ← xi,t ;9t ← t + 1;

6
72 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

The performance of DE depends on the setting of F and C
E.g., An appropriate setting of C depends on separability
Rastrigin (separable)
C = 0.9 is unsuitable

C = 0.1 is suitable

Rosenbrock (nonseparable)

C = 0.1 is unsuitable

C = 0.9 is suitable

Number of function evaluations (FEvals)

The classical DE is not so eﬃcient for black-box optimization
DE needs automated parameter control methods for F and C
A large number of adaptive DE algorithms have been proposed
jDE [Brest 06], JADE [Zhang 09], SaDE [Qin 09],
EPSDE [Mallipeddi 11], MDE [Islam 12], SHADE [Tanabe 13], ...
3 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Parameter Adaptation Methods (PAMs) are poorly understood
We are interested in PAMs in adaptive DE, not adaptive DE
PAMs (our interest) Mutation strategy Cross.
binomial
jDE = PAM of jDE
rand/1JADE = PAM of JADE current-to-pbest/1 binomial

Several previous works have tried to analyze PAMs in adaptive DE
Their results/analysis limited to plots of changes in F and C
E.g., Adaptation process of the meta-parameter of JADE for C
Rosenbrock

The meta-parameter of C
gradually increases
Analysis limited toqualitative descriptions

RastriginThe meta-parameter of C
quickly drops down

Number of iterations

Such qualitative results do notprovide sufficient insight4 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Proposal: Target function-based PAM simulation (TPAM)
Traditional analyses based on plotting parameter values:
Limited to qualitative descriptions
May be useful for analyzing overall behavior of adaptive DEs,but cannot analyze the behavior of PAMs in isolation
Our proposed TPAM:
Quantitatively evaluates the tracking performance of PAMs
Enables analysis for PAMs in isolation
Independent of other mechanisms in adaptive DE
Measures the ability of PAMs to track predefined target
parameters and enables quantitative analysis of PAMs
E.g., PAM-JADE tracks this particular target behavior 1.4
times better than PAM-SHADE

5 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

A generalized Parameter Adaptation Method (PAM) in adaptive DE
1. At the beginning of each iteration t, generate Fi,t and Ci,t foreach individual xi,t using meta-parameters
2. Decide whether {Fi,t , Ci,t } is a success or a failure
Success: if the child ui,t is better than the parent xi,tI.e., if f (ui,t ) ≤ f (xi,t )Failure: Otherwise
3. At the end of each iteration t, update the meta-parameters
based on the success/failure decisions
Strictly speaking:Some PAMs do not use meta-parameters
E.g., PAM-jDE, PAM-EPSDE,...
But, such PAMs can also be generalized into the above
framework
6 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Example: PAM-JADE [Zhang 09]
PAM-JADE uses two meta-parameters µF and µC forparameter adaptation of F and C, respectivelyt ← 1, initialize the population P t , µF , µC ← 0.5;
2 while The termination criteria are not met do
3S F ← ∅, S C ← ∅;4for i ∈ {1, ..., N } do
1

5
6
7
8
9
10
11
12
13

Fi,t ← CauchyRand(µF , 0.1), Ci,t ← NomalRand(µC , 0.1);v i,t ← diﬀerentialMutation(P t , Fi,t );ui,t ← crossover(xi,t , v i,t , Ci,t );for i ∈ {1, ..., N } do
if f (ui,t ) ≤ f (xi,t ) thenxi,t+1 ← ui,t , S F ← Fi,t , S C ← Ci,telse xi,t+1 ← xi,t ;µF ← (1 − c)µF + c meanA (S F ), µC ← (1 − c)µC + c meanL (S C );t ← t + 1;

7 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Example: PAM-SHADE [Tanabe 13]
PAM-SHADE uses M F = (M1F , ..., MHF )T and M C = (M1C , ..., MHC )Tt ← 1, initialize the population P t , M F , M C ← 0.5, k ← 1;2 while The termination criteria are not met do
3S F ← ∅, S C ← ∅;4for i ∈ {1, ..., N } do
15ri,t ← Randi{1, ..., N }, Fi,t ← CauchyRand(MrFi,t , 0.1), Ci,t ←NomalRand(MrCi,t , 0.1);

6
7
8
9
10
11
12
13v i,t ← diﬀerentialMutation(P t , Fi,t );ui,t ← crossover(xi,t , v i,t , Ci,t );for i ∈ {1, ..., N } do
if f (ui,t ) ≤ f (xi,t ) thenxi,t+1 ← ui,t , S F ← Fi,t , S C ← Ci,telse xi,t+1 ← xi,t ;MkF ← meanA (S F ), MkC ← meanL (S C ), k ← mod(k + 1, M );t ← t + 1;

8 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Basic idea of our proposed TPAM: Space reduction
A traditional approach must consider three complex spaces
Control parameter space

Solution space

Objective function space

ALL previous work used the objective function value of thesolution f (x) to evaluate the generated control parameters
Since x is also aﬀected by variation operators, suchapproaches cannot evaluate the control parameters in isolation
PROPOSAL:
Let’s remove the solution space from optimization problems!
The TPAM approach considers only the two simplified spaces
Control parameter space

TPAM success/failure space

The solution space is eliminated, and the objective function
space is replaced by the TPAM success/failure space
Control parameters can be directly evaluated in isolation
9 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Some notes on this presentation
Recall: We are NOT interested in “the whole adaptive DE”
We want to focus only on Parameter Adaptation Methods
We are interested in PAM-jDE, not jDE
TPAM is NOT a class of benchmark function for optimization
The TPAM is a simulation framework to analyze PAMs
TPAM does NOT seek to optimize a static objective function f
TPAM measures the target-tracking behavior of a PAM
Individuals in TPAM only have F , C values but no base level
genome, so variation operators (e.g., mutation) are irrelevant
TPAM can deal with both F and C simultaneously
We investigated (i) C, (ii) F , and (iii) {F, C}
But, the tendency of their results is not diﬀerent
For simplicity, we focus on C in this talk
10 / 21Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

The process of PAMs in adaptive DE only depend onwhether each child generation is a success or a failure
Analyzing the PAM behavior does not require modeling theabsolute objective function values of the individuals
A simulation model of the success/failure decisions is suﬃcientParameter adaptation of PAMs can be simulated by using asurrogate model deciding whether {Fi,t , Ci,t } is a success or not
12345678910t ← 1;
while The termination criteria are not met doS F ← ∅, S C ← ∅;for i ∈ {1, ..., N } do
Generate Fi,t and Ci,t according to meta-parameters;
for i ∈ {1, ..., N } do

if The pair of Fi,t and Ci,t is successful then
S F ← Fi,t , S C ← Ci,tUpdate the meta-parameters based on S F and S C ;t ← t + 1;

11 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

A model of the success/failure decisions in the proposed TPAM
Target parameters θ1target , θ2target , ... are introduced in TPAM
The dicision is made based on the distance from θtarget
The closer θ is from θtarget , the higher its success probability
Target parameters
Successful parameters
Failed parameters
The number of iterations

Success probability depends on two parameters: pmax and d ∈ [0, 1]
A smaller pmax value makes a simulation model diﬃcult
1Success probability = -d + p max

p max

Max. probability 0.50.10d: Distance between a generated parameter and the target parameter

12 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Target parameters θ1target , θ2target , ... are given by a target function g
1. Two types of the linear functions g lin/inc and g lin/dec
1.0

1.0

0.8

0.8

0.6

Target Parameters
PAM-JADE’s µ

0.4
0.2
0.0

010000

20000

30000

40000

50000

0.6
0.4
0.2
0.0

010000

20000

30000

40000

50000

2. The sinusoidal function g sin (left: ω = 10, right: ω = 40)
1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.40.20.0

0.2
010000

20000

30000

40000

50000

0.0010000

20000

30000

40000

50000

3. The random-walk function g ran (left: s = 0.04, right: s = 0.1)
1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2
0.0

0.2
010000

20000

30000

40000

50000

0.0

010000

20000

30000

40000

50000

13 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

The overall TPAM frameworkt ← 1, initialize a meta-parameter;while The termination criteria are not met do3
θttarget ← g(t);4S θ ← ∅;5for i ∈ {1, ..., N } do
6Generate θi,t according to the meta-parameter;
127891011for i ∈ {1, ..., N } do
if isParametersSuccessful(θi,t , θttarget ) = successful thenS θ ← θi,t ;Update the meta-parameter based on S θ ;t ← t + 1;

A parameter θ is (i) C, (ii) F , or (iii) {F, C}
14 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Experimental settings
Settings for Parameter Adaptation Methods (PAMs)
PAM-jDE, PAM-EPSDE, PAM-JADE, PAM-MDE, PAM-SHADEFor each PAM, the hyperparameters recommended by
the original authors were used
Population size = 50
Settings for the proposed TPAM
Number of parameter sampling steps = 50, 000
To evaluate PAMs over a large window of activity
This does not correspond to any specific number ofsearch steps executed by a DE
101 independent runs. pmax ∈ {0.1, 0.2, ..., 1.0}
Evaluation metric for TPAM:
The percentage of successful parameters rsucc ∈ [0, 1]
A higher rsucc represents that the PAM is able to track given
target parameters θ1target , θ2target , ...
15 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

The tracking performance of the five PAMs on the linear functions
PAM-JADE has best tracking for all the pmax values
For the smaller pmax values, PAM-EPSDE cannot track θtarget
PAM-MDE and PAM-SHADE have a hidden bias
Linearly increasing function

Linearly decreasing function

The tracking performance ofPAM-JADE is 1.4 times better
than that of PAM-SHADE

Max. success probability pmax (Smaller is more difficult)

16 / 21Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

The tracking performance of the five PAMs on the sinusoidal function
PAM-EPSDE has best tracking for the larger pmax values
PAM-SHADE has best tracking for the smaller pmax values
The tracking performance of PAM-SHADE on hard TPAM
instances is better than that of the other PAMs
Angular frequency = 10 (easy)

Angular frequency = 40 (hard)

2

PAM-SHADE has 1.04
times the tracking
performance of PAM-JADE

PAM-EPSDE has 1.2
times better tracking
than PAM-SHADEPAM-SHADE has 1.3 times
the tracking performanceof PAM-JADE

Max. success probability pmax (Smaller is more difficult)

17 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

Why does PAM-SHADE track the target better than PAM-JADE?
The diversity of values in M enables PAM-SHADE to be much
more robust than PAM-JADE on hard TPAM instances
ω=10

μ of PAM-JADE

μ of PAM-JADE
mostly overlaps
the target

ω=40

ω=10

ω=40

PAM-JADE clearlyfails to track thetarget parameters

ω=10M of PAM-SHADE

PAM-SHADE
tracks the target
with broadly
distributed values

ω=40

ω=10

ω=40

PAM-SHADE
succeeds intracking the target

18 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

The tracking performance of the PAMs on the random-walk function
Easy instances: PAM-JADE and PAM-EPSDE track well
Hard instances: PAM-SHADE has the best tracking performancepmax = 1 (easy)
The tracking performance ofPAM-SHADE is 1.18 times
worse than that of PAM-JADE

pmax = 0.1 (hard)
PAM-SHADE has 1.13
times better trackingthan PAM-JADE

Step size of random walk s ∈ [001, 0.1]
Larger s harder to track

19 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAMConclusion

How relevant are the target tracking accuracy of PAMs to the search
performance of adaptive DEs? Results on the BBOB functions [Hansen 09]

Proportion of function+target pairs

The rand/1/bin operators are used for all PAMs
An adaptive DE using PAM-SHADE performs well
The tracking performance of a PAM in the TPAM model iscorrelated with search performance of DE using that PAM
1.0best 2009

f1-24,10-D

0.8

PAM-SHADE

0.6

PAM-jDE

0.4

PAM-MDE

0.2

PAM-EPSDE

0.001234

log10 of (# f-evals / dimension)

PAM-JADE
520 / 21

Introduction

Adaptive DEs

TPAM

Experimental settings

Experiment using TPAM

Conclusion

Conclusion:
The first quantitative investigation of the adaptation ability of PAMs
We proposed a Target function-based PAM simulation (TPAM)
TPAM evaluates the tracking performance of PAMs andenables quantitative comparison of PAMs
E.g., PAM-SHADE tracks this particular target behavior 1.3times better than PAM-JADE

TPAM can provide important insights on PAMs,E.g., Why an adaptive DE using PAM-SHADE performs well

TPAM is a promising simulation framework for analyzing PAMs
Future work
Apply TPAM to analysis of PAMs in other EAs (e.g., ESs)
Design an unified, systematic simulation framework
TPAM evaluates only the tracking performance of PAMs
Other simulation models that evaluate other important
aspects of PAMs (e.g., diversity) are necessary
21 / 21

Appendix

Is our definition of success probability appropriate?
All of the parameter values generated by an adaptive DE using thecurrent-to-pbest/1/bin and PAM-JADE on the Rosenbrock
F1.0C

1.0

0.8

0.8

0.6

0.6

0.4

0.4

Failed F
Successful F
Spline curve

0.2
0.0
0.0

0.5

1.0

1.5

2.0

2.5

3.0

3.5

Number of function evaluations

4.0

Failed C
Successful C
Spline curve

0.2

4.5

×104

0.0
0.0

0.5

1.0

1.5

2.0

2.5

3.0

3.5

Number of function evaluations

4.0

4.5

×104

Success probability as a function of the distance of the F (left)
and C (right) from the spline curve
F0.0450.06

Success probability

0.040

0.05

0.035
0.030

0.04

0.025

0.03

0.020
0.015

0.020.010

The assumption that the probability ofgenerating successful trial vectors ishighly correlated with the ability togenerate control parameters values
which accurately track a target
parameter is justifiable

0.01

0.005
0.000
0.0C

0.1

0.2

0.3

0.4

0.5

0.6

0.00
0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45

Distance

22 / 21