Revisiting Population Models in Differential Evolution
on a Limited Budget of Evaluations
Ryoji Tanabe
Yokohama National University, Yokohama, Japan

1. Introduction

7. Summary

I DE has never shown state-of-the-art performance for expensive optimization
I Even a surrogate-assisted DE has never outperformed a non-surrogate-assisted ES
I This work revisits population models in DE for expensive optimization
I A population model determines how to update the population for each iteration
I DE uses the synchronous model, which was designed for inexpensive optimization
Q. Can the performance of DE be improved by using a suitable population model?

A. Yes, the performance of DE can be improved by using a suitable population model
I The (µ + λ) and worst improvement models are suitable for expensive optimization
I DE with the two models perform better than or similar to CMA-ES depending on
FEs and dim n, especially for small FEs (e.g., 10 × n) and/or low n (e.g., n ≤ 10)
I CMA-ES with the auto-tuned parameters significantly outperforms DE for n ≥ 20

2.2. Asynchronous model (Asy) [Wormington 99]
1 Initialize P = {x1, ..., xµ} randomly;
2 while not happy do

for i ∈ {1, ..., µ} do
4u ← Generate a child;
5if f (u) ≤ f (xi) then xi ← u;
3I Immediately after generating u, theparent xi is compared to u
I Asy is generally faster than Syn
I Asy can exploit a new superior
individual for the search immediately

I The worst improvement and (µ + λ) models show the best performance
I The (µ + λ) performs better than the worst improvement model at the early stage
I The traditional synchronous model performs the worst among the 5 models(a) 5 dim.

Q ← ∅;
4 for i ∈ {1, ..., λ} do
5u ← Generate a child;
6Q ← Q ∪ {u};7 P ← µ best individuals in P ∪ Q;
32.4. Worst improvement model (WI) [Ali 11]
1 Initialize P = {x1, ..., xµ} randomly;
2 while not happy do

K ← IDs of λ worst individuals in P ;4 for i ∈ K do
5ui ← Generate a child;
6 for i ∈ K do
7if f (ui) ≤ f (xi) then xi ← ui;
30.8

WI

0.6

Plus

0.4

Asy0.2

STS

31 targets RLs/dim: 0.5..50
from refalgs/best2009-bbob.tar.gz
15 instances

Synv2.3.2

01.0 bbob f1-f24, 20-D

best 2009

0.8

WI

0.6

Plus

0.4

Asy

0.2

STS

31 targets RLs/dim: 0.5..50
from refalgs/best2009-bbob.tar.gz
15 instances

0.02

Synv2.3.2

