admin管理员组文章数量:1566358
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
版权声明:本文标题:蚂蚁算法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1715435715a452048.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论