超启发式算法的超启发式算法介绍

近年来随着智能计算领域的发展，出现了一类被称为超启发式算法（Hyper-Heuristic Algorithm）的新算法类型。最近几年，智能计算领域的著名国际会议（GECCO 2009, CEC 2010，PPSN 2010）[1]分别举办了专门针对超启发式算法的workshop或session。从GECCO 2011开始，超启发式算法的相关研究正式成为该会议的一个领域（self* search-new frontier track）。国际智能计算领域的两大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分别安排了专刊，着重介绍与超启发式算法有关的研究进展。

定义1. 超启发式算法提供了某种高层策略（High-Level Strategy，HLS），通过操纵或管理一组低层启发式算法（Low-Level Heuristics, LLH），以获得新启发式算法。这些新启发式算法则被运用于求解各类NP-难解问题。

上图给出了超启发式算法的概念模型示意图。从图中可以看出，超启发式算法分为两个层面：在问题域层面上应用领域专家需根据本人的背景知识，提供问题的定义、评估函数等信息和一系列LLH；而在高层策略层面上，智能计算专家则通过设计高效的操纵管理机制，利用问题域所提供的问题特征信息和LLH算法库，构造新的启发式算法。因为这两个层面之间实现了严格的领域屏蔽，仅仅需要修改问题域的问题定义和LLH、评估函数等领域有关信息，一种超启发式算法就可以被快速地迁移到新的问题上。因此，超启发式算法特别适合求解跨领域的问题。需要引起注意的是，研究超启发式算法的目标并不是取代智能计算专家，而是如何将智能计算技术更快地推广到更多的应用领域，同时有效第降低启发式算法的设计难度，从而将领域专家和智能计算专家的研究重点有效地划分开。根据图1 可知，智能计算专家在超启发式算法设计中主要关注于高层策略，而领域专家则重点研究问题的目标函数和LLH等。