启发式算法
栏目：行业动态 发布时间：2024-06-18
播报编辑计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部目标。例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是
计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部目标。 例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。
有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据组合，也许永远不会在现实世界出现。因此现实世界中启发式算法常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。
近年来随着智能计算领域的发展，出现了一类被称为超启发式算法（Hyper-Heuristic Algorithm）的新算法类型。最近几年，智能计算领域的著名国际会议（GECCO 2009, CEC 2010，PPSN 2010）分别举办了专门针对超启发式算法的workshop或session。从GECCO 2011开始，超启发式算法的相关研究正式成为该会议的一个领域（self* search-new frontier track）。国际智能计算领域的两大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分别安排了专刊，着重介绍与超启发式算法有关的研究进展。
现代启发式算法的各种具体实现方法是相对独立提出的,相互之间有一定的区别。从历史上看，现代启发式算法主要有：模拟退火算法(SA)、遗传算法(GA)、列表搜索算法(ST)、进化规划(EP)、进化策略(ES)、蚁群算法(ACA)、人工神经网络(ANN)。如果从决策变量编码方案的不同来考虑，可以有固定长度的编码(静态编码)和可变长度的编码(动态编码)两种方案。SA是基于Monte Carlo算法迭代求解的一种全局概率型搜索算法，具有区别于常规算法的搜索机制和特点，它是借鉴了热力学的退火原理建立起来的。GA是借鉴“优胜劣汰”生物进化与遗传思想而提出的一种全局性并行搜索算法。EP和ES不像GA注重父代与子代遗传细节而侧重父代与子代表现行为上的联系(强调物种层的行为变化)。TS是一种具有记忆功能的全局逐步优化算法。ACA是受到人们对自然界中真实的蚁群集体行为研究成果的启发而提出的一种基于种群的模拟进化算法，属于随机搜索算法。
上世纪50年代中期创立了仿生学，许多科学家从生物中寻求新的用于人造系统的灵感。一些科学家分别独立地从生物进化的机理中发展出适合于现实世界复杂问题优化的模拟进化算法。SA是由Kirkprtricrk等人首先用于组合优化问题，它克服了爬山法(HC)极易陷入局部解的缺点。近年来SA的主要发展方向是与其他算法结合构成新的混合算法来充分发挥其突跳性和可避免局部解的特点。ACA是最近几年才提出的一种新型的模拟进化算法，由意大利学者Dirgo等人首先提出来，他们称之为蚁群算法，并用该方法求解旅行商问题(TSp)、指派问题、job一shop调度问题，取得了一系列较好的实验结果。受其影响，ACA逐渐引起其他研究者的注意，并用该算法解决一些实际问题。 [3]
现代启发式算法在优化机制方面存在一定的差异，但在优化流程上却具有较大的相似性，均是一种“邻域搜索”结构。算法都是从一个(一组)初始解出发，在算法的关键参数的控制下通过邻域函数产生若干邻域解，按接受准则(确定性、概率性或混沌方式)更新当前状态，而后按关键参数修改准则调整关键参数。如此重复上述搜索步骤直到满足算法的收敛准则，最终得到问题的优化结果。
算法类型 | 首次使用者 | 机制 | 优化流程 | 关键参数 | 收敛准则 |
SA | Kirkpatrick | 邻域搜索 | 初始温度、退温函数 | 迭代次数、搜索序列均值与极值的最小偏差 | |
GA | Holland | 基于生物进化和遗传进行全局最优化 | 邻域搜索 | 种群数目、复制、交叉、变异概率 | 同上 |
TS | Glove | 记忆功能的全局逐步优化算法 | 邻域搜索 | 列表大小、邻域函数结构与数量 | 同上 |
ACA | Dorigo | 强化学习功能的全局性并行优化算法 | 邻域搜索 | 残留信息量、信息增量、积累量、启发或消失因子 | 同上 |
超启发式算法是由一系列的启发式算法组合而成的，超启发式算法是智能化程度更高的算法，每一种超启发式算法有其自己的机制。超启发式算法分为两个层面：在问题域层面上应用领域专家需根据本人的背景知识，提供问题的定义、评估函数等信息和一系列低层启发式算法(Low-Level Heuristics)；而在高层策略层面上，智能计算专家则通过设计高效的操纵管理机制，利用问题域所提供的问题特征信息和低层启发式算法算法库，构造新的启发式算法。 [7]
由于超启发式算法的研究尚处于起步阶段，对于已有的各种超启发式算法，国际上尚未形成一致的分类方法。按照高层策略的机制不同，现有超启发式算法可以大致分为4类：基于随机选择、基于贪心算法、基于元启发式算法和基于学习的超启发式算法。 [4]
基于随机选择的超启发式算法
该类超启发式算法是从给定的集合中随机选择LLH，组合形成新的启发式算法。这类超启发式算法的特点是结构简单、容易实现。同时，这类超启发式算法也经常被用作基准（bench mark），以评价其他类型的超启发式算法性能。该类超启发式算法可以进一步细分为纯随机（pure random）、带延迟接受条件的随机（random with late acceptance）等。
基于贪心策略的超启发式算法
该类超启发式算法在构造新启发式算法时，每次都挑选那些能够最大化改进当前（问题实例）解的LLH。由于每次挑选LLH时需要评估所有LLH，故此该类方法的执行效率低于基于随机选择的超启发式算法。
该类超启发式算法采用现有的元启发式算法（作为高层策略）来选择LLH。由于元启发式算法研究相对充分，因此这类超启发式算法的研究成果相对较多。根据所采用的元启发式算法，该类超启发式算法可以细分为基于禁忌搜索、基于遗传算法、基于遗传编程、基于蚁群算法和基于GRASP with path-relinking等。 [5]
基于学习的超启发式算法
该类超启发式算法在构造新启发式算法时，采用一定学习机制，根据现有各种LLH的历史信息来决定采纳哪一个LLH。根据LLH历史信息来源的不同，该类超启发式算法可以进一步分为在线学习（on-line learning）和离线学习（off-line learning）两种：前者是指LLH的历史信息是在求解当前实例过程中积累下来的；后者通常将实例集合分为训练实例和待求解实例两部分，训练实例主要用于积累LLH的历史信息，而待求解实例则可以根据这些历史信息来决定LLH的取舍。
如何找到一个分叉率较少又通用的合理启发式算法，已被人工智能社群深入探究过，部分问题的解答的代价通常可以评估解决整个问题的代价，通常很合理。例如一个10-puzzle拼盘，解题的代价应该与将1到5的方块移回正确位置的代价差不多。通常解题者会先建立一个储存部份问题所需代价的模式数据库(pattern database)以评估问题，解决较易的近似问题通常可以拿来合理评估原先问题。例如曼哈顿距离是一个简单版本的n-puzzle问题，因为我们假设可以独立移动一个方块到我们想要的位置，而暂不考虑会移到其他方块的问题。 给我们一群合理的启发式函式h1(n),h2(n),...,hi(n)，而函式h(n)=max{h1(n),h2(n),...,hi(n)}则是个可预测这些函式的启发式函式。 一个在1993年由A.E. Prieditis写出的程式ABSOLVER就运用了这些技术，这个程式可以自动为问题产生启发式算法。ABSOLVER为8-puzzle产生的启发式算法优于任何先前存在的。而且它也发现了第一个有用的解魔术方块的启发式程式。
为了进一步提高优化质量和搜索效率，近年来发展了一些新的搜索机制和并行、混合搜索算法。由于现代启发式算法结构的开放性、与问题无关性，使得各算法之间容易进行相互综合。研究表明,新型的算法结构或混合算法对算法性能和效率有较大幅度的改善。此外,结合实际应用或理论问题对算法进行对比研究也是算法研究中值得关注的内容。它有助于分析算法的性能和适用域，且由比较可发现各算法独特的优点和不足，以便改进算法结构、参数及操作算子，发展各种可能的高效混合算法。
现代启发式算法的研究,在理论方面还处于不断发展中，新思想和新方法仍不断出现。分析目前的现状和发展方向,其发展方向有如下几个方面： [6]
(3)开发新的混合式算法及开展现有算法改进方面的研究。
(4)研究高效并行或分布式优化算法。
