在实际应用中，有些问题无法用传统的数学方法去建模和求解最优值，有些问题并非要求得精确的最优解。元启发式方法(Meta-heuristics)的提出正是为了求解这样的问题，它可以在合理的计算代价内求得可接受的解，而且对问题建模本身的数学特性要求不高。但是元启发式算法非常依赖于问题本身的特性，往往是针对某个问题或者某类型问题而具体设计的，从而导致其扩展性较差，针对不同问题或者同一类问题的不同测试集都可能需要重新调整算法步骤和算法参数。针对元启发式通用性差的缺点，Cowling等人在2001年提出了超启发式(hyper-heuristics)的概念。与元启发式算法作用在解搜索空间不同的是，超启发式算法的搜索空间是一组给定的低层启发式规则(low-level heuristics)，其目的是找到适合当前情况的低层启发式规则或者低层启发式规则的一组排列。超启发式算法对于问题本身的信息要求较少，因此其通用性较强。在设计超启发式算法时，只需提供一组可作用于该问题的低层启发式规则和目标函数即可。本期AAEO我们将为大家介绍关于超启发式算法的几篇综述论文和最新的应用，如有纰漏之处，还请各位老师和同学批评指正。
Chakhlevitch, K., & Cowling, P. (2008). Hyperheuristics: recent developments. In Adaptive and multilevel metaheuristics (pp. 3-29). Springer Berlin Heidelberg. (原文链接)。本文作者将超启发算法总结为以下5类。(1) 基于随机选择的超启发式算法。顾名思义，此类超启发式算法在优化的每一步都随机从给定的一组低层启发式规则中选择一个执行，即使所选择的启发式规则对于提升解的质量并无作用。这类超启发式算法实现简单、便于应用，所得到的结果可以作为算法评价的基准；(2) 贪婪超启发式算法。贪婪超启发式算法每一次都选择能最大提升解的质量的低层启发式规则。由于在每次选择时要评价每个低层启发式规则对解的质量的提升，因此，这类超启发式方法的缺点是耗时较长；(3)基于元启发式的超启发式方法。元启发式算法作为一类局部搜索算法，也可被用作低层启发规则的选择器，即使用元启发式算法在低层启发式规则组成的空间内搜索。此类方法已被用于求解许多实际问题，其性能堪比当前最好的元启发式算法。然而由于高层的搜索算法是元启发式算法，因此仍未能摆脱调参的困扰；(4) 拥有学习能力的超启发式算法。此类超启发式算法通过多种途径学习低层启发式规则的历史表现，从而根据学习到的信息在每个决策点选择最优的低层启发式规则；(5) 其他方法。作者在本节介绍了几类和超启发式算法相似的优化算法。这类方法大部分致力于提供通用的算法框架并且应用了人工智能的方法。
Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Qu, R. (2013). Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64(12), 1695-1724. (原文链接)。作者在本文中将超启发式方法分为两类。(1)基于启发式选择的方法。这类方法从现有的完整的启发式规则中选择一个或多个规则的排列去生成一个完整的解，或者对一个完整的解进行局部搜索，以达到优化的目的。这类方法已被应用于求解Production scheduling、Educational timetabling、1D packing、2D cutting and packing、Workforce scheduling、Constraint satisfaction、Vehicle routing、Personnel scheduling、Space allocation、Cross-domain(HyFlex平台)等优化问题。(2)基于启发式生成的方法。与基于启发式选择的方法不同之处在于，该类方法的搜索空间是组成启发式规则的更低级的规则，而基于启发式选择的方法的搜索空间是完整的启发式规则。遗传规划(Genetic programming)是一类典型的基于启发式生成的方法。这类方法已用于求解Production scheduling、Cutting and packing、Satisfiability、Travelling salesman problem、Function optimisation、Timetabling and scheduling、Additional domains等问题。
Pillay, N. (2016). A review of hyper-heuristics for educational timetabling. Annals of Operations Research, 239(1), 3-38. (原文链接)。Educational timetabling问题包括大学考试排布(University examination timetabling)、大学排课(University course timetabling)和高中排课(school timetabling)三大类问题。由于这三类问题与图染色问题的相似性，可用于求解图染色问题的低级启发式规则也可用于求解Educational timetabling问题，因此超启发式算法在该领域内的应用十分广泛。本文作者主要回顾了用于求解Educational timetabling问题的超启发式算法，包括基于启发式选择和启发式生成的方法，介绍了被广泛使用的大学考试排布、大学排课和高中排课的数据集，以及提供了不同算法在三类测试集上的详细实验结果对比。
Hyper-heuristics在求解多目标问题上的应用详见AAEO第133期:Meta-Heuristics相关论文分享(链接)。