基于递阶遗传算法的一类多旅行商问题优化

《基于递阶遗传算法的一类多旅行商问题优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第31卷第11期2009年11月系统工程与电子技术SystemsEngineeringandElectronicsVol-31NOVNo．112009文章编号：1001—506X(2009)11-2630—04基于递阶遗传算法的一类多旅行商问题优化周辉仁1’2，唐万生1，牛彝1’2(1．天津大学系统工程研究所，天津300072；2．山东建筑大学管理工程学院，山东济南250101)摘要：针对最小化单个旅行商路程的多旅行商问题，提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点，采用一种递阶编码方

2、案，此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子，操作简单，并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明，递阶遗传算法是有效的，能适用于优化多旅行商问题。关键词：人工智能；优化；递阶遗传算法；多旅行商问题中图分类号：TP301．6；TP18文献标志码：AOptimizationofmultipletravelingsalesmanproblembasedonhierarchicalgeneticalgorithmZHOUHui—renl”，TANG

3、Wan—shen91，NIUBenl’2(1．Inst．ofSystemsEngineering，TianjinUniv．，Tianjin300072，China；2．SchoolofManagementandEngineering，ShandongJianzhuUniv．，Jinan250101，China)Abstract：Inordertosolveakindoflongest—path—shortestmultipletravelingsalesmanproblem，ahierarchi—calgen

4、eticalgorithmanddecodingmethodwithmatrixisproposed．Itscodingmethodissimpleandcaneffec—tivelyreflectthetravelingpolicy，andthemethodsofcrossoverandmutationarenotspecialtodesign．Bythismethod，symmetricandasymmetricmultipletravelingsalesmanproblemscanbeeasilysol

5、ved．Thecomputa—tionalresultsshowthatthehierarchicalgeneticalgorithmisefficientandfitsformultipletravelingsalesmanproblems．Keywords：artificialintelligence；optimization；hierarchiealgeneticalgorithm；multipletravelingsalesmanproblem0引言旅行商问题(travelingsalesmanpro

6、blem，TSP)是一个典型的组合优化难题，它在许多领域都有着广泛的应用，已被证明属于NP问题r1]。所谓TSP是指有N个城市，要求旅行商到达每个城市各一次，且仅一次，并回到起点，且要求旅行路线最短。而多旅行商问题(multipletravelingsalesmanproblem，MTSP)是指M个旅行商从同一个城市(或不同城市)出发，分别走一条旅行路线，使得每个城市有且仅有一个旅行商经过(出发城市除外)，且总路程最短。有关TSP的研究在现实问题中有很大的使用价值，诸如交通运输、管道铺设、路线的选择、计算机网

7、络的拓扑设计、邮递员送信等，都可抽象成TSP或MTSP[2‘]。美国Michigan大学的Holland教授提出的遗传算法是求解复杂的组合优化问题的有效方法，其思想来自于达尔文进化论和门德尔松遗传学说，它通过模拟生物进化过程，从庞大的搜索空间中筛选出较优秀的解，是一种高效且具有强鲁棒性方法。所以，遗传算法在求解TSP和MTSP中得到了广泛的应用。目前，用遗传算法求解MTSP大都是距离对称的MTSP，一般是通过附加虚拟城市的方法将MTSP转化为TSP[5⋯。在实际问题中，限制单个旅行商的费用(或路程)是有一定实

8、际意义的。因此，有必要对单个旅行商路程最小化的MTSP进行研究。为了有效地解决单个旅行商路程最小、距离对称或者非对称的MTSP，本文提出了一种递阶遗传算法和矩阵解码方法，以便确定每个城市由哪个旅行商经过以及各个旅行商的行走路线，即找到一个最优旅行商分配及行走路线，在各旅行商行走完后，使路程最大的那个旅行商的路程最小化。仿真结果证明，本文提出的算法是有效的。收稿日期：2008—07—16；修回日期：2