How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs

Abstract

In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligence (2023)) proved that the Move Acceptance Hyper-Heuristic (MAHH) leaves the local optimum of the multimodal cliff benchmark with remarkable efficiency. With its $O(n^3)$ runtime, for almost all cliff widths $d,$ the MAHH massively outperforms the $\Theta (n^d)$ runtime of simple elitist evolutionary algorithms (EAs). For the most prominent multimodal benchmark, the jump functions, the given runtime estimates of $O(n^{2m}{m}^{-\Theta (m)})$ and $\Omega (2^{\Omega (m)})$, for gap size $m\ge 2$, are far apart and the real performance of MAHH is still an open question. In this work, we resolve this question. We prove that for any choice of the MAHH selection parameter~$p$, the expected runtime of the MAHH on a jump function with gap size $m=o(n^{1/2})$ is at least $\Omega (n^{2m-1}/(2m-1)!)$. This renders the MAHH much slower than simple elitist evolutionary algorithms with their typical $O(n^m)$ runtime. We also show that the MAHH with the global bit-wise mutation operator instead of the local one-bit operator optimizes jump functions in time $O(\min \{m{n}^m,\frac{n^{2m-1}}{m!\Omega (m{)}^{m-2}}\})$, essentially the minimum of the optimization times of the $(1+1)$ EA and the MAHH. This suggests that combining several ways to cope with local optima can be a fruitful approach.

arXiv commentAuthor generated version of a paper appearing in the proceedings of GECCO. With an appendix containing the material omitted in the conference version for reasons of space

References in corpus (10)

• Multiplicative Drift Analysis
• Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices
• A First Runtime Analysis of the NSGA-II on a Multimodal Problem
• Does Comma Selection Help To Cope With Local Optima
• Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
• The Runtime of the Compact Genetic Algorithm on Jump Functions
• A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions
• How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
• How Well Does the Metropolis Algorithm Cope With Local Optima?
• Lasting Diversity and Superior Runtime Guarantees for the $(\mu +1)$ Genetic Algorithm

Cited by in corpus (3)

• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
• How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
• How Well Does the Metropolis Algorithm Cope With Local Optima?