超启发式算法的分类有哪些？

2023-08-23 08:00:00 · baa · 乐百管

由于超启发式算法的研究尚处于起步阶段，对于已有的各种超启发式算法，国际上尚未形成一致的分类方法。按照高层策略的机制不同，现有超启发式算法可以大致分为4类：基于随机选择、基于贪心策略、基于元启发式算法和

由于超启发式算法的研究尚处于起步阶段，对于已有的各种超启发式算法，国际上尚未形成一致的分类方法。按照高层策略的机制不同，现有超启发式算法可以大致分为4类：基于随机选择、基于贪心策略、基于元启发式算法和基于学习的超启发式算法。

基于随机选择的超启发式算法：该类超启发式算法是从给定的集合中随机选择LLH，组合形成新的启发式算法。这类超启发式算法的特点是结构简单、容易实现。同时，这类超启发式算法也经常被用作基准（benchmark），以评价其他类型的超启发式算法性能。

基于贪心策略的超启发式算法：该类超启发式算法在构造新启发式算法时，每次都挑选那些能够最大化改进当前（问题实例）解的LLH。由于每次挑选LLH时需要评估所有LLH，故此该类方法的执行效率低于基于随机选择的超启发式算法。

基于元启发式算法的超启发式算法：该类超启发式算法采用现有的元启发式算法（作为高层策略）来选择LLH。由于元启发式算法研究相对充分，因此这类超启发式算法的研究成果相对较多。根据所采用的元启发式算法，该类超启发式算法可以细分为基于禁忌搜索、基于遗传算法、基于遗传编程、基于蚁群算法和基于GRASP with path-relinking等。

基于学习的超启发式算法：该类超启发式算法在构造新启发式算法时，采用一定学习机制，根据现有各种LLH的历史信息来决定采纳哪一个LLH。根据LLH历史信息来源的不同，该类超启发式算法可以进一步分为在线学习（on-line learning）和离线学习（off-line learning）两种：前者是指LLH的历史信息是在求解当前实例过程中积累下来的；后者通常将实例集合分为训练实例和待求解实例两部分，训练实例主要用于积累LLH的历史信息，而待求解实例则可以根据这些历史信息来决定LLH的取舍。