蚁群算法与其应用分析

《蚁群算法与其应用分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重壅奎堂堡主堂垡笙銮一2基于TSP问题的基本蚁群算法———————————————————————————————一=：：：=：：三．：二：．：!三二!=2基于TSP问题的基本蚁群算法2．1引言受蚂蚁觅食行为的影响，M．Dorigo等人在1991年提出了蚁群算法的最初模型，即蚂蚁系统(AntSystem，AS)算法，并用该算法来解决TSP问题。本章节首先介绍了蚂蚁的觅食习性，然后引入TSP问题，最后给出蚁群算法的模型。2．2蚁群的觅食习性蚂蚁的巢穴与食物源之间总会有一定的距离，但不管食物源离巢穴有多远，蚂蚁总能在团队的协作下，经过一定的时间，找到一条连接二者的最佳路径，也是最短路径。一

2、般情况下，巢穴与食物源之间没有障碍物时，在二者之间会有一条由蚂蚁组成的路径，该路径接近直线，如图1．1(a)所示。蚂蚁对环境的的适应能力是很强的，如果有障碍物出现在巢穴和食物源之间，最初蚂蚁随机选择路线，即选择障碍物两边的路径概率是均等的，如图1．1(b)。在寻找最佳路径的过程中，蚂蚁用一种物质来标记自己走过的路径，这种物质能够被同伴感知并影响同伴的运动方向，被称为信息素。被同等数量的蚂蚁走过的长路径和短路径，同等时间内，短路径上积累的信息浓度较大，对蚂蚁更有吸引力，如图1．1(c)所示。短路径上积累的越来越高的信息浓度会导致几乎所有的蚂蚁都会选择该路径，这种现象称之为正反馈，如图1．

3、1(d)所示。图1．1(a)无障碍物时的实验情况Fi91．1(a)Theforagingprocessoftheantwithoutbarrier臻猿娥∥．蓥礅‰孵食{辟翻炙狗S乃一圳《3皤捌K翔嘴翠受捌K障碍图1．1(b)有障碍物时的实验初期Fig1．1(b)Thesituationatthebeginningwithbarrier重塞盔堂堡主堂垡笙塞2基于TSP问题的基本蚁群算法———————————————————————————一=：：：!竺：：兰：!：竺：!121竺集墓穴图1．1(c)选择较短路径的蚂蚁多Figl·1(c)Moreantsintheshorterpathint

4、heforagingprocess辩壤∥。瓢》鲰辘l骧鲥豳崦国《捌≯期c弓憋奢爱再撼辩辩障碍图1．2双桥试验。(a)A和B长度相等：(b)A和B长度不等。Fig1．2Doublebridgeexperiment．(a)AandBhavethesamelength：(b)AandBhavethedifferentlength．在上图1．2(a)qb，‘=丘，即r=l。在还没有蚂蚁经过两条路径时，两条分支上的信息素都为0，所以蚂蚁在从蚁巢出发后，都会以1／2的概率分别选择两条路径，因此，路径A和B上的蚂蚁数目在觅食初期是一样的。当其中一条路径上的蚂蚁重庆大学硕士学位论文2基于TSP问题的基

5、本蚁群算法数目多于另一条时，显然，蚂蚁数目多的路径占优势，会被更多的蚂蚁选择。在图1．2(b)中，r=2，即较长路径是较短路径的2倍，在觅食的初期，蚂蚁的行为同1．2(a)的情况，仍是以1／2的概率选择两条路径，在相同的时间内，选择A的蚂蚁是B的两倍，而正反馈的存在会使得A上的信息量越来越多，被选择的概率也越来越大。实验结果如下图所示：100o求妞￡慕50≤翁憾0O一2020一4040—6060-8080—100在某条分支上的流量百分比图1．3“双桥”实验的结果．(a)长度相等的A和B被蚂蚁选择的概率相等；Fig1．3Theexperimentresultofdoublebridgee

6、xperiment．(a)TheexperimentresultofAandBhavethesamelength．Antsselectthemnearlyequalinsuchcase；100U求衄蠢50≤黧短0耋奠鬻1

7、

8、

9、

10、垂垂荔i囊堑

11、

12、1鬃*骥i。i∞7-。，。。≯母裁M0—2020一4040—6060-8080—100在较短分支上的流量百分比图1．3“双桥”实验结果。(b)A和B长度不等时，A被选择的概率较大。Fig1．3Theexperimentresultofdoublebridgeexperiment．(b)TheexperimentresultofAandBhavet

13、hedifferentlength．MostlyantsselectAinsuchcase．2．3TSP问题在有向图D中，三元组(矿，E，厂)中的y是非空集合，里面放的是D的节点；集合E放的是D的边；f则是从E到VxV的一个映射。C是一个集合，其含有船个元素c。，c：，⋯c。，其中q(f-72，⋯一叩)代表城市i；L重庆大学硕士学位论文2基于TSP问题的基本蚁群算法为边勺的集合，其中勺=d(q，勺)(f，／=1，2，⋯，刀)，即c，与q之间的距