什么是启发式算法？ – Heuristic

sgy727 · 发表于 2024-7-15 18:47

百度百科的解释

启发式算法（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年分袂放置了专刊，着重介绍与超启发式算法有关的研究进展。
二、元启发式算法

元启发式算法主要指一类通用型的启发式算法，这类算法的优化机理不外分依赖于算法的组织布局信息，可以广泛的应用到函数的组合优化和函数计算中。
1、分类

现代启发式算法的各种具体实现方式是相对独立提出的,彼此之间有必然的区别。从历史上看，现代启发式算法主要有：模拟退火算法 (SA) 、遗传算法 (GA) 、列表搜索算法 (ST) 、进化规划 (EP) 、进化策略 (ES) 、蚁群算法(ACA) 、人工神经网络 (ANN) 。如果从决策变量编码方案的分歧来考虑，可以有固定长度的编码(静态编码)和可变长度的编码(动态编码)两种方案。SA 是基于 Monte Carlo 算法迭代求解的一种全局概率型搜索算法，具有区别于常规算法的搜索机制和特点，它是借鉴了热力学的退火道理成立起来的。GA 是借鉴“优胜劣汰”生物进化与遗传思想而提出的一种全局性并行搜索算法。EP 和 ES 不像 GA 注重父代与子代遗传细节而侧重父代与子代表示行为上的联系(强调物种层的行为变化)。TS是一种具有记忆功能的全局逐步优化算法。ACA 是受到人们对自然界中真实的蚁群集体行为研究成果的启发而提出的一种基于种群的模拟进化算法，属于随机搜索算法。
2、发源与历史

上世纪50年代中期创立了仿生学，许多科学家从生物中寻求新的用于人造系统的灵感。一些科学家分袂独登时从生物进化的机理中成长出适合于现实世界复杂问题优化的模拟进化算法。SA 是由 Kirkprtricrk 等人首先用于组合优化问题，它克服了登山法 (HC) 极易陷入局部解的错误谬误。近年来 SA 的主要成长标的目的是与其他算法结合构成新的混合算法来充实阐扬其突跳性和可避免局部解的特点。ACA 是比来几年才提出的一种新型的模拟进化算法，由意大利学者 Dirgo 等人首先提出来，他们称之为蚁群算法，并用该方式求解旅行商问题 (TSp) 、指派问题、job 一shop调剂问题，取得了一系列较好的尝试成果。受其影响，ACA 逐渐引起其他研究者的注意，并用该算法解决一些实际问题。
3、算法机制特点

现代启发式算法在优化机制方面存在必然的差异，但在优化流程上却具有较大的相似性，均是一种“邻域搜索”布局。算法都是从一个(一组)初始解出发，在算法的关键参数的控制下通过邻域函数发生若干邻域解，按接受准则(确定性、概率性或混沌方式)更新当前状态，尔后按关键参数改削准则调整关键参数。如此反复上述搜索法式直到满足算法的收敛准则，最终得到问题的优化成果。
三、超启发式算法

超启发式算法是由一系列的启发式算法组合而成，超启发式算法是智能化程度更高的算法，每一种超启发式算法有其本身的机制。超启发式算法分为两个层面：在问题域层面上应用范围专家需按照本人的布景常识，提供问题的定义、评估函数等信息和一系列低层启发式算法 (Low-Level Heuristics) ；而在高层策略层面上，智能计算专家则通过设计高效的独霸打点机制，操作问题域所提供的问题特征信息和低层启发式算法算法库，构造新启发式算法。
由于超启发式算法的研究尚处于起步阶段，对于已有的各种超启发式算法，国际上尚未形成一致的分类方式。按照高层策略的机制分歧，现有超启发式算法可以大致分为4类：基于随机选择、基于贪心算法、基于元启发式算法和基于学习的超启发式算法。
1、基于随机选择的超启发式算法

该类超启发式算法是从给定的调集中随机选择 LLH，组合形成新的启发式算法。这类超启发式算法的特点是布局简单、容易实现。同时，这类超启发式算法也经常被用作基准（bench mark），以评价其他类型的超启发式算法性能。该类超启发式算法可以进一步细分为纯随机（pure random）、带延迟接受条件的随机（random with late acceptance）等。
2、基于贪心策略的超启发式算法

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

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

该类超启发式算法在构造新启发式算法时，采用必然学习机制，按照现有各种 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)

		自动登录	找回密码
密码			立即注册