基于em-plant的旅行商问题仿真研究

《基于em-plant的旅行商问题仿真研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于eM-plant的旅行商问题仿真研究第25卷第4期湖北工业大学学报2010年8月VoJournalofHubl.25No.4eiUniversityofTechnologyAug.2010[文章编号]1003-4684(2010)04-0058-03基于eM-plant的旅行商问题仿真研究周敏，陈定方，鄂晓征(武汉理工大学智能制造与控制研究所，湖北武汉430063)[摘要]运用遗传算法对旅行商问题(TSP)进行分析，确定其具体运行步骤，结合Em-plant软件添加遗传算法模块，对所作出的分析进行仿真

2、，求出可能最优解，以验证分析的可行性.仿真结果说明，遗传算法解决旅行商问题是有效的.[关键词]旅行商问题z遗传算法;仿真优化[中图分类号]TP301.6[文献标识码]:A旅行商问题(TravelìngSalesmanProblem,个点，每个点最多只能遍历1次.TSP)又被译为旅行推销员问题、货郎担问题，是最。12345678。。467.592010168基本的路径优化问题，经过70多年的研究，虽已取14。6.541057.51110266.5。7.510107.57.57.5得很大进展，但至今仍未完全

3、解决[IJ其求解的方法37.547.5。105991549101010。107.57.510有很多种，如动态规划法、分支限界法、拉格朗日松520510510。797.56107.57.597.57。710弛法、遗传算法、蚁群算法、模拟退火算法等.本文主716117.597.597。10要采用遗传算法对TSP问题进行分析研究.通过在88107.51旦107.5L1010。eM-plant仿真平台中结合遗传算法建立相应的模O表示配送中心;1~8表示配送点;型，对TSP问题进行数据分析及优化，以更深层次单元格

4、为各点之间的距离(单位:km)地解析生活中的各种组合优化问题.图1所求问题的距离矩阵1TSP问题的数学描述与实例2基于遗传算法的仿真优化1.1TSP问题的数学描述2.1遗传算法的基本思想TSP问题可描述为:设有n个城市，以1，2，…，遗传算法[4-5J借用了生物学中;适者生存;的规n表示叫。表示从i城到1城的距离.一个推销员从律，从众多具有生存能力的子集中选择最大可能地城市1出发到其他每个城市一次且仅是一次，然后继续生存下去.遗传算法的基本思想如图2所示.回到城市1，问他如何选择行走路线，使总的路程最短

5、∞.用图论语言描述为t设有→个图G=(V，日，其中V是顶点集，E是边集，设??=(d;j)是由顶点i与顶点j间的距离所组成的距离矩阵，TSP就是求→条通过所有顶点且每个顶点只通过一次的具有最短路径的Hamìlton回路[3J1.2本文所涉及的TSP实例给定1个配送中心和8个配送点的距离矩阵如图2遗传算法的基本流程图图1所示.求解问题为:寻找一条最短路径，遍历每[收稿日期]2010一03一24[作者简介]周敏(1988-)，女，湖北公安人，武汉理工大学硕士研究生，研究方向为物流仿真及优化第25卷第4期周敏

6、等基于eM-plant的旅行商问题仿真研究592.2基于eM-plant的GA优化模型1)选择顺序交叉，交叉概率为0.2;选择倒置变eM-plant仿真软件的特点主要表现在面向对异，变异概率为0.4.可得z满意解为58，万案为{O一象化的构建模式、图形化与对象化的并行仿真环境、1-3←5-6一7→4-8-2一O}，满意解的个体最早对象的继承、SimTalk语言、与eM-power系列软件产生在第四代.的集成等方面[6]2)选择顺序交叉，交叉概率为0.8;选择交换变利用eM-plant软件建立仿真模型，该

7、模型与遗异，变异概率为0.1.可得z满意解为60，方案为{O←传算法结合起来对TSP问题进行优化.具体优化模2-8-5-6-4一7-3-1一时，满意解的个体最早型如图3所示产生在第五代.[;GA模块俨辛苦吁:3)选择部分影射交叉，交叉概率为0.8;选择倒置变异，变异概率为0.4.可得:满意解为58.5，方案为{0-2-8一7-4-6-5-3-1-0}，满意解的个体最早产生在第八代.4)选择部分影射交叉，交叉概率为0.8;选择交换变异，变异概率为0.1.可得:满意解为60，方案为{0-8←2-6-4-7-

8、5-3一1一时，满意解的个体最早产生在第八代.图3基于Em-plant的GA优化模型其具体的适应度图谱比较见图4所示.提仿真模块初始化时会设置相应的世代数和种群Mm时阐明规模，并将配送点与基因位一一对应起来.开始之后会将个体信息调入算法模块中，产生初始群体，然后解码输出到仿真模块中，在仿真模型里表示出路径的变化，并根据目标函数计算该个体的目标函数值.(a)顺序交叉，倒置变异遗传算法模块调用此目标函数值对各个体的适应度进行评价，选择优良的个