基于蚁群算法的中国旅行商问题满意解

《基于蚁群算法的中国旅行商问题满意解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、维普资讯http://www.cqvip.com计算机与现代化2002年第8期JISUANJIYUXIANDAIHUA总第84期文章编号：1006—2475(2002)08—0OO6—03基于蚁群算法的中国旅行商问题满意解伍文城，肖建(西南交通大学电气工程学院，四川成都610031)摘要：蚁群算法是基于群体合作的一类仿生算法，适合于解困难的离散组合优化问题。本文对其做了适当的改进，以克服其求解速度过慢、容易出现停滞的缺陷，并将其用于解决中国旅行商问题，找到了目前已知的最好的解，同时指出了进一步提高蚁群算法效率还需解决的问题和方向。关键词：模拟进化

2、算法；蚁群算法；旅行商问题；组合优化中图分类号：TP3016文献标识码：ASatisfactorySolutionofChineseTravellingSalesmanProblemBasedonAntColonyAlgorithmrLJWen—cheng．XIAOJian(Electrical~holofSouthwestJiaotongUniversity，Chengdu610031，China)Abstract：Antcolony'algorithmisanovelsimulatedevolutionaryalgorithmbasedOil

3、groupcooperationandCanbeappliedtosolveharddiscretecombinatorialoptimizationproblem．Thispaper画vesabriefintroductionontheantcolonyalgorithmandmodifiesittosolvetheChinesetravellingsalesmanproblemResultshowsthattheperformanceofantcolonyalgorithmisimprovedandthepresentbestsolution

4、isfound．Italsopointsoutthattheantcolonyalgorithmstillhastobemodifiedinmanyways．Keywords：simulatedevolutionaryalgorithm；antcolonyalgorithm；travellingsalesmanproblem；combinatorialoptimization为=15404公里。0引言TSP的算法难度是NP完全难度的，目前尚无很旅行商问题可简单描述为：求一条通过全部N好的求解方法。虽然有枚举法、分支定界法、割平面个城市～次且仅一次

5、的最短旅行路线。可将TSP定法、动态规划法等精确算法_3j，但需时甚长；对于一个义为网络G=[V，A，C]，其中：V={(i，i)li，0，1，仅有30个城市的对称TSP问题，使用枚举法求解，需⋯，N一1，i≠i}为弧集，表示旅行商可能经过的路段集搜索291／2条路径，在每秒运算1000亿次的巨型计合；C={Cl(i，j)∈A}为费用矩阵，Cii表示旅行商经算机上求解也需费时4×10”年。过对应弧(i，)所花费的时间、距离或运输成本等。模拟进化算法就是针对这一类难题而涌现的仿中国旅行商问题(ChineseTravellingSalesman生算法

6、。这一类算法有模拟退火算法、遗传算法以及Problem，P)是一个真实的地理问题，由靳藩教授本文采用的蚁群算法等。蚁群算法在求解离散的复在文献[1]中提出。它可简单表述为：求一条从北京杂的组合优化问题上有优异的表现，在求解TSP问题出发经过中国31个省会／直辖市最后又回到北京的上它甚至可以与目前最好的一些专用算法相媲最短回路。CTSP的求解情况如下：靳藩在1991年的美]。因此，我们用蚁群算法来求解中国旅行商问著作_1提到用神经网络方法求出的一个满意解为题，这一问题已为其他算法所攻克，可以以此来检验Lm=15904公里，在2000年的著作中提到用

7、神经蚁群算法的效能。在求解过程中，我们对蚁群算法进网络、遗传算法求出的满意解均为。=15404公里，行了改进，较好地解决了蚁群算法存在的过早收敛、王攀l4等用改进了的混合遗传算法求得的满意解也计算速度较慢等两大缺点。收稿日期：2002—02—05作者简介：伍文城(1977一)，男，广东郁南人，西南交通大学电气工程学院硕士研究生，研究方向：智能控制、计算机控制技术、集成电路设计等。维普资讯http://www.cqvip.com2002年第8期伍文城等：基于蚁群算法的中国旅行商问题满意解71蚁群算法的基本思想Pk(i，j)：-『I∈r(i，j)]．

8、[T7(i，ifjEJk(i)㈩(1)蚁群算法是由意大利学者M．D0rigo，A．C0lomi．0。thersV．Manizzo等·刮在