Introduction

EMO algorithms

Results

Discussion

Conclusion

Non-elitist Evolutionary Multi-objective Optimizers
Revisited
Ryoji Tanabe and Hisao Ishibuchi (SUSTech)

Slides and source code are available at my website

1 / 23Introduction

EMO algorithms

Results

Discussion

Conclusion

Revisiting non-elitist EMO algorithms (EMOAs)
1985 (VEGA)
Non-elitist EMOAs

1999 (SPEA)
Elitist EMOAs

2019 (Our work)
Non-elitist EMOAs

Common belief: Elitist EMOAs always outperform non-elitist EMOAs
Since 1999, only elitist EMO algorithms have been studied
NSGA-II, SPEA2, IBEA, MOEA/D, SMS-EMOA, ...
We revisit non-elitist EMOAs for the first TIE time in 20 years
COMO-CMA-ES [Touré GECCO’19] presented in the EMO1 session
Target problem domain: Bi-objective continuous optimization
Bi-objective BBOB problems [Tusar 16]
We show a counter-example to the common belief
Non-elitist EMOAs can outperform elitist EMOAs under someconditions
Our results significantly expand the design possibility of EMOAs
T. Tusar, D. Brockhoff, N. Hansen, and A. Auger. 2016. COCO: The Bi-objective Black Box Optimization Benchmarking (bbob-biobj) Test Suite. CoRR abs/1604.00359 (2016).

2 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Comparison of NSGA-II and a non-elitist EMOA
on the 40-dimensional f 46 in the bi-objective BBOB problem suitef 46 : the rotated-Rastrigin (f1 ) and the rotated-Rastrigin (f2 )The final populations in a single run are shown

The non-elitist EMOA finds a better approximation than NSGA-II900

f2NSGA-IINE-EMOA

600

300
300600f1900

1200
3 / 23

Introduction

EMO algorithms

ResultsDiscussion

Conclusion

Please do not get angry at my presentation
One reviewer was extremely angry!

/ Bad

Grrrrrrrrrr! Elitist EMOAs must outperform non-elitist EMOAs!
Terrible! A was not done! B was not done! ... Z was not done!

, GoodElitist EMOAs may be outperformed by non-elitist EMOAs
Blue ocean! I have a lot to do! Homework for GECCO2020!
4 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Five crossover methods in GAs for continuous optimization(a) SBX+PM (Deb 95) (b) BLX (Eshelman 92)(c) PCX (Deb 02)(d) SPX (Tsutsui 99)(e) REX (Akimoto 10)

5 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

A “simple” EMO framework analyzed in this work
Initialize the population P = {x(1) , ..., x(µ) };while Not happy do
R ← Randomly select k parents from P ;Q ← Generate λ children by applying the crossover method to R;
P ← Apply the environmental selection (P , Q, R);
1. Best-all: the traditional elitist (µ + λ)-selection
The best µ individuals are selected from P ∪ Q
2. Best-family: An elitist restricted selection
The selection is performed only among the “family” R ∪ Q
The best k individuals are selected from the k + λ individuals
3. Best-children: A non-elitist restricted selection (not (µ, λ)-selection)
An extended version of JGG [Akimoto 10] for single-obj. opt.
The k parents in R are always removed from P
The best k individuals are selected from the λ children in Q
Youhei Akimoto. Design of Evolutionary Computation for Continuous Optimization. Ph.D. Dissertation. Tokyo
Institute of Technology (2010)

6 / 23

Introduction

EMO algorithms

ResultsDiscussion

Conclusion

The “simple” EMO framework analyzed in this work (continued)
Summary of the three environmental selections
Best-allBest-family
Best-children

Elitism?

Restricted?

Max. replacements

Yes
Yes
NoNo
Yes
Yes

Pop. size µ
Num. parents k
Num. parents k

