abstract

Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives: (hot-off-the-press track at GECCO 2021)

Authors:

Benjamin Doerr,

Weijie ZhengAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 25 - 26

https://doi.org/10.1145/3449726.3462719

Published: 08 July 2021 Publication History

Abstract

Previous theory work on multi-objective evolutionary algorithms considers mostly easy problems that are composed of unimodal objectives. This paper takes a first step towards a deeper understanding of how evolutionary algorithms solve multi-modal multi-objective problems. We propose the OneJumpZeroJump problem, a bi-objective problem with single objectives isomorphic to the classic jump function benchmark. We prove that the simple evolutionary multi-objective optimizer (SEMO) cannot compute the full Pareto front. In contrast, for all problem sizes n and all jump sizes [EQUATION], the global SEMO (GSEMO) covers the Pareto front in Θ((n-2k)n^k) iterations in expectation. To improve the performance, we combine the GSEMO with two approaches, a heavy-tailed mutation operator and a stagnation detection strategy, that showed advantages in single-objective multi-modal problems. Runtime improvements of asymptotic order at least k^Ω(k) are shown for both strategies. Our experiments verify the substantial runtime gains already for moderate problem sizes. Overall, these results show that the ideas recently developed for single-objective evolutionary algorithms can be effectively employed also in multi-objective optimization.

This Hot-off-the-Press paper summarizes "Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives" by B. Doerr and W. Zheng, which has been accepted for publication in AAAI 2021 [9].

Supplementary Material

PDF File (p25-doerr_suppl.pdf)

p25-doerr_suppl.pdf

Download
580.46 KB

References

[1]

Riade Benbaki, Ziyad Benomar, and Benjamin Doerr. 2021. A rigorous runtime analysis of the 2-MMAS_ib on jump functions: ant colony optimizers can cope well with local optima. In GECCO 2021. ACM.

Digital Library

[2]

Chao Bian, Chao Qian, and Ke Tang. 2018. A general approach to running time analysis of multi-objective evolutionary algorithms. In IJCAI 2018. IJCAI, 1405--1411.

[3]

Dimo Brockhoff, Tobias Friedrich, Nils Hebbinghaus, Christian Klein, Frank Neumann, and Eckart Zitzler. 2007. Do additional objectives make a problem harder?. In GECCO 2007. ACM, 765--772.

Digital Library

[4]

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2018. Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation 22 (2018), 484--497.

[5]

Benjamin Doerr. 2019. A tight runtime analysis for the cGA on jump functions: EDAs can cross fitness valleys at no extra cost. In GECCO 2019. ACM, 1488--1496.

Digital Library

[6]

Benjamin Doerr, Wanru Gao, and Frank Neumann. 2016. Runtime analysis of evolutionary diversity maximization for ONEMINMAX. In GECCO 2016. ACM, 557--564.

Digital Library

[7]

Benjamin Doerr, Bojana Kodric, and Marco Voigt. 2013. Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In CEC 2013. IEEE, 432--439.

[8]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast genetic algorithms. In GECCO 2017. ACM, 777--784.

Digital Library

[9]

Benjamin Doerr and Weijie Zheng. 2021. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In AAAI 2021. AAAI. To appear. Full version at https://arxiv.org/abs/2012.07231.

Digital Library

[10]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276 (2002), 51--81.

Digital Library

[11]

Tobias Friedrich, Nils Hebbinghaus, and Frank Neumann. 2010. Plateaus can be harder in multi-objective optimization. Theoretical Computer Science 411, 6 (2010), 854--864.

[12]

Oliver Giel. 2003. Expected runtimes of a simple multi-objective evolutionary algorithm. In CEC 2003, Vol. 3. IEEE, 1918--1925.

[13]

Oliver Giel and Per Kristian Lehre. 2010. On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation 18, 3 (2010), 335--356.

Digital Library

[14]

Václav Hasenöhrl and Andrew M. Sutton. 2018. On the runtime dynamics of the compact genetic algorithm on jump functions. In GECCO 2018. ACM, 967--974.

[15]

Zhengxin Huang and Yuren Zhou. 2020. Runtime analysis of somatic contiguous hypermutation operators in MOEA/D framework. In AAAI 2020, Vol. 34. AAAI, 2359--2366.

[16]

Zhengxin Huang, Yuren Zhou, Zefeng Chen, and Xiaoyu He. 2019. Running time analysis of MOEA/D with crossover on discrete optimization problem. In AAAI 2019, Vol. 33. AAAI, 2296--2303.

Digital Library

[17]

Marco Laumanns, Lothar Thiele, and Eckart Zitzler. 2004. Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Transactions on Evolutionary Computation 8, 2 (2004), 170--182.

