Analyzing Adaptive Parameter Landscapes inParameter Adaptation Methods forDifferential Evolution

Ryoji Tanabe
Yokohama National University
Yokohama, Japan

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Differential Evolution (DE) [Storn 97]: A simple black-box optimizer
DE is sensitive to the setting of two parameters: F and C• Scale factor F controls the magnitude of the differential mutation• Crossover rate C controls the number of inherited variables from x
Adaptive DE algorithms• E.g., jDE [Brest 06], JADE [Zhang 09], SHADE [Tanabe 13]• adaptively adjust F and C values
Poor understanding of parameter adaptation mechanisms in DE• Its working principle is unclear• Only a few previous studies tried to analyze adaptive DEs• E.g., [Zielinski 08, Drozdik 15, Tanabe 16, Tanabe 17, Tanabe 20]

Difficulty comes from the unclarity of the adaptive parameter space• Is it possible to make the adaptive parameter space “visualizable”?
2 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed methodResults

ConclusionContributions
This work
1. proposes a concept called adaptive parameter landscapes
2. proposes a method of analyzing adaptive parameter landscapes
3. provides insightful knowledge on parameter adaptation in DE
Visualization of dynamically changing parameter landscapes

3 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Fitness landscape analysis
Fitness landscape [Pitzer 12]
Lfitness = (X, f, D)• X: solution space, f : objective function, D: distance function

No explanation needed in GECCO

4 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Parameter landscape analysis
Parameter landscape [Harrison 19]
Lparameter = (Θ, M, D),• Θ: parameter space, M : performance metric, D: distance function• Lparameter is an Lfitness of a parameter tuning problem
Example: parameter tuning of F ∈ [0, 1] and C ∈ [0, 1] in DE• to find the best pair (F, C) ∈ Θ on a training problem set I• Θ = [0, 1] × [0, 1], M : ERT on I, D: Euclidean distanceParameter landscapes coined in [Yuan 12] are also known as• performance landscapes [Yuan 07], meta-fitness landscapes [Pedersen 10], utility
landscapes [Eiben 11], ERT landscapes [Belkhir 16], parameter configuration
landscapes [Harrison 19], and algorithm configuration landscapes [Pushak 18]• No consistency in the terminology in the EC community
5 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

ResultsConclusion

Proposed concept: adaptive parameter landscapes
Parameter landscape [Harrison 19]
Lparameter = (Θ, M, D)
Adaptive parameter landscape
Ladaptive = (Θti , M, D)• Θti : dynamic parameter space of xti , M : performance metric, D:distance function• Ladaptive is an Lparameter of the i-th individual at iteration t (xti )• While Lparameter is static, Ladaptive is dynamic
Example: parameter adaptation of F ∈ [0, 1] and C ∈ [0, 1] in DE• to find the best pair (Fit , Cit ) ∈ Θti for xti• Θti = [0, 1] × [0, 1], M : G1 (explained later), D: Euclidean distance
6 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Parameter landscapes vs. adaptive parameter landscapes (F and C in DE)
Parameter landscape Lparameter = (Θ, M, D) is STATIC
Parameter landscape of DE [Belkhir 16]

Adaptive parameter landscape Ladaptive = (Θti , M, D) is DYNAMIC

N. Belkhir, J. Dréo, P. Savéant, M. Schoenauer: Feature Based Algorithm Configuration: A Case Study with Differential Evolution. PPSN
2016: 156-166

7 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Parameter landscapes vs. adaptive parameter landscapes (continued)

What the parameter
landscape analysis focuses on

What the adaptive parameter
landscape analysis focuses on

Overall search process
1st iteration

2nd iteration

1st individual

1st individual

2nd individual

2nd individual

μ-th individualth individual

μ-th individualth individual

8 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

