On
the Unbounded External Archive and Population SizeinPreference-based EMO Using a Reference Point
GECCO 2023 at Lisbon

Ryoji Tanabe
Yokohama National University
Yokohama city, Japan

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

An unbounded archive maintains all non-dominated solutions found so far
The archive can be incorporated into any EMO algorithm
Unb. archive

NSGA-II

MOEA/D

Unb. archive

It can maintain all solutions potentially preferred by the DM
Final pop. of size 8Archive of size 4 933

f2f21f2110.5

0.500Its subset of size 80.5

f1

1000.5

0.5

100

f1

0.5

1f1

• The DM does not want to examine so many solutions• A postprocessing method is available to select only k solutions
2 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

Preference-based EMO using a reference point (PBEMO) [Deb 06]
EMO (e.g., NSGA-II) approximates the whole Pareto frontDMI have no preference a priori.
I want an approximation of the PF.
Then, I will examine it.

PBEMO (e.g., R-NSGA-II) approximates a region of interest (ROI)DMI have a preference a priori.
I want solutions near the ref. point ▲.

• Approximating the ROI can be easier than approximating the PF• Showing only preferred solutions can reduce the DM’s cognitive load
Kalyanmoy Deb, J. Sundar, Udaya Bhaskara, and Shamik Chaudhuri: Reference Point Based Multi-Objective Optimization Using Evolutionary Algorithms. Int. J. Comput. Intell. 2, 3 (2006), 273–286.

3 / 14

IntroductionROI

Proposed postprocessing methodSetup

Results (unb. archive)

Results (pop size)

Conclusion

Three main contributions of this work
Long-term goal: Establishing a benchmarking methodology for PBEMO
1. It proposes a preference-based postprocessing method• Existing pp methods cannot handle the DM’s preference information
2. It investigates effects of the unbounded archive in PBEMO• Except for [Fonseca 93], no previous study used the archive
3. It investigates the best population size for PBEMO• Intuitively, PBEMO requires only a small population size• But, most previous studies used a large population size
Ref.

Population size

NSGA-II

100

R-NSGA-II 100 – 500
PBEA
20 – 200
R-MEAD2 200 – 350
Carlos M. Fonseca, Peter J. Fleming: Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization.
ICGA 1993: 416-423

4 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

Preliminary: The region of interest (ROI) considered in this work
Just as there is no standard GA, there is no standard ROI [Tanabe 23]• If there are 100 researchers, there are 100 different GAs and ROIs
ROI based on the Pareto opt. point ∎ closest to the ref. point ▲• A set of all Pareto opt. points in a sphere of radius r centered at ∎0.5f2∎ = arg min {distance (●, ▲)} ,●∈PF

ROI = {● ∈ PF ∣ distance(●, ∎) < r} .
000.5

r is supplied by the DM or analyst

f1
Ryoji Tanabe, Ke Li: Quality Indicators for Preference-based Evolutionary Multi-objective Optimization Using a Reference Point: A Reviewand Analysis. CoRR abs/2301.12148 (2023)

5 / 14

Introduction

ROI

Proposed postprocessing methodSetupResults (unb. archive)

Results (pop size)

Conclusion

Proposed preference-based postprocessing method

11f2

OutputIts subset of size kf2

Input
Unbounded archive

0.5
000.5

0.5

f1

1000.51

f1

Difficulty: A set of k points should approximates the ROI

6 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

Proposed preference-based postprocessing method
1. Find the closest point ∎ to the ref. point ▲ from the archive

f2

10.5

∎ = arg min {distance (●, ▲)}●∈archive

000.5

1

f1
2. Select points in the region of a sphere of radius r centered at ∎1X = {● ∈ archive ∣ distance(●, ∎) < r}f2

There are three cases

0.5

3.1 ∣X ∣ = k
3.2 ∣X ∣ < k00

0.5

f1

1

3.3 ∣X ∣ > k
7 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

3.2 The size of the subset X is less than k
The proposed method selects unselected points closest to ∎• The DM is interested in closer points to the center point ∎• even though they are out of the approximated ROI
Example: k = 3, ∣X ∣ = 2, and ∣archive∣ = 70.5
123f2

45

6700

X = {∎5 , ●6 }, ∣X ∣ < 3●4 is closest to ∎5●4 is added to X
X = {●4 , ∎5 , ●6 }, ∣X ∣ = 3

0.5

f1
8 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

3.3 The size of the subset X is greater than kA conventional postprocessing method can be used
• It selects k representative points from X• Iterative distance-based subset selection (IDSS) [Shang 21]
Example: k = 3, ∣X ∣ = 4, and ∣archive∣ = 70.5

f2

1

X = {●3 , ●4 , ∎5 , ●6 }, ∣X ∣ > 32345●4 is the most crowded●4 is removed from X

6700

X = {●3 , ∎5 , ●6 }, ∣X ∣ = 30.5

f1
Ke Shang, Hisao Ishibuchi, Yang Nan: Distance-based subset selection revisited. GECCO 2021: 439-447

9 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)Results (pop size)

Conclusion

Experimental setup: We used...
• The ND-Tree-based method for nondom. sorting [Jaszkiewicz 18]• Six representative PBEMO algorithms• R-NSGA-II , r-NSGA-II, g-NSGA-II, PBEA, R-MEAD2, MOEA/D-NUMS• The maximum number of function evaluations = 50, 000• DTLZ1–4 with 2–6 objectives / , the radius of the ROI r = 0.1• k = 100 , a single reference point near the center of the PF• An IGD+ version of IGD-C [Mohammadi 14] as a quality indicator
Ref. set of IGDRef. set of IGD-C

