Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) Problem

Denis Antipov; Aneta Neumann; Frank Neumann; Andrew M. Sutton

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

Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) Problem

Denis Antipov, Aneta Neumann, Frank Neumann, Andrew M. Sutton

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

Abstract

Diversity optimization is a class of optimization problems in which we aim to find a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZ_k, which is a modification of the 2-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in O(kn³) expected iterations. We also analyze the runtime of the GSEMO_D (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures, the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMO_D optimizes it asymptotically faster than it finds a Pareto-optimal population, in O(kn²log(n)) expected iterations, and for the second measure we show an upper bound of O(k²n³log(n)) expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures that is close to the theoretical predictions.

Original language	English (US)
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	19-35
Number of pages	17
ISBN (Print)	9783031700705
DOIs	https://doi.org/10.1007/978-3-031-70071-2_2
State	Published - 2024
Externally published	Yes
Event	18th International Conference on Parallel Problem Solving from Nature, PPSN 2024 - Hagenberg, Austria Duration: Sep 14 2024 → Sep 18 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	9/14/24 → 9/18/24

Bibliographical note

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

Keywords

Diversity optimization
Multi-objective optimization
Runtime analysis
Theory

Publisher link

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

Find It

Find It at U of M Libraries

Cite this

Antipov, D., Neumann, A., Neumann, F., & Sutton, A. M. (2024). Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) 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. 19-35). (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_2

Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) Problem. / Antipov, Denis; Neumann, Aneta; Neumann, Frank 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. 19-35 (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

Antipov, D, Neumann, A, Neumann, F & Sutton, AM 2024, Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) 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. 19-35, 18th International Conference on Parallel Problem Solving from Nature, PPSN 2024, Hagenberg, Austria, 9/14/24. https://doi.org/10.1007/978-3-031-70071-2_2

Antipov D, Neumann A, Neumann F, Sutton AM. Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) 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. 19-35. (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_2

Antipov, Denis ; Neumann, Aneta ; Neumann, Frank et al. / Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) 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. 19-35 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b5ee1bfb2d894ee1ab4079db7f9a81a0,

title = "Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) Problem",

abstract = "Diversity optimization is a class of optimization problems in which we aim to find a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZk, which is a modification of the 2-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in O(kn3) expected iterations. We also analyze the runtime of the GSEMOD (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures, the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMOD optimizes it asymptotically faster than it finds a Pareto-optimal population, in O(kn2log(n)) expected iterations, and for the second measure we show an upper bound of O(k2n3log(n)) expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures that is close to the theoretical predictions.",

keywords = "Diversity optimization, Multi-objective optimization, Runtime analysis, Theory",

author = "Denis Antipov and Aneta Neumann and Frank Neumann and Sutton, {Andrew M.}",

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_2",

language = "English (US)",

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 = "19--35",

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 = "Germany",

}

TY - GEN

T1 - Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) Problem

AU - Antipov, Denis

AU - Neumann, Aneta

AU - Neumann, Frank

AU - Sutton, Andrew M.

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

PY - 2024

Y1 - 2024

N2 - Diversity optimization is a class of optimization problems in which we aim to find a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZk, which is a modification of the 2-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in O(kn3) expected iterations. We also analyze the runtime of the GSEMOD (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures, the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMOD optimizes it asymptotically faster than it finds a Pareto-optimal population, in O(kn2log(n)) expected iterations, and for the second measure we show an upper bound of O(k2n3log(n)) expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures that is close to the theoretical predictions.

AB - Diversity optimization is a class of optimization problems in which we aim to find a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZk, which is a modification of the 2-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in O(kn3) expected iterations. We also analyze the runtime of the GSEMOD (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures, the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMOD optimizes it asymptotically faster than it finds a Pareto-optimal population, in O(kn2log(n)) expected iterations, and for the second measure we show an upper bound of O(k2n3log(n)) expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures that is close to the theoretical predictions.

KW - Diversity optimization

KW - Multi-objective optimization

KW - Runtime analysis

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=85204603436&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85204603436&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85204603436

SN - 9783031700705

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

SP - 19

EP - 35

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 -