Digital Library

[18]

Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, and Kalyanmoy Deb. 2002. Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In PPSN 2002. Springer, 44--53.

[19]

Yuan-Long Li, Yu-Ren Zhou, Zhi-Hui Zhan, and Jun Zhang. 2016. A primary theoretical study on decomposition-based multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation 20, 4 (2016), 563--576.

Digital Library

[20]

Edgar Covantes Osuna, Wanru Gao, Frank Neumann, and Dirk Sudholt. 2020. Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation. Theoretical Computer Science 832 (2020), 123--142.

[21]

Chao Qian, Ke Tang, and Zhi-Hua Zhou. 2016. Selection hyper-heuristics can provably be helpful in evolutionary multi-objective optimization. In PPSN 2016. Springer, 835--846.

[22]

Chao Qian, Yang Yu, and Zhi-Hua Zhou. 2013. An analysis on recombination in multi-objective evolutionary optimization. Artificial Intelligence 204 (2013), 99--119.

Digital Library

[23]

Amirhossein Rajabi and Carsten Witt. 2020. Self-adjusting evolutionary algorithms for multimodal optimization. In GECCO 2020. ACM, 1314--1322.

Digital Library

[24]

Qingfu Zhang and Hui Li. 2007. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (2007), 712--731.

Digital Library

[25]

Aimin Zhou, Bo-Yang Qu, Hui Li, Shi-Zheng Zhao, Ponnuthurai Nagaratnam Suganthan, and Qingfu Zhang. 2011. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation 1, 1 (2011), 32--49.

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Dang DOpris ASudholt DLi XHandl J(2024)Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654177(484-492)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654177
Doerr BKnowles JNeumann ANeumann FLi XHandl J(2024)A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654169(493-501)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654169
Show More Cited By

Index Terms

Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives: (hot-off-the-press track at GECCO 2021)
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

A survey on multi-objective evolutionary algorithms for many-objective problems

Multi-objective evolutionary algorithms (MOEAs) are well-suited for solving several complex multi-objective problems with two or three objectives. However, as the number of conflicting objectives increases, the performance of most MOEAs is severely ...
A new multi-objective evolutionary algorithm based on a performance assessment indicator
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

An emerging trend in the design of multi-objective evolutionary algorithms (MOEAs) is to select individuals through the optimization of a quality assessment indicator. However, the most commonly adopted indicator in current use is the hypervolume which ...
An effective model of multiple multi-objective evolutionary algorithms with the assistance of regional multi-objective evolutionary algorithms: VIPMOEAs

Division of the evolutionary search among multiple multi-objective evolutionary algorithms (MOEAs) is a recent advantage in MOEAs design, particularly in effective parallel and distributed MOEAs. However, most these algorithms rely on such a central (re)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2021

2047 pages

ISBN:9781450383516

DOI:10.1145/3449726

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2021

Check for updates

Author Tags

Qualifiers

Abstract

Funding Sources

Department of Education of Guangdong Province
Science, Technology and Innovation Commission of Shenzhen Municipality
Agence Nationale de Recherche
Guangdong Science and Technology Department

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

Overall Acceptance Rate 829 of 2,029 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
138
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Dang DOpris ASudholt DLi XHandl J(2024)Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654177(484-492)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654177
Doerr BKnowles JNeumann ANeumann FLi XHandl J(2024)A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654169(493-501)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654169
Doerr BKrejca MVu NLi XHandl J(2024)Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy HeuristicsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654140(169-177)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654140
Li MHan XChu XLiang ZLi XHandl J(2024)Empirical Comparison between MOEAs and Local Search on Multi-Objective Combinatorial Optimisation ProblemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654077(547-556)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654077
Ye FNeumann Fde Nobel JNeumann ABäck TLi XHandl J(2024)What Performance Indicators to Use for Self-Adaptation in Multi-Objective Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654073(787-795)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654073
Rajabi AWitt C(2024)Stagnation Detection in Highly Multimodal Fitness LandscapesAlgorithmica10.1007/s00453-024-01249-w86:9(2929-2958)Online publication date: 2-Jul-2024
https://doi.org/10.1007/s00453-024-01249-w
Antipov DKötzing TRadhakrishnan A(2024)Greedy Versus Curious Parent Selection for Multi-objective Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_6(86-101)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_6
Wietheger SDoerr BElkind E(2023)A mathematical runtime analysis of the non-dominated sorting genetic algorithm III (NSGA-III)Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/628(5657-5665)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/628
Dinot MDoerr BHennebelle UWill SElkind E(2023)Runtime analyses of multi-objective evolutionary algorithms in the presence of noiseProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/616(5549-5557)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/616
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents