蚁群优化算法的改进与其在TSP中的应用

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

1、-------重庆大学硕士学位论文2蚁群优化算法的原理及其研究对于蚂蚁而言，最重要的就是对路径上信息素的使用。生物学家研究发现：蚂蚁能够感知路径上信息素的强度大小，并以较大的概率选择信息素强度大的路径。已经有学者对某些种类的蚂蚁通过信息素浓度选择路径的行为进行过可监控的实验。最巧妙的实验是由Deneubourg及其同事设计和完成的，他们使用了一个双桥来连接蚂蚁的蚁穴和食物源。在实验中测试了一组不同比例的r=ll值，其中r是双桥上两ls个分支的长度比，l是长分支的长度，l是短分支的长度。ls在第一个实验中，当r=1时，初始阶段，路径上都没有信息素，蚂蚁以相同的概率选择分支，并在经过的路径

2、上释放信息素。一段时间后，选择A或者B的路径的蚂蚁数量略有不同，但大致相等。在第二个试验中，当r=2时，即较长的分支长度是较短分支长度的2倍。实验结果显示，一段时间后，大多数蚂蚁都会选择较短的分支。A蚁穴12食物源15cmA蚁穴食物源BB(a)(b)图1.1双桥试验的实验设置。(a)两条分支具有相同长度；(b)两条分支具有不同长度。Fig1.1Doublebridgeexperiment.(a)Twoembranchmentshavethesamelength;(b)Twoembranchmentshavethedifferentlength;100 1005050000-2020-4

3、040-6060-8080-1000-2020-4040-6060-8080-100在某条分支上的流量百分比在较短分支上的流量百分比(a)(b)图1.2双桥试验得到的实验结果。Fig1.2Theexperimentresultofdoublebridgeexperiment.在图1.2（a）中，相同长度的两条分支的实验结果表明：蚂蚁选择两条分支的次数基本相等；在(b)中，不同长度的两条分支的实验结果：大部分蚂蚁都选择较短的分支。-----------3-----------重庆大学硕士学位论文2蚁群优化算法的原理及其研究1.3.2蚁群优化算法的基本原理生物学家关于蚂蚁行为的研究表明：在

4、蚂蚁群体中，个体之间以及个体与环境之间的联系是依赖蚂蚁产生的外激素来进行的。蚂蚁这种特有的信息传递方法，不同于人类以及其他的高级种群之间所使用的以视觉和听觉为主的感知方式。对于蚂蚁来说，在他们的种群生活中，最重要的就是路径上信息素的使用。在觅食过程中，蚂蚁可以感知路径上的信息素来探寻食物，这种根据其他蚂蚁释放的信息来影响后续蚂蚁的路径选择的行为方式正是蚁群算法的灵感来源。蚂蚁在觅食过程中，如果蚂蚁从巢穴到食物源所走的路径较短，则蚂蚁从巢穴到食物源后再返回巢穴的时间就短，则相同时间内较短的路径上蚂蚁所分泌的和积累的信息素较多。由于后继的蚂蚁能够感知信息素的多少并能指导自己的方向，所以一条

5、路径上的信息素越多，蚂蚁在寻找食物过程中选择这条路径的概率就越大。所以，蚂蚁群体的集体行为实际上构成了一种学习信息的正反馈机制，蚂蚁之间也通过这种信息素来交流信息。蚂蚁群体就是通过个体之间的信息素的感知和积累，协作交流寻求最优解。蚁群算法就是模拟这样的优化机制而产生的。下面详细地介绍蚁群巡游过程：如图1.3(a)：规定路径nest-ABD-food的长度为4，路径nest-ACD-food的长度为6。在单位时间内，假设蚂蚁移动一个单位的距离。在初始阶段，所有信息素的初始值都为零。如图1.3(b)，在t=0时刻，20只蚂蚁从nest移动到A点，由于无信息素，蚂蚁选择两侧的概率均为50%，

6、即两侧路径各有10只。如图1.3(c)，在t=4时刻，先到达food的蚁群将返回。如图1.3(d)，在t=5时刻，根据前面蚂蚁的行程可知：路径BD上的信息素浓度和CD上相同。两组蚂蚁在D点相遇，各有5只蚂蚁选择两侧路径。如图1.3(e)，在t=8时刻，前5只蚂蚁已经返回nest，在AC、CD和AB上各有5只蚂蚁。如图1.3(f)，在t=9时刻，前5只蚂蚁回到A点。此时，经过路径AB上的蚂蚁数为20而AC上为15，因此路径AB上的信息素多于AC上的信息素，故大多数蚂蚁将选择路径AB。如此往返，路径AB与AC上的信息素浓度的差距将变大，这样会导致大多数蚂蚁都选择路径AB。---------

7、--4-----------重庆大学硕士学位论文2蚁群优化算法的原理及其研究FoodFood t=0t=4Foodd=110antsDD d=2D10antsd=1BObstacleCBObstacleCBObstacleCd=1 d=2A10antsA A10antsd=1t=0NestNestNest(a)(b)(c)FoodFoodt=5t=8t=9Food10ants5ants5ants5antsDDDBObstacleCBObstac