一种求解TSP问题的改进蚂蚁群算法
第22卷总第40期
2,001年6月西北民族学院学报(自然科学版)JournalofNorthwestMinoritiesUniversity(NaturalV01.22.No.2Science)June.2001
一种求解TSP问题的改进蚂蚁群算法
冯祖洪
(西北第二民族学院网络计算中心,宁夏银川750021)
【摘要】通过用混合型蚂蚁群算法求解TSP问题的方法和步骤,并以att532(美国532个城市)为例给出计算实验结果.说明混合型蚂蚁群算法改进了标准蚂蚁群算法的效率和计算结果的质量.
[关键词】TSP问题;蚂蚁群算法;改进蚂蚁群算法
[中图分类号】0211【文献标识码】A[文章编号]1009—2102(2001)02.0010.04
q席-腐■辟-席、簟,客、—、—屯—奢_廊b席h席、_席、|—~—^—奢_店、.卢~—~—瓠—舒 庸■席q脯。席嶂席。席—摩q席-—铲 庸q—~—、—轧∥帛 席-席b席、—、-,稽}
蚂蚁是一种群体生活的昆虫,人们发现蚂蚁的许多行为有助于人类形成解决一些困难问题的新思想.例如,人们发现蚂蚁在如图1所示的蚂蚁取食物实验中,经过一定的时间段以后,大部分蚂蚁总是利用较短的一条路径往返于蚂蚁巢与食物源之间.经过进一步研究分析得知,这是蚂蚁利用生物信息进行间接通信、协同工作的结果.蚂蚁一开始从蚁巢去食物源.来到交叉点后,因没有任何信息可参考,故不知道哪一条路径到达食物源更近一些,只好随机选择一条路径去B点.因而可以假定出发时,蚂蚁以相同的概率选择路径,边走边释放蚂蚁特
有的生物信息.由于选较短路径的蚂蚁首先到食物源并返回,在返回的交叉点,蚂蚁发现一条路径上有一定的生物信息浓度,而另一条是空白,因此选择生物信息浓度大的径路返回,且继续释放生物信息增加它的浓度.这样不断反复,使较短路径与较长路径的生物信息浓度差越来越大,促使大部分蚂蚁都利用较短路径往返于蚁巢和食物源之间.受蚂蚁这种利用生物信息进行间接通信、协同工作方式的启发,Doirog提出蚂蚁群算法,并将这种算法逐步应用于求解TSP(TracelingSalesmanProblem)、QAP(QuadraticA磷signmentProblem)、网络通信等组合优化问题,并取得了'一些成果.实验发现,标准蚂蚁
群算法有许多优点,求解组合优化问题的整体搜索
性能良好,该算法对30个城市以下的TsP问题较
有效。随着TSP问题规模的扩大,常规蚂蚁群算法
的计算效果很不理想.为r解决由TSP的规模带图1AA表示蚂蚁巢。l{表示食物源来的问题。我们提出改进型蚂蚁群算法,取得了较好的效果.
1TSP问题
一般地,TSP问题可描述如下:
设C={cl,c2,…,Cn}是一个城市的集合,L={b
[收稿日期】2001.03—15
[作者简介】冯祖洪(1956一),男,江苏无锡市人,西北第二民族学院网络计算中心副教授,主要研究人工lci、q∈El是C中元素两两连接的智能和计算机网络.一10—
一种改进的蚁群算法求解TSP问题及实验结果分析_IT/计算机_专业资料。一种改进...则第i+l只蚂蚁选择路径 A和B的概率为: 是,由于构造型算法优化质量较差,迄今...
求解TSP问题的一种改进蚁群算法_专业资料。TSP问题是典型的NP—hard组合优化问题,用蚁群算法求解此问题存在搜索时间长,容易陷入局部最优解的不足。本文提出了一种...
介绍了求解 TSP 问题的混合型蚂蚁群算法 ,并以 att532 ( 美国 532 个城市) 为例给出了计算实验结 要果 ,说明了混合型蚂蚁群算法能改进标准蚂蚁群算法的计算...
5 求解 TSP 问题的改进蚁群算法张 军英 , 敖 1, 2 磊 , 贾江 涛 , 高 710071; 1 1 琳 1 ( 11 西安电子科技大学 计算机学院 , 陕西 西安 21 西 ...
“挑战杯”广西大学生课外学术科技作品竞赛 作品申报书作品名称:基于 k-means 的改进粒子群算法求解 TSP 问题 学校全称: 申报者姓名 (集体名称) : 类别:√ □...
信息技术 2004.04大众斟技63 求解TSP问题的蚁群算法改进探讨●王震霆(浙江工商大学计算机与信息工程学院,浙江310013) 〔摘要】蚁群算法是通过模拟蚂蚁觅食而发展出的...
求解 TS P 问题的改进蚁群算法张军英 1, 2 , 敖 磊 , 贾江涛 , 高 琳 1 1 1 摘要 : 分析了标准蚁群算法易于出现早熟停滞现象的主要原因 ,在原有算法...
文中利用速度恒定的蚂蚁群,行走最短路的蚂蚁首先 达到终点这个基本原理,在问题空间中同时构造问题 的多个解,很好地解决了蚁群算法在求解最短路径和 TsP问题的局限性...
一种基于优质边求解TSP的蚁群算法_信息与通信_工程科技_专业资料。32 2013,49...求解 TS P的蚁 群算法 胡银 厚, 王世 卿 HU Yinhou,WANG Shiqing 郑 州...
动态蚁群算法求解TSP问题_理学_高等教育_教育专区。蚁群算法维普资讯 http://...( 1) 3动 态蚁 群算 法 动态蚁群算法相对 A S和MMA S主要 改进在于 ...
热门文档