资源描述：
《蚁群算法求解TSP的基本思想.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Ch9蚁群算法9.1生物学知识1、蚁群算法(AntColonyAlgorithm,ACA)是由意大利M.Dorigo等人于1990到2000发展起来的，模拟进化算法。模拟了自然界蚂蚁群体的觅食行为。2、蚁群社会在昆虫世界中，蚂蚁的组成是一种群居的蓼袭大家庭，称为蚁群。蚁群中除了亲缘上的互助关系外，成蚁划分为世袭制的蚁王和工蚁两个等级，蚁群的大小从几十个到几千万个，蚁群具有高度组织的社会性，彼此间的沟通不仅可以借助触觉的的联系，在大规模的协调行动上，借助外激素之类的生化信息介质。其中每个工蚁具有如下的职能：平时在巢穴附近作无规则行走；一旦发现食物，如果独自能搬的
2、就往回搬，否则就回巢穴搬兵；一路上它会留下外激至少的嗅迹，其强度与食物的品质和数量成正比；其他工蚁遇到嗅迹，就会循迹前进，也会有一定的走失率(选择其他路径)，走失率与嗅迹的强度成反比。蚁群的行为表现出一种信息正反馈的现象；某一路径上走过的蚂蚁越多，则后来选择该路径的概率就大，蚂蚁个体间就是通过这种信息的交流达到搜索食物的目的。3、蚁群觅食过程意大利学者M.Dorigo是最早发现蚂蚁的觅食习性的，蚂蚁总能找到巢穴与食物源之间的最短路径。蚂蚁在寻找食物源后，会在其经过的路径上释放一种信息素，并能够感知其他蚂蚁释放的信息素。当某些路径上走过的蚂蚁越来越多时，留下的信
3、息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径的信息素的浓度，形成一个正反馈。路径上的信息浓度会随时间的推进，而不断挥发，从而不断降低，这似乎也是变异。9.2ACA算法的基本思想30(0.5,0)(0.5,0)(1,0)(1,0)ABCD301515(0.5,30)(0.5,30)(1,15)(1,15)ABCD30左图表示初始状态中，在结点A与C有30只蚂蚁，线上的数字(1,0)表示距离为
4、1，信息素为0。此时每条边上的信息素均为0，故蚂蚁按随机行走，A、C出发时，走两边的概率相等。单位时间后，A出发的蚂蚁，15只达到了B、15只经D到达C。C出发的蚂蚁，15只达到了Ｂ，15只经D到达了A，如右上图所示。各边的信息素如右图所示，A-B有15只蚂蚁走过，留下的信息素是15个单位，C-B也是15只蚂蚁，留下的信息素也是15，此时到B的蚂蚁是15+15=30只。A-D-C的蚂蚁是15只，C-D-A的也是15只，故该条较短路线上的信息素为30个单位。蚂蚁再往前走：A点：由于A-B的信息素是15个单位，A-D是30单位，故A-D的蚂蚁数是A-B的2倍，因此
5、A-B的蚂蚁5只，A-D是10只C点：C-B是5只，C-D是10只B点：B-A是15只，B-C是15只单位时间后：A点：10+15=25C点：10+15=25B点：5+5=10信息素：A-B为15+15+5=35，C-B为15+15+5=35，A-D=30+10+10=50，C-D为30+10+10=501515(0.5,30)(0.5,30)(1,15)(1,15)ABCD302525(0.5,50)(0.5,50)(1,35)(1,35)ABCD10再出发A点：A-B方向=25*35/85=10A-D方向为15只。两边各占0.41:0.59C点：C-B是1
6、0只，C-D是15只B点：B-A是5只，B-C是5只单位时间后：A点：5+15=20C点：5+15=20B点：10+10=20信息素：A-B为35+10+5=50，C-B为35+5+10=50，A-D=50+15+15=80，C-D为50+15+15=802020(0.5,80)(0.5,80)(1,50)(1,50)ABCD202424(0.5,108)(0.5,108)(1,66)(1,66)ABCD12再出发50/130=0.4680/130=0.54A点：A-B方向=20*50/130=6A-D方向为14只。C点：C-B是6只，C-D是14只B点：B-
7、A是10只，B-C是10只单位时间后：A点：10+14=24C点：10+14=24B点：6+6=12信息素：A-B为50+6+10=66，C-B为50+6+10=66，A-D=80+14+14=108，C-D为80+14+14=108两边浓度比为66/174=0.38108/174=0.629.3优缺点优点：(1)蚁群算法是一种分布式内在并行算法。单个蚂蚁的搜索过程是彼此独立的，易于局部最优，通过个体间不断的信息交流和传递有利于发现较好解。(2)蚁群算法是一种正反馈算法。路径上的信息素浓度较高，将吸引更多的蚂蚁沿这条路径运动，又使得信息素浓度增加，加快了算法的
8、进化过程。(3)蚁群算法具有较强的自适
