admin管理员组

文章数量:1532758

2024年5月11日发(作者:)

蚂蚁算法求解TSP问题

指导教师:李正学

系 别:应用数学系

班 级:2003级06班

姓 名:王源

学 号:200312082

蚂蚁算法求解TSP问题

摘 要 蚂蚁算法是通过蚂蚁觅食而发展出的一种新的启发算法,该算法已经成功的解决了

诸如TSP问题。本文简要学习探讨了蚂蚁算法和TSP问题的基本内容,尝试解决一个实例

问题并给出C语言算法。

关键词 蚂蚁算法;TSP问题。

1 蚂蚁算法与TSP问题

1.1 蚂蚁算法

蚂蚁算法(Ant Colony Algorithm) 是由意大利学者 ,V. Manierio ,A.

Collorni等人于二十世纪九十年代提出的一种新型的模拟进化算法。受到人们对

自然界中真实蚁群集体行为研究成果的启发,考虑到蚁群搜索食物的过程与旅行

商问题的相似性,利用蚁群算法求解旅行商问题(Traveling Salesman Problem,

TSP ) 、指派问题(AssignmentProblem)和调度问题( Scheduling Problem) ,取得了

一些比较满意的实验结果。蚁群算法是一种适应性好、鲁棒性强,具有正反馈结

构的并行算法。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离

散优化问题)方面的一些优越性,证明它是一种很有发展前景的方法。蚂蚁算法在

各个领域的应用,说明该算法有着广泛的适应性,但由于该算法出现的较晚,对其

研究还处于起步阶段,远不如遗传算法、人工神经网络和模拟退火算法那样成熟。

算法的很多特性,如算法的收敛性,参数的设定都来自于大量实验统计结果,目前

对该算法理论研究有待进一步加强。

经过研究发现,蚂蚁在觅食的过程中通过一种称之为信息素(Pheromone)

的物质相互传递信息。更具体地,蚂蚁在运动过程中能够在其所经过的路径上留

下信息素,而且在运动过程中能够感受到这种信息素的存在及其强度,并以此指

导自己的运动方向。蚂蚁倾向于朝着信息素浓度高的方向前进,因此,由大量蚂

蚁组成的蚁群的行为便表现出一种信息的正反馈现象:某一路径上走过的蚂蚁越

多,则后来者选择该路径的概率就越大。蚁群就是通过个体之间这种信息交换机

制来彼此协作达到搜索食物的目的。

设有甲、乙两只蚂蚁从蚁穴A出发,分别沿AC 和ABC 路径同时在C 处

1

本文标签: 算法蚂蚁问题信息过程