启发式算法(heuristic)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。
启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。
现阶段,启发式算法以仿自然体算法为主,主要有蚁群算法、模拟退火法、神经网络等。
计算机科学的两大基础目标,就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部目标。 例如它常能发现很不错的解,但也没办法证明它不会得到较坏的解;它通常可在合理时间解出答案,但也没办法知道它是否每次都可以这样的速度求解。
有时候人们会发现在某些特殊情况下,启发式算法会得到很坏的答案或效率极差,然而造成那些特殊情况的数据组合,也许永远不会在现实世界出现。因此现实世界中启发式算法常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。
有一类的通用启发式策略称为元启发式算法(metaheuristic),通常使用乱数搜寻技巧。他们可以应用在非常广泛的问题上,但不能保证效率。
近年来随着智能计算领域的发展,出现了一类被称为超启发式算法(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 逐渐引起其他研究者的注意,并用该算法解决一些实际问题。
现代启发式算法在优化机制方面存在一定的差异,但在优化流程上却具有较大的相似性,均是一种“邻域搜索”结构。算法都是从一个(一组)初始解出发,在算法的关键参数的控制下通过邻域函数产生若干邻域解,按接受准则(确定性、概率性或混沌方式)更新当前状态,而后按关键参数修改准则调整关键参数。如此重复上述搜索步骤直到满足算法的收敛准则,最终得到问题的优化结果。
超启发式算法是由一系列的启发式算法组合而成,超启发式算法是智能化程度更高的算法,每一种超启发式算法有其自己的机制。超启发式算法分为两个层面:在问题域层面上应用领域专家需根据本人的背景知识,提供问题的定义、评估函数等信息和一系列低层启发式算法 (Low-Level Heuristics) ;而在高层策略层面上,智能计算专家则通过设计高效的操纵管理机制,利用问题域所提供的问题特征信息和低层启发式算法算法库,构造新启发式算法。
由于超启发式算法的研究尚处于起步阶段,对于已有的各种超启发式算法,国际上尚未形成一致的分类方法。按照高层策略的机制不同,现有超启发式算法可以大致分为4类:基于随机选择、基于贪心算法、基于元启发式算法和基于学习的超启发式算法。
该类超启发式算法是从给定的集合中随机选择 LLH,组合形成新的启发式算法。这类超启发式算法的特点是结构简单、容易实现。同时,这类超启发式算法也经常被用作基准(bench mark),以评价其他类型的超启发式算法性能。该类超启发式算法可以进一步细分为纯随机(pure random)、带延迟接受条件的随机(random with late acceptance)等。
该类超启发式算法在构造新启发式算法时,每次都挑选那些能够最大化改进当前(问题实例)解的 LLH 。由于每次挑选 LLH 时需要评估所有 LLH ,故此该类方法的执行效率低于基于随机选择的超启发式算法。
该类超启发式算法采用现有的元启发式算法(作为高层策略)来选择 LLH 。由于元启发式算法研究相对充分,因此这类超启发式算法的研究成果相对较多。根据所采用的元启发式算法,该类超启发式算法可以细分为基于禁忌搜索、基于遗传算法、基于遗传编程、基于蚁群算法和基于 GRASP with path-relinking 等。
该类超启发式算法在构造新启发式算法时,采用一定学习机制,根据现有各种 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 产生的启发式算法优于任何先前存在的。而且它也发现了第一个有用的解魔术方块的启发式程式。
为了进一步提高优化质量和搜索效率,近年来发展了一些新的搜索机制和并行、混合搜索算法。由于现代启发式算法结构的开放性、与问题无关性,使得各算法之间容易进行相互综合。研究表明,新型的算法结构或混合算法对算法性能和效率有较大幅度的改善。此外,结合实际应用或理论问题对算法进行对比研究也是算法研究中值得关注的内容。它有助于分析算法的性能和适用域,且由比较可发现各算法独特的优点和不足,以便改进算法结构、参数及操作算子,发展各种可能的高效混合算法。
现代启发式算法的研究,在理论方面还处于不断发展中,新思想和新方法仍不断出现。分析目前的现状和发展方向,其发展方向有如下几个方面:
(1) 整理归纳分散的研究成果,建立统一的算法体系结构;
(2) 在现有的数学方法(模式定理、编码策略、马尔可夫链理论、维数分析理论、复制遗传算法理论、二次动力系统理论、傅立叶分析理论、分离函数理论、Walsh函数分析理论)的基础上寻求新的数学工具;
(3) 开发新的混合式算法及开展现有算法改进方面的研究;
(4) 研究高效并行或分布式优化算法。
在计算机科学,人工智能和数学优化中,启发式是一种技术,用于在经典方法太慢时更快地解决问题,或者用于在经典方法中找到近似解找不到任何确切的解决方案。这是通过交易速度的最佳性,完整性,准确性或精确度来实现的。
在某种程度上,它可以被认为是一种捷径。一个启发式的功能,也简称为启发,是一个功能是居替代搜索算法根据现有的资料,以决定跟随哪一个分支,在每个分支的一步。例如,它可能接近确切的解决方案。
1. 七种启发式算法介绍 https://zhuanlan.zhihu.com/p/371637604
2. 百度链接:启发式算法_百度百科 (baidu.com)
3. 维基链接:https://en.wikipedia.org/wiki/Heuristic_(computer_science)