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.
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:
- $\text{ONEMAX}$: A classic unimodal "hill-climbing" function where the goal is to maximize the number of 1s in a bit-string.
- $\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.
- $\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.
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