有关启发式算法(Heuristic Algorithm)的一些总结
什么是启发式算法节选自维基百科:
启发法(heuristics,源自古希腊语的εὑρίσκω,又译作:策略法、助发现法、启发力、捷思法)是指依据有限的知识(或“不完整的信息”)在短时间内找到问题解决方案的一种技术。
它是一种依据关于系统的有限认知和假说从而得到关于此系统的结论的分析行为。由此得到的解决方案有可能会偏离最佳方案。通过与最佳方案的对比,可以确保启发法的质量。
计算机科学的两大基础目标,就是发现可证明其运行效率良好且可得最佳解或次佳解的算法。
而启发式算法则试图一次提供一个或全部目标。例如它常能发现很不错的解,但也没办法证明它不会得到较坏的解;它通常可在合理时间解出答案,但也没办法知道它是否每次都可以这样的速度求解。
有时候人们会发现在某些特殊情况下,启发式算法会得到很坏的答案或效率极差,然而造成那些特殊情况的数据结构,也许永远不会在现实世界出现。
因此现实世界中启发式算法很常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。
有一类的通用启发式策略称为元启发式算法(metaheuristic),通常使用随机数搜索技巧。他们可以应用在非常广泛的问题上,但不能保证效率。
节选自百度百科:
启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。现阶段,启发式算法以仿自然体算法为主,主要有蚁群算法、模拟退火法、神经网络等。
通用的启发式算法目前比较通用的启发式算法一般有模拟退火算法(SA)、遗传算法(GA)、蚁群算法(ACO)。
模拟退火算法(SA)模拟退火算法(SimulatedAnnealing,SA)的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减小,粒子的慢慢趋于有序,最终,当固体处于常温时,内能达到最小,此时,粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。
步骤初始化温度T(充分大),温度下限Tmin(充分小),初始解X,每个T迭代次数为L;
随机生成临时解域X_new;
设f(x)函数来计算解的好坏,计算出f(X_new)-f(X);
如果f(X_new)-f(X)>0,说明新解比原来的解好,则无条件接受,如果f(X_new)-f(X)