Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem

Renzhong Deng; Weijie Zheng; Mingfeng Li; Jie Liu; Benjamin Doerr

doi:10.1007/978-3-031-70071-2_17

Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem

Renzhong Deng
, Weijie Zheng^*
, Mingfeng Li
, Jie Liu
, Benjamin Doerr

^*Corresponding author for this work

School of Computer Science and Technology, Harbin Institute of Technology
Institut Polytechnique de Paris

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

In the last few years, the mathematical runtime analysis of randomized search heuristics has made a huge step forward by developing the methods to analyze the most prominent multi-objective evolutionary algorithms (MOEAs) as opposed to previously only simplistic algorithms. These results confirmed that many previous results extend to state-of-the-art MOEAs, but also showed that algorithms like the NSGA-II can have unexpected difficulties on problems easily solved by simple MOEAs. We continue this line of research by analyzing how the NSGA-II and the SMS-EMOA (also with a recently proposed stochastic population update) solve the NP-hard subset selection problem. For these two state-of-the-art algorithms, we prove performance guarantees that agree with those previously shown for the POSS algorithm, a variant of the simplistic GSEMO, namely that they compute (1-e^-γ)-approximate solutions in expected time O(k²n). Our experiments confirm these findings. This work is the first runtime analysis of state-of-the-art MOEAs for the subset selection problem, and also the first runtime analysis of SMS-EMOA on a combinatorial problem.

Original language	English
Title of host publication	Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings
Editors	Michael Affenzeller, Stephan M. Winkler, Anna V. Kononova, Thomas Bäck, Heike Trautmann, Tea Tušar, Penousal Machado
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	264-279
Number of pages	16
ISBN (Print)	9783031700705
DOIs	https://doi.org/10.1007/978-3-031-70071-2_17
State	Published - 2024
Externally published	Yes
Event	18th International Conference on Parallel Problem Solving from Nature, PPSN 2024 - Hagenberg, Austria Duration: 14 Sep 2024 → 18 Sep 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	15150 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Parallel Problem Solving from Nature, PPSN 2024
Country/Territory	Austria
City	Hagenberg
Period	14/09/24 → 18/09/24

Keywords

Multi-objective optimization
Runtime analysis
Subset selection
Theory

Access to Document

10.1007/978-3-031-70071-2_17

Cite this

Deng, R., Zheng, W., Li, M., Liu, J., & Doerr, B. (2024). Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem. In M. Affenzeller, S. M. Winkler, A. V. Kononova, T. Bäck, H. Trautmann, T. Tušar, & P. Machado (Eds.), Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings (pp. 264-279). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15150 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-70071-2_17

Deng, Renzhong ; Zheng, Weijie ; Li, Mingfeng et al. / Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem. Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings. editor / Michael Affenzeller ; Stephan M. Winkler ; Anna V. Kononova ; Thomas Bäck ; Heike Trautmann ; Tea Tušar ; Penousal Machado. Springer Science and Business Media Deutschland GmbH, 2024. pp. 264-279 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3062d1ee3b5940568d3faaf8edc3ef2a,

title = "Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem",

abstract = "In the last few years, the mathematical runtime analysis of randomized search heuristics has made a huge step forward by developing the methods to analyze the most prominent multi-objective evolutionary algorithms (MOEAs) as opposed to previously only simplistic algorithms. These results confirmed that many previous results extend to state-of-the-art MOEAs, but also showed that algorithms like the NSGA-II can have unexpected difficulties on problems easily solved by simple MOEAs. We continue this line of research by analyzing how the NSGA-II and the SMS-EMOA (also with a recently proposed stochastic population update) solve the NP-hard subset selection problem. For these two state-of-the-art algorithms, we prove performance guarantees that agree with those previously shown for the POSS algorithm, a variant of the simplistic GSEMO, namely that they compute (1-e-γ)-approximate solutions in expected time O(k2n). Our experiments confirm these findings. This work is the first runtime analysis of state-of-the-art MOEAs for the subset selection problem, and also the first runtime analysis of SMS-EMOA on a combinatorial problem.",

keywords = "Multi-objective optimization, Runtime analysis, Subset selection, Theory",

author = "Renzhong Deng and Weijie Zheng and Mingfeng Li and Jie Liu and Benjamin Doerr",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 18th International Conference on Parallel Problem Solving from Nature, PPSN 2024 ; Conference date: 14-09-2024 Through 18-09-2024",