The EMOA requires a ranking method to select the best individuals
The EMOA can be combined with any ranking method
Similar to MO-CMA-ES
Ranking methods in NSGA-II, SMS-EMOA, SPEA2, and IBEA
Their results are similar
The ranking method in NSGA-II
1. Individuals are ranked based on their non-domination levels
2. Ties are broken by the crowding distance7 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Experimental settings
Problem suite
Experiments were performed using the COCO platform [Hansen 16]
55 bi-objective BBOB problems [Tusar 16]
Number of decision variables n ∈ {2, 3, 5, 10, 20, 40}
Number of function evaluations: 104 × n
Performance measure in COCO
Roughly speaking, hypervolume value of non-dominated solutions in
the unbounded external archive
EMO algorithms
EMOAs were implemented using jMetal [Durillo 11]
Population size µ = ⌊100 ln(n)⌋Number of children λ = 10 × n
Number of parents k = 2 for SBX and BLX
k = n + 1 for PCX, SPX, and REX
N. Hansen, A. Auger, O. Mersmann, T. Tusar, and D. Brockhoff. COCO: A Platform for Comparing Continuous
Optimizers in a Black-Box Setting. CoRR abs/1603.08785 (2016).
J. José Durillo and A. J. Nebro. jMetal: A Java framework for multi-objective optimization. Adv. Eng. Softw. 42,10 (2011), 760771.

8 / 23

Introduction

EMO algorithms

ResultsDiscussion

Conclusion

I am tired of explaining how to read ECDF figures
What’s the vertical axis?

Why not normalize the vertical axis?

Why these fonts
are small?

What’s the cross?

Why start from here?

Why no optimizer reaches 1?
What’s best 2016?

Why the lines sharply
increase/decrease?

What’s thisvertical line?

It is tooooo time-consuming
Please see the guideline [Hansen 16] after this presentation
Don’t think now. Feel
9 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Comparison on all the 55 bi-objective BBOB problems (SBX, n = 2)
NSGA-II outperforms best-all, best-family, and best-children
1.0 bbob-biobj f1-f55, 2-D

best 2016

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.8

NSGA-II
0.6

All
0.4

Children
0.2

0.00v0.0.0, hv-hash=ff0e71e8cd978373

1234

