Hyper-Heuristics with Low Level Parameter Adaptation
Hyper-Heuristics with Low Level Parameter Adaptation
复制标题
DOI：
10.1162/evco_a_00063
复制
发表时间：
2012-06
影响因子：
6.8
通讯作者：
Zhilei Ren;He Jiang;J. Xuan;Zhongxuan Luo
中科院分区：
文献类型：
--
作者：
Zhilei Ren;He Jiang;J. Xuan;Zhongxuan Luo
近年来，超空间技术在实际应用中取得了巨大的成功。超并行算法通过操纵一组低级并行算法（LLH）来解决问题，提高了搜索方法的通用性，旨在使算法设计过程自动化。然而，这些LLH通常是参数化的，这可能与超并行的域独立动机相矛盾。在本文中，我们展示了如何使用超启发式LLP自适应（AD-HH）自动维护低级别参数（LLP），并通过自适应维护两个超启发式模型的LLP来验证AD-HH的可行性。此外，针对由于LLP自适应而导致的搜索空间扩展，我们应用启发式空间缩减（SAR）机制来改进AD-HH框架。LLP自适应和SAR机制的集成能够更有效地探索启发式空间。为了评估所提出的算法的性能，我们选择p-中位数问题作为案例研究。实验结果表明，通过对LLP和SAR机制的自适应，所提出的算法能够在三类异构的基准实例上取得有竞争力的结果。
Recent years have witnessed the great success of hyper-heuristics applying to numerous real-world applications. Hyper-heuristics raise the generality of search methodologies by manipulating a set of low level heuristics (LLHs) to solve problems, and aim to automate the algorithm design process. However, those LLHs are usually parameterized, which may contradict the domain independent motivation of hyper-heuristics. In this paper, we show how to automatically maintain low level parameters (LLPs) using a hyper-heuristic with LLP adaptation (AD-HH), and exemplify the feasibility of AD-HH by adaptively maintaining the LLPs for two hyper-heuristic models. Furthermore, aiming at tackling the search space expansion due to the LLP adaptation, we apply a heuristic space reduction (SAR) mechanism to improve the AD-HH framework. The integration of the LLP adaptation and the SAR mechanism is able to explore the heuristic space more effectively and efficiently. To evaluate the performance of the proposed algorithms, we choose the p-median problem as a case study. The empirical results show that with the adaptation of the LLPs and the SAR mechanism, the proposed algorithms are able to achieve competitive results over the three heterogeneous classes of benchmark instances.