浅谈蚁群算法

《浅谈蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、—、引言蚁群算法(AntColonyOptimization,ACO),是一种用來在图中寻找优化路径的算法。它由MarcoDorigo于1992年在他的博士论文中提；1

2、,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。蚁群算法成功解决了旅行商问题(TravelingSalesmanProblem,TSP)：―个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又冋到第一个城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最

3、后回到起点的总路程最短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的冋路。最基本的蚁群算法见第二节。目前典型的蚁群算法冇随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。二、基本蚁群算法(-)算法思想各个蚂蚁在没冇事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息索，信息索多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁

4、数量同样多(或者较长的路上蚂蚁多，这也无关紧要)。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。蚁群算法的基本思想如下图表示:(c)(a)(b)图3最优比重图1等概率选择图2最优路径(二)算法描述基本蚁群算法的算法简单描述如下：1.所有蚂蚁遇到障碍物时按照等概率选择路径，并留下信息素；2.随着时间

5、的推移，较短路径的信息索浓度升高；3.蚂蚁再次遇到障碍物时，会选择信息素浓度高的路径；4.较短路径的信息素浓度继续升高，最终最优路径被选择出来。三、随机蚁群算法(-)算法思想在基本蚁群算法中，蚂蚁会在多条可选择的路径中，自动选择岀最短的一条路径。但是，一旦蚁群选择了一条比之前短的路径，就会认为这条路径是最好的，在这条路径上一直走下去。这样的算法存在问题：蚂蚁可能只是找到了局部的最短路径，而忽略了全局最优解。因此，在基木蚁群算法的基础上，需要对蚂蚁选路的方案加以改善：有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，

6、也就是它会按照一定的概率不往信息索高的地方。如果令开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被人多数蚂蚁重复着，这就是优化的随机蚁群算法。为了实现蚂蚁的“随机”选路，我们需要做以下假设：1.范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径，如果半径等于2,那么它能观察到的范围就是2*2个方格世界，并且能移动的距离也在这个范围Z内。1.环境：环境以一定的速率让信息索消失。2.觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如

7、果有就直接过去。否则看是否冇信息素，并冃比较在能感知的范围内哪一点的信息素最多，那么它朝哪个方向走的概率就大。这就意味着每只蚂蚁多会以小概率犯错误，从而并不是往信息索最多的点移动。3.避障规则：如果蚂蚁要移动的方向有障碍物扌半住，它会随机的选择另一个方向，并且冇信息素指引的话，它会按照觅食的规则行为。4.播撒信息索规则：每只蚂蚁在找到食物后撒发的信息索。自然想到一个问题：开始时环境没有信息素，蚂蚁为什么会相对有效的找到食物呢？这个问题用蚂蚁的移动规则同样可以解释。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始

8、，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来貝有了一定的目的性，尽量保持原来的方向，但又有新的试探，这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图屮仍然能找到隐蔽得很好的食物。（-）算法描述随机蚁群算法的算法描述如2算法输入：城市数量N,两两城市间的距离，所冇路径的信息素浓度算法输出：蚂蚁走过的路径长度1.设置全部城市都没有去过，走过的路径长度为0；2.随机选择一个出发的城市；3.

9、i=14.while（i