种求解TSP的混合型蚁群算法

《种求解TSP的混合型蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第39卷2003年第4期西北师范大学学报(自然科学版)V01．392003No．4Journal0fNorthwestNormalUniversity(NaturalScience)3l一种求解TSP的混合型蚁群算法赵学峰(西北师范大学数学与信息科学学院，甘肃兰州730070)摘要：针对基本蚁群算法存在的过早收敛问题，提出一种采用混合模式调整信息素的改进蚁群算法，当陷入局部最优解时便启用新的信息素调整规则，从而使算法跳出局部解．计算机仿真结果表明，这种混合型蚁群算法对求解．I难题

2、有较好的改进效果．关键词：蚁群算法；'ISP；信息素中图分类号：TP301．6文献标识码：A文章编号：1001．998X(2003)04-0031．04AhybridantcolonyalgorithmforsolvingTSPZHAOXue—feng(College0fMathexIi~C8andInformationScience，NorthwestNormalUniversity，I．anzlxm730070，Gamu，China)Abstract：Ahybridantalgorithmispresentedtoprev

3、enttheprematureincanonicalantcolony~orithminthispaper．Themainideaofthemeeting~orithmisthatahybridpheromoneupdatestrategyisusedaccordingtothesolutionthatartificialantshavefound．Computersimulationshowsthatthepropo~edalgorithmcaneficientlyfindbettermini／ntllTlbeyondpre

4、matureconvergenceforhardTSPproblem．Keywords：antcolonyalgorithm；TSP；pheromone地球上的生物物种在漫长的演化过程中形成了1基本蚁群算法模型丰富的行为特性，并且不断完善和发展，以更好地适应生存的环境．生物化的过程本质上是一个优化1．1TSP模型过程，这一特点使得生物系统对计算科学具有直接给定／7,个城市(结点)的集合{1，2，⋯，／7,}，启发意义．随着计算机的诞生，人们期望计算机借及城市和．『之间的欧氏距离d(i，．『=1，⋯，／7,，d助程序的形式创造出

5、一些新型的智能体，于是对人=0)，模型的目标是寻找一条经过／7,个城市各1次类的大脑活动、人类的学习方式以及生物界的进化且仅1次最终回到出发点的最短回路．过程进行了模拟研究，促成了人工神经网络、遗传TSP是著名的NP难题【8】，目前尚无一个多项算法和免疫算法等智能计算模型的兴起．意大利学式时间算法，一些传统的确定性算法在求解这一问者DorigoM等提出的蚁群算法(Amcolonysystem)题时显得无能为力，例如用Backtrack法搜索问题类比自然界蚁群的觅食行为与旅行售货商问题的解空间时，算法的计算时间复杂性为o(n!)

6、t91．(TSP)的相似之处，成为求解NP-hard问题的一种1．2蚁群行为分析有潜力的随机优化算法n】．和遗传算法等基于自蚂蚁在搜寻食物时会在它所经过的路径上释放然法则的随机启发式搜索算法一样[5．7】，蚁群算法一种特殊的信息素(PherolTlone)来传递信息，后存在过早收敛现象——算法陷入局部最优解而停止来的蚂蚁走到前面蚂蚁走过的路口时可以感知到环搜索更优的解．为此，笔者对基本蚁群算法的信息境中这种物质的存在及强度，倾向于朝着信息素强素调整规则作了改进，并应用于典型TSP进行了求度高的方向移动．某一路径上走过的蚂蚁越多

7、，则解验证．信息素越来越强，后来者选择该路径的概率就越收稿日期：2002-12-30；修改稿收到日期：2003-09-06作者简介：赵学峰(196一)，男，甘肃渭源人，讲师．主要研究方向为算法分析．维普资讯http://www.cqvip.com西北师范大学学报(自然科学版)第39卷32JournalofNorthwestNormalUniversity(NaturalScience)V01．39大；而其他路径上的信息素却随着时间减弱．通过信息素增量为信息素的作用，蚁群行为与环境之间形成一个信息mAr。(t)=：Ar：(t)，

8、正反馈机制．这种间接的通信方式形成一种分布式自组织行为，个体简单的蚂蚁从初始的随机路径开Ar：(t)=Q／L(k，t)，(2)始，经过群体演化行为最终找到最优路径．表示当蚂蚁k在循环t经过边(i，)时释放的信息1．3蚁群算法的关键因素素，否则为0．Q是一正常数．蚁群算法用一类