02log10(# f-evals / dimension)

I Only a few DEs use Plus
5. Results of DE with the auto-tuned parameters
I The so-called target vector is randomly
I “T-” means that the corresponding optimizer uses the auto-tuned parameters
selected from the population P
I For n ∈ {20, 40}, the auto-tuned parameters are more suitable in most cases
I Syn may discard a child that is worse
than its parent but better than others I The results here are almost consistent with the results with the hand-tuned param.
I In contrast, Plus does not do that(d) 20 dim.
(c) 5 dim.

I WI is similar to Syn
I Only λ worst parents generate children
I A better x is rarely replaced with its u
I Generating u is wasteful
I FEs can be reduced by allowing only λworst parents to generate their children

2.5. Subset-to-subset model (STS) [Guo 19]
I Individuals in P ∪ Q are divided into s groups based on the index-based ring topo.
I Individuals in each group is compared with each other

3. Experimental setup
I Setting for test functions
I BBOB noiseless function set [Hansen 09] in COCO [Hansen 16]
I All ECDF figures were generated by COCO with the option --expensive
I Dimensionality n ∈ {2, 3, 5, 10, 20, 40}
I Maximum number of evaluations = 100 × n, number of runs = 15
I Two parameter settings for DE
1. Hand-tuned parameters
I Configurator: Ryoji Tanabe. Training problem set: the Sphere function

2. Automatically-tuned parameters
I Configurator: SMAC [Hutter 11]. Training problem set: CEC2013 [Liang 13]

I Source code and performance data are available:
I https://github.com/ryojitanabe/de_expensiveopt

Fraction of function,target pairs

2 while not happy dobest 2009log10(# f-evals / dimension)

1.0 bbob f1-f24, 5-D

best 2009

31 targets RLs/dim: 0.5..50
from refalgs/best2009-bbob.tar.gz
15 instances

WI0.8

Plus
T-WI
Asy0.6

T-STSSTS0.4

T-PlusSyn0.2T-Asy
0.0

T-Syn

v2.3.20

1.0 bbob f1-f24, 20-D

T-Plus

0.8

WI
T-STS
Plus

0.6

T-WI
Asy

0.4

T-Asy
STS

0.2

Syn
0.02

best 2009

31 targets RLs/dim: 0.5..50
from refalgs/best2009-bbob.tar.gz
15 instances

T-Syn

v2.3.20log10(# f-evals / dimension)2log10(# f-evals / dimension)

6. Comparison to state-of-the-art optimizers
I Two surrogate model-based optimizers (SMAC-BBOB and lmm-CMA) perform the best
I For any n, WI and (µ + λ) perform better than a SOTA DE (R-SHADE-10e2)
I For n ≤ 10, WI and (µ + λ) perform better than or similar to CMAES Hutter
I For n ≥ 20, WI and (µ + λ) perform better than CMAES Hutter at the early stage
I For n ≥ 20, WI and (µ + λ) perform significantly worse than texp liao at anytime(e) 5 dim.
Fraction of function,target pairs

1 Initialize P = {x1, ..., xµ} randomly;

1.0 bbob f1-f24, 5-D

0.0

2.3. (µ + λ) model (Plus)(b) 20 dim.
Fraction of function,target pairs

for i ∈ {1, ..., µ} do
4ui ← Generate a child;
5 for i ∈ {1, ..., µ} do
6if f (ui) ≤ f (xi) then xi ← ui;
34. Results of DE with the hand-tuned parameters

Fraction of function,target pairs

2 while not happy do

I Population size µ, population P ,parent individual x, child u
I Syn updates all individuals in P
simultaneously
I The index-based niching mechanism in
Syn promotes diversity(f) 20 dim.

1.0 bbob f1-f24, 5-D

best 2009

31 targets RLs/dim: 0.5..50
from refalgs/best2009-bbob.tar.gz
15 instances

lmm-CMA-E

0.8

WIT-Plus

0.6

CMAES Hut
0.4

texp liao
R-SHADE-1

0.2
0.0

SMAC-BBOB
DE-scipy-v2.3.2

02log10(# f-evals / dimension)

Fraction of function,target pairs

1 Initialize P = {x1, ..., xµ} randomly;

Fraction of function,target pairs

2.1. Synchronous model (Syn) [Storn 97]

I Future work
I incorporate a parameter adaptation method for F and C into DE
I design a surrogate-assisted DE with the (µ + λ) and worst improvement models

1.0 bbob f1-f24, 20-D

best 200931 targets RLs/dim: 0.5..50
from refalgs/best2009-bbob.tar.gz
15 instances

lmm-CMA-E

0.8

texp liao
CMAES Hut0.6

T-Plus
0.4

WI
R-SHADE-1

0.2
0.0

SMAC-BBOB
DE-scipy-v2.3.2

02log10(# f-evals / dimension)

I SMAC-BBOB [Hutter 13] is a Bayesian optimizer (almost EGO). lmm-CMA [Auger 13] is a surrogate-assisted CMA-ES
I CMAES Hutter [Hutter 13] is a CMA-ES with the default parameters
I texp liao [Liao 13] is a CMA-ES with auto-tuned parameters for expensive optimization
I R-SHADE-10e2 [Tanabe 15] is a SHADE with auto-tuned parameters for expensive optimization
I DE-scipy [Varelas 19] is DE from the Python SciPy library