蚁群算法、遗传算法、模拟退火算法介绍

杨利霞

% w7 N  E5 x4 r+ G

蚁群算法、遗传算法、模拟退火算法介绍

穷举法

列举所有可能,然后一个个去,得到最优的结果。如图一，需要从A点一直走到G点，才能知道，F是最高的（最优解）。这种算法得到的最优解肯定是最好的，但也是效率最低的。

6 v  d8 k. {2 \& n8 O+ `: G

穷举法虽然能得到最好的最优解，但效率是极其低下的。为了能提高效率，可以不要枚举所有的结果，只枚举结果集中的一部分，如果某个解在这部分解中是最优的，那么就把它当成最优解。显然这样有可能不能得到真正的最优解，但效率却比穷举法高很多。

只枚举部分解的方法很多。

贪心法

在枚举所有解时，当遇到的解在当前情况下是最优时，就认为它是最优解。如图一，当从A点到B点时，由于B点比A点的解更优，所以会认为B点是最优解。

显然这样的效率很高，但得到的最优解质量也很差。

; ~" U- P$ X# l' N

爬山法

贪心法是只和前面的一个比较，为了提高最优解的质量，可以不仅和前一个解比较，也和后一个解比较，如果比前面和后面的解都优，那么就认为它是最优解。如图一，当到C点时，发现它比前面的B和后面的D点的解都好，所以认为它是最优解。

模拟退火算法

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。

如图一，搜索到A点后就停止了搜索。如果能跳出局部最优解，那么得到的最优解的质量相对就会好很多。如当搜索到A点时以一定的概率跳转到另外一个地方。这样就有可能跳出局部最优解A。如果经过一定次数的跳跃，跳到了E点，那么就会找到全局的最优解了。

如果这个概率不变，那么就会一直跳跃下去，不会结束。可以让这个概率逐渐变小，到最后趋于稳定。这里的概率逐渐减小类似于金属冶炼的退火过程，所以称之为模拟退火算法。

模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

模拟退火算法的关键在于控制温度（概率）降低快慢的参数r，这个参数范围是0<r<1。如果参数r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值。

模拟退火算法不能保证得到真正的最优解，但它能在效率不错的情况下得到质量较高的最优解。

遗传算法

) ^) n& B: v+ ^. G

遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，生物在繁衍发展的过程，会通过繁殖，发生基因交叉，基因突变，适应度低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的。

遗传算法初始是一个较差解的解集种群，通过遗传交叉繁殖出下一代的解集种群。在交叉的过程中，有一定的概率发生基因突变。在下一代的解集种群中，通过适者生存的自然选择，淘汰那些较差的解（个体），只让较好的解（个体）繁殖后代，这样产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境。经过许多代的繁殖和自然选择后，就能得到接近于真正最优解的解。

( Z; G6 Q6 U0 c( A' l% {- X4 G

可以用精英主义原则来对基本遗传算法进行优化。所谓精英主义原则，就是为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。

8 g7 R, p7 d) |) j4 P3 m# O% ^

蚁群算法

蚁群算法（Ant Colony Optimization, ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

  L. F" G4 [( Z8 i  y

蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。

, Z& l/ M( Z% j, K- F

蚁群算法就是根据这一特点，通过模仿蚂蚁的行为，从而实现寻优。当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，最终找到最佳路线。

这种优化过程的本质在于：

选择机制：信息素越多的路径，被选择的概率越大。

更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。

/ B: z4 \2 y& P  S8 ]! Z

协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。

出错机制：显然如果蚂蚁都往信息素多的地方移动，会导致局部最优解的问题。可是，总有些具有叛逆精神的蚂蚁，会不往信息素较多的地方移动，从而可以跳出局部最优解，找到全局的最优解。

总结：

遗传算法：优点是能很好的处理约束,能很好的跳出局部最优,最终得到全局最优解,全局搜索能力强；缺点是收敛较慢,局部搜索能力较弱,运行时间长,且容易受参数的影响.
模拟退火：优点是局部搜索能力强,运行时间较短；缺点是全局搜索能力差,容易受参数的影响.
爬山算法：显然爬山算法较简单,效率高,但是处理多约束大规模问题时力不从心,往往不能得到较好的解.

8 k# R) K6 {9 \! V) o" p5 C