TSP问题的遗传算法求解方案--源程序清单旅行商问题包含算法介绍源程序测试结果.doc

《TSP问题的遗传算法求解方案--源程序清单旅行商问题包含算法介绍源程序测试结果.doc》由会员分享，可在线阅读，更多相关《TSP问题的遗传算法求解方案--源程序清单旅行商问题包含算法介绍源程序测试结果.doc（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流TSP问题的遗传算法求解方案-源程序清单旅行商问题，包含算法介绍，源程序，测试结果.精品文档.TSP问题的遗传算法求解方案算法的软件实现4.1 开发环境介绍本文中的所有算法是在Visual C+ 6.0 的操作平台上进行开发的，并结合STL进行编程。1、Visual C+ 6.0简介Visual C+ 6.0 是微软公司最新出品的功能最为强大的可视化开放工具，是计算机界公认的最优秀的应用开发工具之一。Microsoft的基本类库使得开发Windows应用程序比以往任何时候都要容易。Visual C+作为一种程序设计语言，它同时也是一个集成开发

2、工具，提供了软件代码自动生成和可视化的资源编辑功能。2、Visual C+ 6.0的优势(1).拥有强大的编辑环境。(2).拥有强大的类库的支持。(3).拥有强大的调试环境。(4).拥有较强的低层控制能力。(5).拥有强大的帮助系统MSDN的支持。(6).拥有一个高效的编译器，产生的可执行文件体积小巧、运行速度快。 3、STL简介 STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C+程序库。它被容纳于C+标准程序库（C+ Standard Library）中，是ANSI /ISO C+标准中最新的也是极具革命性的一部分。该库包含了诸多在计

3、算机科学领域里所常用的基本数据结构和基本算法。为广大C+程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。这种现象有些类似于Microsoft Visual C+中的MFC（Microsoft Foundation Class Library），或者是Borland C+ Builder中的VCL (Visual Component Library)，但是它比二者具有更强的优势。更加值得一提的是，它具备以下几个区别于其它软件库的优点： (1).经过类属编程方法精心组织的，可互换的编程模块能够提供比传统组件设开始初始化遗传算法的相关参数计算每个个体的适应值产生城市对城市进行编码是否符

4、合终止条件？输出正确的TSP结果 是GEN=GEN+1 选择 交叉 变异 否 世代进化轮盘赌选择普通选择 GXCXOXPMX 基于次序的变异基于位置的变异倒位变异图4.1 遗传算法解TSP的具体流程图计方法丰富得多的组合方式。(2).类属编程方法设计也是将来为数据库，用户界面等专业领域开发组件的基础。(3).通过使用某些编译机制并根据不同的算法进行具体的设计，可以在不损失效率的情况下实现对组件的概括。与此形成鲜明对照的是，其它一些具有复杂继承层次和大量使用虚函数的C+库结构则通常会降低效率。4.2 算法实现的流程图 本设计的具体流程图如图4.1所示：4.3 算法的各个模块及其详细设计思路1城市

5、生成模块 用户可以点击鼠标左键产生城市，也可以选择菜单栏的设置城市选项，通过输入城市数目来随机生成城市。当然，如果用户选择错了城市，可以在该城市上点击鼠标右键来清除城市。如果用户要清除所有的城市，可以双击鼠标右键或选择菜单栏的结束选项，都可以清除所有的城市。其设计设计思路如图4.2所示：调用画图函数画点(即设置城市)程序将点的信息存入一个点向量中程序检测鼠标移动的具体信息 按下鼠标左键用一个变量记入要产生的城市数 按下鼠标右键 选择菜单栏的设置城市选项将点向量中要除去的点找出来循环调用鼠标左键点击消息直到达到要求的城市数 选择菜单栏的结束选项重新画点向量中的所有点(此时该删除的点已从点向量中删

6、除)重新画地图(即清除了所有的点)图4.2 城市生成模块的设计思路最后的效果如图4.3所示：图4.3 TSP问题城市设置实现效果2.地图选择模块 根据具体的需要，用户可以选择不同的地图，本设计提供的地图有：基于直角坐标系的地图和圆形地图，这两个地图由不同的类来产生。其中类DefaultMap产生直角坐标地图，类RoundMap产生圆形地图。图4.4所示的是直角坐标地图，图4.5所示的是圆形地图。图4.4 直角坐标地图图4.5 圆形地图3. 遗传算法解TSP的参数设置模块在具体的应用中，用户可以根据具体情况来设置遗传算法的相关参数，这些参数包括： 交叉率：控制程序进行交叉的次数，在本设计中，先随