1f2

100

f2

0.5

0.5

0.5

f1

1000.5

1f1

Andrzej Jaszkiewicz, Thibaut Lust: ND-Tree-Based Update: A Fast Algorithm for the Dynamic Nondominance Problem. IEEE Trans. Evol.
Comput. 22(5): 778-791 (2018)
Asad Mohammadi, Mohammad Nabi Omidvar, Xiaodong Li, Kalyanmoy Deb: Integrating user preferences and decomposition methods formany-objective optimization. IEEE Congress on Evolutionary Computation 2014: 421-428

10 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)Conclusion

Distributions of points found by R-NSGA-II with µ = 100 (bi-obj. DTLZ2)
The unb. archive pp by the proposed method performs the best
Final population

Arch. pp by IDSS

f2

1

f2

0.5
00

Arch. pp by Proposed

1

f2

1

0.5

0.5

f1

1

00

0.5

0.5

f1

1

0
0

0.5

1

f1

Interesting findings• A PBEMO algorithm generates diverse solutions outside the ROI• Many irrelevant solutions are included in the unbounded archive• An existing method (IDSS) cannot remove the irrelevant solutions• It is important for pp methods to consider the DM’s pref. info.
11 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

Average IGD+ -C values of the three solution subsets found by R-NSGA-II
The unb. archive pp by the proposed method performs the bestfor DTLZ1–4 with m ∈ {2, 3, 4, 5, 6} in most cases
Problemm

Population

Arch./IDSS

Arch./ProposedDTLZ1

2
3
4
5
6

0.0236
0.03340.0562
0.09330.11310.0018 (+)
0.0211 (+)
0.0743 (−)
0.0782 (+)
0.0779 (+)

0.0012 (+, +)0.0220 (+, ≈)0.0442 (+, +)0.0558 (+, +)0.0695 (+, +)

DTLZ2

2
34
56

0.04110.1247
0.1986
0.27290.28400.0016 (+)
0.0276 (+)
0.0720 (+)
0.1162 (+)
0.1540 (+)

0.0004 (+, +)0.0114 (+, +)0.0339 (+, +)0.0600 (+, +)0.0853 (+, +)

DTLZ3

2
3
4
5
6

0.03450.10830.19880.23700.87490.0083 (+)
0.0460 (+)
0.1736 (≈)
0.2169 (≈)
0.8287 (+)

0.0078 (+, ≈)0.0309 (+, +)0.0636 (+, +)0.1024 (+, +)0.7224 (+, +)

DTLZ4

234
56

0.10140.08380.10300.37570.32140.0829 (≈)
0.0528 (+)
0.0741 (+)
0.1206 (+)
0.1144 (+)

0.0818 (≈, ≈)0.0375 (+, +)0.0465 (+, +)0.0759 (+, +)0.0655 (+, +)12 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

The best population size in R-NSGA-II on all DTLZ1–DTLZ4• The pop. size ∈ { 8 , 20 , 40 , 100 , 200 , 300 , 400 , 500 }• The unbounded archive pp by the proposed method is used
A small pop. size is effective even for many obj. and a large budgetObj.

1 000 FEs

5 000 FEs

10 000 FEs

30 000 FEs

50 000 FEs

2-obj
4-obj
6-obj

88
20

20
40
40

8
20
100

820
40

200
20
100

Most previous studies may have used a too large population size
PBEMOPopulation size

Obj.

Budget of FEs

R-NSGA-II
PBEA
R-MEAD2
NUMS

100 – 500
20 , 200
200 – 350
100 – 660

2 – 102, 54 – 10
2 – 10

5 × 104 – 2.5 × 1052 × 103 , 2 × 104
6 × 104 , 9 × 104 , 1.05 × 105
4 × 104 – 1.188 × 106
13 / 14

Introduction

ROI

Proposed postprocessing method

Setup

Results (unb. archive)

Results (pop size)

Conclusion

Conclusion
1. This work proposed a preference-based postprocessing method• The method can handle the DM’s preference information
2. It investigated effects of the unbounded archive in PBEMO• The arch. and the proposed pp method can improve PBEMO algs
3. It investigated the best population size for PBEMO• A smaller population size than commonly used is effective even for• a large budget of function evaluations (in some cases)• many objectives (in some cases)

Future work
• analyzes PBEMO algorithms using other pref. elicitation methods• extends the proposed pp method for interactive PBEMO

14 / 14

Why is a small population size is effective for PBEMO in this work?
1. This work used the unb. archive and the preference-based
postprocessing method• A small-size population cannot maintain many solutions• This issue can be addressed by using the unb. archive and the ppp
method
2. This work used a single reference point• When using multiple reference points, the best pop. size may belarge• But, I believe that the number of reference points is not problematic• Suppose that two reference points are used
• I expect that the best pop. size for two reference points is just twotimes larger than the best pop. size for a single reference point

The best pop. size for two reference points may be just two times larger
than the best pop. size for a single reference point
The best pop. size for a single reference point
Obj.

1 000 FEs

5 000 FEs

10 000 FEs

30 000 FEs

50 000 FEs

2-obj
4-obj
6-obj

8820

2040
40

82010082040200
20100

The EXPECTED best pop. size for two reference points
Obj.

1 000 FEs

5 000 FEs

10 000 FEs

30 000 FEs

50 000 FEs

2-obj
4-obj
6-obj

1616404080
801640200

164080400
40200