通过优化启发式组合策略,简单方法超越顶级超启发式算法。
Key Principles in Cross-Domain Hyper-Heuristic Performance
- 基于解接受、重复次数和扰动强度三原则重构低层启发式集
- 在三个真实世界问题上超越现有最先进方法,发现11个新最优解
- 设计简洁却高效,适合追求性能与鲁棒性的优化研究者
跨域选择型超启发式旨在将多年针对特定问题的启发式搜索算法提炼为可适应的通用搜索策略。现有方法主要关注从预定义集合中自适应选择低层启发式(LLHs),而本文聚焦于该集合的构建及其战略变换。我们系统分析了基于解接受、LLH重复和扰动强度(即扰动型LLH影响解的比例)的三种关键原则。通过在无偏随机选择机制上施加恰当变换,该简单方法在三个具有挑战性的现实世界领域中表现优于所有现有最先进的超启发式,并找到了11个新的已知最佳解。同一方法在CHeSC竞赛标准基准上与优胜者相当。此外,我们还将此类战略变换应用于多个近期超启发式方法,使其在CHeSC基准和真实世界问题上均超越当前最先进水平,同时常简化原有设计。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。