一文详述蚁群算法

前几篇解释了一些智能优化算法，今天才想到还有一个重要的给忘了，，言归正传，蚁群算法也是一种生物仿生算法，它是通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法。自然界常理，蚂蚁可以通过群体行动在没有任何提示下从家找到食物源的最短路径，并能随着环境变化不断调整适应性地搜索出新的路径产生新的选择使得找到的路径最短。一般来说每个蚂蚁可以看成是独立的个体，相互交流的纽带是通过释放分泌信息素来实现的，所以这也是该算法模拟的核心地方，根据信息素的浓度进行下一个最优移动方向的选择，从而做到周游所有地点的最短路径，具体过程下面详述

通俗认识

• 蚂蚁在寻找食物时会在走过的路径上释放分泌物信息素，随着时间的推移，信息素会挥发，毕竟本质是化学物质
• 后来的蚂蚁选择该路径的概率会与该路径上的信息素浓度成正比，群体行为而不是走不寻常的路
• 当在一条路径上的蚂蚁越来越多时，留下的信息素也越来越多，后来蚂蚁选择该路径的概率也就越来越大，从而又反向增加了该条路径上信息素的浓度，这就形成了正反馈机制，所以蚂蚁最终可以发现最短路径即浓度最高大家都走的那条路径，生物的行为本质是会向着少做无用功的路上奋斗的
• 信息素更新方式有两种，第一种是挥发，即路径上的信息素以一定的比率减少，二是增强即有蚂蚁走过释放了信息素
• 蚂蚁在向下一个目标的运动是通过一个随机规则实现的，这个随机规则和信息素浓度相关，需要用公式计算这个概率，并按此概率实现一次移动

一些约定

• 信息素更新方式

这里的信息素更新思想需要着重解释一下，并不是每只蚂蚁从城市i到城市j走过之后就立即更新，而是要等所有的蚂蚁把所有的n个城市都遍历一遍(因为有禁忌表，不会存在重复遍历)后，才计算所有道路的累积的信息素更新。

城市i到城市j的信息素为

其中，令

此时

为一次完整迭代时(一次迭代时间为城市数量n，即需要遍历完所有的城市后才计算信息素更新)在边ij所产生的信息素，这里就又涉及到一个问题，每只蚂蚁在城市i到j走过后信息素变化

怎么计算，为此文献中有几种方法，即

其中

表示第k只蚂蚁在本次周游(遍历n个城市后)中所走过的所有路径长度，

表示城市i到j之间的距离，Q为一个正常数，且当蚂蚁没有从城市i走到城市j时，

第一种策略较为推荐，因为它考虑了蚂蚁走过的全长，使其更容易找到全局最优，而第二种和第三种都只是用了和蚂蚁无关的其他已知信息，这样其实在一定程度上会导致较长的搜索时间和容易出现停滞的现象，毕竟每次迭代时路径上的信息素增量都是有规律的

• 迭代终止条件的选择，这里不要误将遍历完所有n个城市为迭代终止而是应该看成下一次迭代的起点，所以蚁群算法的迭代终止条件只是最大循环次数

算法步骤

• 1、初始化参数，时间t=0，循环次数Nc = 0，设置最大循环次数G(一般100~500)，m个蚂蚁置于n个城市，令每条边ij的初始化信息素量为

初始时刻的信息素

增量为0

• 2、做循环 Nc = Nc + 1
• 3、设置当前蚂蚁k的索引号k=1
• 4、将蚂蚁k此时的起点城市加入禁忌表

中，然后蚂蚁k依据城市切换概率公式选择城市j前进，然后将j加到蚂蚁k的禁忌表中

• 第四步不断循环且t=t+1，直到蚂蚁k完成周游即t>n，禁忌表为所有城市后结束，禁忌表此时的长度为n已满
• 选择下一个蚂蚁，设置当前蚂蚁k的索引号k=k+1 重复四步，直到周游(三、四步可以并行执行，即其他蚂蚁也可以同时前进)
• 所有蚂蚁都周游完后，即k>m后，记录本次最短的路线长度(即信息素最浓的周游遍历长度)
• 根据公式更新下一次迭代的每条路径的信息量
• 清空每只蚂蚁的禁忌表，更新迭代，直到当且迭代次数Nc大于最大循环次数G
• 此时最短的路线长度一定是信息素最浓的周游遍历长度

时间t不是严格意义上的时间，尽管城市i到j之间的距离不一样，依然认为每次经过的时间间隔为1个单位，而路径长短的因素是放在了信息素的产生值上面和增强城市ij切换的期望程度(一般是城市距离的倒数)上面

特点

• 本质上是并行算法，每个蚂蚁搜索过程中彼此独立，仅通过信息素通信，使得算法可靠性和全局搜索能力增强
• 自适应性，没有外界条件的预先设定和干扰，而是使得系统从无序到有序的变化过程
• 较强鲁棒性，求解对初始路线的要求不高，搜索过程不需要人工调整，控制参数较少，易于应用到组合优化问题的求解上
• 具有之前分析的正反馈性，在一定程度上使得结果更加精准。