A runtime analysis of simple hyper-heuristics: to mix or not to mix operators
A runtime analysis of simple hyper-heuristics: to mix or not to mix operators
复制标题
DOI：
10.1145/2460239.2460249
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
P. Lehre;E. Özcan
中科院分区：
文献类型：
--
作者：
P. Lehre;E. Özcan
在超空间学领域有越来越多的工作。超并行是在并行空间上操作以解决困难计算问题的高级搜索方法。经常使用的超启发式框架在搜索过程中混合了一组预定义的低级启发式。虽然大多数的工作，这样的选择hyper-acquistics在文献中是实证的，我们严格分析的运行时间hyper-acquistics。我们的初步分析表明，混合算法可能会导致指数更快的搜索比个人（确定性选择）算法选择的问题。混合的变异算子和混合的验收标准进行了研究，对一些选定的问题。它表明，混合算子是有效的，只有正确的混合分布（参数设置）。此外，一些现有的适应机制混合运营商也进行了评估。
There is a growing body of work in the field of hyper-heuristics. Hyper-heuristics are high level search methodologies that operate on the space of heuristics to solve hard computational problems. A frequently used hyper-heuristic framework mixes a predefined set of low level heuristics during the search process. While most of the work on such selection hyper-heuristics in the literature are empirical, we analyse the runtime of hyper-heuristics rigorously. Our initial analysis shows that mixing heuristics could lead to exponentially faster search than individual (deterministically chosen) heuristics on chosen problems. Both mixing of variation operators and mixing of acceptance criteria are investigated on some selected problems. It is shown that mixing operators is only efficient with the right mixing distribution (parameter setting). Additionally, some of the existing adaptation mechanisms for mixing operators are also evaluated.