7、机生成一个数，如果这个数大于交叉率，则不交叉，如果这个数小于交叉率，则进行交叉。具体实现如下：pick = float(randomInt(0,1000)/1000;if(pick pcross)/进行交叉操作else/不进行交叉操作 变异率：控制程序进行变异的次数，在本设计中，先随机生成一个数，如果这个数大于变异率，则不变异，如果这个数小于变异率，则进行变异操作。具体实现如下：pick = float(randomInt(0,1000)/1000;if(pick pmutation)/进行变异操作else/不进行变异操作 种群大小：即种群中所含有的个体数量，选择一个合理的种群值，不但会使得群

8、体的多样性增强，防止遗传算法的“早熟现象”，还会使得遗传操作收敛得更快。 世代数：控制遗传操作世代进化的次数，合理的世代数能够使得计算结果的优劣程度不同。图4.6 遗传算法解TSP的参数设置 进化设置：根据子染色体与父染色体的关系，进化设置又分为两种：普通进化：完全模仿自然进化，子染色体可能比父染色体优秀，也可能比父染色体差。强制进化：选取子染色体中比父染色体优秀的染色体，杀死子染色体中比父染色体差的染色体。使得进化一直朝着优秀染色体的方向进化。具体的实现效果如图4.6所示：4.交叉算子选择模块交叉操作是遗传算法中最重要的一环，交叉算法的优劣将最大限度地影响遗传算法的结果。本设计先根据国外专家

9、提出的解TSP的几种经典算法，然后编程将其实现，并在此基础上，提出一种改进的交叉算法。在具体的应用中，用户可以根据自己的需要，选择最符合实际情况的交叉算法。程序的具体选择模块如下：/交叉算子的选择模块inline void CGA:crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2)switch (TempCrossoverStyle)case ID_PARTIALLY_MATCHED_CROSSOVER :/部分匹配交叉partially_matched_crossover(parent1,parent2,c

10、hild1,child2);break;case ID_ORDER_CROSSOVER :/顺序交叉order_crossover(parent1,parent2,child1,child2);break;case ID_CYCLE_CROSSOVER :/循环交叉cycle_crossover(parent1,parent2,child1,child2);break;case ID_GREED_CROSSOVER:/循环贪心交叉greed_crossover(parent1,parent2,child1,child2);break;default :break;5.变异算子选择模块求解TSP

11、时，变异算子的设计比交叉算子的设计灵活，任何具有局部搜索能力的算子都可以作为它的变异算子。本设计实现了三种变异：基于次序的变异，基于位置的变异，倒位变异。程序的具体选择模块如下：/变异算子选择模块inline void CGA:mutation(Chrom& chr)switch (TempMutationStyle)case ID_ORDER_MUTATION :/基于次序的变异order_oriented_mutation(chr);break;case ID_POSITION_MUTATION :/基于位置的变异position_oriented_mutation(chr);break;

12、case ID_REVERSE_MUTATION:/倒位变异reverse_mutation(chr);break;default :break;6.具体输出信息显示模块为了使程序运行时具体的算法和各种数据信息更加明确化，增加了信息显示模块，这样，在程序运行时用户可以掌握具体的数据信息，以便对各种算法进行比较。信息显示模块包括：计算结果模块，算法运行时间模块，所选遗传算子模块。下面分别对各个显示模块进行讨论： 计算结果模块：输出的信息包括当前鼠标的横坐标，当前鼠标的纵坐标，这两个信息是为了用户设置城市时参考的。城市总数信息是用户设置的城市数目。总距离信息是经过计算的TSP问题的最优路径长度，它

13、是屏幕上象素点间的距离。 算法运行时间模块：包括算法启动前时间，它是用户设置完城市，进行求解时刻的时间；算法结束时间，它是程序运行完成，正确输出TSP结果时刻的时间；算法耗费时间，它是进行遗传算法求解TSP时算法所消耗的时间。 所选遗传算子模块：它显示的是用户选择了那种交叉算子，那种遗传算子，以便于对各种算法比较时使用。 具体的显示如图4.7所示：图4.7 各种信息显示图4.4 设计中主要的类和函数的功能1. Map类，DefaultMap类，RoundMap类DefaultMap类这三个类均为画图相关的类，其继承关系为： 继承Map类 基类RoundMap类 继承图4.8 画图类继承关系其中

14、，DefaultMap类主要是与直角坐标地图有关，RoundMap类主要是与圆形地图有关。这些类提供了画地图函数：DrawMap，保存地图中的位置函数：SaveClickPoint，清除点向量中所有城市点的函数：DelAllPoint，在地图上画点的函数：DrawPonit，将地图上已存在的点删除函数：SmearPonit等等。2. CGA类 这个类主要是为遗传算法设置的，在这个类中定义了基因结构体代表一个城市，染色体结构体代表到各城市去的一种组合，还定义了种群结构体表示各种不同基因的组合。这个类主要是进行遗传算法操作的，包括各种进化运算，即选择，交叉，变异等等。这个类中的主要函数有：遗传算法

15、参数设置函数：preSet，遗传算法启动函数：start，交叉类型选择函数：SetCrossoverStyle，变异类型选择函数：Set- MutationStyle，世代进化函数：generation，染色体适应度计算函数：chromCost，种群个体适应度计算函数：popCost，初始化染色体函数：initChrom，初始化种群函数：initpop，轮盘赌选择函数：selectChrom等等。3. Control类 Control类主要是对程序进行控制的，它为各个模块的组合提供了接口，并且将必要的数据信息在屏幕上输出。它提供的函数主要有：欢迎窗口显示函数：welcome，遗传算法接口函数：

16、SetGaInformation，信息显示函数：DisPlay等等。4. Line类 Line类主要是计算TSP问题的具体操作，包括对城市点构成矩阵的设置，计算城市点之间的距离，画线，保存城市点的矩阵信息，计算最终结果等。5. main.cpp 这是一个主程序文件，是整个程序启动，操作的主控文件。是整个程序的框架部分。 此外，程序还有头文件类，资源类等等。这里就不详细介绍，具体的源程序见程序文档。5 软件测试及实验结果分析5.1 软件测试 以下是软件测试的步骤：1.运行程序后，弹出欢迎消息，如图5.1所示：图5.1 遗传算法解TSP问题欢迎窗口2.点击确定，进入主程序模块，点击选择地图，可以选

17、择直角坐标地图和圆形地图，默认地图为直角坐标地图，下面的演示以直角坐标地图为主，如图5.2所示：图5.2 遗传算法解TSP问题直角坐标演示地图3. 在屏幕上点击鼠标左键可设置城市，也可以点击菜单栏设置城市，弹出设置城市数目对话框，在对话框中输入城市数目，可以在屏幕上随机生成城市，具体情况如图5.3，5.4所示：图5.3 设置城市数目图5.4 设置城市4. 点击菜单栏遗传算法设置按钮，弹出遗传算法参数设置对话框，如图5.5所示：图5.5 遗传算法参数设置对话框 在遗传算法参数设置对话框中，可以设置交叉率，变异率，种群大小，世代数以及选择进化设置等。5. 点击菜单栏交叉类型按钮，可以选择交叉算法，

18、如图5.6所示：图5.6 交叉类型选择 可供选择的交叉类型有：部分匹配交叉，顺序交叉，循环交叉，循环贪心交叉。6. 点击菜单栏变异类型按钮，可以选择变异算法，如图5.7所示，可供选择的变异类型有：基于次序的变异，基于位置的变异，倒位变异。图5.7 变异类型选择7然后点击菜单栏开始，则进行计算，最终结果如图5.8所示：图5.8 遗传算法解TSP问题计算结果8. 点击菜单栏结束可以清除所有点，点击帮助，可以弹出帮助文件。至于圆形地图的测试过程与直角坐标地图相似。5.2 算法的正确性验证 为了测试算法的正确性，我使用了固定城市测试模块，该模块中的城市坐标，城市大小可以预先设置。其中，城市的数目，坐标

19、和最优解均可以参照国内外专家的文献，然后对比本程序计算的结果。如图5.9所示：图5.9 固定城市测试本设计中的参考文献可见参考文献1，城市坐标见参考文献1，36，交叉率为0.6，变异率为0.2，种群大小为100，世代数为100，采用强制进化方式，交叉类型为部分匹配交叉，变异类型为基于次序的变异。测试的十组数据如下：时间(s)12.67211.82812.7811.76512.68812.84411.25010.84410.68711.954最优解517492505515492509519526549491 计算平均值有平均最优解为：511.5，平均时间为：11.9364s。与参考文献1，37的

20、部分匹配交叉数据，平均最优解为：517.0，平均时间为：31.2s对比可知，本设计的算法符合要求。由于本设计使用的是强制进化方式，所以平均最优解和平均时间均有一定的改进。5.3 模拟实验结果与分析5.3.1 不同遗传操作组合的算法为了考察遗传算法组合优化在求解TSP问题中的重要性,本文进行了多种遗传操作组合的模拟实验，各种遗传操作组合成的算法如下:GA0：部分匹配交叉+基于次序的变异 GA1：部分匹配交叉+基于位置的变异 GA2：部分匹配交叉+倒位变异 GA3：顺序交叉+基于次序的变异 GA4：顺序交叉+基于位置的变异 GA5：顺序交叉+倒位变异GA6：循环交叉+基于次序的变异 GA7：循环交

21、叉+基于位置的变异GA8：循环交叉+倒位变异 GA9：循环贪心交叉+基于次序的变异GA10：循环贪心交叉+基于位置的变异 GA11：循环贪心交叉+倒位变异表5.1 30个城市位置坐标城市编号坐标城市编号坐标城市编号坐标1(40,406)11(190,323)21(2,290)2(33,39)12(401,152)22(521,92)3(268,183)13(291,201)23(172,43)4(277,377)14(620,235)24(440,150)5(361,103)15(117,154)25(252,147)6(104,4)16(546,305)26(346,343)7(180,26

22、)17(70,197)27(461,416)8(160,70)18(468,171)28(436,258)9(194,181)19(466,258)29(322,80)10(626,395)10(234,233)30(228,357)5.3.2 模拟实验结果 对于上述各算法，分别进行了计算机模拟实验，计算中采用的有关数据如下：城市数为30，群体规模为100，交叉概率为0.8，变异概率为0.1，群体更新100代结束，采用强制进化方式进化，每个算法采集了10组数据。其中，TSP旅程长度为屏幕上象素点之间的距离，时间为算法所消耗的CPU时间。30个城市的坐标如表5.1所示：对每个算法采集的数据，计算

23、其平均结果，表5.2中的所有数据都是经过10次测试得出的统计平均结果。表5.2 各种遗传操作组合求解TSP问题模拟实验结果比较算法最佳解时间(s)算法最佳解时间(s)GA02698.419.266GA62947.223.234GA12682.118.110GA72918.619.250GA22675.918.234GA82903.919.360GA32524.816.125GA92521.624.695GA42524.316.187GA102523.924.685GA52523.516.309GA112522.723.8565.3.3 实验结果分析 由表5.2可见：1.GA0与GA1与GA2以

24、及GA3与GA4与GA5，GA6与GA7与GA8，GA9与GA10与GA11的优化结果无大的差异，这说明变异算子在优化过程中所起的作用相对小一些。事实上，几种算法结果的相对一致性, 很大程度上是变异概率取的较小, 使变异在整个搜索过程中发生次数甚微造成的。这也符合自然进化的规律，毕竟，变异的发生概率是极其微小的。2.排除变异算子所带来的差异，只比较交叉算子可知，循环交叉算子的效果最差，这主要是因为经过循环之后，有可能到最后才完成循环。也就是说，循环了一周，子代和父代却没有大的改变。但由于进行了一系列循环，耗费了不少时间，因此，循环交叉所花费的时间也比较多。3.通过改进的交叉算子(循环贪心交叉)

25、和其它算子作比较可知，虽然改进的交叉算子所求的旅程长度有一定的改观，但耗费了不少时间。这主要是因为改进的交叉算子不但要循环，还要比较相邻城市之间的距离，并且所比较的城市都被扩展时，还要随机选择一个城市直到它不在所扩展的城市中或者所有的城市都被扩展，因此花费了大量的时间。因此对于改进的交叉算子不宜处理太多城市的TSP问题。4.总体来说，顺序交叉比较稳定，没有太多随机选择的情况，因此，对于多城市问题，不失为一种较理想的选择。5.4 改进算法与原算法的比较对于下面各比较算法，分别进行了计算机模拟实验，计算中采用的有关数据如下：城市数为30，群体规模为100，交叉概率为0.6，变异概率为0.2，群体更

26、新100代结束，采用强制进化方式进化，每个算法采集了10组数据。其中，TSP旅程长度为屏幕上象素点之间的距离，时间为算法所消耗的CPU时间。30个城市的坐标如表5.3所示：表5.3 30个城市坐标城市编号坐标城市编号坐标城市编号坐标1(87,7)11(58,69)21(4,50)2(91,83)12(54,62)22(13,40)3(83,46)13(51,67)23(18,40)4(71,44)14(37,84)24(24,42)5(64,60)15(41,94)25(25,38)6(68,58)16(2,99)26(41,26)7(83,69)17(7,64)27(45,21)8(87,7

27、6)18(22,60)28(44,35)9(74,78)19(25,62)29(58,35)10(71,71)10(18,54)30(62,32)5.4.1 改进循环交叉算法与循环交叉算法的数值比较 对于循环交叉测试的十组数据如下：时间(s)15.67214.82814.7814.76515.68816.84414.65015.84414.68715.954最优解684717705715692709669676689691 对于改进的循环交叉测试的十组数据如下：时间(s)11.96911.70312.32811.76512.18812.84411.25011.84410.48710.954最优

28、解615621640632609651603621630612对于循环交叉平均最优解为：694.7，平均时间为：15.3712s。对于改进循环交叉平均最优解为：623.4，平均时间为：11.7332s。通过对比可知，改进后的算法明显优于改进前的算法。5.4.2 改进循环贪心交叉算法与循环贪心交叉算法的数值比较对于改进的循环贪心交叉测试的十组数据如下：时间(s)12.68713.35912.9312.42212.50012.28112.93811.50012.85912.953最优解610616643644655643590699613617对于循环贪心交叉测试的十组数据如下：时间(s)14.2

29、5013.62514.75014.17213.75014.50013.40614.31213.98514.734最优解580614626594624651626570694586对于改进的循环贪心交叉平均最优解为：633.0，平均时间为：12.6429s。对于循环贪心交叉平均最优解为：616.5，平均时间为：14.1484s。通过对比可知，改进后的算法时间上明显优于改进前的算法。主要是减少了随机查找数据的时间，但由于改进后的算法是循环查找未扩展的城市，因此使得种群的多样性减少了，即使得平均最优解要比改进前差一些，但对于大量城市的TSP问题来说，节省时间是很值得考虑的。6 结论TSP是一个具有广

30、泛的应用背景和重要理论价值的组合优化问题，它已经被证明属NP难题。TSP搜索空间随着城市数的增加而增大，在庞大的空间中寻找最优解，对于现有的常规方法和现有的计算工具而言，存在着诸多的困难。借助遗传算法的搜索能力解决TSP问题是很自然的想法。本设计在深入分析和研究遗传算法基本理论与方法的基础上，不但编程实现了国内外专家提出的一些优秀的算法，而且结合具体的编程情况，对其中的一些算法作了必要的改进。最后，本设计对各种算法的组合进行了实验，并且对各种算法结果进行了比较和分析。在本文研究基础上，还可以进一步开拓以下几个方向的研究工作:1.将遗传算法运用于大规模的旅行商问题；2.将许多实际应用问题(如印制

31、电路板的钻孔路线方案、连锁店的货物陪送路线等)建模为TSP问题，并应用遗传算法来解决；3.如何获得更好的性能是遗传算法研究中的重要课题。如何在保证求解质量的同时降低时间的开销，如何针对具体问题寻找优化的并行计算策略和群体划分策略，也是遗传算法中需要进一步深入研究的重要课题。遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，需要进一步地发展和完善，但它已为解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用过程中会出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和

32、方法运用于自己的专业领域中。随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键的作用。程序核心代码一资源类1.头文件/NO_DEPENDENCIES/ Microsoft Developer Studio generated include file./ Used by resource.rc#define IDDefault 3#define IDR_MENU1 101#define IDI_ICON1 104#define IDD_GA_BOX 105#define IDD_HELP_BOX 106#define IDD_SETCITY 107#define IDC_ED

33、IT2 1002#define IDC_EDIT3 1003#define IDC_EDIT4 1004#define IDC_EDIT6 1008#define IDC_RADIO1 1019#define IDC_RADIO2 1020#define IDI_TSP 1022#define IDC_ICON1 1023#define IDC_ICON2 1023#define IDC_CITYNUMBER 1025#define ID_GA_SET 40012#define ID_DefaultMap 40020#define ID_RoundMap 40021#define ID_CUS

34、TOMMAP 40023#define ID_HELP_BOX 40024#define ID_GASET 40026#define ID_END 40027#define ID_EXIT 40028#define ID_ORDER_MUTATION 40030#define ID_POSITION_MUTATION 40031#define ID_REVERSE_MUTATION 40032#define ID_PARTIALLY_MATCHED_CROSSOVER 40033#define ID_ORDER_CROSSOVER 40034#define ID_CYCLE_CROSSOVER

35、 40035#define ID_SET_CITY 40036#define ID_GREED_CROSSOVER 40037#define ID_FIXED_CITY 40038/ Next default values for new objects#ifdef APSTUDIO_INVOKED#ifndef APSTUDIO_READONLY_SYMBOLS#define _APS_NEXT_RESOURCE_VALUE 108#define _APS_NEXT_COMMAND_VALUE 40039#define _APS_NEXT_CONTROL_VALUE 1027#define

36、_APS_NEXT_SYMED_VALUE 101#endif#endif二头文件类1.头文件/head.h/#pragma once#include #include #include #include #include #include #include #include #include #include #include #include#include using namespace std;/命名空间三地图类1.头文件/map.h/#pragma once#include head.h/MapControl控制地图以及左右键点击后对的处理/class Map public: vir

37、tual void DrawMap(HWND hwnd,HDC hdc)=0;/画地图 / virtual void SaveClickPoint()=0;/保存格式为地图中的位置 virtual void DelAllPoint()=0;/清除vecpoin所有点 /在地图上画点（参数为实际位置）virtual void DrawPonit(HWND hwnd,const POINT&)=0; /将地图上已存在的点（参数为实际位置）删除virtual void SmearPonit(HWND hwnd,const POINT&)=0;/保存POINT(参数为实际位置)到向量 virtual

38、void AddPoint(const POINT&)=0;/删除POINT(参数为实际位置)到向量 virtual void SubPoint(const POINT&)=0; /获得所有已点击的点的位置(实际值) virtual vector GetAllClickPoint( )=0;protected: POINT beginpoint;/实际位置 vector vecpoint;/地图中的位置/函数对象/class equal_point public: equal_point() equal_point(const POINT& _val):val(_val) bool opera

39、tor()(const POINT& point) return (point.x=val.x)&(point.y=val.y); bool operator()(const POINT& point1,const POINT& point2) return (point1.x=point2.x)&(point1.y=point2.y); private: POINT val;四直角坐标地图类1.头文件/defaultmap.h/#pragma once#include map.h#define DIVISIONS1 10 #define DIVISIONS2 6class DefaultMap:public Map public: void DrawMap(HWND hwnd,HDC hdc);/画地图 /void SaveClickPoint( );/保