Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives

Authors

  • Benjamin Doerr Laboratoire d'Informatique (LIX), École Polytechnique, CNRS, Institut Polytechnique de Paris, Palaiseau, France
  • Weijie Zheng Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China

Keywords:

Evolutionary Computation, Heuristic Search, Other Foundations of Search & Optimization, Runtime Modeling

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 whose single objectives are isomorphic to the classic jump functions 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 k in [4..n/2-1], 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.

Downloads

Published

2021-05-18

How to Cite

Doerr, B., & Zheng, W. (2021). Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12293-12301. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17459

Issue

Section

AAAI Technical Track on Search and Optimization