启发式算法

说文解字

Heuristic 启发式的;探索的。

  • 启发法(Heuristics):是凭经验的解题方法,也可称经验规则。

人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案

看上去有点类似streaming,有点像markov

  • 特点:不能保证问题一定得到解决,但却常常有效解决问题。

来源 定位 在算法中的位置

决方法, 有2类, 分别是 确定方式和近似方式( Exact Method, Approximate Method)

对于优化问题的解决方法, 有2类, 分别是 确定方式和近似方式( Exact Method, Approximate Method)

对于优化问题. 根据条件,和限制, 可以描绘出一个解集空间(Solution Space), 确定算法, 只可用在解集空间很小的问题, 但对于NP hard 问题, 可行时间内在个空间中找到 全局最优解(Global Optimum ) 的可能性很小 ( 几乎不可能)。 故需要使用近似算法(Approximate Method) 在有限时间内来寻找一个近似最优解。 近似方法分为两种 分别为 近似算法(Approximate Algorithms) 和启发式算法( Heuristic Algorithms)。 近似算法通常可得到一个有质量保证的解。 然而 启发式算法通常可找到在传统解决问题的经验中找到寻求一种面向问题的策略, 之后用这种策略来在可行时间内寻找一个相对比较好的解,但对解的质量没有保证。

https://www.zhihu.com/question/28874818/answer/67504126

简介

启发式就是能快速出结果的算法,出来的结果一般是可用的,但是不能保证全局最优,也不能保证算法的完备性。全局最优容易理解,完备性是说能这个算法能不能找到所有的解,或者干脆判定此问题无解。

启发式方法(试探法)是一种帮你寻求答案的技术,但它给出的答案是具有偶然性的(subject to chance),因为启发式方法仅仅告诉你该如何去找,而没有告诉你要找什么。它并不告诉你该如何直接从A 点到达B 点,它甚至可能连A点和B点在哪里都不知道。实际上,启发式方法是穿着小丑儿外套的算法:它的结果不太好预测,也更有趣,但不会给你什么30 天无效退款的保证。

启发式方法 VS 算法

启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试,最终能找到问题的答案,但它是在很大的问题空间内,花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内,大大减少尝试的数量,能迅速地达到问题的解决。但由于这种方法具有尝试错误的特点,所以也有失败的可能性。科学家的许多重大发现,常常是利用极为简单的启发式规则。

驾驶汽车到达某人的家,写成算法是这样的:沿167 号高速公路往南行至Puyallup;从South Hill Mall 出口出来后往山上开4.5 英里;在一个杂物店旁边的红绿灯路口右转,接着在第一个路口左转;从左边褐色大房子的车道进去,就是North Cedar 路714 号。

用启发式方法来描述则可能是这样:找出上一次我们寄给你的信,照着信上面的寄出地址开车到这个镇;到了之后你问一下我们的房子在哪里。这里每个人都认识我们——肯定有人会很愿意帮助你的;如果你找不到人,那就找个公共电话亭给我们打电话,我们会出来接你。

算法和启发式方法之间的差别很微妙,两个术语的意思也有一些重叠。就本书的目的而言,它们之间的差别就在于其距离最终解决办法的间接程度:算法直接给你解决问题的指导,而启发式方法则告诉你该如何发现这些指导信息,或者至少到哪里去寻找它们。

ss

对于优化问题. 根据条件,和限制, 可以描绘出一个解集空间(Solution Space), 确定算法, 只可用在解集空间很小的问题, 但对于NP hard 问题, 可行时间内在个空间中找到 全局最优解(Global Optimum ) 的可能性很小 ( 几乎不可能)。 故需要使用近似算法(Approximate Method) 在有限时间内来寻找一个近似最优解。 近似方法分为两种 分别为 近似算法(Approximate Algorithms) 和启发式算法( Heuristic Algorithms)。 近似算法通常可得到一个有质量保证的解。 然而 启发式算法通常可找到在传统解决问题的经验中找到寻求一种面向问题的策略, 之后用这种策略来在可行时间内寻找一个相对比较好的解,但对解的质量没有保证。

启发式算法的发展

