Key Principles in Cross-Domain Hyper-Heuristic Performance
This work addresses the challenge of developing more effective and general-purpose search strategies for optimization problems across domains, offering incremental improvements by simplifying designs and enhancing performance.
The paper tackled the problem of improving cross-domain selection hyper-heuristics by focusing on the composition and strategic transformation of low-level heuristic sets, rather than just adaptive selection, and demonstrated that a trivial random selection method with appropriate transformations outperformed state-of-the-art hyper-heuristics on real-world domains, finding 11 new best-known solutions and being competitive with the CHeSC competition winner.
Cross-domain selection hyper-heuristics aim to distill decades of research on problem-specific heuristic search algorithms into adaptable general-purpose search strategies. In this respect, existing selection hyper-heuristics primarily focus on an adaptive selection of low-level heuristics (LLHs) from a predefined set. In contrast, we concentrate on the composition of this set and its strategic transformations. We systematically analyze transformations based on three key principles: solution acceptance, LLH repetitions, and perturbation intensity, i.e., the proportion of a solution affected by a perturbative LLH. We demonstrate the raw effects of our transformations on a trivial unbiased random selection mechanism. With an appropriately constructed transformation, this trivial method outperforms all available state-of-the-art hyper-heuristics on three challenging real-world domains and finds 11 new best-known solutions. The same method is competitive with the winner of the CHeSC competition, commonly used as the standard cross-domain benchmark. Moreover, we accompany several recent hyper-heuristics with such strategic transformations. Using this approach, we outperform the current state-of-the-art methods on both the CHeSC benchmark and real-world domains while often simplifying their designs.