Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives

Abstract

The theoretical understanding of MOEAs is lagging far behind their success in practice. In particular, previous theory work considers mostly easy problems that are composed of unimodal objectives. As a first step towards a deeper understanding of how evolutionary algorithms solve multimodal multiobjective problems, we propose the OJZJ problem, a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark. We prove that SEMO with probability one does not compute the full Pareto front, regardless of the runtime. In contrast, for all problem sizes $n$ and all jump sizes $k\in [\mathrm{4..}\frac{n}{2}-1]$, the global SEMO (GSEMO) covers the Pareto front in an expected number of $\Theta ((n-2k)n^k)$ iterations. For $k=o(n)$, we also show the tighter bound $\frac{3}{2}e{n}^{k+1}\pm o(n^{k+1})$, which might be the first runtime bound for an MOEA that is tight apart from lower-order terms. We also combine the GSEMO with two approaches that showed advantages in single-objective multimodal problems. When using the GSEMO with a heavy-tailed mutation operator, the expected runtime improves by a factor of at least $k^{\Omega (k)}$. When adapting the recent stagnation-detection strategy of Rajabi and Witt (2022) to the GSEMO, the expected runtime also improves by a factor of at least $k^{\Omega (k)}$ and surpasses the heavy-tailed GSEMO by a small polynomial factor in $k$. Via an experimental analysis, we show that these asymptotic differences are visible already for small problem sizes: A factor-$5$ speed-up from heavy-tailed mutation and a factor-$10$ speed-up from stagnation detection can be observed already for jump size~$4$ and problem sizes between $10$ and $50$. Overall, our results show that the ideas recently developed to aid single-objective evolutionary algorithms to cope with local optima can be effectively employed also in multiobjective optimization.

Extended version of a paper that appeared in the proceedings of AAAI 2021. 49 pages. Latest version only fixed two bugs in the references

References in corpus (10)

• A Review of Evolutionary Multi-modal Multi-objective Optimization
• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices
• Pareto Optimization for Subset Selection with Dynamic Cost Constraints
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• The Runtime of the Compact Genetic Algorithm on Jump Functions
• Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation
• A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
• The $(1+(\lambda ,\lambda ))$ Global SEMO Algorithm

Cited by in corpus (10)

• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
• Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
• Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
• Lower Bounds from Fitness Levels Made Easy
• Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise
• Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
• How Well Does the Metropolis Algorithm Cope With Local Optima?
• A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive