蚁群优化算法与其改进

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

1、-------重庆大学硕士学位论文1绪论生的化学物质进行的，人们称这种化学物质为信息素（pheromone）。蚂蚁这种特有的信息传递方法，不同于人类以及其他的高级种群之间所使用的以视觉和听觉为主的感知方式。对于某些蚂蚁来说，在他们的种群生活中，最重要的就是路径上信息素的使用。蚂蚁是一种群居性的生物群体，其在群居过程中存在着蚂蚁的分工，有的筑巢，有的觅食等，蚁群算法是基于蚂蚁觅食的过程中发现并应用于实际的。经过研究表明，蚂蚁在觅食过程中会在其经过的路径上留下信息素（pheromone），其他的蚂蚁个体能够感知到信息素，并且通过信息

2、素的浓度来指导自己的移动方向。蚂蚁在觅食过程中，如果蚂蚁从巢穴到食物源所走的路径较短，则蚂蚁从巢穴到食物源后再返回巢穴的时间就短，这样的话相同时间内较短的路径上蚂蚁所分泌的和积累的信息素较多。由于后继的蚂蚁能够感知信息素的多少并能指导自己的方向，所以一条路径上的信息素越多，蚂蚁在寻找食物过程中选择这条路径的概率就越大。所以，蚂蚁群体的集体行为实际上构成了一种学习信息的正反馈机制，蚂蚁之间也通过这种信息素来交流信息。蚂蚁群体就是通过个体之间的信息素的感知和积累，协作交流寻求最优解。蚁群算法就是模拟这样的优化机制而产生的。目前已经有

3、学者对某些种类的蚂蚁通过信息素浓度选择路径的行为进行过可监控的实验。对于蚂蚁群体通过信息素浓度选择路径的行为已经有学者做了监控实验，最巧妙的一种实验是由Deneubourg及其同事设计和完成的，他们使用了一个双桥来连接蚂蚁的蚁穴和食物源。在实验中他们测试了一组不同比例的r=ll值，其中rls是双桥上两个分支的长度比，l是较长分支的长度，l是较短分支的长度。lsA蚁穴12食物源15cmA蚁穴食物源BB(a)(b)图1.1双桥试验的实验设置。(a)两条分支具有相同长度；(b)两条分支具有不同长度。Fig1.1Doublebridge

4、experiment.(a)Twoembranchmentshavethesamelength;(b)Twoembranchmentshavethedifferentlength;-----------2-----------重庆大学硕士学位论文1绪论1001005050000-2020-4040-6060-8080-1000-2020-4040-6060-8080-100在某条分支上的流量百分比在较短分支上的流量百分比图1.2双桥试验得到的实验结果。Fig1.2Theexperimentresultofdoublebridge

5、experiment.(a)Theexperimentresultoftwoembranchmentshasthesamelength.Antsselecttwoembranchmentsnearlyequalinsuchcase.(b)Theexperimentresultoftwoembranchmentshasthedifferentlength.Mostlyantsselecttheshorterembranchmentinsuchcase.在图1.1（a）所示的实验中，双桥的两条分支长度相等（即r=1）。在实验开始的时

6、候，在A和B两条路径上的信息素的浓度都是一样的，都是0，所以蚂蚁在经过桥的分界点时就会以相同的概率选择A和B，所以两条路径的蚂蚁数目刚开始是相同的，经过外力的作用，或者是某一种波动，使得原来的平衡被打坏，使得一条路径上的蚂蚁选择了另外的一条路径，使得经过蚂蚁多的路径上信息素的浓度增加，使得更多的蚂蚁选择这一条路径，最终导致所有蚂蚁都选择这一条信息素浓度高的路径。在图1.1（b）所表示的实验中，双桥的两条分支长度比例设为r=2，即较长的分支长度是较短分支长度的2倍。在这种条件下，蚂蚁在经过双桥的时候，由于A路径和B路径上的信息素都

7、是0，所以蚂蚁会以相同的概率选择这两条路径，但是由于B路径是A路径的两倍，所以在相同的时间内，通过A路径的蚂蚁是B路径的两倍，使得A路径信息素的浓度迅速的增加，使得越来越多的蚂蚁选择A路径。最终导致所有蚂蚁都选择A路径。1.2.2蚁群优化算法特点①系统性。蚂蚁是算法中的相对独立的个体，但是其在整个算法的运作过程中又体现出所有的蚂蚁是一个整体的系统，同时实验结果显示蚁群的搜索性能明显强于单只蚂蚁的搜索能力。蚁群算法的系统性的特点使得算法在求解系统问题时有一定的优势；②分布式计算。实验进行中是m只蚂蚁，蚂蚁是独立进行搜索，并不会因为

8、一只蚂蚁停滞而中断自己的行为；③每个个体只能感知局部的信息，不能直接使用全局信息；-----------3-----------重庆大学硕士学位论文1绪论④自组织性。蚁群算法的自组织性也大大增强了算法的鲁棒性，寻优过程也恰恰体现了这种自组织性；⑤正反馈。由于蚂蚁