Benchmarking Parameter Control Methods in DE
for Mixed-Integer Black-Box Optimization
GECCO 2024 at Melbourne

Ryoji Tanabe
Yokohama National University
Yokohama city, Japan

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

Mixed-integer black-box optimization in this work

Note: Categorical variables are not considered

2 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

Mixed-integer BBOB (bbob-mixint) [Tušar 19]• bbob-mixint consists of 24 mixed-integer functions• They are mixed-integer versions of the 24 bbob functions• The first 4n/5 variables are integer

Tea Tušar, Dimo Brockhoff, Nikolaus Hansen: Mixed-integer benchmark problems for single- and bi-objective optimization. GECCO
2019: 718-726

3 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

CMA-ES variants outperform the Scipy imple. ofdifferential evolution (DE) on bbob-mixint [Marty 23]

Tristan Marty, Yann Semet, Anne Auger, Sébastien Héron, Nikolaus Hansen : Benchmarking CMA-ES with Basic Integer Handlingon a Mixed-Integer Test Problem Suite. GECCO Companion 2023: 1628-1635

4 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

SetupResults

Conclusion

Contribution: This work benchmarks parameter
control methods (PCMs) in DE on bbob-mixint• Two critical parameters in DE• Scale factor s > 0 for differential mutation• Crossover rate c ∈ [0, 1] for crossover• Best settings of s and c depend on a problem• DE requires a PCM that automatically adjusts s and c• Their importance is well known for continuous optimization• All state-of-the-art DEs (e.g., L-SHADE) use them

• Their effectiveness is unknown for mixed-integer opt.
• The performance of DE can possibly be improved

5 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

Scale factor s and crossover rate c are critical in DE• For each iteration of DE, the µ individuals x1 , . . . , xµgenerate the µ children u1 , . . . , uµ
• In environmental selection, ui is compared only to xi• For each i ∈ {1, . . . , µ}, if f (ui ) ≤ f (xi ), xi ← ui

• Scale factor s determines the magnitude of mutationvi = xr1 + s (xr2 − xr3 )• Crossover rate c determines the number of elements
inherited from each parent x to a child u⎧⎪⎪vi,j if rand[0, 1] ≤ c or j = jrandui,j = ⎨⎪⎪⎩xi,j otherwise
6 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

This work focuses only on PCMs in DE
I am interested in “the PCM in jDE”, not “jDE”

7 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

This work benchmarks 9 PCMs in DE• 3 deterministic PCMs
• PCM in CoDE [Wang 11]• PCM in SinDE [Draa 15]• PCM in CaRS+S [Molina-Pérez 24]• 6 adaptive PCMs
• PCM in jDE [Brest 06]• PCM in cDE [Tvrdık 06]• PCM in JADE [Zhang 09]• PCM in EPSDE [Mallipeddi 11]• PCM in SHADE [Tanabe 13]• PCM in CoBiDE [Wang 14]

8 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

SetupResults

Conclusion

Deterministic parameter control methods in DE• Generating s and c values based on a simple rule

• without using any information obtained by the search• Example: The PCM in SinDE [Draa 15]• s and c are determined based on the sinusoidal functions

Amer Draa, Samira Bouzoubia, Imene Boukhalfa: A sinusoidal differential evolution algorithm for numerical optimisation. Appl.
Soft Comput. 27: 99-126 (2015)

9 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

Most adaptive PCMs in DE use a success criterion• If the child ui is better than its parent xi , the pair ofsi and ci are said to be successful• Assumption: The better child was generated because thepair of si and ci was suitable for a target problem• Example: The PCM in jDE [Brest 06]

Janez Brest, Saso Greiner, Borko Boskovic, Marjan Mernik, Viljem Zumer: Self-Adapting Control Parameters in Differential Evolution:
A Comparative Study on Numerical Benchmark Problems. IEEE Trans. Evol. Comput. 10(6): 646-657 (2006)
10 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

SetupResults

Conclusion

Rounding operator to repair infeasible solutions

11 / 19Introduction

Parameter control methods (PCMs)

Repair methods

SetupResults

Conclusion

The Lamarckian and Baldwinian repair methods• Let y be a repaired feasible version of an infeasible x• Both of them use f (y) as f (x) , but ...
• The Lamarckian one replaces x with y• The Baldwinian one doesn’t replace x with y• All individuals in the population are ...
• always feasible for the Lamarckian one• likely to be infeasible for the Baldwinian one• There is no clear winner between them [Salcedo-Sanz 09]

Sancho Salcedo-Sanz: A survey of repair methods used as constraint handling techniques in evolutionary algorithms. Comput. Sci.
Rev. 3(3): 175-192 (2009)12 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

Experimental setup• The COCO platform [Hansen 21]• The 24 bbob-mixint functions• Num. variables n ∈ {5, 10, 20, 40, 80, 160}

