「启发式算法」启发式算法

启发式算法

现代启发式 算法

启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。现阶段，启发式算法以仿自然体算法为主，主要有蚁群算法、模拟退火法、神经网络等。

模拟退火算法

为了解决贪心算法容易陷入局部最优解的困境，受材料的统计力学的研究成果的启发。通过模拟材料退火过程求解最优解。通概率接受比现有解更差的解，试图跳出局部最优解。具体过程如下：

给定初始温度和初始解；

在解的邻域里随机产生一个解计算函数值与原来的函数值相比较计算Δf" role="presentation" style="position: relative;"> $Δ f$ ;
若Δf<0" role="presentation" style="position: relative;"> $Δ f < 0$ ，则接受该解，反之则计算以概率f(Δf)=exp(−Δf/Tk)" role="presentation" style="position: relative;"> $f (Δ f) = e x p (- Δ f / T_{k})$ 接受该解,其中Tk=1ln((k/T)+1)" role="presentation" style="position: relative;"> $T_{k} = \frac{1}{l n ((k / T) + 1)}$ ;
温度下降并再次循环；
结束条件：温度下降到约定值或连续几个温度解不变。

但是模拟退火算法由于随机的原因效率不确定，也不一定有效（即可能跳不出局部最优）。而且理论上,降温过程要足够缓慢,要使得在每一温度下达到热平衡。但在计算机实现中,如果降温速度过缓,所得到的解的性能会较为令人满意,但是算法会太慢, 相对于简单的搜索算法不具有明显优势。如果降温速度过快,很可能最终得不到全局最优解。因此使用时要综合考虑解的性能和算法速度,在两者之间采取一种折衷。

遗传算法

通过模仿自然界生物进化的过程对问题进行优化。

具体过程如下：

编码个体：将各个解进行编码构成染色体（编码规则因情景而异）
多个染色体组成种群，选择初始种群；
计算适应度（适应度计算方法因情景而异）；
选择运算，通过产生随机数淘汰适应度低的，同时提高适应度高的染色体的出现概率；
交换，变异,交换染色体的部分片段，并对一小部分的基因变异；
重复3-5；
结束条件：连续数代适应值没有改变或达到循环上限。

蚁群算法

算法的思想来源于模拟自然界蚂蚁群觅食找寻路径，假设你的蚁群有n只蚂蚁，你想知道从a地点到b地点最近的路径，现在通过让这些蚂蚁不断地去从a走到b，并且在它走过的路径的每一步中留下信息，使得之后的蚂蚁在选择路径提供信息，例如：这里你希望蚂蚁找到的路径是长度最短的，那么就可以设定，蚂蚁每次完成从a到b行走的路径长度越短，每一步中留下的信息量越多；而蚂蚁每一次选择下一步的路径时，留下信息量多的路径，就更可能被选中，那么这样不断地让蚂蚁选择从a到b的路径过程中，长度越短的下一步路径，就越来越容易被之后的蚂蚁选中；这样经过若干轮的蚂蚁重复试验，记录试验中最佳的目标，便得到一个不错的解。但是蚁群算法收敛慢、容易出现停滞现象、算法的运算时间长的缺点。

文章最后发布于: 2018-09-13 16:23:35

启发式算法