蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。今天总体了解了这个算法的原理，启发很大！蚂蚁找食物估计大家都见过，但是谁又认证想过其原理，并且将其应用于实践呢？
【蚁群算法中的参数】
ALPHA : 启发因子，信息素的重要程度，一般取值1.0。
BETA：期望因子，城市间距离的重要程度，一般取值2.0。
ROU：信息素挥发系数，一般取值0.5。
ANT_COUNT : 蚂蚁数量，一般取值为城市数量的2/3。
CITY_COUNT：城市数量。
IT_COUNT：迭代次数，就是全部蚂蚁搜索多少次，取值自己设定。
Q : 信息素总量，取值多少对算法没什么影响。
【路径选择的期望】
p[i][j]=(T[i][j]^ALPHA)/(D[i][j]^BETA) //信息素的量和城市距离间的取舍
Pij等于Tij的ALPHA次方除以Dij的BETA次方，式中
Pij是从城市i移动到城市j的概率值
Tij是城市i和城市j之间的信息素
Dij是城市i和城市j之间的距离
【轮盘选择】
假设p[0]点有如下的路径选择期望
p[0][1]=0.05
p[0][2]=0.02
p[0][3]=0.03
则：
pa=p[0][1]/(p[0][1]+p[0][2]+p[0][3])*100%=50%
pb=...=20%
pc=...=30%
在[0,1]之间取一个随机数R。然后用R减pa,如果减去后的结果小于等于0就选pb作
为下一个点，如果减去后还大于0，就继续再减去pc,…………，直到减去后的结果小于
等于0。
【蚁群算法解货郎挡问题的过程】
1.让每只蚂蚁都在图中遍历一边，记录路径和总路程L，并记录最短路径。每只蚂蚁遍历图如下：
假设蚂蚁在i点，接下来可选点j、k、l
1）计算p[i][j],p[i][k],p[i][l]
2)用轮盘选择下一个点
3）重复1,2直到到达目的地。
2.对图中的信息度进行更新（ ANT-CYCLE）
1）图中每个点统一信息度挥发ROU
2）再对蚂蚁i经过的点增加Q/L，其中Q为信息素总量，L为总路程
3.重复蚁群遍历（1,2）IT_COUNT次，最终的最短路径即为近似全局最短路径。
【说明】
更新信息素有两种方式。
1、 ANT-CYCLE方式：蚂蚁周游完所有城市后才更新。
2、 ANT-STEP方式：蚂蚁每走一步就更新一下环境信息素。
实践表明ANT-CYCLE方式效果比较好，本文中也是采用的这种方式。
参考：蚁群算法教程 / Ver : 1.0.0 / Made by wugsh / 2011.12.07
阅读(2856) | 评论(0) | 转发(0) |