启发式算法的计算量都比较大,所以启发式算法伴随着计算机技术的发展,取得了巨大的成就。

  • 40年代:由于实际需要,提出了启发式算法(快速有效)。
  • 50年代:逐步繁荣,其中贪婪算法和局部搜索 等到人们的关注。
  • 60年代: 反思,发现以前提出的启发式算法速度很快,但是解得质量不能保证,而且对大规 模的问题仍然无能为力(收敛速度慢)。
  • 70年代:计算复杂性理论的提出,NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快,但解不好的原因主要是他们只是在局部的区域内找解,等到的解没有全局最优性。由此必须引入新的搜索机制和策略………..Holland的遗传算法出现了(GEnetic Algorithm)再次引发了人们研究启发式算法的兴趣。
  • 80年代以后:模拟退火算法(SiMUlated Annealing Algorithm),人工神经网络(Artificial Neural Network),禁忌搜索(Tabu Search)相继出现。
  • 最近比较热或刚热过去的:演化算法(Evolutionary Algorithm), 蚁群算法(Ant Algorithms), 拟人拟物算法,量子算法等。

  各个算法的思想这就不再详细给出,为什么要引出启发式算法,因为NP问题,一般的经典算法是无法求解,或求解时间过长,我们无法接受。这里要说明的是:启发式算法得到的解只是近似最优解(近似到什么程度,只有根据具体问题才能给出). 二十一世纪的最大的数学难题NP?=P,如果NP=P启发式算法就不在有存在的意义。

群体智能算法就是启发式算法;研究的重点就是如何平衡局部搜索与全局搜索有效逃离局部最优解

近几年比较活跃的算法有如下:

  • 仿动物类的算法:粒子群优化,蚂蚁优化,鱼群算法,蜂群算法等;
  • 仿植物类的算法:向光性算法,杂草优化算法,等等;仿人类的算法有:
  • 和声搜索算法是较好的算法;近年开始研究情感计算的人较多。

实际应用时差分进化算法较有优势。关于粒子群算法,理论成熟,应用广泛。

Shi Cheng: 上面提到的算法,应该属于元启发式算法 meta-heuristics algorithms

疑问

那,梯度下降是贪心算法吗?

贪心算法是启发式算法吗?

贪心算法是一种启发式算法,它企图寻求局部最优解,容易陷入局部最优的困境。

梯度下降法也是启发式咯?

启发式搜索与传统基于梯度信息的方法

启发式搜索在机器学习优化中的研究有哪些?

什么算法不是启发式算法?

启发式方法并不告诉你该如何直接从A 点到达B 点,而是仅仅告诉你该如何去找。 按照这个意思,梯度下降法、神经网络、 机器学习算法 是不是 基本都是启发式方法?

决策树不是启发式的吧,

哪些机器学习算法 是启发式算法咯?

所以后来有了元启发式算法,如蚁群算法,模拟退火算法,禁忌算法等等,这类算法通过一些策略,某种程度上可以跳出局部最优解,从而寻求更好的全局最优解。

各类启发式算法概述

优胜劣汰是大自然的普遍规律,它主要通过选择和变异来实现。选择是优化的基本思想,变异(多样化)是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心,根据“优胜劣汰”策略的不同,可以获得不同的超启发式算法。超启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践,以及对这些自然现象的深刻理解,逐步向大自然学习,模仿其中的自然现象的运行机制而得到的。

  • 遗传算法:是根据生物演化,模拟演化过程中基因染色体的选择、交叉和变异得到的算法。在进化过程中,较好的个体有较大的生存几率。
  • 模拟退火:是模拟统计物理中固体物质的结晶过程。在退火的过程中,如果搜索到好的解接受;否则,以一定的概率接受不好的解(即实现多样化或变异的思想),达到跳出局部最优解得目的。
  • 神经网络:模拟大脑神经处理的过程,通过各个神经元的竞争和协作,实现选择和变异的过程。
  • 禁忌搜索:模拟人的经验,通过禁忌表记忆最近搜索过程中的历史信息,禁忌某些解,以避免走回头路,达到跳出局部最优解的目的。
  • 蚂蚁算法:模拟蚂蚁的行为,拟人拟物,向蚂蚁的协作方式学习。

这几种超启发式算法都有一个共同的特点:从随机的可行初始解出发,才用迭代改进的策略,去逼近问题的最优解。他们的基本要素:

  (1)随机初始可行解;

  (2)给定一个评价函数(常常与目标函数值有关);

  (3)邻域,产生新的可行解;

  (4)选择和接受解得准则;

  (5)终止准则。

  其中(4)集中反映了超启发式算法的克服局部最优的能力。

启发式算法的不足和如何解决方法:

参考

  • https://tuotiansudai.com/cms/fund/jijingongsi/57939.html
  • http://www.cnblogs.com/p2pstream/archive/2009/04/09/1432270.html