On the Time Complexity of Algorithm Selection Hyper-Heuristics for Multimodal Optimisation

Andrei Lissovoi, Pietro S. Oliveto, John Alasdair WarwickerAAAI 2019 · DOI

Introduction

Hyper-heuristics are meta-algorithms designed to select and apply low-level heuristics during an optimization process. While they have demonstrated significant empirical success in solving complex real-world problems like scheduling and routing, a rigorous theoretical foundation for their performance has been largely missing. Most existing theoretical work focuses on "unimodal" functions—landscapes with a single peak. However, real-world optimization is typically "multimodal," characterized by numerous local optima that can trap simple algorithms. This paper provides the first formal runtime analysis of how algorithm-selection hyper-heuristics navigate these deceptive landscapes, specifically focusing on the trade-off between exploitation and exploration.

The $\text{MAHH}_{\text{OI}}$ Framework

The authors analyze a specific hyper-heuristic called the Move Acceptance Hyper-Heuristic with Only Improving ($\text{MAHH}_{\text{OI}}$). This algorithm manages the exploration-exploitation trade-off by randomly switching between an elitist and a non-elitist move acceptance operator.

Algorithm 1: The Move Acceptance Hyper-Heuristic ($\text{MAHH}_{\text{OI}}$) pseudocode.

As shown in Algorithm 1, the process begins with a random bit-string $x$. In each iteration, a new candidate solution $x'$ is generated by flipping a single random bit. The algorithm then selects an acceptance operator:

  • $\text{ONLYIMPROVING}$ (OI): An elitist operator that accepts $x'$ only if its fitness is greater than or equal to $x$.
  • $\text{ALLMOVES}$ (AM): A non-elitist operator that accepts $x'$ regardless of its fitness.

The choice is governed by a parameter $p$: the non-elitist $\text{AM}$ operator is chosen with probability $p$, while the elitist $\text{OI}$ is chosen with probability $1-p$.

Benchmark Landscapes

To evaluate $\text{MAHH}_{\text{OI}}$, the researchers utilized several standard mathematical benchmark functions that represent different landscape challenges:

  1. $\text{ONEMAX}$: A classic unimodal "hill-climbing" function where the goal is to maximize the number of 1s in a bit-string.
  2. $\text{CLIFF}_d$: A multimodal function where the landscape features a "cliff." An algorithm must climb to a local peak, drop down a cliff (losing fitness), and then follow a new gradient to reach the global optimum.
  3. $\text{JUMP}_m$: A harder multimodal function where a "gap" of decreasing fitness separates a local peak from the global optimum, requiring a large jump in the search space.
The $\text{CLIFF}_{35}$ function landscape, illustrating the local optimum and the subsequent path to the global optimum.

Key Theoretical Insights

The analysis reveals several critical insights into the behavior of hyper-heuristics:

  • The "Goldilocks" Probability: For simple hill-climbing on $\text{ONEMAX}$, the probability $p$ of choosing the non-elitist operator must be carefully tuned. If $p$ is too high, the algorithm behaves like a random walk. If $p \approx 1/n$, the algorithm matches the $O(n \log n)$ performance of optimal specialized hill-climbers.
  • Efficiency through "Blind" Acceptance: The hyper-heuristic is particularly effective on the $\text{CLIFF}$ function. Because the $\text{AM}$ operator is "blind" to the magnitude of fitness loss, it can quickly descend the cliff to find the next upward slope. This allows it to outperform many standard evolutionary algorithms that struggle with fitness-decreasing moves.
  • Hyper-Heuristics vs. Metropolis: Unlike the Metropolis algorithm, which accepts worse moves based on the degree of fitness loss, $\text{MAHH}_{\text{OI}}$'s $\text{AM}$ operator accepts any move. This subtle difference allows the hyper-heuristic to escape certain local optima much faster than Metropolis-based approaches.

Runtime Results

The paper establishes rigorous upper bounds on the expected runtime (the average number of steps to find the global optimum):

  • Unimodal: $O(n \log n)$ on $\text{ONEMAX}$ with $p = \frac{1}{(1+\epsilon)n}$.
  • Multimodal (Cliff): $O(n \log n + n^3/d^2)$ on $\text{CLIFF}_d$. This polynomial runtime demonstrates high efficiency in escaping local traps with a clear exit path.
  • Multimodal (Jump): $O(n \log n + n^{(2m-1)/m})$ on $\text{JUMP}_m$. While exponential in the jump size $m$, this is still proven to be faster than the Metropolis algorithm on the same function.

Conclusion

This work provides a theoretical foundation for the success of simple hyper-heuristics in multimodal optimization. By showing that a "blind" non-elitist operator can efficiently navigate complex landscapes like $\text{CLIFF}$, the authors highlight a unique advantage of hyper-heuristics over more traditional probabilistic acceptance mechanisms. Future work will explore more complex learning-based hyper-heuristics and self-adjusting mechanisms for the selection probability $p$.

Summary updated

BibTeX
@inproceedings{lissovoi2019time,
  author = {Andrei Lissovoi and Pietro S. Oliveto and John Alasdair Warwicker},
  title = {{On the Time Complexity of Algorithm Selection Hyper-Heuristics for Multimodal Optimisation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012322},
}
Figure