还剩74页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
TSP问题的遗传算法求解方案算法的软件实现
4.1开发环境介绍本文中的所有算法是在VisualC++
6.0的操作平台上进行开发的，并结合STL进行编程
1、VisualC++
6.0简介VisualC++
6.0是微软公司最新出品的功能最为强大的可视化开放工具，是计算机界公认的最优秀的应用开发工具之一Microsoft的基本类库使得开发Windows应用程序比以往任何时候都要容易VisualC++作为一种程序设计语言，它同时也是一个集成开发工具，提供了软件代码自动生成和可视化的资源编辑功能
2、VisualC++
6.0的优势
1.拥有强大的编辑环境
2.拥有强大的类库的支持
3.拥有强大的调试环境
4.拥有较强的低层控制能力
5.拥有强大的帮助系统MSDN的支持
6.拥有一个高效的编译器，产生的可执行文件体积小巧、运行速度快
3、STL简介STL（StandardTemplateLibrary），即标准模板库，是一个具有工业强度的，高效的C++程序库它被容纳于C++标准程序库（C++StandardLibrary）中，是ANSI/ISOC++标准中最新的也是极具革命性的一部分该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性这种现象有些类似于MicrosoftVisualC++中的MFC（MicrosoftFoundationClassLibrary），或者是BorlandC++Builder中的VCLVisualComponentLibrary，但是它比二者具有更强的优势更加值得一提的是，它具备以下几个区别于其它软件库的优点
1.经过类属编程方法精心组织的，可互换的编程模块能够提供比传统组件设是否世代进化图
4.1遗传算法解TSP的具体流程图计方法丰富得多的组合方式
2.类属编程方法设计也是将来为数据库，用户界面等专业领域开发组件的基础
3.通过使用某些编译机制并根据不同的算法进行具体的设计，可以在不损失效率的情况下实现对组件的概括与此形成鲜明对照的是，其它一些具有复杂继承层次和大量使用虚函数的C++库结构则通常会降低效率
4.2算法实现的流程图本设计的具体流程图如图
4.1所示
4.3算法的各个模块及其详细设计思路1．城市生成模块用户可以点击鼠标左键产生城市，也可以选择菜单栏的设置城市选项，通过输入城市数目来随机生成城市当然，如果用户选择错了城市，可以在该城市上点击鼠标右键来清除城市如果用户要清除所有的城市，可以双击鼠标右键或选择菜单栏的结束选项，都可以清除所有的城市其设计设计思路如图
4.2所示按下鼠标左键按下鼠标右键选择菜单栏的设置城市选项选择菜单栏的结束选项图
4.2城市生成模块的设计思路最后的效果如图
4.3所示图
4.3TSP问题城市设置实现效果
2.地图选择模块根据具体的需要，用户可以选择不同的地图，本设计提供的地图有基于直角坐标系的地图和圆形地图，这两个地图由不同的类来产生其中类DefaultMap产生直角坐标地图，类RoundMap产生圆形地图图
4.4所示的是直角坐标地图，图
4.5所示的是圆形地图图
4.4直角坐标地图图
4.5圆形地图
3.遗传算法解TSP的参数设置模块在具体的应用中，用户可以根据具体情况来设置遗传算法的相关参数，这些参数包括交叉率控制程序进行交叉的次数，在本设计中，先随机生成一个数，如果这个数大于交叉率，则不交叉，如果这个数小于交叉率，则进行交叉具体实现如下pick=floatrandomInt01000/1000;ifpickpcross{//进行交叉操作}else//不进行交叉操作变异率控制程序进行变异的次数，在本设计中，先随机生成一个数，如果这个数大于变异率，则不变异，如果这个数小于变异率，则进行变异操作具体实现如下pick=floatrandomInt01000/1000;ifpickpmutation{//进行变异操作}else//不进行变异操作种群大小即种群中所含有的个体数量，选择一个合理的种群值，不但会使得群体的多样性增强，防止遗传算法的“早熟现象”，还会使得遗传操作收敛得更快世代数控制遗传操作世代进化的次数，合理的世代数能够使得计算结果的优劣程度不同图
4.6遗传算法解TSP的参数设置进化设置根据子染色体与父染色体的关系，进化设置又分为两种·普通进化完全模仿自然进化，子染色体可能比父染色体优秀，也可能比父染色体差·强制进化选取子染色体中比父染色体优秀的染色体，杀死子染色体中比父染色体差的染色体使得进化一直朝着优秀染色体的方向进化具体的实现效果如图
4.6所示
4.交叉算子选择模块交叉操作是遗传算法中最重要的一环，交叉算法的优劣将最大限度地影响遗传算法的结果本设计先根据国外专家提出的解TSP的几种经典算法，然后编程将其实现，并在此基础上，提出一种改进的交叉算法在具体的应用中，用户可以根据自己的需要，选择最符合实际情况的交叉算法程序的具体选择模块如下//交叉算子的选择模块inlinevoidCGA::crossoverChromparent1Chromparent2Chromchild1Chromchild2{switchTempCrossoverStyle{caseID_PARTIALLY_MATCHED_CROSSOVER://部分匹配交叉{partially_matched_crossoverparent1parent2child1child2;}break;caseID_ORDER_CROSSOVER://顺序交叉{order_crossoverparent1parent2child1child2;}break;caseID_CYCLE_CROSSOVER://循环交叉{cycle_crossoverparent1parent2child1child2;}break;caseID_GREED_CROSSOVER://循环贪心交叉{greed_crossoverparent1parent2child1child2;}break;default:break;}}
5.变异算子选择模块求解TSP时，变异算子的设计比交叉算子的设计灵活，任何具有局部搜索能力的算子都可以作为它的变异算子本设计实现了三种变异基于次序的变异，基于位置的变异，倒位变异程序的具体选择模块如下//变异算子选择模块inlinevoidCGA::mutationChromchr{switchTempMutationStyle{caseID_ORDER_MUTATION://基于次序的变异{order_oriented_mutationchr;}break;caseID_POSITION_MUTATION://基于位置的变异{position_oriented_mutationchr;}break;caseID_REVERSE_MUTATION://倒位变异{reverse_mutationchr;}break;default:break;}}
6.具体输出信息显示模块为了使程序运行时具体的算法和各种数据信息更加明确化，增加了信息显示模块，这样，在程序运行时用户可以掌握具体的数据信息，以便对各种算法进行比较信息显示模块包括计算结果模块，算法运行时间模块，所选遗传算子模块下面分别对各个显示模块进行讨论计算结果模块输出的信息包括当前鼠标的横坐标，当前鼠标的纵坐标，这两个信息是为了用户设置城市时参考的城市总数信息是用户设置的城市数目总距离信息是经过计算的TSP问题的最优路径长度，它是屏幕上象素点间的距离算法运行时间模块包括算法启动前时间，它是用户设置完城市，进行求解时刻的时间；算法结束时间，它是程序运行完成，正确输出TSP结果时刻的时间；算法耗费时间，它是进行遗传算法求解TSP时算法所消耗的时间所选遗传算子模块它显示的是用户选择了那种交叉算子，那种遗传算子，以便于对各种算法比较时使用具体的显示如图
4.7所示图
4.7各种信息显示图
4.4设计中主要的类和函数的功能
1.Map类，DefaultMap类，RoundMap类这三个类均为画图相关的类，其继承关系为继承基类继承图
4.8画图类继承关系其中，DefaultMap类主要是与直角坐标地图有关，RoundMap类主要是与圆形地图有关这些类提供了画地图函数DrawMap，保存地图中的位置函数SaveClickPoint，清除点向量中所有城市点的函数DelAllPoint，在地图上画点的函数DrawPonit，将地图上已存在的点删除函数SmearPonit等等
2.CGA类这个类主要是为遗传算法设置的，在这个类中定义了基因结构体代表一个城市，染色体结构体代表到各城市去的一种组合，还定义了种群结构体表示各种不同基因的组合这个类主要是进行遗传算法操作的，包括各种进化运算，即选择，交叉，变异等等这个类中的主要函数有遗传算法参数设置函数preSet，遗传算法启动函数start，交叉类型选择函数SetCrossoverStyle，变异类型选择函数Set-MutationStyle，世代进化函数generation，染色体适应度计算函数chromCost，种群个体适应度计算函数popCost，初始化染色体函数initChrom，初始化种群函数initpop，轮盘赌选择函数selectChrom等等
3.Control类Control类主要是对程序进行控制的，它为各个模块的组合提供了接口，并且将必要的数据信息在屏幕上输出它提供的函数主要有欢迎窗口显示函数welcome，遗传算法接口函数SetGaInformation，信息显示函数DisPlay等等
4.Line类Line类主要是计算TSP问题的具体操作，包括对城市点构成矩阵的设置，计算城市点之间的距离，画线，保存城市点的矩阵信息，计算最终结果等
5.main.cpp这是一个主程序文件，是整个程序启动，操作的主控文件是整个程序的框架部分此外，程序还有头文件类，资源类等等这里就不详细介绍，具体的源程序见程序文档5软件测试及实验结果分析
5.1软件测试以下是软件测试的步骤
1.运行程序后，弹出欢迎消息，如图
5.1所示图
5.1遗传算法解TSP问题欢迎窗口
2.点击确定，进入主程序模块，点击选择地图，可以选择直角坐标地图和圆形地图，默认地图为直角坐标地图，下面的演示以直角坐标地图为主，如图
5.2所示图
5.2遗传算法解TSP问题直角坐标演示地图
3.在屏幕上点击鼠标左键可设置城市，也可以点击菜单栏设置城市，弹出设置城市数目对话框，在对话框中输入城市数目，可以在屏幕上随机生成城市，具体情况如图
5.3，
5.4所示图
5.3设置城市数目图
5.4设置城市
4.点击菜单栏遗传算法设置按钮，弹出遗传算法参数设置对话框，如图
5.5所示图
5.5遗传算法参数设置对话框在遗传算法参数设置对话框中，可以设置交叉率，变异率，种群大小，世代数以及选择进化设置等
5.点击菜单栏交叉类型按钮，可以选择交叉算法，如图
5.6所示图
5.6交叉类型选择可供选择的交叉类型有部分匹配交叉，顺序交叉，循环交叉，循环贪心交叉
6.点击菜单栏变异类型按钮，可以选择变异算法，如图
5.7所示，可供选择的变异类型有基于次序的变异，基于位置的变异，倒位变异图
5.7变异类型选择7．然后点击菜单栏开始，则进行计算，最终结果如图
5.8所示图
5.8遗传算法解TSP问题计算结果
8.点击菜单栏结束可以清除所有点，点击帮助，可以弹出帮助文件至于圆形地图的测试过程与直角坐标地图相似
5.2算法的正确性验证为了测试算法的正确性，我使用了固定城市测试模块，该模块中的城市坐标，城市大小可以预先设置其中，城市的数目，坐标和最优解均可以参照国内外专家的文献，然后对比本程序计算的结果如图
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]的部分匹配交叉数据，平均最优解为
517.0，平均时间为
31.2s对比可知，本设计的算法符合要求由于本设计使用的是强制进化方式，所以平均最优解和平均时间均有一定的改进
5.3模拟实验结果与分析
5.
3.1不同遗传操作组合的算法为了考察遗传算法组合优化在求解TSP问题中的重要性本文进行了多种遗传操作组合的模拟实验，各种遗传操作组合成的算法如下:GA0部分匹配交叉+基于次序的变异GA1部分匹配交叉+基于位置的变异GA2部分匹配交叉+倒位变异GA3顺序交叉+基于次序的变异GA4顺序交叉+基于位置的变异GA5顺序交叉+倒位变异GA6循环交叉+基于次序的变异GA7循环交叉+基于位置的变异GA8循环交叉+倒位变异GA9循环贪心交叉+基于次序的变异GA10循环贪心交叉+基于位置的变异GA11循环贪心交叉+倒位变异表
5.130个城市位置坐标城市编号坐标城市编号坐标城市编号坐标
140406111903232122902333912401152225219232681831329120123172434277377146202352444015053611031511715425252147610441654630526346343718026177019727461416816070184681712843625891941811946625829322801062639510234233302283575.
3.2模拟实验结果对于上述各算法，分别进行了计算机模拟实验，计算中采用的有关数据如下城市数为30，群体规模为100，交叉概率为
0.8，变异概率为
0.1，群体更新100代结束，采用强制进化方式进化，每个算法采集了10组数据其中，TSP旅程长度为屏幕上象素点之间的距离，时间为算法所消耗的CPU时间30个城市的坐标如表
5.1所示对每个算法采集的数据，计算其平均结果，表
5.2中的所有数据都是经过10次测试得出的统计平均结果表
5.2各种遗传操作组合求解TSP问题模拟实验结果比较算法最佳解时间s算法最佳解时间sGA
02698.
419.266GA
62947.
223.234GA
12682.
118.110GA
72918.
619.250GA
22675.
918.234GA
82903.
919.360GA
32524.
816.125GA
92521.
624.695GA
42524.
316.187GA
102523.
924.685GA
52523.
516.309GA
112522.
723.
8565.
3.3实验结果分析由表
5.2可见
1.GA0与GA1与GA2以及GA3与GA4与GA5，GA6与GA7与GA8，GA9与GA10与GA11的优化结果无大的差异，这说明变异算子在优化过程中所起的作用相对小一些事实上，几种算法结果的相对一致性很大程度上是变异概率取的较小使变异在整个搜索过程中发生次数甚微造成的这也符合自然进化的规律，毕竟，变异的发生概率是极其微小的
2.排除变异算子所带来的差异，只比较交叉算子可知，循环交叉算子的效果最差，这主要是因为经过循环之后，有可能到最后才完成循环也就是说，循环了一周，子代和父代却没有大的改变但由于进行了一系列循环，耗费了不少时间，因此，循环交叉所花费的时间也比较多
3.通过改进的交叉算子循环贪心交叉和其它算子作比较可知，虽然改进的交叉算子所求的旅程长度有一定的改观，但耗费了不少时间这主要是因为改进的交叉算子不但要循环，还要比较相邻城市之间的距离，并且所比较的城市都被扩展时，还要随机选择一个城市直到它不在所扩展的城市中或者所有的城市都被扩展，因此花费了大量的时间因此对于改进的交叉算子不宜处理太多城市的TSP问题
4.总体来说，顺序交叉比较稳定，没有太多随机选择的情况，因此，对于多城市问题，不失为一种较理想的选择
5.4改进算法与原算法的比较对于下面各比较算法，分别进行了计算机模拟实验，计算中采用的有关数据如下城市数为30，群体规模为100，交叉概率为
0.6，变异概率为
0.2，群体更新100代结束，采用强制进化方式进化，每个算法采集了10组数据其中，TSP旅程长度为屏幕上象素点之间的距离，时间为算法所消耗的CPU时间30个城市的坐标如表
5.3所示表
5.330个城市坐标城市编号坐标城市编号坐标城市编号坐标
187711586921450291831254622213403834613516723184047144143784242442564601541942525386685816299264126783691776427452188776182260284435974781925622958351071711018543062325.
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最优解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.
25013.
62514.
75014.
17213.
75014.
50013.
40614.
31213.
98514.734最优解580614626594624651626570694586对于改进的循环贪心交叉平均最优解为
633.0，平均时间为
12.6429s对于循环贪心交叉平均最优解为
616.5，平均时间为
14.1484s通过对比可知，改进后的算法时间上明显优于改进前的算法主要是减少了随机查找数据的时间，但由于改进后的算法是循环查找未扩展的城市，因此使得种群的多样性减少了，即使得平均最优解要比改进前差一些，但对于大量城市的TSP问题来说，节省时间是很值得考虑的6结论TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题，它已经被证明属NP难题TSP搜索空间随着城市数的增加而增大，在庞大的空间中寻找最优解，对于现有的常规方法和现有的计算工具而言，存在着诸多的困难借助遗传算法的搜索能力解决TSP问题是很自然的想法本设计在深入分析和研究遗传算法基本理论与方法的基础上，不但编程实现了国内外专家提出的一些优秀的算法，而且结合具体的编程情况，对其中的一些算法作了必要的改进最后，本设计对各种算法的组合进行了实验，并且对各种算法结果进行了比较和分析在本文研究基础上，还可以进一步开拓以下几个方向的研究工作:
1.将遗传算法运用于大规模的旅行商问题；
2.将许多实际应用问题如印制电路板的钻孔路线方案、连锁店的货物陪送路线等建模为TSP问题，并应用遗传算法来解决；
3.如何获得更好的性能是遗传算法研究中的重要课题如何在保证求解质量的同时降低时间的开销，如何针对具体问题寻找优化的并行计算策略和群体划分策略，也是遗传算法中需要进一步深入研究的重要课题遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，需要进一步地发展和完善，但它已为解决许多复杂问题提供了希望尽管在遗传算法的研究和应用过程中会出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的专业领域中随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键的作用程序核心代码一．资源类
1.头文件//{{NO_DEPENDENCIES}}//MicrosoftDeveloperStudiogeneratedincludefile.//Usedbyresource.rc#defineIDDefault3#defineIDR_MENU1101#defineIDI_ICON1104#defineIDD_GA_BOX105#defineIDD_HELP_BOX106#defineIDD_SETCITY107#defineIDC_EDIT21002#defineIDC_EDIT31003#defineIDC_EDIT41004#defineIDC_EDIT61008#defineIDC_RADIO11019#defineIDC_RADIO21020#defineIDI_TSP1022#defineIDC_ICON11023#defineIDC_ICON21023#defineIDC_CITYNUMBER1025#defineID_GA_SET40012#defineID_DefaultMap40020#defineID_RoundMap40021#defineID_CUSTOMMAP40023#defineID_HELP_BOX40024#defineID_GASET40026#defineID_END40027#defineID_EXIT40028#defineID_ORDER_MUTATION40030#defineID_POSITION_MUTATION40031#defineID_REVERSE_MUTATION40032#defineID_PARTIALLY_MATCHED_CROSSOVER40033#defineID_ORDER_CROSSOVER40034#defineID_CYCLE_CROSSOVER40035#defineID_SET_CITY40036#defineID_GREED_CROSSOVER40037#defineID_FIXED_CITY40038//Nextdefaultvaluesfornewobjects//#ifdefAPSTUDIO_INVOKED#ifndefAPSTUDIO_READONLY_SYMBOLS#define_APS_NEXT_RESOURCE_VALUE108#define_APS_NEXT_COMMAND_VALUE40039#define_APS_NEXT_CONTROL_VALUE1027#define_APS_NEXT_SYMED_VALUE101#endif#endif二．头文件类
1.头文件///////////head.h////////////////////////////////////////////////////////////#pragmaonce#includewindows.h#includewindowsx.h#includestdio.h#includemath.h#includeutility#includevector#includestdlib.h#includeiostream#includefstream#includeiomanip#includealgorithm#includemap#includectimeusingnamespacestd;//命名空间/////////////////////////////////////////////////////////////////////////////三．地图类
1.头文件////////////////map.h////////////////////////////////////////////////////////#pragmaonce#includehead.h//////////////////MapControl控制地图以及左右键点击后对的处理///////////////classMap{public:virtualvoidDrawMapHWNDhwndHDChdc=0;//画地图//virtualvoidSaveClickPoint=0;//保存格式为地图中的位置virtualvoidDelAllPoint=0;//清除vecpoin所有点//在地图上画点（参数为实际位置）virtualvoidDrawPonitHWNDhwndconstPOINT=0;//将地图上已存在的点（参数为实际位置）删除virtualvoidSmearPonitHWNDhwndconstPOINT=0;//保存POINT参数为实际位置到向量virtualvoidAddPointconstPOINT=0;//删除POINT参数为实际位置到向量virtualvoidSubPointconstPOINT=0;//获得所有已点击的点的位置实际值virtualvectorPOINTGetAllClickPoint=0;protected:POINTbeginpoint;//实际位置vectorPOINTvecpoint;//地图中的位置};///////////////////函数对象//////////////////////////////////////////////////classequal_point{public:equal_point{}equal_pointconstPOINT_val:val_val{}booloperatorconstPOINTpoint{returnpoint.x==val.xpoint.y==val.y;}booloperatorconstPOINTpoint1constPOINTpoint2{returnpoint
1.x==point
2.xpoint
1.y==point
2.y;}private:POINTval;};/////////////////////////////////////////////////////////////////////////////四．直角坐标地图类
1.头文件///////////////defaultmap.h//////////////////////////////////////////////////#pragmaonce#includemap.h#defineDIVISIONS110#defineDIVISIONS26classDefaultMap:publicMap{public:voidDrawMapHWNDhwndHDChdc;//画地图//voidSaveClickPoint;//保存格式为地图中的位置voidDelAllPoint;//清除vecpoin所有点//在地图上画点参数为实际位置voidDrawPonitHWNDhwndconstPOINT;//将地图上已存在的点参数为实际位置删除voidSmearPonitHWNDhwndconstPOINT;voidAddPointconstPOINT;//保存POINT参数为实际位置到向量voidSubPointconstPOINT;//删除POINT参数为实际位置到向量//获得所有已点击的点的位置实际值vectorPOINTGetAllClickPoint;POINTGetMapPointconstPOINTpoint;//实际POINT在地图位置POINTGetRealPointconstPOINTpoint;//地图POINT实际位置protected://找到该点附近的像素点iarea为该点的半径vectorPOINTFindAroundPointconstPOINTpointintiarea;};/////////////////////////////////////////////////////////////////////////////
2.源文件//////////////////////////defaultmap.cpp/////////////////////////////////////#includedefaultmap.h/////////////////////画地图//////////////////////////////////////////////////voidDefaultMap::DrawMapHWNDhwndHDChdc{HPENhpen;hpen=CreatePenPS_SOLID1RGB0128128;///创建画笔SelectObjecthdchpen;forintx=0;xDIVISIONS1;x++//10forinty=0;yDIVISIONS2;y++//6{Rectanglehdc5+x*7050+y*705+x+1*7050+y+1*70;}DeleteObjecthpen;//删除画笔return;}///////////////////////////////////////////////////////////////////////////////////////////////////保存删除POINT在地图位置到向量/////////////////////////*voidDefaultMap::SaveClickPoint{fstreamoutFilecopy.textios_base::out;//以写方式打开文件if!outFile{cerrunabletoopeninputfile:--bailingout!\n;return;}ifvecpoint.size=0{return;}outFile#DEFAULT_MAP_NAME\n;///以后有用outFile#vecpoint.size\n;forintn=0;nvecpoint.size;n++{outFilevecpoint[n].x;outFile;outFilevecpoint[n].y;outFile\n;}return;}*///////////////////////////////////////////////////////////////////////////////////////////////删除所有点//////////////////////////////////////////////////voidDefaultMap::DelAllPoint{ifvecpoint.size=0{return;}vecpoint.clear;return;}//////////////////////////////////////////////////////////////////////////////////////////////////找到该点附近的点////////////////////////////////////////vectorPOINTDefaultMap::FindAroundPointconstPOINTpointintiarea{//iarea为该点的半径POINTtemppoint;vectorPOINTvecroundpoint;temppoint.x=point.x-6;//判断点是否在有效区域//-51temppoint.y=point.y-51;//-51iftemppoint.x0||temppoint.y0||temppoint.x700||temppoint.y420{returnvecroundpoint;}iarea=absiarea;//防止iarea小于零forintn=-iarea;n1+iarea;n++forintm=iarea;m-1-iarea;m--{temppoint.x=point.x+m;temppoint.y=point.y+n;vecroundpoint.push_backtemppoint;temppoint.x=point.x+n;temppoint.y=point.y+m;vecroundpoint.push_backtemppoint;}returnvecroundpoint;}////////////////////////////////////////////////////////////////////////////////////在地图上画点/////在地图上画点参数为实际位置/////////////////////////voidDefaultMap::DrawPonitHWNDhwndconstPOINTpoint{intcx=point.x-6;//判断点是否在有效区域intcy=point.y-51;ifcx0||cy0||cx700||cy420{return;}AddPointpoint;HDChdc;hdc=GetDChwnd;HPENhpen;hpen=CreatePenPS_DOT5RGB25500;SelectObjecthdchpen;//选择对象进DCEllipsehdcpoint.x+2point.y+2point.x-2point.y-2;////画圆点DeleteObjecthpen;ReleaseDChwndhdc;return;}////////////////////////////////////////////////////////////////////////////////////添加和减少点在地图位置到向量/////保存POINT参数为实际位置到向量////voidDefaultMap::AddPointconstPOINTpoint{POINTtempoint=point;ifvecpoint.size!=0find_ifvecpoint.beginvecpoint.endequal_pointtempoint!=vecpoint.end{return;}//保证点不重复vecpoint.push_backtempoint;}///////////////////////////////////////////////////////////////////////////////////////////清除一个指定的点///////////////////////////////////////////////voidDefaultMap::SubPointconstPOINTpoint{ifvecpoint.size=0{return;}vectorPOINTvecroundpoint;vectorPOINT::iteratorIter1;vecroundpoint=FindAroundPointpoint2;//获得该点附近的像素点ifvecroundpoint.size==0{return;}Iter1=find_first_ofvecpoint.beginvecpoint.endvecroundpoint.beginvecroundpoint.endequal_point;ifIter1==vecpoint.end{return;}vecpoint.eraseIter1;}////////////////////////////////////////////////////////////////////////////////将地图上已存在的点参数为实际位置删除//擦掉该点重画所有的点和地图//////voidDefaultMap::SmearPonitHWNDhwndconstPOINTpoint{HDChdc;hdc=GetDChwnd;intn=vecpoint.size;SubPointpoint;ifn==vecpoint.size//没找到则向量大小不变{return;}DrawMaphwndhdc;ReleaseDChwndhdc;forn=0;nvecpoint.size;n++///重画所有的点和地图{DrawPonithwndvecpoint[n];}return;}/////////////////////////////////////////////////////////////////////////////////////////////////获得所有已点击的点的位置/////////////////////////////////vectorPOINTDefaultMap::GetAllClickPoint{returnvecpoint;}////////////////////////////////////////////////////////////////////////////////////////////////将地图与实际位置之间转换//////////////////////////////////POINTDefaultMap::GetRealPointconstPOINTpoint//实际位置转换为地图位置{POINTtemppoint;temppoint.x=point.x-6;temppoint.y=point.y-51;//判断点是否在有效区域iftemppoint.x0||temppoint.y0||temppoint.x700||temppoint.y420{temppoint.x=-1;temppoint.y=-1;returntemppoint;}temppoint.x+=6;temppoint.y+=51;returntemppoint;}//////////////////////////////////////////////////////////////////////////////////地图位置转换为实际位置//////////////////////////////////////////////////POINTDefaultMap::GetMapPointconstPOINTpoint{POINTtemppoint=point;temppoint.x-=6;temppoint.y-=51;iftemppoint.x0||temppoint.y0||700temppoint.x||420temppoint.y{temppoint.x=-1;//点在无效区域temppoint.y=-1;returntemppoint;}returntemppoint;//点在有效区域}/////////////////////////////////////////////////////////////////////////////五．圆形坐标地图类
1.头文件//////////////////roundmap.h/////////////////////////////////////////////////#pragmaonce#includemap.hclassRoundMap:publicMap{public:RoundMap;voidDrawMapHWNDhwndHDChdc;//画地图POINTFindAroundPointconstPOINT;//voidSaveClickPoint;//保存格式为地图中的位置voidDelAllPoint;//清除vecpoin所有点//在地图上画点参数为实际位置voidDrawPonitHWNDhwndconstPOINT;//将地图上已存在的点参数为实际位置删除voidSmearPonitHWNDhwndconstPOINT;voidAddPointconstPOINT;//保存POINT参数为实际位置到向量voidSubPointconstPOINT;//删除POINT参数为实际位置到向量vectorPOINTGetAllClickPoint;//获得所有已点击的点的位置实际值protected:vectorPOINTmappoint;};/////////////////////////////////////////////////////////////////////////////
2.源文件///////////////////////////////////roundmap.cpp//////////////////////////////#includeroundmap.h///////圆形地图//////////////////////////////////////////////////////////////RoundMap::RoundMap{//doinitializationstuffherevectorPOINTpoint6060;intiallpoint
[120]={305-21324-23344-23365-19384-13402-64214437164542846841482574937450393509113515132518152520173518193514214510233501254493271481287468304456318439329422342284-16263-12246-42253210171942817842166561567414593137112133131129153127173128195132213137233146255155272165290180307194318208331227343244352265360282365303366326369343368368365385360404353};forintn=0;n60;n++{point60[n].x=iallpoint[2*n];point60[n].y=iallpoint[2*n+1];}forn=0;n60;n++{point60[n].x=point60[n].x+21;point60[n].y=point60[n].y+81;}mappoint=point60;}///////////////////////////////////////////////////////////////////////////////////////////////////画地图/////////////////////////////////////////////////voidRoundMap::DrawMapHWNDhwndHDChdc////n表示线的条数{RECTrect;rect.bottom=450;/////无效区域（背景区域）rect.left=100;rect.right=740;rect.top=0;HBRUSHhbrush;//擦除背景区域hbrush=CreateSolidBrushRGB255255255;FillRecthdcrecthbrush;SelectObjecthdcGetStockObjectBLACK_PEN;forintn=0;n60;n++{Ellipsehdcmappoint[n].x-5mappoint[n].y-5mappoint[n].x+5mappoint[n].y+5;}}//////////////////////保存删除POINT（在地图位置到向量////////////////////////*voidRoundMap::SaveClickPoint{fstreamoutFilecopy.textios_base::out;if!outFile{cerrunabletoopeninputfile:--bailingout!\n;return;}ifvecpoint.size=0{return;}outFile#Round_Map_NAME\n;///以后有用outFile#vecpoint.size\n;forintn=0;nvecpoint.size;n++{outFilevecpoint[n].x;outFile;outFilevecpoint[n].y;outFile\n;}return;}*//////////////////////////////////////////////////////////////////////////////////////////删除所有的点/////////////////////////////////////////////////////voidRoundMap::DelAllPoint{ifvecpoint.size=0{return;}vecpoint.clear;return;}/////////////////////////////////////////////////////////////////////////////////////////////找到该点是否有所在区域的值///////////////////////////////////POINTRoundMap::FindAroundPointconstPOINTpoint{vectorPOINTvecroundpoint;POINTtemppoint;vectorPOINT::iteratorIter;forintn=-3;n4;n++forintm=3;m-4;m--{temppoint.x=point.x+m;temppoint.y=point.y+n;vecroundpoint.push_backtemppoint;//获得该点附近的点temppoint.x=point.x+n;temppoint.y=point.y+m;vecroundpoint.push_backtemppoint;//获得该点附近的点}Iter=find_first_ofmappoint.beginmappoint.endvecroundpoint.beginvecroundpoint.endequal_point;ifIter==mappoint.end{temppoint.x=-1;temppoint.y=-1;returntemppoint;}return*Iter;}//////////////////////////////////////////////////////////////////////////////////////////////在地图上画点或将地点上以存在的点从地图上删除////////////////voidRoundMap::DrawPonitHWNDhwndconstPOINTpoint{//在地图上画点参数为实际位置//HDChdc;POINTtemppointDrawpoint;temppoint.x=-1;temppoint.y=-1;Drawpoint=FindAroundPointpoint;ifDrawpoint.x==temppoint.xDrawpoint.y==temppoint.y{return;}AddPointpoint;hdc=GetDChwnd;HBRUSHhbrush=CreateSolidBrushRGB25500;SelectObjecthdchbrush;EllipsehdcDrawpoint.x-5Drawpoint.y-5Drawpoint.x+5Drawpoint.y+5;DeleteObjecthbrush;ReleaseDChwndhdc;}/////////////////////////////////////////////////////////////////////////////////////将地图上已存在的点（参数为实际位置）重画/////////////////////////////voidRoundMap::SmearPonitHWNDhwndconstPOINTpoint{intn=vecpoint.size;SubPointpoint;ifn==vecpoint.size//在其他地区60个之外点击右键则向量大小不变{return;}forn=0;nvecpoint.size;n++///重画所有的点和地图{DrawPonithwndvecpoint[n];}//1return;}////////////////////////////////////////////////////////////////////////////////////////////////添加和减少点（在地图位置到向量//////////////////////////voidRoundMap::AddPointconstPOINTpoint//保存POINT参数为实际位置到向量{POINTtemppointDrawpoint;temppoint.x=-1;temppoint.y=-1;Drawpoint=FindAroundPointpoint;ifDrawpoint.x==temppoint.x//表示未找到点{return;}iffind_ifvecpoint.beginvecpoint.endequal_pointDrawpoint!=vecpoint.end{return;}//保证点不重复vecpoint.push_backDrawpoint;}///////////////////////////////////////////////////////////////////////////////////////删除点/////////////////////////////////////////////////////////////voidRoundMap::SubPointconstPOINTpoint{POINTtemppointDrawpoint;vectorPOINT::iteratorIter;temppoint.x=-1;temppoint.y=-1;Drawpoint=FindAroundPointpoint;ifDrawpoint.x==temppoint.x{return;}Iter=remove_ifvecpoint.beginvecpoint.endequal_pointDrawpoint;ifIter==vecpoint.end{return;}vecpoint.eraseIter;}/////////////////////////////////////////////////////////////////////////////////////////////////获得所有已点击的点的位置/////////////////////////////////vectorPOINTRoundMap::GetAllClickPoint{returnvecpoint;}/////////////////////////////////////////////////////////////////////////////六．控制类
1.头文件/////////////control.h///////////////////////////////////////////////////////#pragmaonce#includehead.h#includemap.h#includedefaultmap.h#includeroundmap.h#includeconnectline.h#includega.h#includeresource.h//算法启动前时间externWORDbeforehourtime;externWORDbeforeminutetime;externWORDbeforesecondtime;externWORDbeforemillisecondtime;//算法结束时的时间externWORDafterhourtime;externWORDafterminutetime;externWORDaftersecondtime;externWORDaftermillisecondtime;externUINTDrawMutationStyle;//进化类型externUINTDrawCrossoverStyle;//交叉类型classControl{public:Control;//初始化数据voidwelcomeHWNDhwnd;//显示欢迎窗口开始//voidhelpHWNDhwnd;//完整的帮助UINTGetMapStyle;//获得当前地图类型voidSetMapStyleHWNDhwndWPARAMwParam;//设置地图类型//交叉率变异率种群大小最大世代数voidSetGaInformationfloatfpcrossfloatfpmutationintfpopsizeintfmaxgen;voidCleanAllUpDate;//清除所有点//显示其它与鼠标位置或地图相关信息voidDisPlayHWNDhwndconstPOINTpointboolbdrawline;voidDrawAllPointHWNDhwnd;//画出所有的点voidDrawMapHWNDhwndHDChdc;//画地图voidDrawTruePointHWNDhwndconstPOINTpoint;//画点voidDrawFalsePointHWNDhwndconstPOINTpoint;//去掉点voidDrawLineWait;//画线的准备voidDrawLineHWNDhwnd;//画线floatGetpcross//获得交叉概率{returnpcross;}floatGetpmutation//获得变异概率{returnpmutation;}intGetpopsize//获得种群大小{returnpopsize;}intGetmaxgen//获得世代数{returnmaxgen;}intGetcitynumber//获得城市数{returncitynumber;}voidSetPowerbooln//设置世代进化类型{power=n;}boolGetPower//获得世代进化类型{returnpower;}private:UINTMapStyle;//标志当前地图类型floatpcross;//交叉率floatpmutation;//变异率intpopsize;//种群大小intmaxgen;//最大世代数intcitynumber;//城市数目boolpower;DefaultMapDefaultMapObject;RoundMapRoundMapObject;LineLineObject;Map*MapObject;};///////////初始化数据////////inlineControl::Control:pcross
0.6fpmutation
0.2fpopsize30maxgen30citynumber30MapObjectDefaultMapObjectMapStyleID_DefaultMappower1{return;}/////////////////////////////////////////////////////////////////////////////
2.源文件/////////////////////////control.cpp/////////////////////////////////////////#includecontrol.hWORDbeforehourtime;WORDbeforeminutetime;WORDbeforesecondtime;WORDbeforemillisecondtime;WORDafterhourtime;WORDafterminutetime;WORDaftersecondtime;WORDaftermillisecondtime;UINTDrawMutationStyle=ID_ORDER_MUTATION;//进化类型UINTDrawCrossoverStyle=ID_PARTIALLY_MATCHED_CROSSOVER;//交叉类型//////////////////////////提供提示和帮助信息/////////////////////////////////voidControl::welcomeHWNDhwnd{//创建一个对话框显示提示信息MessageBoxhwnd欢迎进入遗传算法解TSP问题演示系统!遗传算法解TSP问题演示实验MB_OK;//return;}/////////////////////////////////////////////////////////////////////////////////////帮助//////////////////////////////////////////////////////////////////*voidControl::helpHWNDhwnd{}*//////////////////////////////////////////////////////////////////////////////////////////////获得当前地图类型/////////////////////////////////////////////UINTControl::GetMapStyle{returnMapStyle;}///////////////////////////////////////////////////////////////////////////////////////////////设置地图类型///////////////////////////////////////////////voidControl::SetMapStyleHWNDhwndWPARAMwParam{HMENUhMenu;hMenu=GetMenuhwnd;switchLOWORDwParam{caseID_DefaultMap:{MapObject=DefaultMapObject;}break;caseID_RoundMap:{MapObject=RoundMapObject;}break;default:break;}CheckMenuItemhMenuMapStyleMF_UNCHECKED;MapStyle=LOWORDwParam;CheckMenuItemhMenuMapStyleMF_CHECKED;return;}////////////////////////////////////////////////////////////////////////////////////////////遗传算法信息//////////////////////////////////////////////////voidControl::SetGaInformationfloatfpcrossfloatfpmutationintfpopsizeintfmaxgen{//依次:交叉率变异率种群大小最大世代数.iffpcross!=
0.0{pcross=fpcross;}iffpmutation!=
0.0{pmutation=fpmutation;}iffpopsize!=0||fpopsize!=1{popsize=fpopsize;}iffmaxgen!=0||fmaxgen!=1{maxgen=fmaxgen;}return;}/////////////////////////////////////////////////////////////////////////////////////////////////////////清除所有点//////////////////////////////////////////////////////Map*MapObject;///////voidControl::CleanAllUpDate{MapObject-DelAllPoint;return;}//////////////////////////////////////////////////////////////////////////////////////////////////////显示其它与鼠标位置或地图相关信息////////////////////voidControl::DisPlayHWNDhwndconstPOINTpointboolbdrawline{HDChdc;hdc=GetDChwnd;POINTtemppoint;charbuffer
[80];SetBkModehdcOPAQUE;HPENhpen;SetTextColorhdcRGB00255;TextOuthdc25010遗传算法解TSP问题演示地图strlen遗传算法解TSP问题演示地图;SetTextColorhdcRGB000;TextOuthdc50500注意:点击鼠标左键设置城市点点击鼠标右键清空一个点strlen注意:点击鼠标左键设置城市点点击鼠标右键清空一个点;TextOuthdc82530点击菜单开始或ENTER键进行寻路详细信息请选菜单中帮助strlen点击菜单开始或ENTER键进行寻路详细信息请选菜单中帮助;////算法运行时间显示模块/////////////////////////////////////////////////////WORDtempbeforehourtime=beforehourtime;WORDtempbeforeminutetime=beforeminutetime;WORDtempbeforesecondtime=beforesecondtime;WORDtempbeforemillisecondtime=beforemillisecondtime;WORDtempafterhourtime=afterhourtime;WORDtempafterminutetime=afterminutetime;WORDtempaftersecondtime=aftersecondtime;WORDtempaftermillisecondtime=aftermillisecondtime;hpen=CreatePenPS_SOLID1RGB0128128;///创建画笔SelectObjecthdchpen;Rectanglehdc710180960340;DeleteObjecthpen;SetTextColorhdcRGB000;TextOuthdc780170算法运行时间strlen算法运行时间;TextOuthdc730190算法启动前时间:strlen算法启动前时间:;sprintfbuffer%d时%d分%d秒%d微秒beforehourtimebeforeminutetimebeforesecondtimebeforemillisecondtime;TextOuthdc730210bufferstrlenbuffer;TextOuthdc730240算法结束时间:strlen算法结束时间:;sprintfbuffer%d时%d分%d秒%d微秒afterhourtimeafterminutetimeaftersecondtimeaftermillisecondtime;TextOuthdc730260bufferstrlenbuffer;WORDintervalhourtime;WORDintervalminutetime;WORDintervalsecondtime;WORDintervalmillisecondtime;intflag=0;ifaftermillisecondtimebeforemillisecondtimeflag==0{aftersecondtime=aftersecondtime-1;intervalmillisecondtime=aftermillisecondtime+1000-beforemillisecondtime;flag++;}elseintervalmillisecondtime=aftermillisecondtime-beforemillisecondtime;flag=0;ifaftersecondtimebeforesecondtimeflag==0{afterminutetime=afterminutetime-1;intervalsecondtime=aftersecondtime+60-beforesecondtime;flag++;}elseintervalsecondtime=aftersecondtime-beforesecondtime;flag=0;ifafterminutetimebeforeminutetimeflag==0{afterhourtime=afterhourtime-1;intervalminutetime=afterminutetime+60-beforeminutetime;flag++;}elseintervalminutetime=afterminutetime-beforeminutetime;intervalhourtime=afterhourtime-beforehourtime;TextOuthdc730290算法耗费时间:strlen算法耗费时间:;sprintfbuffer%d时%d分%d秒%d微秒intervalhourtimeintervalminutetimeintervalsecondtimeintervalmillisecondtime;TextOuthdc730310bufferstrlenbuffer;beforehourtime=tempbeforehourtime;beforeminutetime=tempbeforeminutetime;beforesecondtime=tempbeforesecondtime;beforemillisecondtime=tempbeforemillisecondtime;afterhourtime=tempafterhourtime;afterminutetime=tempafterminutetime;aftersecondtime=tempaftersecondtime;aftermillisecondtime=tempaftermillisecondtime;/////////////////////////////////////////////////////////////////////////////////所用遗传算子显示模块/////////////////////////////////////////////////////hpen=CreatePenPS_SOLID1RGB0128128;///创建画笔SelectObjecthdchpen;Rectanglehdc710370960490;DeleteObjecthpen;SetTextColorhdcRGB000;TextOuthdc780360所选遗传算子strlen所选遗传算子;TextOuthdc730390交叉算子:strlen交叉算子:;TextOuthdc730440变异算子:strlen变异算子:;switchDrawCrossoverStyle{caseID_PARTIALLY_MATCHED_CROSSOVER:{TextOuthdc760410部分匹配交叉strlen部分匹配交叉;}break;caseID_ORDER_CROSSOVER:{TextOuthdc760410顺序交叉strlen顺序交叉;}break;caseID_CYCLE_CROSSOVER:{TextOuthdc760410循环交叉strlen循环交叉;}break;caseID_GREED_CROSSOVER:{TextOuthdc760410改进交叉循环贪心交叉strlen改进交叉循环贪心交叉;}break;default:break;}switchDrawMutationStyle{caseID_ORDER_MUTATION:{TextOuthdc760460基于次序的变异strlen基于次序的变异;}break;caseID_POSITION_MUTATION:{TextOuthdc760460基于位置的变异strlen基于位置的变异;}break;caseID_REVERSE_MUTATION:{TextOuthdc760460倒位变异strlen倒位变异;}break;default:break;}/////////////////////////////////////////////////////////////////////////////////计算结果显示模块/////////////////////////////////////////////////////////hpen=CreatePenPS_SOLID1RGB0128128;///创建画笔SelectObjecthdchpen;Rectanglehdc71050960150;DeleteObjecthpen;SetTextColorhdcRGB000;TextOuthdc78040计算结果strlen计算结果;//点菜单开始或ENTER进行寻路详细信息请选菜单中帮助SetTextColorhdcRGB000;//blacksprintfbuffer城市总数:%dMapObject-GetAllClickPoint.size;TextOuthdc730120bufferstrlenbuffer;//ifbdrawline==1//当前未准备好所有的点{TextOuthdc850120总距离:0strlen总距离:0;}else{sprintfbuffer总距离:%dLineObject.GetSumDistance;TextOuthdc850120bufferstrlenbuffer;//显示连线总长}ifMapStyle==ID_DefaultMap//默认地图才显示坐标{temppoint=DefaultMapObject.GetMapPointpoint;//获得地图上的点位置700*420if-1!=temppoint.x//测试点在有效区没有{SetTextColorhdcRGB000;}//没在无效区域则为黑笔，只是显示坐标点的颜色else{SetTextColorhdcRGB25500;}//在无效区域则为红笔sprintfbuffer当前鼠标的横坐标:%ldtemppoint.x;TextOuthdc73070bufferstrlenbuffer;//sprintfbuffer当前鼠标的纵坐标:%ldtemppoint.y;TextOuthdc73090bufferstrlenbuffer;}ReleaseDChwndhdc;/////////////////////////////////////////////////////////////////////////////return;}/////////////////////////////////////////////////////////////////////////////////////////////////////以下为画地图/////////////////////////////////////////////////////Map*MapObject;//////////////////////////////voidControl::DrawMapHWNDhwndHDChdc{MapObject-DrawMaphwndhdc;return;}///////////////////////////////////////////////////////////////////////////////////////////画出所有在向量里的点///////////////////////////////////////////////////////Map*MapObject;///////////////////////////////////vectorPOINTGetAllClickPoint;//获得所有已点击的点的位置实际值///voidControl::DrawAllPointHWNDhwnd{//vectorPOINTGetAllClickPoint//获得所有已点击的点的位置实际值forintn=MapObject-GetAllClickPoint.size;n0;{MapObject-DrawPonithwndMapObject-GetAllClickPoint[--n];}return;}///////////////////////////////////////////////////////////////////////////////////////////画出所有在向量里的点///////////////////////////////////////////voidControl::DrawTruePointHWNDhwndconstPOINTpoint{MapObject-DrawPonithwndpoint;return;}///////////////////////////////////////////////////////////////////////////////////清除点/////////////////////////////////////////////////////////////////voidControl::DrawFalsePointHWNDhwndconstPOINTpoint{MapObject-SmearPonithwndpoint;return;}///////////////////////////////////////////////////////////////////////////////画线的准备和画线///设置矩阵////设置遗传算法参数函数////设置遗传算法接口////////////CGAga;***************************************/////////LineLineObject;////////////////////////voidControl::DrawLineWait{CGAga;ifMapObject-GetAllClickPoint.size=2{return;}//将地图中所有点一位置作参数LineObject.SetPointMatrixMapObject-GetAllClickPoint;//产生点的矩阵ga.preSetLineObject.GetPointMatrixpcrosspmutationpopsizemaxgenpower+1;//矩阵作参数LineObject.GaInterfacega.start;}//////////////////////////////////////////////////////////////////////////////////////画线//////////////////////////////////////////////////////////////////////////vectorPOINTGetPointPosition//获得存储点的位置////////////////LineLineObject;////////////////////////voidControl::DrawLineHWNDhwnd{ifLineObject.GetPointPosition.size=0{return;}ifLineObject.GetPointPosition.size=2{LineObject.DrawLinehwndMapObject-GetAllClickPoint;return;}LineObject.DrawLinehwndLineObject.GetPointPosition;}/////////////////////////////////////////////////////////////////////////////七．连线类
1.头文件///////////////connectline.h/////////////////////////////////////////////////#pragmaonce#includemap.hclassLine{public:voidSetPointMatrixconstvectorPOINT;//由已知的点构成矩阵vectorvectorintGetPointMatrix;//获得矩阵intCalculateDistanceconstPOINTconstPOINT;//求两点间的距离voidDrawLineHWNDhwndconstvectorPOINT;//按存储点的顺序连线`//voidSavePointMatrix;//保存点矩阵voidGaInterfaceconstpairvectorintint;//遗传算法接口vectorPOINTGetPointPosition//获得存储点的位置{returnresultpoint.first;}intGetSumDistance//获得存储点的距离{returnresultpoint.second;}private:vectorpairPOINTintdrawpoint;//储存点的位置并标号vectorvectorintpointmatrix;//储存任意两点的距离pairvectorPOINTintresultpoint;//储存点的位置和距离};/////////////////////////////////////////////////////////////////////////////
2.源文件/////////////////////////////connectline.cpp/////////////////////////////////#includeconnectline.h////////////////生成矩阵和获得矩阵/////////////////////////////////////////////vectorpairPOINTintdrawpoint;//储存点的位置并标号*******************//vectorvectorintpointmatrix;//储存任意两点的距离*********************voidLine::SetPointMatrixconstvectorPOINTvecpoint{drawpoint.clear;pointmatrix.clear;//为向量vectorpairPOINTintdrawpoint分配存储空间drawpoint.reservevecpoint.size;forintn=0;nvecpoint.size;n++//将所有的点编号{drawpoint[n].first.x=vecpoint[n].x;drawpoint[n].first.y=vecpoint[n].y;drawpoint[n].second=n;}//为向量vectorvectorintpointmatrix分配内存vectorintvectempvecpoint.size;forn=0;nvecpoint.size;n++{pointmatrix.push_backvectemp;}forn=0;nvecpoint.size;n++//生成二维矩阵forintm=vecpoint.size-1;mn;m--{//编号为n和编号为m的两个点之间的距离pointmatrix[n][m]=sqrtpowabsvecpoint[n].x-vecpoint[m].x2+powabsvecpoint[n].y-vecpoint[m].y2;pointmatrix[m][n]=pointmatrix[n][m];}return;}////////////////////////////////////////////////////////////////////////////////////获得矩阵//////////////////////////////////////////////////////////////vectorvectorintLine::GetPointMatrix{returnpointmatrix;//储存任意两点的距离}/////////////////////////////////////////////////////////////////////////////////////////////计算两个点之间的距离/////////////////////////////////////////intLine::CalculateDistanceconstPOINTpoint1constPOINTpoint2{returnsqrtpowabspoint
1.x-point
2.x2+powabspoint
1.y-point
2.y2;}///////////////////////////////////////////////////////////////////////////////////////////根据点向量画线/////////////////////////////////////////////////voidLine::DrawLineHWNDhwndconstvectorPOINTvecpoint{//连线按存储的点的顺序HDChdc=GetDChwnd;HPENhpen;hpen=CreatePenPS_DOT1RGB00255;SelectObjecthdchpen;ifvecpoint.size=0{return;}SetTextColorhdcRGB02550;/////TextOuthdcvecpoint
[0].x+15vecpoint
[0].y+15起点strlen起点;charbuffer
[5];/////forintn=0;nvecpoint.size-1;n++{sprintfbuffer%dn;/////SetTextColorhdcRGB12800;/////TextOuthdcvecpoint[n].x+5vecpoint[n].y+5bufferstrlenbuffer;MoveToExhdcvecpoint[n].xvecpoint[n].yLPPOINTNULL;LineTohdcvecpoint[n+1].xvecpoint[n+1].y;}sprintfbuffer%dn;/////SetTextColorhdcRGB12800;/////TextOuthdcvecpoint[n].x+5vecpoint[n].y+5bufferstrlenbuffer;MoveToExhdcvecpoint.front.xvecpoint.front.yNULL;//回到起点LineTohdcvecpoint.back.xvecpoint.back.y;DeleteObjecthpen;ReleaseDChwndhdc;return;}/////////////////////////////////////////////////////////////////////////////////////////////保存vectorvectorintpointmatrix//////////////////////////*voidLine::SavePointMatrix{fstreamoutFilecopy.textios_base::out|ios_base::app;if!outFile{cerrunabletoopeninputfile:--bailingout!\n;return;}ifpointmatrix.size=0{return;}outFile#矩阵\n;///以后有用outFile#pointmatrix.size\n;forintn=0;npointmatrix.size;n++{forintm=0;mpointmatrix[n].size;m++{outFilepointmatrix[n][m];}outFile\n;}return;}*//////////////////////////////////////////////////////////////////////////////////////////////遗传算法接口函数///////////////////////////////////////////////pairvectorPOINTintresultpoint;//储存点的位置和距离///**************//vectorpairPOINTintdrawpoint;//储存点的位置并标号///////////////////voidLine::GaInterfaceconstpairvectorintintpointorder{vectorPOINTresult;forintn=0;npointorder.first.size;n++{result.push_backdrawpoint[pointorder.first[n]].first;}resultpoint.first=result;//获得所有的点的位置resultpoint.second=pointorder.second;//获得路程的总长度}/////////////////////////////////////////////////////////////////////////////八．遗传算法类
1.头文件voidorder_crossoverChromparent1Chromparent2Chromchild1Chromchild2;//循环交叉voidcycle_crossoverChromparent1Chromparent2Chromchild1Chromchild2;//循环贪心交叉voidgreed_crossoverChromparent1Chromparent2Chromchild1Chromchild2;intrandomIntintlowinthigh;//产生一个随机整数在low和high之间private:Popoldpop;//当前代种群Popnewpop;//新一代种群vectorGenegenes;//保存全部基因floatpcross;//交叉率floatpmutation;//变异率intpopsize;//种群大小intlchrom;//染色体长度intmaxgen;//最大世代数intgen;//当前世代floatmax_var;//路径最大连接开销!!intevolveWay;//进化方案UINTMutationStyle;//进化类型UINTCrossoverStyle;//交叉类型voidchromCostChromchr;//计算一条染色体的个体适应度voidpopCostPoppop;//计算一个种群的个体适应度之和voidinitChromChromchr;//随机初始化一条染色体voidinitpopPoppop;//随机初始化种群intselectChromconstPoppop;//轮盘赌选择返回种群中被选个体编号intchooseBestconstPoppop;//精英策略，返回最优秀的一条染色体//染色体交叉操作由两个父代产生两个子代voidcrossoverChromparent1Chromparent2Chromchild1Chromchild2;//染色体变异操作voidmutationChromchr;//世代进化由当前种群产生新种群voidgenerationPopoldpopPopnewpop;//循环贪心voidtempcrossoverChromparent1Chromparent2Chromchild1;};inlineCGA::CGA:MutationStyleID_ORDER_MUTATIONCrossoverStyleID_PARTIALLY_MATCHED_CROSSOVER{return;}/////////////////////////////////////////////////////////////////////////////
2.源文件//////////////////////////ga.cpp/////////////////////////////////////////////#pragmaonce#includega.husingnamespacestd;UINTTempMutationStyle=ID_ORDER_MUTATION;//进化类型UINTTempCrossoverStyle=ID_PARTIALLY_MATCHED_CROSSOVER;//交叉类型//////////////////////////设置变异类型///////////////////////////////////////voidCGA::SetMutationStyleHWNDhwndWPARAMwparam{HMENUhMenu;hMenu=GetMenuhwnd;CheckMenuItemhMenuMutationStyleMF_UNCHECKED;MutationStyle=LOWORDwparam;CheckMenuItemhMenuMutationStyleMF_CHECKED;TempMutationStyle=MutationStyle;return;}///////////////////////////////////////////////////////////////////////////////////////////////////设置交叉类型///////////////////////////////////////////voidCGA::SetCrossoverStyleHWNDhwndWPARAMwparam{HMENUhMenu;hMenu=GetMenuhwnd;CheckMenuItemhMenuCrossoverStyleMF_UNCHECKED;CrossoverStyle=LOWORDwparam;CheckMenuItemhMenuCrossoverStyleMF_CHECKED;TempCrossoverStyle=CrossoverStyle;return;}////////////////////////////////////////////////////////////////////////////////////////////////遗传算法参数设置函数定义//////////////////////////////////voidCGA::preSetvectorvectorintmapDistfloat_pcrossfloat_pmutationint_popsizeint_maxgenint_evolveWay{//设置参数pcross=_pcross;popsize=_popsize;pmutation=_pmutation;maxgen=_maxgen;evolveWay=_evolveWay;lchrom=mapDist.size;genes.resizelchrom;max_var=0;//路径最大连接开销forinti=0;ilchrom;++i{genes[i].ID=i;forintj=0;jlchrom;++j{genes[i].linkCost[genes[j]]=mapDist[i][j];ifmapDist[i][j]max_varmax_var=mapDist[i][j];//路径最大连接开销}}}/////////////////////////////////////////////////////////////////////////////////////////////遗传算法启动函数定义/////////////////////////////////////////pairvectorintintCGA::start{initpopoldpop;//产生初始种群//通过不断进化，直到达到最大世代数intbest;//最优染色体编号forgen=0;genmaxgen;gen++{generationoldpopnewpop;//从当前种群产生新种群oldpop.pop_chrom.swapnewpop.pop_chrom;oldpop.sumfitness=newpop.sumfitness;newpop.pop_chrom.clear;}best=chooseBestoldpop;//最佳染色体pairvectorintintresult;//最优结果forinti=0;ilchrom;++iresult.first.push_backoldpop.pop_chrom[best].chrom_gene[i]-ID;result.second=oldpop.pop_chrom[best].varible;returnresult;}//////////////////////////////////////////////////////////////////////////////////产生一个随机整数在[lowhigh区间上////////////////////////////////////inlineintCGA::randomIntintlowinthigh{iflow==highreturnlow;returnlow+rand%high-low;}///////////////////////////////////////////////////////////////////////////////////计算一条染色体的个体适应度/////////////////////////////////////////////inlinevoidCGA::chromCostChromchr{floatsum=0;forinti=0;ilchrom;++i{sum+=chr.chrom_gene[i]-linkCost[chr.chrom_gene[i+1]];}sum+=chr.chrom_gene.front-linkCost[chr.chrom_gene.back];chr.varible=sum;//路径是一个环chr.fitness=max_var*lchrom-chr.varible;//fitness个体适应度}///////////////////////////////////////////////////////////////////////////////////计算一个种群的个体适应度之和///////////////////////////////////////////inlinevoidCGA::popCostPoppop{floatsum=0;forinti=0;ipopsize;++i{sum+=pop.pop_chrom[i].fitness;}pop.sumfitness=sum;}/////////////////////////////////////////////////////////////////////////////////////随机初始化一条染色体/////////////////////////////////////////////////inlinevoidCGA::initChromChromchr{vectorinttmplchrom;forinti=0;ilchrom;i++tmp[i]=i;intchoose;whiletmp.size1{choose=randomInt0tmp.size;chr.chrom_gene.push_backgenes[tmp[choose]];tmp.erasetmp.begin+choose;}chr.chrom_gene.push_backgenes[tmp
[0]];chromCostchr;}///////////////////////////////////////////////////////////////////////////////////////随机初始化种群/////////////////////////////////////////////////////inlinevoidCGA::initpopPoppop{pop.pop_chrom.reservepopsize;Chromtmp;tmp.chrom_gene.reservelchrom;forinti=0;ipopsize;i++{initChromtmp;pop.pop_chrom.push_backtmp;tmp.chrom_gene.clear;}popCostpop;}////////////////////////////////////////////////////////////////////////////////////////轮盘赌选择返回种群中被选择的个体编号/////////////////////////////inlineintCGA::selectChromconstPoppop{floatsum=0;floatpick=floatrandomInt01000/1000;inti=0;ifpop.sumfitness!=0{while1{sum+=pop.pop_chrom[i].fitness/pop.sumfitness;++i;ifsumpick||i==pop.pop_chrom.sizereturni-1;}}elsereturnrandomInt0pop.pop_chrom.size;}///////////////////////////////////////////////////////////////////////////////////精英策略，返回最优秀的一条染色体///////////////////////////////////////inlineintCGA::chooseBestconstPoppop{intchoose=0;floatbest=0;forinti=0;ipop.pop_chrom.size;++i{ifpop.pop_chrom[i].fitnessbest{best=pop.pop_chrom[i].fitness;choose=i;}}returnchoose;}////////////////////////////////////////////////////////////////////////////////////////选择交叉类型//////////////////////////////////////////////////////inlinevoidCGA::crossoverChromparent1Chromparent2Chromchild1Chromchild2{switchTempCrossoverStyle{caseID_PARTIALLY_MATCHED_CROSSOVER:{partially_matched_crossoverparent1parent2child1child2;}break;caseID_ORDER_CROSSOVER:{order_crossoverparent1parent2child1child2;}break;caseID_CYCLE_CROSSOVER:{cycle_crossoverparent1parent2child1child2;}break;caseID_GREED_CROSSOVER:{greed_crossoverparent1parent2child1child2;}break;default:break;}}///////////////////////////////////////////////////////////////////////////////////部分匹配交叉///////////////////////////////////////////////////////////inlinevoidCGA::partially_matched_crossoverChromparent1Chromparent2Chromchild1Chromchild2{child
1.chrom_gene.resizelchrom;child
2.chrom_gene.resizelchrom;vectorGene*::iteratorp1_begp2_begc1_begc2_begp1_endp2_endc1_endc2_end;p1_beg=parent
1.chrom_gene.begin;p2_beg=parent
2.chrom_gene.begin;c1_beg=child
1.chrom_gene.begin;c2_beg=child
2.chrom_gene.begin;p1_end=parent
1.chrom_gene.end;p2_end=parent
2.chrom_gene.end;c1_end=child
1.chrom_gene.end;c2_end=child
2.chrom_gene.end;//交换了parent1和parent2的值//用于交叉的临时表vectorGene*v1parent
1.chrom_genev2parent
2.chrom_gene;//随机选择两个交叉点intpick1=randomInt1lchrom-1;///////intpick2=randomIntpick1lchrom-1;////intdist=lchrom-1-pick2;//第二交叉点到尾部的距离copyp1_beg+pick1p1_beg+pick2+1c2_beg+pick1;copyp2_beg+pick1p2_beg+pick2+1c1_beg+pick1;vectorinttemchild1;vectorinttemchild2;intvalue;forvalue=pick1;value=pick2;value++temchild
1.push_backparent
1.chrom_gene[value]-ID;forvalue=pick1;value=pick2;value++temchild
2.push_backparent
2.chrom_gene[value]-ID;//把表中元素复制到子代中copyv
1.beginv
1.begin+pick1c1_beg;copyv
1.begin+pick2+1v
1.endc1_beg+pick2+1;copyv
2.beginv
2.begin+pick1c2_beg;copyv
2.begin+pick2+1v
2.endc2_beg+pick2+1;vectorGene*::iteratorch1;vectorGene*::iteratorch2;vectorint::iteratorvec;intijk;forch1=child
1.chrom_gene.begini=0;ch1!=child
1.chrom_gene.begin+pick1;ch1++i++iffindtemchild
2.begintemchild
2.endchild
1.chrom_gene[i]-ID!=temchild
2.end{forvec=temchild
2.beginj=0;vec!=temchild
2.end;vec++j++ifchild
1.chrom_gene[i]-ID==temchild2[j]{break;}whilefindtemchild
2.begintemchild
2.endtemchild1[j]!=temchild
2.end{forvec=temchild
2.begink=0;vec!=temchild
2.end;vec++k++iftemchild1[j]==temchild2[k]{break;}j=k;}copyparent
1.chrom_gene.begin+pick1+jparent
1.chrom_gene.begin+pick1+j+1child
1.chrom_gene.begin+i;}forch1=child
1.chrom_gene.begin+pick2+1i=pick2+1;ch1!=child
1.chrom_gene.end;ch1++i++iffindtemchild
2.begintemchild
2.endchild
1.chrom_gene[i]-ID!=temchild
2.end{forvec=temchild
2.beginj=0;vec!=temchild
2.end;vec++j++ifchild
1.chrom_gene[i]-ID==temchild2[j]{break;}whilefindtemchild
2.begintemchild
2.endtemchild1[j]!=temchild
2.end{forvec=temchild
2.begink=0;vec!=temchild
2.end;vec++k++iftemchild1[j]==temchild2[k]{break;}j=k;}copyparent
1.chrom_gene.begin+pick1+jparent
1.chrom_gene.begin+pick1+j+1child
1.chrom_gene.begin+i;}forch2=child
2.chrom_gene.begini=0;ch2!=child
2.chrom_gene.begin+pick1;ch2++i++iffindtemchild
1.begintemchild
1.endchild
2.chrom_gene[i]-ID!=temchild
1.end{forvec=temchild
1.beginj=0;vec!=temchild
1.end;vec++j++ifchild
2.chrom_gene[i]-ID==temchild1[j]{break;}whilefindtemchild
1.begintemchild
1.endtemchild2[j]!=temchild
1.end{forvec=temchild
1.begink=0;vec!=temchild
1.end;vec++k++iftemchild2[j]==temchild1[k]{break;}j=k;}copyparent
2.chrom_gene.begin+pick1+jparent
2.chrom_gene.begin+pick1+j+1child
2.chrom_gene.begin+i;}forch2=child
2.chrom_gene.begin+pick2+1i=pick2+1;ch2!=child
2.chrom_gene.end;ch2++i++iffindtemchild
1.begintemchild
1.endchild
2.chrom_gene[i]-ID!=temchild
1.end{forvec=temchild
1.beginj=0;vec!=temchild
1.end;vec++j++ifchild
2.chrom_gene[i]-ID==temchild1[j]{break;}whilefindtemchild
1.begintemchild
1.endtemchild2[j]!=temchild
1.end{forvec=temchild
1.begink=0;vec!=temchild
1.end;vec++k++iftemchild2[j]==temchild1[k]{break;}j=k;}copyparent
2.chrom_gene.begin+pick1+jparent
2.chrom_gene.begin+pick1+j+1child
2.chrom_gene.begin+i;}}////////////////////////////////////////////////////////////////////////////////////顺序交叉/////////////////////////////////////////////////////////////////rotatev
1.beginv
1.begin+pick2+1v
1.end;///rotatev
2.beginv
2.begin+pick2+1v
2.end;inlinevoidCGA::order_crossoverChromparent1Chromparent2Chromchild1Chromchild2{child
1.chrom_gene.resizelchrom;child
2.chrom_gene.resizelchrom;vectorGene*::iteratorv_iterp1_begp2_begc1_begc2_begp1_endp2_endc1_endc2_end;p1_beg=parent
1.chrom_gene.begin;p2_beg=parent
2.chrom_gene.begin;c1_beg=child
1.chrom_gene.begin;c2_beg=child
2.chrom_gene.begin;p1_end=parent
1.chrom_gene.end;p2_end=parent
2.chrom_gene.end;c1_end=child
1.chrom_gene.end;c2_end=child
2.chrom_gene.end;//交换了parent1和parent2的值//用于交叉的临时表vectorGene*v1parent
2.chrom_genev2parent
1.chrom_gene;//随机选择两个交叉点intpick1=randomInt1lchrom-1;///////intpick2=randomIntpick1lchrom-1;////修改intdist=lchrom-1-pick2;//第二交叉点到尾部的距离//子代保持两交叉点间的基因不变copyp1_beg+pick1p1_beg+pick2+1c1_beg+pick1;copyp2_beg+pick1p2_beg+pick2+1c2_beg+pick1;//循环移动表中元素rotatev
1.beginv
1.begin+pick2+1v
1.end;rotatev
2.beginv
2.begin+pick2+1v
2.end;//从表中除去父代已有的元素forv_iter=p1_beg+pick1;v_iter!=p1_beg+pick2+1;++v_iterremovev
1.beginv
1.end*v_iter;forv_iter=p2_beg+pick1;v_iter!=p2_beg+pick2+1;++v_iterremovev
2.beginv
2.end*v_iter;//把表中元素复制到子代中copyv
1.beginv
1.begin+distc1_beg+pick2+1;copyv
1.begin+distv
1.begin+dist+pick1c1_beg;copyv
2.beginv
2.begin+distc2_beg+pick2+1;copyv
2.begin+distv
2.begin+dist+pick1c2_beg;}//////////////////////////////////////////////////////////////////////////////////////////循环交叉////////////////////////////////////////////////////////inlinevoidCGA::cycle_crossoverChromparent1Chromparent2Chromchild1Chromchild2{child
1.chrom_gene.resizelchrom;child
2.chrom_gene.resizelchrom;vectorGene*::iteratorp1_begp2_begc1_begc2_beg;p1_beg=parent
1.chrom_gene.begin;p2_beg=parent
2.chrom_gene.begin;c1_beg=child
1.chrom_gene.begin;c2_beg=child
2.chrom_gene.begin;copyparent
1.chrom_gene.beginparent
1.chrom_gene.endc2_beg;copyparent
2.chrom_gene.beginparent
2.chrom_gene.endc1_beg;//copyp1_begp1_beg+1c1_beg;//未改进//copyp2_begp2_beg+1c2_beg;intsign=randomInt0lchrom-1;//改进copyp1_beg+signp1_beg+sign+1c1_beg+sign;copyp2_beg+signp2_beg+sign+1c2_beg+sign;intflag=parent
2.chrom_gene[sign]-ID;//改进inttempchild=parent
2.chrom_gene[sign]-ID;//intflag=parent
2.chrom_gene
[0]-ID;//未改进//inttempchild=parent
2.chrom_gene
[0]-ID;vectorGene*::iteratorvecchild;inti;whileflag!=parent
1.chrom_gene[sign]-ID//改进//whileflag!=parent
1.chrom_gene
[0]-ID//未改进{forvecchild=parent
1.chrom_gene.begini=0;vecchild!=parent
1.chrom_gene.end;vecchild++i++iftempchild==parent
1.chrom_gene[i]-ID{copyp1_beg+ip1_beg+i+1c1_beg+i;copyp2_beg+ip2_beg+i+1c2_beg+i;tempchild=parent
2.chrom_gene[i]-ID;flag=parent
2.chrom_gene[i]-ID;break;}}}///////////////////////////////////////////////////////////////////////////////////////////////////改进交叉方法:循环贪心交叉//////////////////////////////inlinevoidCGA::tempcrossoverChromparent1Chromparent2Chromchild1{child
1.chrom_gene.resizelchrom;vectorGene*::iteratorp1_begp2_begc1_beg;p1_beg=parent
1.chrom_gene.begin;p2_beg=parent
2.chrom_gene.begin;c1_beg=child
1.chrom_gene.begin;intchildsize;intsign=randomInt0lchrom;//改进**********//intsign=0;//未改进**********vectorinttemchild;copyp1_beg+signp1_beg+sign+1c1_beg;temchild.push_backparent
1.chrom_gene[sign]-ID;childsize=1;whilechildsizelchrom{intpleft1;intpright1;intpleft2;intpright2;ifsign==0{pleft1=lchrom-1;pright1=sign+1;}elseifsign==lchrom-1{pright1=0;pleft1=sign-1;}else{pleft1=sign-1;pright1=sign+1;}intvalue;forinti=0;ilchrom;i++ifparent
1.chrom_gene[sign]-ID==parent
2.chrom_gene[i]-ID{value=i;break;}ifvalue==0{pleft2=lchrom-1;pright2=value+1;}elseifvalue==lchrom-1{pright2=0;pleft2=value-1;}else{pleft2=value-1;pright2=value+1;}intsign1;intsign2;intflag1;intflag2;intflag;iffindtemchild.begintemchild.endparent
1.chrom_gene[pleft1]-ID==temchild.endfindtemchild.begintemchild.endparent
1.chrom_gene[pright1]-ID==temchild.end{flag1=1;ifparent
1.chrom_gene[sign]-linkCost[parent
1.chrom_gene[pleft1]]parent
1.chrom_gene[sign]-linkCost[parent
1.chrom_gene[pright1]]{sign1=pleft1;}elsesign1=pright1;}elseiffindtemchild.begintemchild.endparent
1.chrom_gene[pleft1]-ID==temchild.endfindtemchild.begintemchild.endparent
1.chrom_gene[pright1]-ID!=temchild.end{flag1=1;sign1=pleft1;}elseiffindtemchild.begintemchild.endparent
1.chrom_gene[pleft1]-ID!=temchild.endfindtemchild.begintemchild.endparent
1.chrom_gene[pright1]-ID==temchild.end{flag1=1;sign1=pright1;}elseflag1=0;iffindtemchild.begintemchild.endparent
2.chrom_gene[pleft2]-ID==temchild.endfindtemchild.begintemchild.endparent
2.chrom_gene[pright2]-ID==temchild.end{flag2=1;ifparent
2.chrom_gene[value]-linkCost[parent
2.chrom_gene[pleft2]]parent
2.chrom_gene[value]-linkCost[parent
2.chrom_gene[pright2]]{sign2=pleft2;}elsesign2=pright2;}elseiffindtemchild.begintemchild.endparent
2.chrom_gene[pleft2]-ID==temchild.endfindtemchild.begintemchild.endparent
2.chrom_gene[pright2]-ID!=temchild.end{flag2=1;sign2=pleft2;}elseiffindtemchild.begintemchild.endparent
2.chrom_gene[pleft2]-ID!=temchild.endfindtemchild.begintemchild.endparent
2.chrom_gene[pright2]-ID==temchild.end{flag2=1;sign2=pright2;}elseflag2=0;ifflag1==1flag2==1{flag=1;ifparent
1.chrom_gene[sign]-linkCost[parent
1.chrom_gene[sign1]]parent
2.chrom_gene[value]-linkCost[parent
2.chrom_gene[sign2]]{sign=sign1;copyp1_beg+signp1_beg+sign+1c1_beg+childsize;temchild.push_backparent
1.chrom_gene[sign]-ID;childsize++;}else{sign=sign2;copyp2_beg+signp2_beg+sign+1c1_beg+childsize;temchild.push_backparent
2.chrom_gene[sign]-ID;childsize++;}}elseifflag1==1flag2==0{flag=1;sign=sign1;copyp1_beg+signp1_beg+sign+1c1_beg+childsize;temchild.push_backparent
1.chrom_gene[sign]-ID;childsize++;}elseifflag1==0flag2==1{flag=1;sign=sign2;copyp2_beg+signp2_beg+sign+1c1_beg+childsize;temchild.push_backparent
2.chrom_gene[sign]-ID;childsize++;}else{intsignal=0;flag=0;/*whilesignal==0//未改进**********{sign=randomInt0lchrom;//randomIntintlowinthighiffindtemchild.begintemchild.endparent
1.chrom_gene[sign]-ID==temchild.end{signal=1;}}*///未改进**********forintk=0;klchrom;k++//改进**********{sign=k;iffindtemchild.begintemchild.endparent
1.chrom_gene[sign]-ID==temchild.end{signal=1;break;}}//改进**********ifsignal==1{copyp1_beg+signp1_beg+sign+1c1_beg+childsize;temchild.push_backparent
1.chrom_gene[sign]-ID;childsize++;}}}}inlinevoidCGA::greed_crossoverChromparent1Chromparent2Chromchild1Chromchild2{tempcrossoverparent1parent2child1;tempcrossoverparent2parent1child2;}//////////////////////////////////////////////////////////////////////////////////////选择变异算法////////////////////////////////////////////////////////inlinevoidCGA::mutationChromchr{switchTempMutationStyle{caseID_ORDER_MUTATION:{order_oriented_mutationchr;}break;caseID_POSITION_MUTATION:{position_oriented_mutationchr;}break;caseID_REVERSE_MUTATION:{reverse_mutationchr;}break;default:break;}}/////////////////////////////////////////////////////////////////////////////////////////染色体变异操作基于次序的变异//////////////////////////////////////随机地产生两个变异位，然后交换这两个变异位上的基因inlinevoidCGA::order_oriented_mutationChromchr{vectorGene*::iteratorbeg=chr.chrom_gene.begin;intpick1pick2;pick1=randomInt0lchrom;do{pick2=randomInt0lchrom;}whilepick1==pick2;iter_swapbeg+pick1beg+pick2;}///////////////////////////////////////////////////////////////////////////////////染色体变异操作基于位置的变异，随机产生两个变异位////////////////////////然后将第二个变异位上的基因移动到第一个变异位之前inlinevoidCGA::position_oriented_mutationChromchr{vectorGene*::iteratorbeg=chr.chrom_gene.begin;intpick1pick2;pick1=randomInt0lchrom;do{pick2=randomInt0lchrom;}whilepick1==pick2;//控制，使pick1pick2inttemp;ifpick2pick1{temp=pick1;pick1=pick2;pick2=temp;}forinti=pick1;ipick2;i++iter_swapbeg+ibeg+pick2;}////////////////////////////////////////////////////////////////////////////////////染色体变异操作倒位变异，随机产生两个变异位/////////////////////////////然后将这两个变异位所夹的子串中的城市进行反序inlinevoidCGA::reverse_mutationChromchr{vectorGene*::iteratorbeg=chr.chrom_gene.begin;intpick1pick2;vectorGene*tempchromchr.chrom_gene;pick1=randomInt0lchrom;do{pick2=randomInt0lchrom;}whilepick1==pick2;//控制，使pick1pick2inttemp;ifpick2pick1{temp=pick1;pick1=pick2;pick2=temp;}reverse_copytempchrom.begin+pick1tempchrom.begin+pick2+1beg+pick1;}////////////////////////////////////////////////////////////////////////////////////世代进化由当前种群产生新种群////////////////////////////////////////voidCGA::generationPopoldpopPopnewpop{newpop.pop_chrom.resizepopsize;intmate1mate2j;floatpick;floattmp;Chromgene1gene2tmp1tmp2;gene
1.chrom_gene.resizelchrom;gene
2.chrom_gene.resizelchrom;tmp
1.chrom_gene.resizelchrom;tmp
2.chrom_gene.resizelchrom;//将最佳染色体放入下一代mate1=chooseBestoldpop;newpop.pop_chrom
[0]=oldpop.pop_chrom[mate1];j=1;//产生两条新染色体do{intcount=0;mate1=selectChromoldpop;mate2=selectChromoldpop;pick=floatrandomInt01000/1000;gene1=oldpop.pop_chrom[mate1];gene2=oldpop.pop_chrom[mate1];ifpickpcross//交叉操作{ifevolveWay==1{crossoveroldpop.pop_chrom[mate1]oldpop.pop_chrom[mate2]newpop.pop_chrom[j]newpop.pop_chrom[j+1];chromCostnewpop.pop_chrom[j];//计算适应度chromCostnewpop.pop_chrom[j+1];}elseifevolveWay==2//强迫进化{intcount=0;boolflag1=false;boolflag2=false;while1{crossoveroldpop.pop_chrom[mate1]oldpop.pop_chrom[mate2]tmp1tmp2;chromCosttmp1;//计算适应度chromCosttmp2;iftmp
1.fitnessgene
1.fitness{gene1=tmp1;flag1=true;}iftmp
2.fitnessgene
2.fitness{gene2=tmp2;flag2=true;}//当子代都比父代优秀或寻找次数超过n次，跳出ifflag1==trueflag2==true||countmaxgen{newpop.pop_chrom[j]=gene1;newpop.pop_chrom[j+1]=gene2;break;}count++;}}}else{newpop.pop_chrom[j].chrom_gene=oldpop.pop_chrom[mate1].chrom_gene;newpop.pop_chrom[j+1].chrom_gene=oldpop.pop_chrom[mate2].chrom_gene;chromCostnewpop.pop_chrom[j];chromCostnewpop.pop_chrom[j+1];}pick=floatrandomInt01000/1000;ifpickpmutation//变异操作{ifevolveWay==1{mutationnewpop.pop_chrom[j];chromCostnewpop.pop_chrom[j];//计算适应度}elseifevolveWay==2//强迫进化{intcount=0;tmp=newpop.pop_chrom[j].fitness;do{mutationnewpop.pop_chrom[j];chromCostnewpop.pop_chrom[j];//计算适应度count++;}whiletmpnewpop.pop_chrom[j].fitnesscountmaxgen;}//当子代比父代优秀或寻找次数超过n次，跳出}pick=floatrandomInt01000/1000;ifpickpmutation//变异操作{ifevolveWay==1{mutationnewpop.pop_chrom[j+1];chromCostnewpop.pop_chrom[j+1];//计算适应度}elseifevolveWay==2//强迫进化{intcount=0;tmp=newpop.pop_chrom[j+1].fitness;do{mutationnewpop.pop_chrom[j+1];chromCostnewpop.pop_chrom[j+1];//计算适应度count++;}whiletmpnewpop.pop_chrom[j+1].fitnesscountmaxgen;}//当子代比父代优秀或寻找次数超过n次，跳出}j+=2;}whilejpopsize-1;popCostnewpop;//计算新种群的适应度之和}/////////////////////////////////////////////////////////////////////////////九．主控模块
1.源文件///////////////////////////main.cpp//////////////////////////////////////////#includecontrol.h#includega.h#defineWINDOW_CLASS_NAMEGASOLVETSPWINCLASS//窗体类名称boolbdrawline=1;//表示是否画直线1表示未画HINSTANCEg_hinstance;//当前实例charc_buffer
[4]
[5];//char数组类型临时变量RECTrect;//要更新的窗口部分charcity
[5];intcitynum;ControlControlObject;//控制模块类对象CGACgaObject;//遗传算法类对象//CgaObject.randomIntSYSTEMTIMEsystime;//获取系统的时间////////字符类型转化为整型数或浮点型数///////////////////////////////////////floatStringToIntstringstrboolbflg{intsize=str.size;floatresult=0;forintn=0;nsize;n++{result+=str[n]-48;//0的ASCII码为48result*=10;}result/=10;ifbflg==0//这一段处理字符串为大于1的数{returnresult;}whilesize--{result/=10;//获得1到0的数}returnresult;}///////////////////////////////////////////////////////////////////////////////////////////城市设置对话框/////////////////////////////////////////////////LRESULTCALLBACKAboutCITYNUMBERSetHWNDhDlgUINTmessageWPARAMwParamLPARAMlParam{switchmessage{caseWM_INITDIALOG://初始化对话框//把对话框中控制文本设置为用一个指定整型值的字符串表示SetDlgItemInthDlgIDC_CITYNUMBERControlObject.GetcitynumberTRUE;returnTRUE;caseWM_COMMAND:switchLOWORDwParam{caseIDOK://按确认键{//获取对话框中与控制有关的文本或标题GetDlgItemTexthDlgIDC_CITYNUMBERcity5;citynum=StringToIntcity0;EndDialoghDlgLOWORDwParam;returnTRUE;}caseIDCANCEL://按取消键{EndDialoghDlgLOWORDwParam;returnTRUE;}break;}break;}returnfalse;}///////////////////////////////////////////////////////////////////////////////////////////////遗传算法设置对话框/////////////////////////////////////////LRESULTCALLBACKAboutGASetHWNDhDlgUINTmessageWPARAMwParamLPARAMlParam{switchmessage{caseWM_INITDIALOG://初始化对话框//把对话框中控制文本设置为用一个指定整型值的字符串表示SetDlgItemInthDlgIDC_EDIT2ControlObject.Getpcross*100000TRUE;SetDlgItemInthDlgIDC_EDIT3ControlObject.Getpmutation*100000TRUE;SetDlgItemInthDlgIDC_EDIT4ControlObject.GetpopsizeTRUE;SetDlgItemInthDlgIDC_EDIT6ControlObject.GetmaxgenTRUE;//给一组单选按钮中的一个指定按钮加上选中标志并且清除组中其他按钮的选中标志//#defineIDC_RADIO11019//#defineIDC_RADIO21020CheckRadioButtonhDlgIDC_RADIO1IDC_RADIO2IDC_RADIO1+ControlObject.GetPower;returnTRUE;caseWM_COMMAND:switchLOWORDwParam{caseIDC_RADIO1://选中第一个按纽{ControlObject.SetPower0;break;}caseIDC_RADIO2://选中第二个按纽{ControlObject.SetPower1;break;}caseIDOK://按确认键{//获取对话框中与控制有关的文本或标题GetDlgItemTexthDlgIDC_EDIT2c_buffer
[0]5;GetDlgItemTexthDlgIDC_EDIT3c_buffer
[1]5;GetDlgItemTexthDlgIDC_EDIT4c_buffer
[2]5;GetDlgItemTexthDlgIDC_EDIT6c_buffer
[3]5;ControlObject.SetGaInformationStringToIntc_buffer
[0]1StringToIntc_buffer
[1]1StringToIntc_buffer
[2]0StringToIntc_buffer
[3]0;EndDialoghDlgLOWORDwParam;returnTRUE;}caseIDCANCEL://按取消键{EndDialoghDlgLOWORDwParam;returnTRUE;}caseIDDefault://按默认值键{ControlObject.SetGaInformation
0.6f
0.2f3030;ControlObject.SetPower1;SendMessagehDlgWM_INITDIALOG00;returnTRUE;}break;}break;}returnFALSE;}///////////////////////////////////////////////////////////////////////////////////////////////窗口过程函数///////////////////////////////////////////////LRESULTCALLBACKWindowProcHWNDhwndUINTmsgWPARAMwparamLPARAMlparam{PAINTSTRUCTps;//将发送WM_PAINT消息HDChdc;//设备环境句柄staticPOINTpoint;//临时点//无效区域网格以外的区域rect.left=715;rect.top=55;rect.right=950;rect.bottom=140;switchmsg{caseWM_CREATE://应用程序创建一个窗口{ControlObject.welcomehwnd;return0;}break;caseWM_PAINT://要求一个窗口重画自己{hdc=BeginPainthwndps;//画地图ControlObject.DrawMaphwndhdc;ControlObject.DisPlayhwndpointbdrawline;ControlObject.DrawAllPointhwnd;ifbdrawline==0//已画直线但未消除直线{ControlObject.DrawLinehwnd;}}EndPainthwndps;break;caseWM_MOUSEMOVE://移动鼠标{point.x=intLOWORDlparam;point.y=intHIWORDlparam;InvalidateRecthwndrect1;//刷新消息会发送WM_PAINT消息}break;caseWM_LBUTTONDOWN://按下鼠标左键{//SendMessagehwndWM_LBUTTONDOWNNULL0;ControlObject.DrawTruePointhwndpoint;ControlObject.DrawAllPointhwnd;ifbdrawline==0{InvalidateRecthwndNULL1;//刷新消息}InvalidateRecthwndrect1;//刷新消息bdrawline=1;//标志画直线后已清除直线}break;caseWM_RBUTTONDOWN://按下鼠标右键{ControlObject.DrawFalsePointhwndpoint;ControlObject.DrawAllPointhwnd;InvalidateRecthwndNULL1;//刷新消息bdrawline=1;}break;caseWM_RBUTTONDBLCLK://双击鼠标右键{//SendMessagehwndWM_COMMANDID_CLEAN_ALL0;ControlObject.CleanAllUpDate;InvalidateRecthwndNULL1;bdrawline=1;}break;caseWM_KEYDOWN://按下一个键{switchLOWORDwparam{caseVK_RETURN:SendMessagehwndWM_COMMANDIDOK0;break;}}break;//当用户选择一个菜单命令项，或当某个控件发送一条消息给它的父窗口caseWM_COMMAND:{switchLOWORDwparam{caseID_SET_CITY:{SendMessagehwndWM_RBUTTONDBLCLKNULL0;DialogBoxg_hinstanceLPCTSTRIDD_SETCITYhwndDLGPROCAboutCITYNUMBERSet;forintnum=0;numcitynum;num++{point.x=CgaObject.randomInt5705;point.y=CgaObject.randomInt50470;SendMessagehwndWM_LBUTTONDOWNNULL0;}}break;caseIDOK://选择开始菜单{HDChdc;hdc=GetDChwnd;GetLocalTimesystime;beforehourtime=systime.wHour;beforeminutetime=systime.wMinute;beforesecondtime=systime.wSecond;beforemillisecondtime=systime.wMilliseconds;SetTextColorhdcRGB1280128;TextOuthdc72010请稍等:正在计算!strlen请稍等:正在计算!;ReleaseDChwndhdc;ControlObject.DrawLineWait;ControlObject.DrawLinehwnd;GetLocalTimesystime;afterhourtime=systime.wHour;afterminutetime=systime.wMinute;aftersecondtime=systime.wSecond;aftermillisecondtime=systime.wMilliseconds;bdrawline=0;InvalidateRecthwndNULL1;//刷新消息}break;caseID_DefaultMap://选择默认地图菜单caseID_RoundMap://选择圆形地图菜单{//如果选择类型不变，不清空点ifControlObject.GetMapStyle==LOWORDwparam{break;}ControlObject.CleanAllUpDate;//清空当前所有点ControlObject.SetMapStylehwndwparam;InvalidateRecthwndNULL1;bdrawline=1;}break;caseID_GA_SET://选择遗传算法设置菜单{DialogBoxg_hinstanceLPCTSTRIDD_GA_BOXhwndDLGPROCAboutGASet;}break;caseID_ORDER_MUTATION://选择基于次序的变异菜单{DrawMutationStyle=ID_ORDER_MUTATION;CgaObject.SetMutationStylehwndwparam;}break;caseID_POSITION_MUTATION://选择基于位置的变异菜单{DrawMutationStyle=ID_POSITION_MUTATION;CgaObject.SetMutationStylehwndwparam;}break;caseID_REVERSE_MUTATION://选择倒位变异菜单{DrawMutationStyle=ID_REVERSE_MUTATION;CgaObject.SetMutationStylehwndwparam;}break;caseID_PARTIALLY_MATCHED_CROSSOVER:{//选择部分匹配交叉菜单DrawCrossoverStyle=ID_PARTIALLY_MATCHED_CROSSOVER;CgaObject.SetCrossoverStylehwndwparam;}break;caseID_ORDER_CROSSOVER://选择顺序交叉菜单{DrawCrossoverStyle=ID_ORDER_CROSSOVER;CgaObject.SetCrossoverStylehwndwparam;}break;caseID_CYCLE_CROSSOVER://选择循环交叉菜单{DrawCrossoverStyle=ID_CYCLE_CROSSOVER;CgaObject.SetCrossoverStylehwndwparam;}break;caseID_GREED_CROSSOVER://循环贪心交叉{DrawCrossoverStyle=ID_GREED_CROSSOVER;CgaObject.SetCrossoverStylehwndwparam;}break;caseID_FIXED_CITY://固定城市的求解主要用于测试{vectorPOINTpoint3030;intiallpoint
[60]={87791838346714464606858836987767478717158695462516737844194299764226025621854450134018402442253841264521443558356232};forintn=0;n30;n++{point30[n].x=iallpoint[2*n];point30[n].y=iallpoint[2*n+1];}forn=0;n30;n++{point30[n].x=point30[n].x+6;point30[n].y=point30[n].y+51;}forn=0;n30;n++{point.x=point30[n].x;point.y=point30[n].y;SendMessagehwndWM_LBUTTONDOWNNULL0;}}break;caseID_HELP_BOX://选择帮助菜单{DialogBoxg_hinstanceLPCTSTRIDD_HELP_BOXhwndDLGPROCAboutGASet;}//帮助对话框break;caseID_END://选择结束菜单{//SendMessagehwndWM_COMMANDID_CLEAN_ALL0;ControlObject.CleanAllUpDate;InvalidateRecthwndNULL1;bdrawline=1;}break;caseID_EXIT://选择退出菜单{SendMessagehwndWM_CLOSENULL0;}break;default:break;}}break;caseWM_DESTROY://结束应用程序{PostQuitMessage0;return0;}break;default:break;}returnDefWindowProchwndmsgwparamlparam;}////////////////////////////////////////////////////////////////////////////////////////////windows程序入口函数///////////////////////////////////////////intWINAPIWinMainHINSTANCEhinstanceHINSTANCEhprevinstanceLPSTRlpcmdlineintncmdshow{WNDCLASSEXwinclass;//窗口类HWNDhwnd;//窗口句柄MSGmsg;//消息//设置窗口类结构winclass.cbSize=sizeofWNDCLASSEX;winclass.style=CS_SAVEBITS|CS_DBLCLKS|CS_HREDRAW|CS_VREDRAW;winclass.lpfnWndProc=WindowProc;winclass.cbClsExtra=0;winclass.cbWndExtra=0;winclass.hInstance=hinstance;winclass.hIcon=LoadIconhinstanceMAKEINTRESOURCEIDI_ICON1;winclass.hCursor=LoadCursorNULLIDC_ARROW;winclass.hbrBackground=HBRUSHGetStockObjectWHITE_BRUSH;winclass.lpszMenuName=MAKEINTRESOURCE101;winclass.lpszClassName=WINDOW_CLASS_NAME;winclass.hIconSm=LoadIconhinstanceMAKEINTRESOURCEIDI_ICON1;//注册窗口类if!RegisterClassExwinclassreturn0;//创建窗口if!hwnd=CreateWindowExNULLWINDOW_CLASS_NAME遗传算法解TSP问题演示WS_OVERLAPPED|WS_CAPTION|WS_MINIMIZEBOX|WS_VISIBLE|WS_SYSMENU001000700NULLNULLhinstanceNULLreturn0;hinstance=g_hinstance;whileTRUE//不断从消息队列中获取消息{ifPeekMessagemsgNULL00PM_REMOVE{ifmsg.message==WM_QUITbreak;TranslateMessagemsg;DispatchMessagemsg;}}returnmsg.wParam;}/////////////////////////////////////////////////////////////////////////////开始初始化遗传算法的相关参数计算每个个体的适应值产生城市对城市进行编码是否符合终止条件？输出正确的TSP结果GEN=GEN+1选择交叉变异轮盘赌选择普通选择GXCXOXPMX基于次序的变异基于位置的变异倒位变异调用画图函数画点即设置城市程序将点的信息存入一个点向量中程序检测鼠标移动的具体信息用一个变量记入要产生的城市数将点向量中要除去的点找出来循环调用鼠标左键点击消息直到达到要求的城市数重新画点向量中的所有点此时该删除的点已从点向量中删除重新画地图即清除了所有的点DefaultMap类Map类RoundMap类。
个人认证
优秀文档
获得点赞 0
