95蚁群算法求解TSP的基本思想.DOC

Ch9 蚁群算法 9.1生物学知识 1、蚁群算法(Ant Colony Algorithm ,ACA)是由意大利M. Dorigo等人于1990到2000发展起来的，模拟进化算法。模拟了自然界蚂蚁群体的觅食行为。 2、蚁群社会 在昆虫世界中，蚂蚁的组成是一种群居的蓼袭大家庭，称为蚁群。蚁群中除了亲缘上的互助关系外，成蚁划分为世袭制的蚁王和工蚁两个等级，蚁群的大小从几十个到几千万个，蚁群具有高度组织的社会性，彼此间的沟通不仅可以借助触觉的的联系，在大规模的协调行动上，借助外激素之类的生化信息介质。 其中每个工蚁具有如下的职能： 平时在巢穴附近作无规则行走； 一旦发现食物，如果独自能搬的就往回搬，否则就回巢穴搬兵； 一路上它会留下外激至少的嗅迹，其强度与食物的品质和数量成正比； 其他工蚁遇到嗅迹，就会循迹前进，也会有一定的走失率(选择其他路径)，走失率与嗅迹的强度成反比。 蚁群的行为表现出一种信息正反馈的现象； 某一路径上走过的蚂蚁越多，则后来选择该路径的概率就大，蚂蚁个体间就是通过这种信息的交流达到有哪些信誉好的足球投注网站食物的目的。 3、蚁群觅食过程 意大利学者M. Dorigo是最早发现蚂蚁的觅食习性的，蚂蚁总能找到巢穴与食物源之间的最短路径。 蚂蚁在寻找食物源后，会在其经过的路径上释放一种信息素，并能够感知其他蚂蚁释放的信息素。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。 蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径的信息素的浓度，形成一个正反馈。 路径上的信息浓度会随时间的推进，而不断挥发，从而不断降低，这似乎也是变异。 9.2ACA算法的基本思想 左图表示初始状态中，在结点A与C有30只蚂蚁，线上的数字(1,0)表示距离为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倍，因此A-B的蚂蚁5只，A-D是10只 C点：C-B是5只，C-D是10只 B点：B-A是15只，B-C是15只 单位时间后： A点：10+15=25 C点：10+15=25 B点：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=50 再出发 A点：A-B方向=25*35/85=10 A-D方向为15只。 两边各占0.41:0.59 C点：C-B是10只，C-D是15只 B点：B-A是5只，B-C是5只 单位时间后： A点：5+15=20 C点：5+15=20 B点：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=80 再出发 50/130=0.46 80/130=0.54 A点：A-B方向=20*50/130=6 A-D方向为14只。 C点：C-B是6只，C-D是14只 B点：B-A是10只，B-C是10只 单位时间后： A点：10+14=24 C点：10+14=24 B点：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.38 108/174=0.62 9.3优缺点 优点： (1)蚁群算法是一种分布式内在并行算法。单个蚂蚁的有哪些信誉好的足球投注网站过程是彼此独立的，易于局部最优，通过个体间不断的信息交流和传递有利于发现较好解。 (2)蚁群算法是一种正反馈算法。路径上的信息素浓度较高，将吸引更多的蚂蚁沿这条路径运动，又使得信息素浓度增加，加快了算法的进化过程。 (3)蚁群算法具有较强的自适应性，对其模型稍做修改，可应用于其他问题。 (4)易于其他方法组合，以改善算法的效率。 缺点： (1)需要较长时间有哪些信誉好的足球投注网站。主要是因为各蚂蚁的运动是随机的，当群体规模稍大时，需要很长时间才能收敛。 (2)易出现停滞现象，早熟现象。 9.4蚁群算法的研究进展 1、20世纪90年代 意