Familylog10(# f-evals / dimension)

10 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Comparison on all the 55 bi-objective BBOB problems (SBX, n = 10)
NSGA-II outperforms best-all, best-family, and best-children
1.0 bbob-biobj f1-f55, 10-D

best 2016Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.8

NSGA-II
0.6

All
0.4

Family0.2

0.00v0.0.0, hv-hash=ff0e71e8cd978373

1234Children

log10(# f-evals / dimension)

11 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Comparison on all the 55 bi-objective BBOB problems (SBX, n = 40)
NSGA-II outperforms best-all, best-family, and best-children
1.0 bbob-biobj f1-f55, 40-D

best 2016

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances0.8

NSGA-II
0.6

All0.4

Children0.2

0.00

v0.0.0, hv-hash=ff0e71e8cd978373

1234

Familylog10(# f-evals / dimension)

12 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Summary of the results when using SBX
Restricted best-family and best-children perform the worst
NSGA-II performs the best
Results are consistent with previous studies
Results of SBX, BLX, and PCX are similar
1.0 bbob-biobj f1-f55, 40-D

best 2016

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.8

NSGA-II0.6

All0.4

Children
0.2

0.00v0.0.0, hv-hash=ff0e71e8cd978373

1234

Familylog10(# f-evals / dimension)

13 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Comparison on all the 55 bi-objective BBOB problems (SPX, n = 2)Best-family performs the best after 103 × n function evaluations
Best-children performs the second best
1.0 bbob-biobj f1-f55, 2-D

best 2016

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.8

Family0.6

Children0.4

NSGA-II0.20.00v0.0.0, hv-hash=ff0e71e8cd978373

1234Alllog10(# f-evals / dimension)

14 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Comparison on all the 55 bi-objective BBOB problems (SPX, n = 10)Best-family performs the best after 2 × 103 × n function evaluations
Difference between best-family and best-children is small
1.0 bbob-biobj f1-f55, 10-D

best 2016

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.8

Family0.6

Children0.4

NSGA-II
0.20.00v0.0.0, hv-hash=ff0e71e8cd978373

1234

All

log10(# f-evals / dimension)

15 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Comparison on all the 55 bi-objective BBOB problems (SPX, n = 40)
Best-children performs the best after 2 × 103 × n function evaluations
Best-family performs the second best
1.0 bbob-biobj f1-f55, 40-D

Children

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.8

Family0.6

best 2016
0.4

NSGA-II0.2

0.00

v0.0.0, hv-hash=ff0e71e8cd978373

1234

Alllog10(# f-evals / dimension)

16 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Summary of the results when using SPX
Non-elitist best-children performs best on the 40-dimensional problems
Best-family performs the best for n < 40
Two restricted selections (best-family and best-children) work well
Results using SPX and REX are similar
1.0 bbob-biobj f1-f55, 40-D

Children

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.8

Family0.6

best 2016
0.4

NSGA-II
0.20.00v0.0.0, hv-hash=ff0e71e8cd978373

1234Alllog10(# f-evals / dimension)

17 / 23

Introduction

EMO algorithms

ResultsDiscussion

Conclusion

Why SPX is unsuitable for the traditional (µ + λ) best-all?
Why SPX is suitable for the restricted best-family and best-children?
Recall the property of the three environmental selections
Best-allBest-family
Best-children

Elitism?

Restricted?

Max. replacements

Yes
Yes
NoNo
Yes
Yes

Pop. size µ
Num. parents k
Num. parents kAnswer: Restricted selection can prevent the premature convergence
SPX can generate children near the parents when λ is enough large
This causes the premature convergence in best-all(a) SBX+PM (Deb 95)(b) SPX (Tsutsui 99)

18 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Effect of the restricted selection on the 3-dim f 1 (when using SPX)
Current population

Parents and children

BiasedNext population(Best-all)

Next population(Best-family)

BiasedUnbiased

19 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Bad effect of the restricted selection on the 3-dim f 1 (when using SBX)
Current population

Parents and children

Unbiased

Next population(Best-all)Unbiased

Next population(Best-family)
Unbiased
Restriction causes a weak
selection pressure

20 / 23Introduction

EMO algorithms

ResultsDiscussion

Conclusion

Advantage of the non-elitist best-children selection
Non-elitist selections can accept “uphill” moves as in simulated annealing
Elitist selections (best-family) can accept only “downhill” moves
Uphill moves help the population to escape from local optima
Benefit of the non-elitist selection is consistent with [Akimoto 10]

Results on the 40-dimensional f 46 function (Rast./Rast.)

Almost HV

0.50.4Best-familyBest-children

0.3
0.2
0.101e5 2e5 3e5 4e5
Number of evaluations
21 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Disadvantages of the non-elitist best-children
1. Poor performance on problems n < 40Best-children is outperformed by best-family for n < 40
Reason is unclear
2. Slow convergence
Best-children performs worse than best-family at the early stage
Reason is similar to the relation between (1, λ)-ES and (1 + λ)-ES(a) n = 10(b) n = 40

1.0 bbob-biobj f1-f55, 10-D

0.8

Family0.6Children
0.4

NSGA-II
0.2

0v0.0.0, hv-hash=ff0e71e8cd978373

123

log10(# f-evals / dimension)

4

All

Children

58 targets: 1..-1.0e-4
10 instances

Fraction of function,target pairs

Fraction of function,target pairs

58 targets: 1..-1.0e-4
10 instances

0.0

1.0 bbob-biobj f1-f55, 40-D

best 2016

0.8

Family0.6

best 2016
0.4

NSGA-II
0.2

0.00v0.0.0, hv-hash=ff0e71e8cd978373

123

4Alllog10(# f-evals / dimension)

22 / 23

Introduction

EMO algorithms

Results

Discussion

Conclusion

Conclusion
We revisited the performance of non-elitist EMOAs
We examined the three environmental selections
Two elitist selections: best-all and best-family
One non-elitist selection: best-children
Results show that best-children performs better than best-all andbest-family on the bi-objective BBOB problems with n = 40
When using rotational invariant SPX and REX
Similar results are found in NSGA-II, SPEA2, IBEA, and SMS
A counter-example to the common belief
Non-elitist EMOAs can outperform elitist EMOAs
Not claim: non-elitist EMOAs always outperform elitist ones
Many future works
Investigating the scalability with respect to the num. of objectives
Designing a non-elitist decomposition-based EMOA
Designing a non-elitist MO-CMA-ES (but difficult)23 / 23

Appendix

Q. Why no one has tried to design non-elitist EMOAs for 20 years?
A. Because of DTLZ and WFGDTLZ and WFG have produced many elitist EMOAs
1. Only the DTLZ and WFG test problems have been available
2. Only SBX+PM works well on DTLZ and WFG
Because of the position and distance variables [Ishibuchi 17]
3. Only elitist EMOAs fit for SBX
4. Only elitist EMOAs with SBX have been studied
BBOB may produce many non-elitist EMOAs
1. BBOB is now available
2. Rotational invariant operators (e.g., SPX and REX) work well onmost BBOB problems
3. Non-elitist EMOAs fit for some rotational invariant operators
4. Non-elitist EMOAs may be studied

H. Ishibuchi, Y. Setoguchi, H. Masuda, Y. Nojima: Performance of Decomposition-Based Many-Objective Algorithms
Strongly Depends on Pareto Front Shapes. IEEE Trans. Evolutionary Computation 21(2): 169-190 (2017)24 / 23

Appendix

Traditional benchmarking scenario for EMOAs
The traditional benchmarking scenario
Nondominated solutions in the population P are usedE.g., the hypervolume value of P is the performance of an EMOA
Issues of the traditional benchmarking scenario
1. Difficulty in comparing EMOAs with different population sizes[Ishibuchi 16]
The appropriate population size differ depending on EMOAs
Solution set with different sizes cannot be compared in a fairmanner
2. Difficulty in maintaining good solutions
Good potential solutions found so far are likely to be discarded
from the population

25 / 23

Appendix

Benchmarking scenario with an unbounded external archive
Benchmarking scenario
The unbounded external archive A stores all nondominatedsolutions found so far
All nondominated solutions in A are used
E.g., the hypervolume value of A is the performance of an EMOA
The unbounded external archive addresses the issues of the
traditional benchmarking scenario
Post-processing methods for decision making
If the decision maker wants to examine a small number of solutions,a post-processing method can be applied to26 / 23

Appendix

Three solution sets (MOEA/D with the Tchebycheff function, WFG4)(i) 210 solutionsin the population(ii) 8,120 solutions in theunbounded external archive(iii) 28 solutions selectedfrom the unbounded
external archive

27 / 23

Appendix

1. Best-all: An elitist (µ + λ)-selection
The best individual is repeatedly added to the next P
1. Assign ranks to µ + λ individuals in P ∪ Q
2. Let S be P ∪ Q
3. Remove all µ individuals from P
4. Until ∣P ∣ = µ, repeatedly select the best x from S, adding x to P

28 / 23

Appendix

2. Best-family: An elitist restricted selection
The selection is performed only among the so-called “family” (R ∪ Q)
1. Assign ranks to µ + λ individuals in P ∪ Q
2. Let S be R ∪Q
3. Remove all k individuals in R from P (i.e., P ← P /R)
4. Until ∣P ∣ = µ, repeatedly select the best x from S, adding x to P

29 / 23

Appendix

3. Best-children: A non-elitist restricted selection (λ > k)The selection is performed only among the children
1. Remove all k individuals in R from P (i.e., P ← P /R)
2. Assign ranks to µ − k + λ individuals in P ∪ Q
3. Until ∣P ∣ = µ, repeatedly select the best x from Q, adding x to P

30 / 23

Appendix

Best-children is an extended version of JGG [Akimoto 10]
Just generation gap (JGG)
A non-elitist selection in GA for single-objective optimization
When using SPX, GA with JGG significantly outperforms elitist GAs
JGG

assigns the rank to each child absolutelyChildren x(1) , ..., x(λ) are ranked based on their objective valuesf (x(1) ), ..., f (x(λ) )Best-children assigns the rank to each child relatively
Children x(1) , ..., x(λ) are ranked based on their objective vectorsf (x(1) ), ..., f (x(λ) ) and objective vectors of individuals in P
Individuals in P do not directly participate in the selection process
But, they indirectly contribute to assign ranks to the children

Youhei Akimoto. Design of Evolutionary Computation for Continuous Optimization. Ph.D. Dissertation. Tokyo
Institute of Technology (2010)31 / 23

AppendixQ. Why has only SBX been used in the EMO community?
A. Because SBX specially works well on DTLZ and WFG [Ishibuchi 17]

Position variables

Distance variables

H. Ishibuchi, Y. Setoguchi, H. Masuda, Y. Nojima: Performance of Decomposition-Based Many-Objective Algorithms
Strongly Depends on Pareto Front Shapes. IEEE Trans. Evolutionary Computation 21(2): 169-190 (2017)32 / 23

Appendix

Traditional (µ + λ) best-all selection is in a dilemma

Fraction of function,target pairs

A large λ value is helpful to exploit the current search area
But it causes premature convergence
A small λ value can prevent from the premature convergence
But it is not sufficiently large to exploit the current search area
1.00.8BC-SPX-NS

bbob-biobj f1-f55, 40-D
58 targets: 1..-1.0e-4
10 instances

BF-SPX-NS
best 2016
NSGA-II

0.6

1n
0.4

3n
5n

0.2

8n
0.0

0v0.0.0, hv-hash=ff0e71e8cd978373

1234

10n

log10(# f-evals / dimension)

33 / 23