NOT proposed: 1-step-lookahead greedy improvement metric (G1)
Nomenclature• xti : the i-th individual in the population at iteration t• uti : the i-th child generated by xti at iteration t• Fit : the scale factor value used for generating uti• Cit : the crossover rate value used for generating uti
G1 measures how much Fit and Cit improve the fitness value of xti
G1(Fit , Cit ) =(|f (xti ) − f (uti )|0

if f (uti ) < f (xti )otherwise• If f (xti ) = 10 and f (uti ) = 3, G1(Fit , Cit ) = 7• If f (xti ) = 10 and f (uti ) = 30, G1(Fit , Cit ) = 0• Just for the sake of simplicity, we use the term “G1”
• G1 can be replaced with G2, G3, and G1 + novelty
9 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Proposed method for analyzing adaptive parameter landscapes
For the i-th individual at iteration t (xti )1. Generate 50 × 50 = 2 500 pairs of F and C in a grid manner
2. Generate 2 500 children by using the 2 500 pairs of F and C• Same random numbers are used for generating the 2 500 children

3. Evaluate the objective function values of the 2 500 children• Extra 2 500 function evaluations are not counted

4. Calculate the G1 values of the 2 500 pairs(a) 50 × 50 pairs(b) Contour map of Ladaptive

0.6

0.6

0.60

0.4

0.45

0.4
0.2
00 0.2 0.4 0.6 0.8 1
FC

1
0.8

C1
0.8

0.2
00 0.2 0.4 0.6 0.8 1
F

1.00
0.90
0.75

0.30
0.15
0.00

10 / 16Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Properties of the proposed method
Proposed method is totally independent from the procedure of DE• Proposed method is just a logger, not an optimizer• 2 500 children are used only for the analysis, not for the search• Behavior of DE with/without the proposed method is the same
Suppression strategy of the randomness in DE• 1 child for the actual search and 2 500 children for the G1
calculation are generated using the same parents and crossover mask
• Stochastic nature of DE can be suppressed
Cheat in not counting the 2 500 extra function evaluations• This cheat is no problem at all for the analysis• We are not interested in solving any real-world problem

11 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Experimental setup
Settings for adaptive DEs• jDE [Brest 06], JADE [Zhang 09], SHADE [Tanabe 13]• Default hyperparameter settings• Population size µ = 100, no restart• Current-to-pbest/1 [Zhang 09], binomial crossover [Storn 97]
Settings for test functions• 24 BBOB noiseless functions [Hansen 09] in COCO [Hansen 16]• Dimensionality n ∈ {2, 3, 5, 10, 20, 40}• Maximum number of evaluations = 10 000 × n• Number of runs = 15 (results of a single run are shown)
Source code is available:• https://github.com/ryojitanabe/APL
12 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

ResultsConclusion

Contour maps of adaptive parameter landscapes in SHADE on
the 20-dimensional Sphere function (f1 )100fe

18,000fe112,000fe

116,000fe

25th

100001 011 011 0110001 0101 0
101 01101 0
101 0
101 011• ◦: the pair generated by SHADE• ?: the best pair regarding G175th

100100th

100
1 0

000
1 00.15 0.3 0.45 0.6 0.75 0.9 1

G1

01 0x axis: Fy axis: C• Pairs for the best (1st) individual
are seldom successful, so omitted it• SHADE found x∗ at ≈ 16 000 fe

50th

10

• 100 individuals were sorted1• Shape of Ladaptive is different
depending on:• the rank of each individual• the search progress• ◦ and ? are far from each other• Ladaptive is unimodal/multimodal?

13 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed methodResults

Conclusion

Contour maps of adaptive parameter landscapes in SHADE on
the 20-dimensional Rastrigin function (f3 )100fe

143,000fe 65,000fe

87,000fe

1101 0101 0110011101 0101 0101 0101 01125th

100
1 000

• Ladaptive at 43 000 fe looks hard0175th

100100th10• Ladaptive at 100 fe looks easy
• Area with G1 > 0 is large

50th

1

• Generating a successful pair on f3
is more difficult than that on f1• Area with G1 > 0 is very small
like needle-in-haystack land.
• When all 2 500 pairs obtain
G1 = 0, Ladaptive is not shown• Ladaptive at 87 000 fe looks easy
01 00001 00.15 0.3 0.45 0.6 0.75 0.9 1G101 0x axis: Fy axis: C1• Area with G1 > 0 values
becomes large again• SHADE found x∗ at ≈ 87 000 fe• Population has converged to x∗• Generating better children is easy
14 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

ResultsConclusion

Average FDC values of adaptive parameter landscapes in SHADE (n = 20)• Results of FDC [Jones 95] and Dispersion [Lunacek 06] are similar• FDC value is different depending on the function• Ladaptive of individuals with similar ranks have similar FDC values• E.g., FDC values of the 75th and 100th individuals are similar• Global structures of Ladaptive can correlate with the rank of indiv.
1st25th

50th

75th

100th

0.8

0.4
0.2
0.0

12
3
4
56
78
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

FDC

0.6

24 BBOB functions

15 / 16

Introduction

Fitness/parameter landscapes

Proposed adaptive parameter landscapes

Proposed method

Results

Conclusion

Conclusion
This work• proposed the concept called adaptive parameter landscapes Ladaptive• proposed the method of analyzing adaptive parameter landscapes• provided insightful knowledge on parameter adaptation in DE
Our observations• Ladaptive is different depending on the search progress• Ladaptive is influenced by the properties of a problem• Global structures of Ladaptive can correlate with the rank of indiv.
• ADEs generally generate a pair of F and C far from the best pair
Future work
• analyze other adaptive evolutionary algorithms, e.g., GA and ES• use other performance metric, e.g., G2 and G1+novelty
16 / 16

Contour maps of adaptive parameter landscapes in SHADE on
the 20-dimensional Gallagher and Katsuura functions (f22 and f23 )• Results of the 100-th individual at 100 evaluations• Shape of adaptive parameter landscapes is significantly influenced by
the global structures of fitness landscapes

0.4

0.45

C

0.60

00 0.2 0.4 0.6 0.8 1
F

0.8

0.75

0.6
0.2

1

1.00
0.90

0.30
0.15
0.00

1.00
0.90
0.75

0.6

0.60

0.4

0.45

C1
0.8

0.2
00 0.2 0.4 0.6 0.8 1F[Hansen 09]

0.30
0.15
0.00Parameter landscape analysis
Parameter landscapes of MMAS [Yuan 12]

Motivation• A better understanding of Lparameter can lead to a better
understanding of the corresponding optimizer• making the optimizer more efficient• Knowledge on Lparameter are useful for designing a parameter tuner
Z. Yuan and M. A. M. de Oca, M. Birattari, T. Stützle: Continuous optimization algorithms for tuning real and integer parameters of swarm
intelligence algorithms. Swarm Intelligence 6(1): 49-75 (2012)Basic DE with almost any parameter adaptation method
input: X ⊆ Rn , f : Rn → R, population size µ, some hyperparameterst ← 1, initialize P = {x1 , ..., xµ } randomly;
Initialize internal parameters for adaptation of F and C;
while The termination criteria are not met dofor i ∈ {1, ..., µ} do
Generate Fi and Ci ;Randomly select r1 , r2 , r3 from {1, ..., µ} \ {i} s.t. r1 6= r2 6= r3 ;Mutant vector v i ← xr1 + Fi (xr2 − xr3 );Child ui = (ui,1 , ..., ui,n )> , randomly select jrand form {1, ..., n};
for j ∈ {1, ..., n} do
if rand[0, 1] ≤ Ci or j = jrand then ui,j ← vi,j ;else ui,j ← xi,j ;for i ∈ {1, ..., µ} do
if f (ui ) ≤ f (xi ) then xi ← ui ;Update internal parameters for adaptation of F and C;t ← t + 1;

Basic DE [Storn 97]
input: X ⊆ Rn , f : Rn → R, population size µ, scale factor F , crossover rate Ct ← 1, initialize P = {x1 , ..., xµ } randomly;
while The termination criteria are not met dofor i ∈ {1, ..., µ} do
Randomly select r1 , r2 , r3 from {1, ..., µ} \ {i} s.t. r1 6= r2 6= r3 ;Mutant vector v i ← xr1 + F (xr2 − xr3 );Child ui = (ui,1 , ..., ui,n )> , randomly select jrand form {1, ..., n};
for j ∈ {1, ..., n} do
if rand[0, 1] ≤ C or j = jrand then ui,j ← vi,j ;else ui,j ← xi,j ;for i ∈ {1, ..., µ} do
if f (ui ) ≤ f (xi ) then xi ← ui ;t ← t + 1;

Basic DE with the parameter adaptation method in JADE [Zhang 09]
input: X ⊆ Rn , f : Rn → R, population size µ, adaptation rate α = 0.1t ← 1, initialize P = {x1 , ..., xµ } randomly;
Initialize internal parameters mF ← 0.5 and mC ← 0.5;
while The termination criteria are not met dofor i ∈ {1, ..., µ} doFi ∼ CauchyDist(mF , 0.1) and Ci ∼ NormalDist(mC , 0.1);
Randomly select r1 , r2 , r3 from {1, ..., µ} \ {i} s.t. r1 6= r2 6= r3 ;Mutant vector v i ← xr1 + Fi (xr2 − xr3 );Child ui = (ui,1 , ..., ui,n )> , randomly select jrand form {1, ..., n};
for j ∈ {1, ..., n} do
if rand[0, 1] ≤ Ci or j = jrand then ui,j ← vi,j ;else ui,j ← xi,j ;for i ∈ {1, ..., µ} do
if f (ui ) ≤ f (xi ) then xi ← ui ;mF ← (1 − α)mF + α Lmean(S F ) and mC ← (1 − α)mC + α mean(S C );t ← t + 1;

Behavior of the internal parameters mF and mC in JADE(c) Rastrigin (n = 10)

mC

1.0
0.8
0.6
0.4
0.2
0.00

mF

mC

mF and mC

mF

mF and mC

1.0
0.8
0.6
0.4
0.2
0.00

(d) Rosenbrock (n = 10)15000 30000 45000

Number of evaluations

20000

40000

Number of evaluations