小窗口蚁群算法

《小窗口蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第29卷　第20期计　算　机　工　程2003年11月Vol.29№20ComputerEngineeringNovember2003·人工智能及识别技术·文章编号：1000—3428(2003)20—0143—03文献标识码：A中图分类号：TP301.6小窗口蚁群算法萧蕴诗，李炳宇(同济大学电子与信息工程学院，上海200092)摘要：在蚁群算法的基础上，提出了小窗口蚁群算法。通过对旅行商问题解集的分析，找到其最优解的特点，通过限定蚂蚁每次只向距离最近的几个城市移动，大大缩小其搜索范围，减少对算法中主要参数的依赖，提高其搜索精度并

2、减少搜索时间。实验结果表明该算法有较好的效果。关键词：蚁群算法；小窗口；旅行商问题AntColonyAlgorithmBasedonLittleWindowXIAOYunshi，LIBingyu(SchoolofElectronicandInformationEngineering,TongjiUniversity,Shanghai200092)【Abstract】Thispaperproposesanantcolonyalgorithmbasedonlittlewindowfromtypicalantalgorithm.Bya

3、nalyzingthesolutionspaceofTSPtofindcharacteristicsaboutoptimizationsolution,thisalgorithmreducesthescopeofsolutionspaceandthedependenceoncriticalparameterintypicalalgorithm.Itimprovestheprecisionandreducesthesearchingtime.Simulationsdemonstratesthattheimprovedalgorit

4、hmcanachievebetterperformancethantypicalalgorithmandsomeotherimprovedalgorithms.【Keywords】Antcolonyalgorithm；；LittlewindowTravelingsalesmanproblem(TSP)近年来，蚂蚁、蜜蜂以及鸟鱼群的群体运动行为引起了度高的方向运动。换句话说，蚂蚁选择信息素强度高的路径一些科学家的注意。其中，意大利学者Dorigo，等Maniezzo比强度低的路径的概率要高些。设想当几只蚂蚁分别沿着不人受到蚂蚁在觅

5、食过程中可以找出巢穴到食物源的最短路径同的路径回巢，长度越短的路径上信息素的强度越高，其它[1]的启发，提出了蚁群算法(antcolonyalgorithm)，并将其应蚂蚁选择这样路径的概率也越大，选择的蚂蚁越多，路径上[2][3][4]用于求解TSP、资源二次分配、Job-Shop调度等问题，的信息素强度也会更高，这样形成正反馈，使越来越多的蚂取得了较好的结果。除此之外，蚁群算法在路由方面的应用蚁集中到最短的路径上来。[5]也被认为是目前较好的算法之一。蚁群算法就是模拟上述蚂蚁觅食行为，设计虚拟的蚂然而，蚁群算法本质上和模拟退

6、火算法、遗传算法等随蚁，使其随机搜索不同的路径，并留下会随时间变化而蒸发机搜索算法一样，容易陷入局部极小点，存在扩大搜索空间的“信息素”，根据“信息素”强度来寻找最短路径。与寻找最优解之间的矛盾，对算法的参数敏感且运算周期蚁群算法提出后，首先被应用于求解TSP问题。下面通长，例如文献[6]中的对称TSP问题(城市数目>50)就进行了过TSP问题来说明蚁群算法的数学模型。TSP问题可以表述100003次迭代。本文在蚁群算法的基础上，针对以上个不足为：给定n个城市和每两个城市之间的距离，要寻找一条路点，提出了小窗口蚁群算法，限定了每

7、只蚂蚁下一步移动所径，从某个城市出发，周游其它所有城市一次且仅一次，最能“看见”的城市，从而大大缩减了解空间，避开了许多局后回到出发城市的闭环路径长度最短。可以用有向图G=部极小点，使蚂蚁搜索空间集中于最优解附近，搜索速度和(V，E)表示，其中V表示nE个城市，表示各个城市之间的搜索时间得到极大改善，并且对参数不敏感，无须大量实验边。非负矩阵D=[d]表示各个边的距离，本文选用的实ij来寻找合适的参数。该算法在TSP问题中的应用结果表明，例都是对称TSP问题，因此，dij=dji.除此之外，还要求其搜索精度和搜索时间都是同类算法

8、中较出色的。1基本的蚁群算法矩阵D的对角线上元素为0，任意3,个元素满足三角不定式诸如蚂蚁、蜜蜂、鸟鱼群等群居生物，单个个体的行为即：.dij+djk³dik,1£i,j,k£n比较简单，但由这些单个个体组成的群体，在一定内在规律在蚁群算法中，将自然蚂蚁群体抽象