Key Principles in Cross-Domain Hyper-Heuristic Performance

Václav Sobotka, Lucas Kletzander, Nysret Musliu, Hana Rudová · 2025

Read Key Principles in Cross-Domain Hyper-Heuristic Performance by Václav Sobotka, Lucas Kletzander, Nysret Musliu, Hana Rudová (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02782.txt.

Introduction

Václav Sobotka, Lucas Kletzander, Nysret Musliu, and Hana Rudová wrote a 2025 optimisation paper on cross-domain hyper-heuristics, methods that choose among simple search heuristics to solve varied problems. Most research tunes how heuristics get selected; this paper instead studies what the heuristic set contains.

Three transformation principles are analysed: which solutions get accepted, how often heuristics repeat, and how much of a solution each perturbative step changes. With the right transformation, even a trivial random selector beat all published rivals on three hard real-world domains and found eleven solutions better than any previously known. Against a famous competition winner, the same recipe stayed competitive. Adding the transformations to recent methods improved them too, often while simplifying their designs.

Catalog record

CREATORVáclav Sobotka, Lucas Kletzander, Nysret Musliu, Hana Rudová
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-02782

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Key Principles in Cross-Domain Hyper-Heuristic Performance Václav Sobotka, Lucas Kletzander, Nysret Musliu, Hana Rudová Abstract 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. 1 Introduction Metaheuristic search strategies Gendreau and Potvin 2010 are the cornerstone of methodologies tackling a vast range of combinatorial optimization problems. While metaheuristics address issues common to all search algorithms, such as local optima evasion or balancing exploitation and exploration in the process, they still serve as templates for implementations of problem-specific algorithms. In contrast, selection hyper-heuristics Drake et al. 2020 aim to provide domain-agnostic search strategies. Given a set of low-level heuristics (LLHs), hyper-heuristics aim to steer the search process by adaptively selecting from the available LLHs, often using information from previous iterations of the search process. Research on hyper-heuristics has attracted attention, arguably due to the appealing idea of generalizing and consolidating decades of research on problem-specific approaches and metaheuristics into general domain-agnostic methods. As a result, a wide range of adaptive and learning LLH selection mechanisms has emerged. Interestingly, the vast majority of works on hyper-heuristic methods assume a fixed set of LLHs is provided and use it as is. In this paper, we challenge this approach by transparently transforming existing LLH sets into new virtual LLH sets . Our virtual LLH sets effectively modify the original LLHs in three fundamental aspects: solution acceptance, repeated LLH applications, and perturbation intensity. By running existing hyper-heuristics on top of properly designed virtual LLH sets, we systematically obtain significant cross-domain performance benefits. With this approach, we demonstrate substantial improvements for the majority of the available recent hyper-heuristics, outperforming the current state-of-the-art hyper-heuristics on both the standard CHeSC cross-domain benchmark Burke et al. 2011 and three challenging real-world application domains. Critically, we exemplify the raw effects of the aforementioned three key principles on a trivial random unbiased selection mechanism. We show that the trivial selection mechanism, accompanied by a strategically transformed LLH set, outperforms all tested state-of-the-art hyper-heuristics on three real-world domains and provides performance comparable to the CHeSC-winning hyper-heuristic Mısır et al. 2012 on the standard CHeSC benchmark. To summarize, the key contributions of our paper are: • We identify and analyze the three aforementioned key principles, use them to transparently transform existing LLH sets, and demonstrate their critical impacts on cross-domain search performance. • We demonstrate that solely the three key principles accompanying a trivial selection mechanism are enough to obtain results comparable to or even outperforming recent hyper-heuristics. This finding strongly contrasts with the general focus on the LLH selection mechanisms. • Using only the trivial selection mechanism and the three key principles, we obtain 11 new best-known solutions on two challenging real-world domains. • By transforming existing LLH sets, we significantly improve the cross-domain performance for the majority of the available recent hyper-heuristics. We demonstrate the benefits of our methodology on both standard benchmarks and three real-world domains. 2 Related works Hyper-heuristics aim to provide high-level search strategies. Previously, comprehensive reviews and classifications of existing hyper-heuristics were provided in Burke et al. 2013 , Drake et al. 2020 , and most recently by Dokeroglu et al. 2024 . In terms of the standard classification Burke et al. 2019 , we concentrate on perturbative selection hyper-heuristics . Such hyper-heuristics operate online by progressively selecting the LLHs to be applied and adapting this selection based on the past search trajectory. A large body of research concentrating on this type of hyper-heuristics is centered around the Cross-Domain Heuristic Search Challenge 2011 (CHeSC) Burke et al. 2011 . The competition introduced the HyFlex framework Ochoa et al. 2012 , providing a diverse benchmark implementing six search domains with a standardized interface and predefined LLH sets for each domain. The CHeSC competition-winning hyper-heuristic GIHH Mısır et al. 2012 combines a large number of adaptive mechanisms. It was followed by a self-adaptive variable-neighborhood search hyper-heuristic Hsiao et al. 2012 , and a method using intensification-diversification cycles with reinforcement learning mechanisms Larose 2011 . Overall, there was a total of 20 teams competing in CHeSC, resulting in a collection of well-evaluated hyper-heuristic concepts and mechanisms. Notably, a recent meta-study Razali et al. 2025 systematically reviews all hyper-heuristics competing in CHeSC, comprehensively analyzing several key design decisions and their impact on the methods’ performance. Among the hyper-heuristics developed after CHeSC, we observe several trends. First is the aim for design simplicity. In Adriaensen and Nowé 2016 (LGIHH), the original GIHH algorithm was simplified by analyzing its mechanisms and eliminating the unnecessary ones. The simplified algorithm was shown to outperform the original GIHH algorithm. With a similar motivation, Adriaensen et al. 2014 (FSILS) introduced a conceptually simple algorithm combining an iterated local search (ILS) scheme with time normalization, acceptance, and restart mechanisms. FSILS is shown to outperform GIHH with a strikingly simpler design and a well-documented role of all applied mechanisms. Subsequently, the key design decisions of FSILS were later used in Adubi et al. 2021 (TSILS) with adaptive mechanisms combined with Thompson sampling LLH selection, and in Adubi et al. 2022 (EAILS), where evolutionary mechanisms steer the combination of perturbative LLHs. To the best of our knowledge, the results of TSILS on the CHesC benchmark form the current state-of-the-art. The last notable trend is the employment of learning, often based on reinforcement learning techniques Sutton and Barto 2018 (RL). In Sabar et al. 2014 (GEPHH), gene expression programming is used to automatically select LLHs and acceptance mechanisms. The Monte Carlo tree search scheme with multi-armed bandit principles was used in Sabar and Kendall 2015 (MCTS) and Ferreira et al. 2015 (FRAMAB) to steer the search trajectory. Later, both Choong et al. 2018 (QHH) and Mischek and Musliu 2022 (MC) used Q-learning-based selection of LLHs. Most recently, Kletzander and Musliu 2023 (LASTRL) combined ILS with adaptive RL strategies and rich state representation. We separately emphasize Chuang 2020 (LUBY) using Luby sequence restarts Luby et al. 1993 in an automated synthesis of search strategies. To the best of our knowledge, this is the only existing work proposing an LLH set transformation. The described domain amplification doubles the LLH set size by adding an ”amplified” duplicate for each LLH. The amplified LLHs execute the original LLH for 10 ms while rejecting non-improving solutions. Interestingly, this exact concept was later used in Mischek

Read the complete text