year = "2024",

doi = "10.1007/978-3-031-70071-2\_17",

language = "英语",

isbn = "9783031700705",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "264--279",

editor = "Michael Affenzeller and Winkler, \{Stephan M.\} and Kononova, \{Anna V.\} and Thomas B{\"a}ck and Heike Trautmann and Tea Tu{\v s}ar and Penousal Machado",

booktitle = "Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings",

address = "德国",

}

Deng, R, Zheng, W, Li, M, Liu, J & Doerr, B 2024, Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem. in M Affenzeller, SM Winkler, AV Kononova, T Bäck, H Trautmann, T Tušar & P Machado (eds), Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 15150 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 264-279, 18th International Conference on Parallel Problem Solving from Nature, PPSN 2024, Hagenberg, Austria, 14/09/24. https://doi.org/10.1007/978-3-031-70071-2_17

Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem. / Deng, Renzhong; Zheng, Weijie; Li, Mingfeng et al.
Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings. ed. / Michael Affenzeller; Stephan M. Winkler; Anna V. Kononova; Thomas Bäck; Heike Trautmann; Tea Tušar; Penousal Machado. Springer Science and Business Media Deutschland GmbH, 2024. p. 264-279 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15150 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem

AU - Deng, Renzhong

AU - Zheng, Weijie

AU - Li, Mingfeng

AU - Liu, Jie

AU - Doerr, Benjamin

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024

Y1 - 2024

N2 - In the last few years, the mathematical runtime analysis of randomized search heuristics has made a huge step forward by developing the methods to analyze the most prominent multi-objective evolutionary algorithms (MOEAs) as opposed to previously only simplistic algorithms. These results confirmed that many previous results extend to state-of-the-art MOEAs, but also showed that algorithms like the NSGA-II can have unexpected difficulties on problems easily solved by simple MOEAs. We continue this line of research by analyzing how the NSGA-II and the SMS-EMOA (also with a recently proposed stochastic population update) solve the NP-hard subset selection problem. For these two state-of-the-art algorithms, we prove performance guarantees that agree with those previously shown for the POSS algorithm, a variant of the simplistic GSEMO, namely that they compute (1-e-γ)-approximate solutions in expected time O(k2n). Our experiments confirm these findings. This work is the first runtime analysis of state-of-the-art MOEAs for the subset selection problem, and also the first runtime analysis of SMS-EMOA on a combinatorial problem.

AB - In the last few years, the mathematical runtime analysis of randomized search heuristics has made a huge step forward by developing the methods to analyze the most prominent multi-objective evolutionary algorithms (MOEAs) as opposed to previously only simplistic algorithms. These results confirmed that many previous results extend to state-of-the-art MOEAs, but also showed that algorithms like the NSGA-II can have unexpected difficulties on problems easily solved by simple MOEAs. We continue this line of research by analyzing how the NSGA-II and the SMS-EMOA (also with a recently proposed stochastic population update) solve the NP-hard subset selection problem. For these two state-of-the-art algorithms, we prove performance guarantees that agree with those previously shown for the POSS algorithm, a variant of the simplistic GSEMO, namely that they compute (1-e-γ)-approximate solutions in expected time O(k2n). Our experiments confirm these findings. This work is the first runtime analysis of state-of-the-art MOEAs for the subset selection problem, and also the first runtime analysis of SMS-EMOA on a combinatorial problem.

KW - Multi-objective optimization

KW - Runtime analysis

KW - Subset selection

KW - Theory

UR - https://www.scopus.com/pages/publications/85204529674

U2 - 10.1007/978-3-031-70071-2_17

DO - 10.1007/978-3-031-70071-2_17

M3 - 会议稿件

AN - SCOPUS:85204529674

SN - 9783031700705

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 264

EP - 279

BT - Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings

A2 - Affenzeller, Michael

A2 - Winkler, Stephan M.

A2 - Kononova, Anna V.

A2 - Bäck, Thomas

A2 - Trautmann, Heike

A2 - Tušar, Tea

A2 - Machado, Penousal

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th International Conference on Parallel Problem Solving from Nature, PPSN 2024

Y2 - 14 September 2024 through 18 September 2024

ER -

Deng R, Zheng W, Li M, Liu J, Doerr B. Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem. In Affenzeller M, Winkler SM, Kononova AV, Bäck T, Trautmann H, Tušar T, Machado P, editors, Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 264-279. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-70071-2_17