• Settings for DE: (9 + 1) × 8 × 2 = 160 configurations• The max. fun. evals. was set to 104 × n• The population size µ: 100• Hyper-par. in the 9 PCMs: default• For DE with no PCM, s = 0.5 and c = 0.9• Eight representative mutation strategies• The Lamarckian and Baldwinian repair methods
Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, Dimo Brockhoff: COCO: a platform for comparing
continuous optimizers in a black-box setting. Optim. Methods Softw. 36(1): 114-144 (2021)

13 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

Results for n = 80 (rand/1, Baldwinian)
PCMs can improve the performance of DE
Fraction of function,target pairs

1.0

P-Sinbbob-mixint f1-f24, 80-D
51 targets: 100..1e-08
15 instances

P-j

0.8

P-EPS
P-CoBi

0.6

P-CaRS
P-JA

0.4

P-c
NOPCM

0.2

P-Co
0.0

P-SHA

v2.6.3012

34log10(# f-evals / dimension)
14 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

Conclusion

Results for n = 80 (rand/1, Baldwinian)• DE with the PCM in SHADE performs poorly• P-SHA is SOTA for continuous bbob
• Rankings for bbob and bbob-mixint are different
Fraction of function,target pairs

1.0

P-Sin

bbob-mixint f1-f24, 80-D
51 targets: 100..1e-08
15 instances

P-j

0.8

P-EPS
P-CoBi

0.6

P-CaRS
P-JA

0.4

P-c
NOPCM

0.2

P-Co
0.0

P-SHA

v2.6.3

01

2

3

4

log10(# f-evals / dimension)

15 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

ResultsConclusion

Best PCM depends on the type of mutation strategy
Results of the Baldwinian repair method
Strategyn=5n = 10n = 20n = 40n = 80n = 160rand/1
rand/2
best/1
best/2
ctb/1
ctr/1
ctp/1
rtp/1

NOPCM
P-Sin
P-Co
P-CoBiP-CoBiP-CoBi
P-Co
P-Co

P-CoBi
P-c
P-Sin
P-Sin
P-Sin
P-Sin
P-Sin
P-j
P-Co
P-Co
P-Co
P-Co
P-CoBi P-EPS P-CoBi
P-c
P-Co
P-Co P-CoBi P-Co
P-CoBi P-CoBi P-CoBi P-CoBi
P-CoBi P-Co
P-Co
P-Co
P-Co
P-Co
P-Co
P-Co

P-Sin
P-j
P-JA
P-c
P-JA
P-CoBi
P-Co
P-Co

16 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

Setup

Results

ConclusionBest PCM depends on the type of repair method
Results of the Lamarckian repair method
Strategyn=5n = 10n = 20n = 40n = 80n = 160

rand/1
rand/2
best/1
best/2
ctb/1
ctr/1
ctp/1
rtp/1

P-CoBi
P-Sin
P-Co
P-CoBiP-Co
P-CoBiP-CoBiP-CoBiP-CoBi P-CoBi P-CaRS P-CoBi
P-Sin P-CoBi P-Sin P-CoBi
P-Co
P-Co
P-Co
P-Co
P-CoBi P-Co P-CaRS P-Co
P-CoBi P-Co
P-Co
P-Co
P-CoBi P-Co
P-CoBi P-CoBi
P-CoBi P-CoBi
P-Co
P-CoP-SHA P-Co
P-Co
P-Co

P-JA
P-CoBi
P-Co
P-Co
P-Co
P-CoBi
P-Co
P-Co

17 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

SetupResults

Conclusion

Comparison with CMA-ES variants (n = 80)
DE with PCMs perform well for larger budgets of fevals
Fraction of function,target pairs

1.0

P-j

bbob-mixint f1-f24, 80-D
51 targets: 100..1e-08
15 instances

0.8

P-CoBi0.6

cmaIH1e-1

0.4

CMA-ESwM

0.2

CMA-ES-py

0.0

DE-scipy

v2.6.3012

34

log10(# f-evals / dimension)
18 / 19

Introduction

Parameter control methods (PCMs)

Repair methods

SetupResults

Conclusion

Conclusion: parameter control methods (PCMs)• 9 PCMs in DE were benchmarked on bbob-mixint• Using a PCM can improve the performance of DE• The best PCM depends on the type of• mutation strategy (e.g., rand/1, rand/2, best/1, etc.)• repair method (Lamarckian and Baldwinian)• The best PCMs on bbob and bbob-mixint are different• PCM in SHADE does not work for bbob-mixint• PCM in CoDE, CoBiDE, jDE, and SinDE work well

• DE with a suitable PCM performs better than CMA-ES on
bbob-mixint for larger budgets of fevals• Many future works: analysis of “DE” and “PCMs”• Nobody can explain how the results happened• Even analysis of DE for mix-int. opt. has not been done
19 / 19