全部栏目

首页 旅游资讯 线路攻略 景点大全 国内游 境外游 美食特产
您的当前位置：首页正文

TSP问题的遗传 算法求解方案 及 源程序 清单 (旅行商问题：包含实现介绍,源代码,程序测试结果说明)

2021-02-26 来源：易榕旅网
TSP问题的遗传算法求解方案

算法的软件实现

4.1 开发环境介绍

本文中的所有算法是在Visual C++ 6.0 的操作平台上进行开发的，并结合STL进行编程。

1、Visual C++ 6.0简介

Visual C++ 6.0 是微软公司最新出品的功能最为强大的可视化开放工具，是计算机界公认的最优秀的应用开发工具之一。Microsoft的基本类库使得开发Windows应用程序比以往任何时候都要容易。Visual C++作为一种程序设计语言，它同时也是一个集成开发工具，提供了软件代码自动生成和可视化的资源编辑功能。 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++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。这种现象有些类似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library），或者是Borland C++ Builder中的VCL (Visual Component Library)，但是它比二者具有更强的优势。更加值得一提的是，它具备以下几个区别于其它软件库的优点：

(1).经过类属编程方法精心组织的，可互换的编程模块能够提供比传统组件设

开始 是否符合终止 GEN=GEN+1 是 条件？ 输出正确的 TSP结果 初始化遗传算法的相关参数 产生城市 对城市进行编码 计算每个个体的适应值 否 世代进化 选择 普通选择 轮盘赌选择 交叉 图4.1 遗传算法解TSP的具体流程图

PMX 基于次序的变异 基于位置的变异 变异 倒位 变异 OX CX GX 计方法丰富得多的组合方式。

(2).类属编程方法设计也是将来为数据库，用户界面等专业领域开发组件的基础。

(3).通过使用某些编译机制并根据不同的算法进行具体的设计，可以在不损失效率的情况下实现对组件的概括。与此形成鲜明对照的是，其它一些具有复杂继承层次和大量使用虚函数的C++库结构则通常会降低效率。 4.2 算法实现的流程图

本设计的具体流程图如图4.1所示： 4.3 算法的各个模块及其详细设计思路 1．城市生成模块

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

图4.2 城市生成模块的设计思路

最后的效果如图4.3所示：

图4.3 TSP问题城市设置实现效果

2.地图选择模块

根据具体的需要，用户可以选择不同的地图，本设计提供的地图有：基于直角坐标系的地图和圆形地图，这两个地图由不同的类来产生。其中类DefaultMap产生直角坐标地图，类RoundMap产生圆形地图。图4.4所示的是直角坐标地图，图4.5所示的是圆形地图。

图4.4 直角坐标地图

图4.5 圆形地图

3. 遗传算法解TSP的参数设置模块

在具体的应用中，用户可以根据具体情况来设置遗传算法的相关参数，这些参数包括：

 交叉率：控制程序进行交叉的次数，在本设计中，先随机生成一个数，如果这

个数大于交叉率，则不交叉，如果这个数小于交叉率，则进行交叉。具体实现如下：

pick = float(randomInt(0,1000))/1000; if(pick < pcross) {

//进行交叉操作 } else

//不进行交叉操作

 变异率：控制程序进行变异的次数，在本设计中，先随机生成一个数，如果这

个数大于变异率，则不变异，如果这个数小于变异率，则进行变异操作。具体实现如下：

pick = float(randomInt(0,1000))/1000;

if(pick < pmutation) {

//进行变异操作 } else

//不进行变异操作

 种群大小：即种群中所含有的个体数量，选择一个合理的种群值，不但会使得

群体的多样性增强，防止遗传算法的“早熟现象”，还会使得遗传操作收敛得更快。

 世代数：控制遗传操作世代进化的次数，合理的世代数能够使得计算结果的优

劣程度不同。

图4.6 遗传算法解TSP的参数设置

 进化设置：根据子染色体与父染色体的关系，进化设置又分为两种：

·普通进化：完全模仿自然进化，子染色体可能比父染色体优秀，也可能比父染色体差。

·强制进化：选取子染色体中比父染色体优秀的染色体，杀死子染色体中比父染色体差的染色体。使得进化一直朝着优秀染色体的方向进化。 具体的实现效果如图4.6所示： 4.交叉算子选择模块

交叉操作是遗传算法中最重要的一环，交叉算法的优劣将最大限度地影响遗传算法的结果。本设计先根据国外专家提出的解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,child1,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时，变异算子的设计比交叉算子的设计灵活，任何具有局部搜索能力的算子都可以作为它的变异算子。本设计实现了三种变异：基于次序的变异，基于位置的变异，倒位变异。程序的具体选择模块如下： //变异算子选择模块

inline void CGA::mutation(Chrom& chr) {

switch (TempMutationStyle)

}

{

case ID_ORDER_MUTATION ://基于次序的变异

{ } break;

order_oriented_mutation(chr);

case ID_POSITION_MUTATION ://基于位置的变异

{ } break;

position_oriented_mutation(chr);

case ID_REVERSE_MUTATION://倒位变异

{ } break;

reverse_mutation(chr);

default : }

break;

6.具体输出信息显示模块

为了使程序运行时具体的算法和各种数据信息更加明确化，增加了信息显示模块，这样，在程序运行时用户可以掌握具体的数据信息，以便对各种算法进行比较。信息显示模块包括：计算结果模块，算法运行时间模块，所选遗传算子模块。下面分别对各个显示模块进行讨论：

 计算结果模块：输出的信息包括当前鼠标的横坐标，当前鼠标的纵坐标，这两

个信息是为了用户设置城市时参考的。城市总数信息是用户设置的城市数目。总距离信息是经过计算的TSP问题的最优路径长度，它是屏幕上象素点间的距离。

 算法运行时间模块：包括算法启动前时间，它是用户设置完城市，进行求解时

刻的时间；算法结束时间，它是程序运行完成，正确输出TSP结果时刻的时间；算法耗费时间，它是进行遗传算法求解TSP时算法所消耗的时间。

 所选遗传算子模块：它显示的是用户选择了那种交叉算子，那种遗传算子，以

便于对各种算法比较时使用。

具体的显示如图4.7所示：

图4.7 各种信息显示图

4.4 设计中主要的类和函数的功能 1. Map类，DefaultMap类，RoundMap类

这三个类均为画图相关的类，其继承关系为： 继承 基类 Map类

继承 图4.8 画图类继承关系

DefaultMap类 RoundMap类 其中，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.6 11.8 12.7 11.7 12.6 12.8 11.2 10.8 10.6 11.9 72 28 8 65 88 44 50 44 87 54 最优解 517 492 505 515 492 509 519 526 549 491 计算平均值有平均最优解为：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.1 30个城市位置坐标

城市编号 1 2 3 4 5 6 7 8 坐标 (40,406) (33,39) (268,183) (277,377) (361,103) (104,4) (180,26) (160,70) 城市编号 11 12 13 14 15 16 17 18 坐标 (190,323) (401,152) (291,201) (620,235) (117,154) (546,305) (70,197) (468,171) 城市编号 21 22 23 24 25 26 27 28 坐标 (2,290) (521,92) (172,43) (440,150) (252,147) (346,343) (461,416) (436,258) 9 10 (194,181) (626,395) 19 10 (466,258) (234,233) 29 30 (322,80) (228,357) 5.3.2 模拟实验结果

对于上述各算法，分别进行了计算机模拟实验，计算中采用的有关数据如下：城市数为30，群体规模为100，交叉概率为0.8，变异概率为0.1，群体更新100代结束，采用强制进化方式进化，每个算法采集了10组数据。其中，TSP旅程长度为屏幕上象素点之间的距离，时间为算法所消耗的CPU时间。30个城市的坐标如表5.1所示：

对每个算法采集的数据，计算其平均结果，表5.2中的所有数据都是经过10次测试得出的统计平均结果。

表5.2 各种遗传操作组合求解TSP问题模拟实验结果比较

算法 GA0 GA1 GA2 GA3 GA4 GA5 最佳解 2698.4 2682.1 2675.9 2524.8 2524.3 2523.5 时间(s) 19.266 18.110 18.234 16.125 16.187 16.309 算法 GA6 GA7 GA8 GA9 GA10 GA11 最佳解 2947.2 2918.6 2903.9 2521.6 2523.9 2522.7 时间(s) 23.234 19.250 19.360 24.695 24.685 23.856 5.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.3 30个城市坐标

城市编号 1 2 3 4 5 6 7 8 9 10

坐标 (87,7) (91,83) (83,46) (71,44) (64,60) (68,58) (83,69) (87,76) (74,78) (71,71)

城市编号 11 12 13 14 15 16 17 18 19 10

坐标 (58,69) (54,62) (51,67) (37,84) (41,94) (2,99) (7,64) (22,60) (25,62) (18,54)

城市编号 21 22 23 24 25 26 27 28 29 30

坐标 (4,50) (13,40) (18,40) (24,42) (25,38) (41,26) (45,21) (44,35) (58,35) (62,32)

5.4.1 改进循环交叉算法与循环交叉算法的数值比较

对于循环交叉测试的十组数据如下：

时间(s) 15.6 14.8 14.7 14.7 15.6 16.8 14.6 15.8 14.6 15.9 72 28 8 65 88 44 50 44 87 54 最优解 684 717 705 715 692 709 669 676 689 691 对于改进的循环交叉测试的十组数据如下：

时间(s) 11.9 11.7 12.3 11.7 12.1 12.8 11.2 11.8 10.4 10.9 69 03 28 65 88 44 50 44 87 54 最优解 615 621 640 632 609 651 603 621 630 612 对于循环交叉平均最优解为：694.7，平均时间为：15.3712s。对于改进循环交叉平均最优解为：623.4，平均时间为：11.7332s。通过对比可知，改进后的算法明显优于改进前的算法。

5.4.2 改进循环贪心交叉算法与循环贪心交叉算法的数值比较

对于改进的循环贪心交叉测试的十组数据如下：

时间(s) 12.6 13.3 12.9 12.4 12.5 12.2 12.9 11.5 12.8 12.9 87 59 3 22 00 81 38 00 59 53 最优解 610 616 643 644 655 643 590 699 613 617 对于循环贪心交叉测试的十组数据如下：

时间(s) 14.2 13.6 14.7 14.1 13.7 14.5 13.4 14.3 13.9 14.7 50 25 50 72 50 00 06 12 85 34 最优解 580 614 626 594 624 651 626 570 694 586 对于改进的循环贪心交叉平均最优解为：633.0，平均时间为：12.6429s。对于循环贪心交叉平均最优解为：616.5，平均时间为：14.1484s。通过对比可知，改进后的算法时间上明显优于改进前的算法。主要是减少了随机查找数据的时间，但由于改进后的算法是循环查找未扩展的城市，因此使得种群的多样性减少了，即使得平均最优解要比改进前差一些，但对于大量城市的TSP问题来说，节省时间是很值得考虑的。

6 结论

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

在本文研究基础上，还可以进一步开拓以下几个方向的研究工作: 1.将遗传算法运用于大规模的旅行商问题；

2.将许多实际应用问题(如印制电路板的钻孔路线方案、连锁店的货物陪送路线等)建模为TSP问题，并应用遗传算法来解决；

3.如何获得更好的性能是遗传算法研究中的重要课题。如何在保证求解质量的同时降低时间的开销，如何针对具体问题寻找优化的并行计算策略和群体划分策略，也是遗传算法中需要进一步深入研究的重要课题。

遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，需要进一步地发展和完善，但它已为解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用过程中会出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的专业领域中。随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键的作用。

程序核心代码

一．资源类

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_EDIT2 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_CUSTOMMAP 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 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 _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: virtual 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 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() {

} { }

bool operator()(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); equal_point(const POINT& _val):val(_val)

} private: POINT val; };

/////////////////////////////////////////////////////////////////////////////

四．直角坐标地图类

1.头文件

///////////////defaultmap.h////////////////////////////////////////////////// #pragma once

#include \"map.h\"

#define DIVISIONS1 10 #define DIVISIONS2 6 class DefaultMap:public Map {

public: void DrawMap(HWND hwnd,HDC hdc);//画地图

//void SaveClickPoint( );//保存格式为地图中的位置 void DelAllPoint ( );//清除vecpoin所有点

//在地图上画点(参数为实际位置)

void DrawPonit(HWND hwnd,const POINT&); //将地图上已存在的点(参数为实际位置)删除

void SmearPonit(HWND hwnd,const POINT&);

void AddPoint(const POINT&);//保存POINT(参数为实际位置)到向量 void SubPoint(const POINT&);//删除POINT(参数为实际位置)到向量 //获得所有已点击的点的位置(实际值) vector GetAllClickPoint( );

POINT GetMapPoint (const POINT& point);//实际POINT在地图位置

POINT GetRealPoint (const POINT& point);//地图POINT实际位置 protected:

//找到该点附近的像素点iarea为该点的半径

vector FindAroundPoint(const POINT& point,int iarea);

};

/////////////////////////////////////////////////////////////////////////////

2.源文件

//////////////////////////defaultmap.cpp///////////////////////////////////// #include \"defaultmap.h\"

/////////////////////画地图////////////////////////////////////////////////// void DefaultMap::DrawMap(HWND hwnd,HDC hdc ) {

HPEN hpen;

hpen=CreatePen(PS_SOLID,1,RGB(0,128,128)); ///创建画笔 SelectObject(hdc,hpen);

for (int x = 0 ; x < DIVISIONS1 ; x++) //10 for (int y = 0; y < DIVISIONS2 ; y++) //6 {

Rectangle (hdc,5+x * 70,50+y * 70, 5+(x + 1) * 70,50+(y + 1) * 70); }

DeleteObject(hpen); //删除画笔

return; }

/////////////////////////////////////////////////////////////////////////////

//////////////////////保存删除POINT(在地图位置)到向量//////////////////////// /*void DefaultMap::SaveClickPoint() {

fstream outFile( \"copy.text\以写方式打开文件 if ( !outFile ) { }

cerr << \"unable to open input file: \"<< \" -- bailing out!\\n\"; return ;

if(vecpoint.size()<=0) { return; }

outFile<<\"#\"<<\"DEFAULT_MAP_NAME\"<<'\\n'; ///以后有用 outFile<<\"#\"<outFile<outFile<return;

} */

/////////////////////////////////////////////////////////////////////////////

/////////////////删除所有点////////////////////////////////////////////////// void DefaultMap::DelAllPoint() {

if(vecpoint.size()<=0) { return; }

vecpoint.clear(); return;

}

/////////////////////////////////////////////////////////////////////////////

/////////////////////找到该点附近的点////////////////////////////////////////

vector DefaultMap::FindAroundPoint(const POINT& point,int iarea)

{ //iarea为该点的半径

POINT temppoint;

vector< POINT> vecroundpoint;

temppoint.x =point.x-6 ;// 判断点是否在有效区域//-51 temppoint.y =point.y-51 ;//-51

if(temppoint.x<0||temppoint.y<0||temppoint.x>700||temppoint.y>420) { return vecroundpoint; } iarea=abs(iarea);//防止iarea小于零

for(int n=-iarea;n<1+iarea;n++) for(int m=iarea;m>-1-iarea;m--) { temppoint.x=point.x+m; }

temppoint.y=point.y+n;

vecroundpoint.push_back( temppoint ); temppoint.x=point.x+n; temppoint.y=point.y+m;

vecroundpoint.push_back( temppoint );

return vecroundpoint;

}

/////////////////////////////////////////////////////////////////////////////

///////在地图上画点/////在地图上画点(参数为实际位置)///////////////////////// void DefaultMap::DrawPonit( HWND hwnd ,const POINT& point) {

int cx =point.x-6 ;// 判断点是否在有效区域 int cy =point.y-51;

if(cx<0||cy<0||cx>700||cy>420)

}

{

return; }

AddPoint( point ); HDC hdc; hdc=GetDC(hwnd); HPEN hpen;

hpen=CreatePen(PS_DOT,5,RGB(255,0,0)); SelectObject(hdc,hpen); //选择对象进DC

Ellipse(hdc,point.x+2,point.y+2,point.x-2,point.y-2); ////画圆点 DeleteObject(hpen); ReleaseDC (hwnd, hdc); return;

/////////////////////////////////////////////////////////////////////////////

///////添加和减少点(在地图位置)到向量/////保存POINT(参数为实际位置)到向量//// void DefaultMap::AddPoint(const POINT& point) { POINT tempoint=point;

if( vecpoint.size()!=0 &&

find_if( vecpoint.begin(),vecpoint.end(),

equal_point(tempoint) )!=vecpoint.end() ) { return;

} //保证点不重复

vecpoint.push_back( tempoint );

}

/////////////////////////////////////////////////////////////////////////////

//////////////清除一个指定的点/////////////////////////////////////////////// void DefaultMap::SubPoint(const POINT& point) {

if(vecpoint.size()<=0) { }

return;

vector< POINT> vecroundpoint;

vector ::iterator Iter1;

vecroundpoint=FindAroundPoint(point,2); //获得该点附近的像素点 if(vecroundpoint.size()==0 ) {

return; }

Iter1=find_first_of( vecpoint.begin(),vecpoint.end(),vecroundpoint.begin(), vecroundpoint.end(),equal_point() );

if(Iter1==vecpoint.end()) { return; }

vecpoint.erase(Iter1); }

/////////////////////////////////////////////////////////////////////////////

///将地图上已存在的点(参数为实际位置)删除//擦掉该点(重画所有的点和地图)////// void DefaultMap::SmearPonit( HWND hwnd ,const POINT& point) {

HDC hdc;

hdc=GetDC(hwnd);

int n=vecpoint.size(); SubPoint(point);

if(n==vecpoint.size()) //没找到则向量大小不变 {

return; }

DrawMap( hwnd, hdc );

ReleaseDC (hwnd, hdc);

for(n=0;n}

/////////////////////////////////////////////////////////////////////////////

////////////////////获得所有已点击的点的位置///////////////////////////////// vector DefaultMap::GetAllClickPoint( ) { }

return vecpoint;

/////////////////////////////////////////////////////////////////////////////

///////////////////将地图与实际位置之间转换//////////////////////////////////

POINT DefaultMap::GetRealPoint(const POINT& point) //实际位置转换为地图位置 {

POINT temppoint;

temppoint.x=point.x-6 ;

temppoint.y=point.y-51;// 判断点是否在有效区域 { }

temppoint.x=-1; temppoint.y=-1; return temppoint;

if(temppoint.x<0||temppoint.y<0||temppoint.x>700||temppoint.y>420)

temppoint.x+=6;

temppoint.y+=51; return temppoint; }

/////////////////////////////////////////////////////////////////////////////

/////地图位置转换为实际位置////////////////////////////////////////////////// POINT DefaultMap::GetMapPoint(const POINT& point) { }

/////////////////////////////////////////////////////////////////////////////

POINT temppoint=point; temppoint.x-=6;

temppoint.y-=51;

if( temppoint.x<0||temppoint.y<0||700temppoint.y=-1; return temppoint;

}

return temppoint;//点在有效区域

五．圆形坐标地图类

1.头文件

//////////////////roundmap.h///////////////////////////////////////////////// #pragma once #include \"map.h\"

class RoundMap:public Map {

public:

RoundMap();

void DrawMap(HWND hwnd,HDC hdc);//画地图 POINT FindAroundPoint(const POINT&);

// void SaveClickPoint( );//保存格式为地图中的位置 void DelAllPoint ( );//清除vecpoin所有点 //在地图上画点(参数为实际位置)

void DrawPonit(HWND hwnd ,const POINT&); //将地图上已存在的点(参数为实际位置)删除 void SmearPonit(HWND hwnd ,const POINT&);

void AddPoint(const POINT&);// 保存POINT(参数为实际位置)到向量 void SubPoint(const POINT&);// 删除POINT(参数为实际位置)到向量 vector GetAllClickPoint( );//获得所有已点击的点的位置(实际值)

protected: vector mappoint; };

/////////////////////////////////////////////////////////////////////////////

2.源文件

///////////////////////////////////roundmap.cpp////////////////////////////// #include \"roundmap.h\"

///////圆形地图////////////////////////////////////////////////////////////// RoundMap::RoundMap() { }

///////////////////////////////////////////////////////////////////////////// //////////////////////画地图/////////////////////////////////////////////////

void RoundMap::DrawMap(HWND hwnd,HDC hdc ) ////n表示线的条数 {

RECT rect;

rect.bottom=450;///// 无效区域 （背景区域） rect.left=100; rect.right=740;

// do initialization stuff here vector point60(60); int iallpoint[120]= {

305,-21,324,-23,344 , -23 ,365 ,-19,384, -13, 402, -6,421, 4,437, 16 ,454 ,28,468 ,41,

482, 57, 493, 74,503, 93,509, 113, 515, 132, 518, 152,520,173,518, 193,514, 214,510,233, 501, 254,493, 271,481, 287,468,304, 456, 318, 439,329,422, 342,284, -16,263 ,-12,246, -4, 225, 3, 210, 17,194, 28,178, 42, 166, 56, 156, 74,145, 93,137, 112,133,131,129, 153, 127, 173,128,195,132, 213,137, 233,146 ,255, 155 ,272,165, 290,180, 307,194,318,208, 331,

227 ,343,244,352,265, 360,282 ,365,303 ,366, 326, 369,343, 368,368, 365,385, 360,404, 353 };

for(int n=0;n<60;n++) { }

point60[n].x=iallpoint[2*n]; point60[n].y=iallpoint[2*n+1];

for(n=0;n<60;n++) {

point60[n].x=point60[n].x+21; point60[n].y=point60[n].y+81;

}

mappoint=point60;

rect.top=0;

HBRUSH hbrush; //擦除背景区域 hbrush=CreateSolidBrush( RGB(255,255,255) ); FillRect(hdc,& rect, hbrush );

SelectObject (hdc, GetStockObject (BLACK_PEN)) ; for(int n=0;n<60;n++) { }

Ellipse (hdc, mappoint[n].x-5, mappoint[n].y-5, mappoint[n].x+5, mappoint[n].y+5);

}

//////////////////////保存删除POINT（在地图位置)到向量/////////////////////// /*void RoundMap::SaveClickPoint() {

fstream outFile( \"copy.text\if ( !outFile ) { }

if(vecpoint.size()<=0)

{ return; }

outFile<<\"#\"<<\"Round_Map_NAME\"<<'\\n'; ///以后有用 outFile<<\"#\"<outFile<outFile<cerr << \"unable to open input file: \"<< \" -- bailing out!\\n\"; return ;

} return;

}*/

/////////////////////////////////////////////////////////////////////////////

////////////删除所有的点///////////////////////////////////////////////////// void RoundMap::DelAllPoint() {

if(vecpoint.size()<=0) { }

return;

vecpoint.clear(); return; }

/////////////////////////////////////////////////////////////////////////////

////////////////找到该点是否有所在区域的值/////////////////////////////////// POINT RoundMap::FindAroundPoint( const POINT& point) { vector< POINT> vecroundpoint; POINT temppoint;

vector ::iterator Iter; for(int n=-3;n<4;n++) for(int m=3;m>-4;m--) { }

Iter=find_first_of(mappoint.begin(),mappoint.end(),vecroundpoint.begin(), vecroundpoint.end(),equal_point()); if(Iter==mappoint.end()) {

temppoint.x=-1; temppoint.x=point.x+m;

temppoint.y=point.y+n;

vecroundpoint.push_back(temppoint); //获得该点附近的点 temppoint.x=point.x+n; temppoint.y=point.y+m;

vecroundpoint.push_back(temppoint); //获得该点附近的点

temppoint.y=-1; return temppoint; }

return (*Iter);

}

/////////////////////////////////////////////////////////////////////////////

/////////////////在地图上画点或将地点上以存在的点从地图上删除//////////////// void RoundMap::DrawPonit( HWND hwnd ,const POINT& point)

{ //在地图上画点(参数为实际位置)//

HDC hdc;

POINT temppoint,Drawpoint; temppoint.x=-1; temppoint.y=-1;

Drawpoint=FindAroundPoint(point); if(Drawpoint.x==temppoint.x&&Drawpoint.y==temppoint.y)

{ return;} AddPoint( point );

hdc=GetDC( hwnd );

HBRUSH hbrush=CreateSolidBrush( RGB(255,0,0) ); SelectObject( hdc,hbrush );

Ellipse (hdc, (Drawpoint).x-5, (Drawpoint).y-5, (Drawpoint).x+5, (Drawpoint).y+5) ; DeleteObject( hbrush );

ReleaseDC (hwnd, hdc);

}

/////////////////////////////////////////////////////////////////////////////

////////将地图上已存在的点（参数为实际位置）重画///////////////////////////// void RoundMap::SmearPonit( HWND hwnd ,const POINT& point) { }

int n=vecpoint.size();

SubPoint(point);

if(n==vecpoint.size()) //在其他地区(60个之外)点击右键则向量大小不变 { return;}

for(n=0;n/////////////////////////////////////////////////////////////////////////////

///////////////////添加和减少点（ 在地图位置)到向量//////////////////////////

void RoundMap::AddPoint(const POINT& point)//保存POINT(参数为实际位置)到向量 {

POINT temppoint,Drawpoint;

temppoint.x=-1; temppoint.y=-1;

Drawpoint=FindAroundPoint(point); if(Drawpoint.x==temppoint.x)//表示未找到点 }

{ return;}

if(find_if(vecpoint.begin(),vecpoint.end(),

equal_point(Drawpoint))!=vecpoint.end()) { return;

} //保证点不重复 vecpoint.push_back(Drawpoint);

///////////////////////////////////////////////////////////////////////////// //////////删除点///////////////////////////////////////////////////////////// void RoundMap::SubPoint(const POINT& point) {

POINT temppoint,Drawpoint; vector ::iterator Iter; temppoint.x=-1;

temppoint.y=-1;

Drawpoint=FindAroundPoint(point); if(Drawpoint.x==temppoint.x) {

}

return;

}

Iter=remove_if(vecpoint.begin(),vecpoint.end(),equal_point( Drawpoint)); if( Iter==vecpoint.end( )) { }

vecpoint.erase(Iter);

return;

/////////////////////////////////////////////////////////////////////////////

////////////////////获得所有已点击的点的位置///////////////////////////////// vector RoundMap::GetAllClickPoint( ) {

return vecpoint;

}

/////////////////////////////////////////////////////////////////////////////

六．控制类

1.头文件

/////////////control.h/////////////////////////////////////////////////////// #pragma once #include \"head.h\" #include \"map.h\"

#include \"defaultmap.h\" #include \"roundmap.h\" #include \"connectline.h\" #include \"ga.h\"

#include \"resource.h\" //算法启动前时间

extern WORD beforehourtime; extern WORD beforeminutetime; extern WORD beforesecondtime; extern WORD beforemillisecondtime; //算法结束时的时间 extern WORD afterhourtime; extern WORD afterminutetime;

extern WORD aftersecondtime; extern WORD aftermillisecondtime;

extern UINT DrawMutationStyle;//进化类型 extern UINT DrawCrossoverStyle;//交叉类型 class Control {

public: Control( );//初始化数据

void welcome(HWND hwnd);//显示欢迎窗口(开始)

//void help(HWND hwnd);//完整的帮助 UINT GetMapStyle( );//获得当前地图类型

void SetMapStyle(HWND hwnd,WPARAM wParam);//设置地图类型 //交叉率,变异率,种群大小,最大世代数

void SetGaInformation(float fpcross,float fpmutation,

int fpopsize,int fmaxgen); void CleanAllUpDate( );//清除所有点 //显示其它与鼠标位置或地图相关信息

void DisPlay(HWND hwnd,const POINT& point,bool bdrawline); void DrawAllPoint(HWND hwnd );//画出所有的点 void DrawMap(HWND hwnd,HDC hdc);//画地图

void DrawTruePoint(HWND hwnd,const POINT& point);//画点 void DrawFalsePoint(HWND hwnd,const POINT& point);//去掉点 void DrawLineWait( );//画线的准备 void DrawLine(HWND hwnd );//画线 float Getpcross( ) //获得交叉概率

{ return pcross;

}

float Getpmutation( ) //获得变异概率 { return pmutation; }

int Getpopsize( )//获得种群大小

{ return popsize;

}

int Getmaxgen( ) //获得世代数

{

return maxgen; }

int Getcitynumber() //获得城市数 {

return citynumber; }

void SetPower(bool n) //设置世代进化类型

{ power=n;

}

bool GetPower( )//获得世代进化类型

{ return power; } private:

UINT MapStyle;//标志当前地图类型

float pcross;//交叉率 float pmutation;//变异率 int popsize;//种群大小 int maxgen;//最大世代数 int citynumber;//城市数目

bool power;

DefaultMap DefaultMapObject; RoundMap RoundMapObject; Line LineObject;

Map *MapObject; };

///////////初始化数据////////

inline Control::Control( ):pcross(0.6f),pmutation (0.2f),popsize (30), maxgen(30),citynumber(30),

MapObject( &DefaultMapObject), { }

/////////////////////////////////////////////////////////////////////////////

return;

MapStyle(ID_DefaultMap),power(1)

2.源文件

/////////////////////////control.cpp///////////////////////////////////////// #include \"control.h\" WORD beforehourtime; WORD beforeminutetime; WORD beforesecondtime; WORD beforemillisecondtime; WORD afterhourtime; WORD afterminutetime; WORD aftersecondtime;

WORD aftermillisecondtime;

UINT DrawMutationStyle=ID_ORDER_MUTATION;//进化类型

UINT DrawCrossoverStyle=ID_PARTIALLY_MATCHED_CROSSOVER;//交叉类型 //////////////////////////提供提示和帮助信息///////////////////////////////// void Control::welcome(HWND hwnd) {

//创建一个对话框显示提示信息

MessageBox(hwnd, \"欢迎进入遗传算法解TSP问题演示系统!\ \"遗传算法解TSP问题演示实验\ return; }

///////////////////////////////////////////////////////////////////////////// ////////帮助/////////////////////////////////////////////////////////////////

/*void Control::help(HWND hwnd)

{ }*/

/////////////////////////////////////////////////////////////////////////////

////////////////获得当前地图类型///////////////////////////////////////////// UINT Control::GetMapStyle( ) {

return MapStyle;

}

/////////////////////////////////////////////////////////////////////////////

//////////////////设置地图类型/////////////////////////////////////////////// void Control::SetMapStyle(HWND hwnd, WPARAM wParam) {

HMENU hMenu ; hMenu = GetMenu (hwnd) ;

switch ( LOWORD(wParam) ) {

case ID_DefaultMap : {

}

MapObject= &DefaultMapObject;

break;

case ID_RoundMap : { MapObject=&RoundMapObject ;

}

break;

default : break; }

CheckMenuItem (hMenu, MapStyle, MF_UNCHECKED); MapStyle=LOWORD (wParam);

CheckMenuItem (hMenu, MapStyle, MF_CHECKED ); return;

}

/////////////////////////////////////////////////////////////////////////////

///////////////遗传算法信息//////////////////////////////////////////////////

void Control::SetGaInformation(float fpcross ,float fpmutation , int fpopsize , int fmaxgen)

{ //依次:交叉率,变异率,种群大小,最大世代数.

if( fpcross!=0.0 ) { pcross=fpcross; }

if(fpmutation!=0.0)

{

pmutation=fpmutation; }

if( fpopsize!=0|| fpopsize!=1) { }

if( fmaxgen!=0|| fmaxgen!=1 ) {

maxgen=fmaxgen; } return;

popsize=fpopsize;

}

/////////////////////////////////////////////////////////////////////////////

////////////////////////////清除所有点/////////////////////////////////////// ///////////////Map *MapObject;/////// void Control::CleanAllUpDate( ) { MapObject->DelAllPoint(); }

/////////////////////////////////////////////////////////////////////////////

/////////////////////////显示其它与鼠标位置或地图相关信息//////////////////// void Control::DisPlay( HWND hwnd ,const POINT& point,bool bdrawline) {

HDC hdc;

hdc=GetDC(hwnd);

POINT temppoint;

char buffer[80]; SetBkMode(hdc,OPAQUE);

HPEN hpen;

SetTextColor(hdc,RGB(0,0,255) );

TextOut( hdc,250,10,\"遗传算法解TSP问题演示地图\ strlen(\"遗传算法解TSP问题演示地图\") );

SetTextColor( hdc,RGB(0,0,0) ); TextOut( hdc,50,500, \"注意: 点击鼠标左键设置城市点,点击鼠标右键清空一个点。\

strlen(\"注意: 点击鼠标左键设置城市点,点击鼠标右键清空一个点。\") ); return ;

TextOut( hdc,82,530, \" 点击菜单开始或ENTER键进行寻路,详细信息请选菜单中帮助。\

strlen(\" 点击菜单开始或ENTER键进行寻路,详细信息请选菜单中帮助。\")

);

////算法运行时间显示模块/////////////////////////////////////////////////////

WORD tempbeforehourtime=beforehourtime;

WORD tempbeforeminutetime=beforeminutetime;

WORD tempbeforesecondtime=beforesecondtime;

WORD tempbeforemillisecondtime=beforemillisecondtime; WORD tempafterhourtime=afterhourtime; WORD tempafterminutetime=afterminutetime;

WORD tempaftersecondtime=aftersecondtime;

WORD tempaftermillisecondtime=aftermillisecondtime; hpen=CreatePen(PS_SOLID,1,RGB(0,128,128)); ///创建画笔 SelectObject(hdc,hpen);

Rectangle (hdc,710,180,960,340);

DeleteObject(hpen);

SetTextColor(hdc,RGB(0,0,0) );

TextOut( hdc,780,170,\"算法运行时间\算法运行时间\") );

TextOut( hdc,730,190,\"算法启动前时间:\算法启动前时间:\") ); sprintf(buffer,\"%d 时,%d 分,%d 秒,%d 微秒\

beforeminutetime,beforesecondtime,beforemillisecondtime); TextOut(hdc,730,210,buffer,strlen(buffer));

TextOut( hdc,730,240,\"算法结束时间:\算法结束时间:\") ); sprintf(buffer,\"%d 时,%d 分,%d 秒,%d 微秒\

afterminutetime,aftersecondtime,aftermillisecondtime);

intervalhourtime; intervalminutetime; intervalsecondtime; intervalmillisecondtime;

TextOut(hdc,730,260,buffer,strlen(buffer));

WORD WORD WORD WORD

int flag=0;

if( (aftermillisecondtime{

aftersecondtime=aftersecondtime-1;

intervalmillisecondtime=aftermillisecondtime+1000-beforemillisecondtime; flag++; }

else

intervalmillisecondtime=aftermillisecondtime-beforemillisecondtime; flag=0;

if( (aftersecondtimeafterminutetime=afterminutetime-1;

intervalsecondtime=aftersecondtime+60-beforesecondtime; flag++;

else

intervalsecondtime=aftersecondtime-beforesecondtime; flag=0; if( (afterminutetime{ } else

intervalminutetime=afterminutetime-beforeminutetime; intervalhourtime=afterhourtime-beforehourtime;

TextOut( hdc,730,290,\"算法耗费时间:\算法耗费时间:\") ); sprintf(buffer,\"%d 时,%d 分,%d 秒,%d 微秒\ intervalminutetime,intervalsecondtime,intervalmillisecondtime); TextOut(hdc,730,310,buffer,strlen(buffer));

afterhourtime=afterhourtime-1;

intervalminutetime=afterminutetime+60-beforeminutetime; flag++;

beforehourtime=tempbeforehourtime; beforeminutetime=tempbeforeminutetime; beforesecondtime=tempbeforesecondtime;

beforemillisecondtime=tempbeforemillisecondtime; afterhourtime=tempafterhourtime; afterminutetime=tempafterminutetime; aftersecondtime=tempaftersecondtime; aftermillisecondtime=tempaftermillisecondtime;

/////////////////////////////////////////////////////////////////////////////

////所用遗传算子显示模块///////////////////////////////////////////////////// hpen=CreatePen(PS_SOLID,1,RGB(0,128,128)); ///创建画笔

SelectObject(hdc,hpen);

Rectangle (hdc,710,370,960,490);

DeleteObject(hpen);

SetTextColor(hdc,RGB(0,0,0) );

TextOut( hdc,780,360,\"所选遗传算子\所选遗传算子\") ); TextOut( hdc,730,390,\"交叉算子:\交叉算子:\") ); TextOut( hdc,730,440,\"变异算子:\变异算子:\") ); switch (DrawCrossoverStyle) {

case ID_PARTIALLY_MATCHED_CROSSOVER : { TextOut( hdc,760,410,\"部分匹配交叉\部分匹配交叉\") );

} break;

case ID_ORDER_CROSSOVER : { TextOut( hdc,760,410,\"顺序交叉\顺序交叉\") );

}

break;

case ID_CYCLE_CROSSOVER : { TextOut( hdc,760,410,\"循环交叉\循环交叉\") );

}

break;

case ID_GREED_CROSSOVER: { TextOut( hdc,760,410,\"改进交叉(循环贪心交叉)\

}

strlen(\"改进交叉(循环贪心交叉)\") );

break; default :

break;

}

switch (DrawMutationStyle) {

case ID_ORDER_MUTATION :

{ TextOut( hdc,760,460,\"基于次序的变异\基于次序的变异\") );

} break;

case ID_POSITION_MUTATION :

{ TextOut( hdc,760,460,\"基于位置的变异\基于位置的变异\") );

} break;

case ID_REVERSE_MUTATION: { TextOut( hdc,760,460,\"倒位变异\倒位变异\") );

} break; default : break;

}

/////////////////////////////////////////////////////////////////////////////

////计算结果显示模块///////////////////////////////////////////////////////// hpen=CreatePen(PS_SOLID,1,RGB(0,128,128)); ///创建画笔

SelectObject(hdc,hpen);

Rectangle (hdc,710,50,960,150); DeleteObject(hpen);

SetTextColor(hdc,RGB(0,0,0) );

TextOut( hdc,780,40,\"计算结果\计算结果\") ); //点菜单开始或ENTER进行寻路,详细信息请选菜单中帮助

SetTextColor(hdc,RGB(0,0,0)); //black

sprintf(buffer,\"城市总数: %d\

TextOut(hdc,730,120,buffer,strlen(buffer));//

if( bdrawline==1 ) // 当前未准备好所有的点 { TextOut(hdc,850,120,\" 总距离: 0 \总距离: 0 \")); }

else {

sprintf(buffer,\" 总距离:%d\

TextOut(hdc,850,120,buffer,strlen(buffer)); //显示连线总长

}

if(MapStyle==ID_DefaultMap ) //默认地图才显示坐标 {

temppoint=DefaultMapObject.GetMapPoint(point);

//获得地图上的点位置700*420 if(-1!=temppoint.x ) //测试点在有效区没有 { SetTextColor(hdc,RGB(0,0,0));

} //没在无效区域则为黑笔，只是显示坐标点的颜色 else

{ SetTextColor(hdc,RGB(255,0,0)); } //在无效区域则为红笔

sprintf(buffer,\"当前鼠标的横坐标: %ld\

TextOut(hdc,730,70,buffer,strlen(buffer));//

sprintf(buffer,\"当前鼠标的纵坐标: %ld\TextOut(hdc,730,90,buffer,strlen(buffer));

}

ReleaseDC (hwnd, hdc);

///////////////////////////////////////////////////////////////////////////// return; }

/////////////////////////////////////////////////////////////////////////////

////////////////////////以下为画地图///////////////////////////////////////// ////////////Map *MapObject;////////////////////////////// void Control::DrawMap(HWND hwnd,HDC hdc ) {

MapObject->DrawMap( hwnd,hdc); return;

}

/////////////////////////////////////////////////////////////////////////////

//////////////画出所有在向量里的点///////////////////////////////////////////

////////////Map *MapObject;//////////////////////////////

/////vector GetAllClickPoint( );//获得所有已点击的点的位置(实际值)/// void Control::DrawAllPoint(HWND hwnd) { //vector GetAllClickPoint( )//获得所有已点击的点的位置(实际值)

for( int n=(MapObject->GetAllClickPoint( )).size( );n>0;)

{ MapObject->DrawPonit(hwnd, (MapObject->GetAllClickPoint( ) )[--n] ); }

return;

}

/////////////////////////////////////////////////////////////////////////////

//////////////画出所有在向量里的点/////////////////////////////////////////// void Control::DrawTruePoint( HWND hwnd ,const POINT& point ) {

MapObject->DrawPonit( hwnd , point); return;

}

///////////////////////////////////////////////////////////////////////////// //////清除点/////////////////////////////////////////////////////////////////

void Control::DrawFalsePoint( HWND hwnd ,const POINT& point ) {

MapObject->SmearPonit(hwnd , point); return;

}

/////////////////////////////////////////////////////////////////////////////

//画线的准备和画线///设置矩阵////设置遗传算法参数函数////设置遗传算法接口//// ////////CGA ga;*************************************** /////////Line LineObject;//////////////////////// void Control::DrawLineWait( ) {

CGA ga;

if( (MapObject->GetAllClickPoint( )).size( )<=2) { return; }

//将地图中所有点一位置作参数

LineObject.SetPointMatrix(MapObject->GetAllClickPoint( ) );

//产生点的矩阵 ga.preSet(LineObject.GetPointMatrix(),pcross, pmutation,popsize,maxgen,power+1);//矩阵作参数 LineObject.GaInterface( ga.start() );

}

///////////////////////////////////////////////////////////////////////////// /////////画线////////////////////////////////////////////////////////////////

//////////vector GetPointPosition( )//获得存储点的位置/////// /////////Line LineObject;//////////////////////// void Control::DrawLine(HWND hwnd) {

if(LineObject.GetPointPosition( ).size( )<=0) { return;

}

if(LineObject.GetPointPosition( ).size( )<=2) {

}

LineObject.DrawLine(hwnd,MapObject->GetAllClickPoint( ));

return; }

LineObject.DrawLine(hwnd,LineObject.GetPointPosition( ));

/////////////////////////////////////////////////////////////////////////////

七．连线类

1.头文件

///////////////connectline.h///////////////////////////////////////////////// #pragma once #include \"map.h\" class Line

{

public: void SetPointMatrix(const vector& );//由已知的点构成矩阵 vector< vector >GetPointMatrix( );//获得矩阵

int CalculateDistance(const POINT&,const POINT&);//求两点间的距离 void DrawLine(HWND hwnd,const vector&);//按存储点的顺序连线` //void SavePointMatrix();//保存点矩阵

void GaInterface(const pair,int> &);//遗传算法接口 vector GetPointPosition( )//获得存储点的位置

{ return resultpoint.first;

}

int GetSumDistance( ) //获得存储点的距离

{

return resultpoint.second; }

private: vector< pair > drawpoint;//储存点的位置并标号

vector< vector > pointmatrix;//储存任意两点的距离 pair< vector,int > resultpoint;//储存点的位置和距离

};

/////////////////////////////////////////////////////////////////////////////

2.源文件

/////////////////////////////connectline.cpp///////////////////////////////// #include \"connectline.h\"

////////////////生成矩阵和获得矩阵///////////////////////////////////////////

//vector< pair > drawpoint;//储存点的位置并标号******************* //vector< vector > pointmatrix;//储存任意两点的距离********************* void Line::SetPointMatrix( const vector& vecpoint) {

drawpoint.clear();

pointmatrix.clear();

//为向量vector > drawpoint分配存储空间 drawpoint.reserve(vecpoint.size());

for(int n=0;ndrawpoint[n].first.x=vecpoint[n].x; drawpoint[n].first.y=vecpoint[n].y; drawpoint[n].second=n;

}

//为向量vector > pointmatrix分配内存 vector vectemp(vecpoint.size());

for(n=0;npointmatrix.push_back(vectemp); }

for(n=0;nn;m--)

{ //编号为n和编号为m的两个点之间的距离

pointmatrix[n][m]=sqrt(

pow( abs(vecpoint[n].x-vecpoint[m].x) ,2)+

pow( abs(vecpoint[n].y-vecpoint[m].y) ,2) ); pointmatrix[m][n]=pointmatrix[n][m]; }

return;

}

///////////////////////////////////////////////////////////////////////////// ///////获得矩阵////////////////////////////////////////////////////////////// vector > Line::GetPointMatrix ( ) { return pointmatrix; //储存任意两点的距离 }

/////////////////////////////////////////////////////////////////////////////

////////////////计算两个点之间的距离///////////////////////////////////////// int Line::CalculateDistance(const POINT& point1,const POINT& point2) {

return sqrt(pow(abs(point1.x-point2.x),2)+pow(abs(point1.y-point2.y),2)); }

/////////////////////////////////////////////////////////////////////////////

//////////////根据点向量画线/////////////////////////////////////////////////

void Line::DrawLine(HWND hwnd,const vector& vecpoint)

{ //连线,按存储的点的顺序

HDC hdc=GetDC(hwnd); HPEN hpen;

hpen=CreatePen(PS_DOT,1,RGB(0,0,255) );

SelectObject(hdc,hpen);

if(vecpoint.size()<=0) { return; }

SetTextColor(hdc,RGB(0,255,0) );/////

TextOut( hdc,vecpoint[0].x+15,vecpoint[0].y+15,\"起点\起点\") ); char buffer[5];/////

for(int n=0;nsprintf(buffer,\"%d\

SetTextColor(hdc,RGB(128,0,0) );/////

TextOut(hdc,vecpoint[n].x+5,vecpoint[n].y+5,buffer,strlen(buffer));

}

MoveToEx( hdc,vecpoint[n].x,vecpoint[n].y,(LPPOINT) NULL); LineTo(hdc,vecpoint[n+1].x,vecpoint[n+1].y);

sprintf(buffer,\"%d\

SetTextColor(hdc,RGB(128,0,0) );/////

TextOut( hdc,vecpoint[n].x+5,vecpoint[n].y+5,buffer,strlen(buffer) ); MoveToEx( hdc,vecpoint.front().x,vecpoint.front().y,NULL);//回到起点 }

LineTo(hdc,vecpoint.back().x,vecpoint.back().y);

DeleteObject( hpen );

ReleaseDC (hwnd, hdc); return;

/////////////////////////////////////////////////////////////////////////////

////////////////保存vector > pointmatrix///////////////////////// /*void Line::SavePointMatrix() {

fstream outFile( \"copy.text\if ( !outFile ) { }

if(pointmatrix.size()<=0)

{ return; }

outFile<<\"#\"<<\"矩阵\"<<'\\n'; ///以后有用 outFile<<\"#\"<cerr << \"unable to open input file: \"<< \" -- bailing out!\\n\"; return ;

{

for(int m=0;moutFile<<'\\n'; }

return; }*/

/////////////////////////////////////////////////////////////////////////////

////////////////遗传算法接口函数/////////////////////////////////////////////

//pair< vector,int > resultpoint;//储存点的位置和距离///************** //vector< pair > drawpoint;//储存点的位置并标号/////////////////// void Line::GaInterface(const pair,int> & pointorder) {

vector result;

for(int n=0;nresultpoint.first=result; //获得所有的点的位置

resultpoint.second=pointorder.second; //获得路程的总长度

}

/////////////////////////////////////////////////////////////////////////////

八．遗传算法类

1.头文件

void order_crossover(Chrom& parent1,Chrom& parent2, Chrom& child1,Chrom& child2); //循环交叉

void cycle_crossover(Chrom& parent1,Chrom& parent2, Chrom& child1,Chrom& child2); //循环贪心交叉

void greed_crossover(Chrom& parent1,Chrom& parent2,

Chrom& child1,Chrom& child2); int randomInt(int low,int high);//产生一个随机整数(在low和high之间) private: Pop oldpop;//当前代种群 Pop newpop;//新一代种群

vector genes;//保存全部基因

float pcross;//交叉率 float pmutation;//变异率 int popsize;//种群大小

int lchrom;//染色体长度

int maxgen;//最大世代数 int gen;//当前世代

float max_var;//路径最大连接开销!! int evolveWay;//进化方案

UINT MutationStyle;//进化类型 UINT CrossoverStyle;//交叉类型

void chromCost(Chrom& chr);//计算一条染色体的个体适应度 void popCost(Pop &pop);//计算一个种群的个体适应度之和 void initChrom(Chrom& chr);//随机初始化一条染色体 void initpop(Pop& pop);//随机初始化种群

int selectChrom(const Pop& pop);//轮盘赌选择,返回种群中被选个体编号

int chooseBest(const Pop& pop);//精英策略，返回最优秀的一条染色体 //染色体交叉操作,由两个父代产生两个子代 void crossover(Chrom& parent1,Chrom& parent2, Chrom& child1,Chrom& child2); //染色体变异操作 void mutation(Chrom& chr);

//世代进化(由当前种群产生新种群) void generation(Pop& oldpop,Pop& newpop); //循环贪心

void tempcrossover(Chrom& parent1,Chrom& parent2,Chrom& child1); };

inline CGA::CGA():MutationStyle(ID_ORDER_MUTATION), CrossoverStyle(ID_PARTIALLY_MATCHED_CROSSOVER) {

return;

}

/////////////////////////////////////////////////////////////////////////////

2.源文件

//////////////////////////ga.cpp///////////////////////////////////////////// #pragma once #include \"ga.h\"

using namespace std;

UINT TempMutationStyle=ID_ORDER_MUTATION;//进化类型

UINT TempCrossoverStyle=ID_PARTIALLY_MATCHED_CROSSOVER;//交叉类型 //////////////////////////设置变异类型///////////////////////////////////////

void CGA::SetMutationStyle(HWND hwnd,WPARAM wparam) {

HMENU hMenu ;

hMenu = GetMenu (hwnd) ;

CheckMenuItem (hMenu, MutationStyle, MF_UNCHECKED); MutationStyle=LOWORD (wparam);

CheckMenuItem (hMenu, MutationStyle, MF_CHECKED );

TempMutationStyle=MutationStyle;

return; }

/////////////////////////////////////////////////////////////////////////////

//////////////////////设置交叉类型/////////////////////////////////////////// void CGA::SetCrossoverStyle(HWND hwnd,WPARAM wparam) {

HMENU hMenu ; hMenu = GetMenu (hwnd) ;

CheckMenuItem (hMenu, CrossoverStyle, MF_UNCHECKED); CrossoverStyle=LOWORD (wparam);

CheckMenuItem (hMenu, CrossoverStyle, MF_CHECKED );

TempCrossoverStyle=CrossoverStyle; return;

}

/////////////////////////////////////////////////////////////////////////////

///////////////////遗传算法参数设置函数定义//////////////////////////////////

void CGA::preSet(vector< vector >& mapDist,float _pcross, float _pmutation,int _popsize,int _maxgen,int _evolveWay) {

//设置参数

pcross = _pcross; popsize = _popsize;

pmutation = _pmutation; maxgen = _maxgen;

evolveWay = _evolveWay; lchrom = mapDist.size(); }

/////////////////////////////////////////////////////////////////////////////

////////////////遗传算法启动函数定义///////////////////////////////////////// pair,int> CGA::start() { initpop(oldpop); //产生初始种群

genes.resize(lchrom);

max_var = 0; //路径最大连接开销 for(int i=0;igenes[i].ID = i;

for(int j=0;jgenes[i].linkCost[ &genes[j] ] = mapDist[i][j]; if( mapDist[i][j] > max_var) max_var = mapDist[i][j];//路径最大连接开销

//通过不断进化，直到达到最大世代数 int best; //最优染色体编号

for(gen=0;genoldpop.pop_chrom.swap(newpop.pop_chrom); oldpop.sumfitness = newpop.sumfitness;

newpop.pop_chrom.clear(); }

best = chooseBest(oldpop); //最佳染色体

pair,int> result; //最优结果 for(int i=0;iresult.first.push_back(oldpop.pop_chrom[best].chrom_gene[i]->ID); result.second = oldpop.pop_chrom[best].varible; return result;

/////////////////////////////////////////////////////////////////////////////

/////产生一个随机整数(在[low,high)区间上)//////////////////////////////////// inline int CGA::randomInt(int low,int high) {

if(low==high)

return low; return low + ( rand()%(high-low) ); }

/////////////////////////////////////////////////////////////////////////////

//////计算一条染色体的个体适应度///////////////////////////////////////////// inline void CGA::chromCost(Chrom& chr) { }

/////////////////////////////////////////////////////////////////////////////

//////计算一个种群的个体适应度之和/////////////////////////////////////////// inline void CGA::popCost(Pop &pop) {

float sum=0;

for(int i=0;ifor(int i=0;isum += (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 个体适应度

}

pop.sumfitness = sum; }

/////////////////////////////////////////////////////////////////////////////

////////随机初始化一条染色体///////////////////////////////////////////////// inline void CGA::initChrom(Chrom& chr) { }

/////////////////////////////////////////////////////////////////////////////

//////////随机初始化种群///////////////////////////////////////////////////// inline void CGA::initpop(Pop& pop) { pop.pop_chrom.reserve(popsize);

Chrom tmp;

tmp.chrom_gene.reserve(lchrom); for(int i=0;ipop.pop_chrom.push_back(tmp); tmp.chrom_gene.clear();

vector tmp(lchrom); for(int i=0;itmp[i]=i; int choose;

while(tmp.size()>1) {

choose = randomInt(0,tmp.size());

chr.chrom_gene.push_back(&genes[tmp[choose]]); tmp.erase(tmp.begin()+choose);

}

chr.chrom_gene.push_back(&genes[tmp[0]]); chromCost(chr);

}

popCost(pop);

}

/////////////////////////////////////////////////////////////////////////////

///////////轮盘赌选择,返回种群中被选择的个体编号///////////////////////////// inline int CGA::selectChrom(const Pop& pop) {

float sum = 0;

float pick = float(randomInt(0,1000))/1000; int i = 0;

if(pop.sumfitness!=0) { while(1)

}

}

{ }

sum += pop.pop_chrom[i].fitness/pop.sumfitness; ++i;

if( (sum > pick) || i==pop.pop_chrom.size()) return i-1;

else

return randomInt(0,pop.pop_chrom.size());

/////////////////////////////////////////////////////////////////////////////

//////精英策略，返回最优秀的一条染色体/////////////////////////////////////// inline int CGA::chooseBest(const Pop& pop) {

int choose = 0; float best = 0;

for(int i = 0;i< pop.pop_chrom.size();++i) { if(pop.pop_chrom[i].fitness > best)

{

best = pop.pop_chrom[i].fitness;

choose = i; } }

return choose;

}

/////////////////////////////////////////////////////////////////////////////

///////////选择交叉类型////////////////////////////////////////////////////// inline void CGA::crossover(Chrom& parent1,Chrom& parent2, Chrom& child1,Chrom& child2 ) {

switch (TempCrossoverStyle)

{

case ID_PARTIALLY_MATCHED_CROSSOVER :

{ partially_matched_crossover(parent1,parent2,child1,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;

/////////////////////////////////////////////////////////////////////////////

//////部分匹配交叉///////////////////////////////////////////////////////////

inline void CGA::partially_matched_crossover(Chrom& parent1,Chrom& parent2, Chrom& child1,Chrom& child2) {

child1.chrom_gene.resize(lchrom); child2.chrom_gene.resize(lchrom);

vector::iterator p1_beg,p2_beg,c1_beg,c2_beg,

p1_end,p2_end,c1_end,c2_end;

p1_beg = parent1.chrom_gene.begin(); p2_beg = parent2.chrom_gene.begin(); c1_beg = child1.chrom_gene.begin(); c2_beg = child2.chrom_gene.begin(); p1_end = parent1.chrom_gene.end(); p2_end = parent2.chrom_gene.end();

c1_end = child1.chrom_gene.end(); c2_end = child2.chrom_gene.end();

//交换了parent1和parent2的值 //用于交叉的临时表

vector v1(parent1.chrom_gene), v2(parent2.chrom_gene); //随机选择两个交叉点

int pick1 = randomInt(1,lchrom-1);/////// int pick2 = randomInt(pick1,lchrom-1);//// int dist = lchrom-1-pick2; //第二交叉点到尾部的距离 copy(p1_beg+pick1, p1_beg+pick2+1, c2_beg+pick1); copy(p2_beg+pick1, p2_beg+pick2+1, c1_beg+pick1);

vector temchild1; vector temchild2; int value;

for(value=pick1;value<=pick2;value++)

temchild1.push_back(parent1.chrom_gene[value]->ID); for(value=pick1;value<=pick2;value++) temchild2.push_back(parent2.chrom_gene[value]->ID); //把表中元素复制到子代中

copy(v1.begin(), v1.begin()+pick1, c1_beg);

copy(v1.begin()+pick2+1, v1.end(), c1_beg+pick2+1); copy(v2.begin(), v2.begin()+pick1, c2_beg);

copy(v2.begin()+pick2+1, v2.end(), c2_beg+pick2+1); vector::iterator ch1; vector::iterator ch2; vector::iterator vec;

int i,j,k;

for(ch1=child1.chrom_gene.begin(),i=0;

ch1!=child1.chrom_gene.begin()+pick1;ch1++,i++)

if( find(temchild2.begin(),temchild2.end(), child1.chrom_gene[i]->ID)!=temchild2.end() ) {

for(vec=temchild2.begin(),j=0;vec!=temchild2.end();vec++,j++)

if(child1.chrom_gene[i]->ID==temchild2[j]) {

break; }

while( find(temchild2.begin(),temchild2.end(), {

temchild1[j])!=temchild2.end() )

for(vec=temchild2.begin(),k=0;vec!=temchild2.end();vec++,k++) if(temchild1[j]==temchild2[k]) { break; } j=k;

}

copy(parent1.chrom_gene.begin()+pick1+j, parent1.chrom_gene.begin()+pick1+j+1,

child1.chrom_gene.begin()+i);

}

for(ch1=child1.chrom_gene.begin()+pick2+1,i=pick2+1; ch1!=child1.chrom_gene.end();ch1++,i++)

if( find(temchild2.begin(),temchild2.end(), child1.chrom_gene[i]->ID)!=temchild2.end() ) {

for(vec=temchild2.begin(),j=0;vec!=temchild2.end();vec++,j++) if(child1.chrom_gene[i]->ID==temchild2[j])

{

break;

}

while( find(temchild2.begin(),temchild2.end(), temchild1[j])!=temchild2.end() ) {

for(vec=temchild2.begin(),k=0;vec!=temchild2.end();vec++,k++)

if(temchild1[j]==temchild2[k]) { break; } }

copy(parent1.chrom_gene.begin()+pick1+j, parent1.chrom_gene.begin()+pick1+j+1,

j=k;

child1.chrom_gene.begin()+i); }

for(ch2=child2.chrom_gene.begin(),i=0;

ch2!=child2.chrom_gene.begin()+pick1;ch2++,i++) if( find(temchild1.begin(),temchild1.end(),

{

child2.chrom_gene[i]->ID)!=temchild1.end() )

for(vec=temchild1.begin(),j=0;vec!=temchild1.end();vec++,j++) if(child2.chrom_gene[i]->ID==temchild1[j]) {

}

break;

while( find(temchild1.begin(),temchild1.end(), temchild2[j])!=temchild1.end() ) {

for(vec=temchild1.begin(),k=0;vec!=temchild1.end();vec++,k++)

if(temchild2[j]==temchild1[k]) {

break; } j=k;

}

copy(parent2.chrom_gene.begin()+pick1+j,

parent2.chrom_gene.begin()+pick1+j+1, child2.chrom_gene.begin()+i);

}

for(ch2=child2.chrom_gene.begin()+pick2+1,i=pick2+1;

ch2!=child2.chrom_gene.end();ch2++,i++)

if( find(temchild1.begin(),temchild1.end(), child2.chrom_gene[i]->ID)!=temchild1.end() ) {

for(vec=temchild1.begin(),j=0;vec!=temchild1.end();vec++,j++)

if(child2.chrom_gene[i]->ID==temchild1[j]) { break; }

while( find(temchild1.begin(),temchild1.end(),

temchild2[j])!=temchild1.end() ) {

for(vec=temchild1.begin(),k=0;vec!=temchild1.end();vec++,k++) if(temchild2[j]==temchild1[k])

{ break;

} j=k;

}

copy(parent2.chrom_gene.begin()+pick1+j, parent2.chrom_gene.begin()+pick1+j+1, child2.chrom_gene.begin()+i); }

}

///////////////////////////////////////////////////////////////////////////// ///////顺序交叉////////////////////////////////////////////////////////////// ///rotate(v1.begin(), v1.begin()+pick2+1,v1.end()); ///rotate(v2.begin(), v2.begin()+pick2+1,v2.end());

inline void CGA::order_crossover(Chrom& parent1,Chrom& parent2, {

Chrom& child1,Chrom& child2)

child1.chrom_gene.resize(lchrom); child2.chrom_gene.resize(lchrom);

vector::iterator v_iter,p1_beg,p2_beg,c1_beg,c2_beg, p1_end,p2_end,c1_end,c2_end;

p1_beg = parent1.chrom_gene.begin(); p2_beg = parent2.chrom_gene.begin(); c1_beg = child1.chrom_gene.begin(); c2_beg = child2.chrom_gene.begin(); p1_end = parent1.chrom_gene.end(); p2_end = parent2.chrom_gene.end(); c1_end = child1.chrom_gene.end();

c2_end = child2.chrom_gene.end();

//交换了parent1和parent2的值 //用于交叉的临时表

vector v1(parent2.chrom_gene), v2(parent1.chrom_gene); //随机选择两个交叉点

int pick1 = randomInt(1,lchrom-1);/////// int pick2 = randomInt(pick1,lchrom-1);//// 修改 int dist = lchrom-1-pick2; //第二交叉点到尾部的距离

//子代保持两交叉点间的基因不变

copy(p1_beg+pick1, p1_beg+pick2+1, c1_beg+pick1); copy(p2_beg+pick1, p2_beg+pick2+1, c2_beg+pick1); //循环移动表中元素

rotate(v1.begin(), v1.begin()+pick2+1,v1.end());

rotate(v2.begin(), v2.begin()+pick2+1,v2.end()); //从表中除去父代已有的元素

for(v_iter = p1_beg+pick1; v_iter!=p1_beg+pick2+1; ++v_iter) remove(v1.begin(),v1.end(),*v_iter); for(v_iter = p2_beg+pick1; v_iter!=p2_beg+pick2+1; ++v_iter) remove(v2.begin(),v2.end(),*v_iter); //把表中元素复制到子代中

copy(v1.begin(), v1.begin()+dist, c1_beg+pick2+1); copy(v1.begin()+dist, v1.begin()+dist+pick1, c1_beg); copy(v2.begin(), v2.begin()+dist, c2_beg+pick2+1); copy(v2.begin()+dist, v2.begin()+dist+pick1, c2_beg);

}

///////////////////////////////////////////////////////////////////////////// /////////////循环交叉////////////////////////////////////////////////////////

inline void CGA::cycle_crossover(Chrom& parent1,Chrom& parent2, {

Chrom& child1,Chrom& child2)

child1.chrom_gene.resize(lchrom); child2.chrom_gene.resize(lchrom);

vector::iterator p1_beg,p2_beg,c1_beg,c2_beg;

p1_beg = parent1.chrom_gene.begin(); p2_beg = parent2.chrom_gene.begin(); c1_beg = child1.chrom_gene.begin(); c2_beg = child2.chrom_gene.begin();

copy(parent1.chrom_gene.begin(), parent1.chrom_gene.end(), c2_beg); copy(parent2.chrom_gene.begin(), parent2.chrom_gene.end(), c1_beg); //copy(p1_beg, p1_beg+1, c1_beg); //未改进 //copy(p2_beg, p2_beg+1, c2_beg); int sign=randomInt(0,lchrom-1);//改进

copy(p1_beg+sign, p1_beg+sign+1, c1_beg+sign); copy(p2_beg+sign, p2_beg+sign+1, c2_beg+sign); int flag=parent2.chrom_gene[sign]->ID;//改进 int tempchild=parent2.chrom_gene[sign]->ID; //int flag=parent2.chrom_gene[0]->ID;//未改进

//int tempchild=parent2.chrom_gene[0]->ID; vector::iterator vecchild;

int i;

while(flag!=parent1.chrom_gene[sign]->ID)//改进 //while(flag!=parent1.chrom_gene[0]->ID) //未改进 {

for(vecchild=parent1.chrom_gene.begin(),i=0;

vecchild!=parent1.chrom_gene.end();vecchild++,i++) if(tempchild==parent1.chrom_gene[i]->ID) {

}

}

copy(p1_beg+i, p1_beg+i+1, c1_beg+i); copy(p2_beg+i, p2_beg+i+1, c2_beg+i); tempchild=parent2.chrom_gene[i]->ID; flag=parent2.chrom_gene[i]->ID; break;

}

/////////////////////////////////////////////////////////////////////////////

//////////////////////改进交叉方法:循环贪心交叉//////////////////////////////

inline void CGA::tempcrossover(Chrom& parent1,Chrom& parent2,Chrom& child1) {

child1.chrom_gene.resize(lchrom);

vector::iterator p1_beg,p2_beg,c1_beg;

p1_beg = parent1.chrom_gene.begin(); p2_beg = parent2.chrom_gene.begin();

c1_beg = child1.chrom_gene.begin(); int childsize;

int sign=randomInt(0,lchrom); //改进********** //int sign=0; //未改进********** vector temchild;

copy(p1_beg+sign,p1_beg+sign+1,c1_beg);

temchild.push_back(parent1.chrom_gene[sign]->ID); childsize=1;

while(childsizeint pleft1; int pright1; int pleft2; int pright2; if(sign==0) {

pleft1=lchrom-1; pright1=sign+1;

}

else if(sign==lchrom-1) { } else { }

pleft1=sign-1; pright1=sign+1; pright1=0; pleft1=sign-1;

int value;

for(int i=0;iID==parent2.chrom_gene[i]->ID) { value=i;

}

break;

if(value==0) { }

pleft2=lchrom-1; pright2=value+1;

else if(value==lchrom-1) { } else {

pleft2=value-1; pright2=value+1; pright2=0; pleft2=value-1;

}

int sign1; int sign2; int flag1; int flag2; int flag;

if( ( find(temchild.begin(),temchild.end(), parent1.chrom_gene[pleft1]->ID) ==temchild.end() )&&

( find(temchild.begin(),temchild.end(),

parent1.chrom_gene[pright1]->ID)

==temchild.end() ) ) {

flag1=1;

if( (parent1.chrom_gene[sign])-> )

{ sign1=pleft1; } else

linkCost[ parent1.chrom_gene[pleft1] ]< (parent1.chrom_gene[sign])->

linkCost[ parent1.chrom_gene[pright1] ]

sign1=pright1;

}

else if( ( find(temchild.begin(),temchild.end(), parent1.chrom_gene[pleft1]->ID) ==temchild.end() )&&

( find(temchild.begin(),temchild.end(), parent1.chrom_gene[pright1]->ID)

!=temchild.end() ) ) {

flag1=1; sign1=pleft1;

}

else if( ( find(temchild.begin(),temchild.end(), ) {

flag1=1; sign1=pright1; } else

flag1=0;

if( ( find(temchild.begin(),temchild.end(), ) {

flag2=1;

if( (parent2.chrom_gene[value])-> ) {

sign2=pleft2; } else sign2=pright2;

linkCost[ parent2.chrom_gene[pleft2] ]< (parent2.chrom_gene[value])->

linkCost[ parent2.chrom_gene[pright2] ] parent2.chrom_gene[pleft2]->ID) ==temchild.end() )&&

( find(temchild.begin(),temchild.end(), parent2.chrom_gene[pright2]->ID) ==temchild.end() )

parent1.chrom_gene[pleft1]->ID) !=temchild.end() )&&

( find(temchild.begin(),temchild.end(),

parent1.chrom_gene[pright1]->ID) ==temchild.end() )

}

else if( ( find(temchild.begin(),temchild.end(), parent2.chrom_gene[pleft2]->ID) ==temchild.end() )&& ( find(temchild.begin(),temchild.end(), ) { }

flag2=1; sign2=pleft2;

parent2.chrom_gene[pright2]->ID) !=temchild.end() )

else if( ( find(temchild.begin(),temchild.end(), parent2.chrom_gene[pleft2]->ID)

!=temchild.end() )&&

( find(temchild.begin(),temchild.end(),

parent2.chrom_gene[pright2]->ID) ==temchild.end() ) ) {

flag2=1; sign2=pright2; } else flag2=0;

if( (flag1==1)&&(flag2==1) ) {

flag=1;

if( (parent1.chrom_gene[sign])-> linkCost[ parent1.chrom_gene[sign1] ]< ) {

sign=sign1;

copy(p1_beg+sign,p1_beg+sign+1,c1_beg+childsize); (parent2.chrom_gene[value])->

linkCost[ parent2.chrom_gene[sign2] ]

temchild.push_back(parent1.chrom_gene[sign]->ID); childsize++; }

else {

sign=sign2; copy(p2_beg+sign,p2_beg+sign+1,c1_beg+childsize); temchild.push_back(parent2.chrom_gene[sign]->ID); childsize++;

}

}

else if( (flag1==1)&&(flag2==0) ) { flag=1;

sign=sign1;

copy(p1_beg+sign,p1_beg+sign+1,c1_beg+childsize);

temchild.push_back(parent1.chrom_gene[sign]->ID); childsize++;

}

else if( (flag1==0)&&(flag2==1) ) {

flag=1; sign=sign2;

copy(p2_beg+sign,p2_beg+sign+1,c1_beg+childsize); temchild.push_back(parent2.chrom_gene[sign]->ID); childsize++; } else

{

int signal=0;

flag=0;

/*while(signal==0) //未改进**********

{

sign=randomInt(0,lchrom);//randomInt(int low,int high) if( find(temchild.begin(),temchild.end(),

parent1.chrom_gene[sign]->ID)== {

temchild.end() ) signal=1;

}

} */ //未改进**********

for(int k=0;ksign=k;

if( find(temchild.begin(),temchild.end(), {

parent1.chrom_gene[sign]->ID)== temchild.end() ) signal=1; break;

}

} //改进**********

if(signal==1) {

}

copy(p1_beg+sign,p1_beg+sign+1,c1_beg+childsize);

temchild.push_back(parent1.chrom_gene[sign]->ID); childsize++; } } }

inline void CGA::greed_crossover(Chrom& parent1,Chrom& parent2, Chrom& child1,Chrom& child2) { tempcrossover(parent1,parent2,child1); tempcrossover(parent2,parent1,child2);

}

/////////////////////////////////////////////////////////////////////////////

/////////选择变异算法//////////////////////////////////////////////////////// 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;

case ID_REVERSE_MUTATION: { reverse_mutation(chr);

}

break; default : break;

}

}

/////////////////////////////////////////////////////////////////////////////

////////////染色体变异操作,基于次序的变异//////////////////////////////////// //随机地产生两个变异位，然后交换这两个变异位上的基因 inline void CGA::order_oriented_mutation(Chrom& chr) { vector::iterator beg = chr.chrom_gene.begin();

}

int pick1,pick2;

pick1 = randomInt(0,lchrom); do{ pick2 =randomInt(0,lchrom); }while(pick1==pick2);

iter_swap(beg+pick1, beg+pick2);

/////////////////////////////////////////////////////////////////////////////

//////染色体变异操作,基于位置的变异，随机产生两个变异位////////////////////// //然后将第二个变异位上的基因移动到第一个变异位之前 inline void CGA::position_oriented_mutation(Chrom& chr) { vector::iterator beg = chr.chrom_gene.begin();

int pick1,pick2;

pick1 = randomInt(0,lchrom); do{ pick2 =randomInt(0,lchrom); }while(pick1==pick2); //控制，使pick1temp=pick1; pick1=pick2; pick2=temp;

for(int i=pick1;iiter_swap(beg+i,beg+pick2);

}

/////////////////////////////////////////////////////////////////////////////

///////染色体变异操作,倒位变异，随机产生两个变异位/////////////////////////// //然后将这两个变异位所夹的子串中的城市进行反序 inline void CGA::reverse_mutation(Chrom& chr) {

vector::iterator beg = chr.chrom_gene.begin(); int pick1,pick2;

vector tempchrom(chr.chrom_gene); pick1 = randomInt(0,lchrom); do{ pick2 =randomInt(0,lchrom); }while(pick1==pick2);

//控制，使pick1int temp;

if(pick2}

temp=pick1;

pick1=pick2; pick2=temp; }

reverse_copy(tempchrom.begin()+pick1,

tempchrom.begin()+pick2+1,beg+pick1);

/////////////////////////////////////////////////////////////////////////////

///////世代进化(由当前种群产生新种群)//////////////////////////////////////// void CGA::generation(Pop& oldpop,Pop& newpop) {

newpop.pop_chrom.resize(popsize); int mate1,mate2,j; float pick;

float tmp;

Chrom gene1,gene2,tmp1,tmp2; gene1.chrom_gene.resize(lchrom); gene2.chrom_gene.resize(lchrom); tmp1.chrom_gene.resize(lchrom); tmp2.chrom_gene.resize(lchrom); //将最佳染色体放入下一代

mate1 = chooseBest(oldpop);

newpop.pop_chrom[0] = oldpop.pop_chrom[mate1]; j = 1;

//产生两条新染色体 do{ int count = 0;

mate1 = selectChrom(oldpop); mate2 = selectChrom(oldpop);

pick = float(randomInt(0,1000))/1000; gene1= oldpop.pop_chrom[mate1]; gene2= oldpop.pop_chrom[mate1]; if(pick < pcross) //交叉操作 {

if(evolveWay==1) {

crossover(oldpop.pop_chrom[mate1],oldpop.pop_chrom[mate2], newpop.pop_chrom[j],newpop.pop_chrom[j+1]); chromCost(newpop.pop_chrom[j]); //计算适应度 chromCost(newpop.pop_chrom[j+1]);

}

else if(evolveWay==2) //强迫进化

{

int count = 0; bool flag1 = false;

} else { }

}

bool flag2 = false;

while(1) { crossover(oldpop.pop_chrom[mate1], oldpop.pop_chrom[mate2],tmp1,tmp2); chromCost(tmp1); //计算适应度 }

chromCost(tmp2);

if(tmp1.fitness > gene1.fitness) { }

gene1 = tmp1; flag1 = true;

if(tmp2.fitness > gene2.fitness) {

gene2 = tmp2; flag2 = true;

}

//当子代都比父代优秀或寻找次数超过n次，跳出 if((flag1==true && flag2==true) || count> maxgen) {

newpop.pop_chrom[j] = gene1; newpop.pop_chrom[j+1] = gene2; break; }

count++;

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; chromCost(newpop.pop_chrom[j]); chromCost(newpop.pop_chrom[j+1]);

pick = float(randomInt(0,1000))/1000; if(pick < pmutation) //变异操作 {

{ }

if(evolveWay==1)

mutation(newpop.pop_chrom[j]);

chromCost(newpop.pop_chrom[j]); //计算适应度

}

else if(evolveWay==2) //强迫进化 {

int count = 0;

tmp = newpop.pop_chrom[j].fitness; do{

mutation(newpop.pop_chrom[j]);

chromCost(newpop.pop_chrom[j]); //计算适应度

count++; }while(tmp > newpop.pop_chrom[j].fitness && count}

pick = float(randomInt(0,1000))/1000; if(pick < pmutation) //变异操作 { }

if(evolveWay==1) {

mutation(newpop.pop_chrom[j+1]);

chromCost(newpop.pop_chrom[j+1]); //计算适应度

}

else if(evolveWay==2) //强迫进化 {

int count = 0;

tmp = newpop.pop_chrom[j+1].fitness; do{ mutation(newpop.pop_chrom[j+1]); chromCost(newpop.pop_chrom[j+1]); //计算适应度

count++;

}while(tmp > newpop.pop_chrom[j+1].fitness&&countj += 2; }while(j < popsize-1);

popCost(newpop); //计算新种群的适应度之和

/////////////////////////////////////////////////////////////////////////////

九．主控模块

1.源文件

///////////////////////////main.cpp////////////////////////////////////////// #include \"control.h\"

#include \"ga.h\"

#define WINDOW_CLASS_NAME \"GASOLVETSPWINCLASS\"//窗体类名称 bool bdrawline=1;//表示是否画直线 1表示未画 HINSTANCE g_hinstance;//当前实例

char c_buffer[4][5];//char数组类型临时变量 RECT rect;//要更新的窗口部分 char city[5]; int citynum;

Control ControlObject;//控制模块类对象

CGA CgaObject;//遗传算法类对象 //CgaObject.randomInt(,) SYSTEMTIME systime;//获取系统的时间

////////字符类型转化为整型数或浮点型数/////////////////////////////////////// float StringToInt(string str,bool bflg ) {

int size=str.size( ); float result=0;

for(int n=0;nresult *=10 ;

}

result/=10;

if( bflg==0) //这一段处理字符串为大于1的数 {

return result;

}

while( size-- ) { result/=10;//获得1到0的数 }

return result;

}

/////////////////////////////////////////////////////////////////////////////

//////////////城市设置对话框/////////////////////////////////////////////////

LRESULT CALLBACK AboutCITYNUMBERSet( HWND hDlg,UINT message, WPARAM wParam,LPARAM lParam) { switch(message)

{

case WM_INITDIALOG: //初始化对话框

//把对话框中控制文本设置为用一个指定整型值的字符串表示 SetDlgItemInt ( hDlg,IDC_CITYNUMBER, ControlObject.Getcitynumber( ),TRUE);

return TRUE;

case WM_COMMAND:

switch(LOWORD(wParam)) {

case IDOK://按确认键

{

//获取对话框中与控制有关的文本或标题

GetDlgItemText(hDlg, IDC_CITYNUMBER,city,5); citynum=StringToInt(city,0) ;

EndDialog(hDlg,LOWORD(wParam)); return TRUE;

}

case IDCANCEL://按取消键

{

EndDialog(hDlg, LOWORD(wParam)); return TRUE;

} break;

}

break;

}

return false;

}

/////////////////////////////////////////////////////////////////////////////

//////////////////遗传算法设置对话框///////////////////////////////////////// LRESULT CALLBACK AboutGASet(HWND hDlg,UINT message, {

WPARAM wParam,LPARAM lParam)

switch(message) {

case WM_INITDIALOG: //初始化对话框

//把对话框中控制文本设置为用一个指定整型值的字符串表示 SetDlgItemInt (hDlg,IDC_EDIT2,

ControlObject.Getpcross( )*100000,TRUE); SetDlgItemInt (hDlg,IDC_EDIT3, ControlObject.Getpmutation( )*100000,TRUE); SetDlgItemInt (hDlg,IDC_EDIT4, ControlObject.Getpopsize( ),TRUE);

SetDlgItemInt (hDlg,IDC_EDIT6,

ControlObject.Getmaxgen( ),TRUE);

//给一组单选按钮中的一个指定按钮加上选中标志,并且清除组中其他按钮的选中标志

//#define IDC_RADIO1 1019 //#define IDC_RADIO2 1020

CheckRadioButton(hDlg,IDC_RADIO1,IDC_RADIO2, IDC_RADIO1+ControlObject.GetPower( )); return TRUE;

switch(LOWORD(wParam)) { case IDC_RADIO1://选中第一个按纽

{

ControlObject.SetPower(0);

case WM_COMMAND:

break;

}

case IDC_RADIO2://选中第二个按纽

{

ControlObject.SetPower(1); break;

}

case IDOK://按确认键 { //获取对话框中与控制有关的文本或标题

GetDlgItemText(hDlg, IDC_EDIT2,c_buffer[0],5); GetDlgItemText(hDlg, IDC_EDIT3,c_buffer[1],5); GetDlgItemText(hDlg, IDC_EDIT4,c_buffer[2],5); GetDlgItemText(hDlg, IDC_EDIT6,c_buffer[3],5);

ControlObject.SetGaInformation( StringToInt(c_buffer[0],1),

StringToInt(c_buffer[1],1),

StringToInt(c_buffer[2],0), StringToInt(c_buffer[3],0)); return TRUE;

EndDialog(hDlg,LOWORD(wParam));

}

case IDCANCEL://按取消键

{

EndDialog(hDlg, LOWORD(wParam));

return TRUE; }

case IDDefault://按默认值键

{

ControlObject.SetGaInformation(0.6f,0.2f,30,30);

ControlObject.SetPower(1);

SendMessage(hDlg,WM_INITDIALOG,0,0); }

/////////////////////////////////////////////////////////////////////////////

//////////////////窗口过程函数///////////////////////////////////////////////

LRESULT CALLBACK WindowProc(HWND hwnd, UINT msg, WPARAM wparam, LPARAM lparam ) {

return TRUE; }

break;

} break;

}

return FALSE;

PAINTSTRUCT ps; //将发送WM_PAINT消息

HDC hdc; //设备环境句柄 static POINT point;//临时点 // 无效区域(网格以外的区域)

rect.left=715; rect.top=55; rect.right=950;

rect.bottom=140; switch(msg)

{

case WM_CREATE: //应用程序创建一个窗口

{

ControlObject.welcome( hwnd ); return(0);

} break;

case WM_PAINT: //要求一个窗口重画自己

{

hdc = BeginPaint(hwnd,&ps); //画地图

ControlObject.DrawMap(hwnd ,hdc);

ControlObject.DisPlay(hwnd,point,bdrawline); ControlObject.DrawAllPoint(hwnd );

if( bdrawline==0) //已画直线但未消除直线

{

ControlObject.DrawLine(hwnd ); }

} EndPaint(hwnd,&ps); break;

case WM_MOUSEMOVE : //移动鼠标

{

point.x=(int)LOWORD(lparam); point.y=(int)HIWORD(lparam);

InvalidateRect (hwnd, &rect, 1);//刷新消息,会发送WM_PAINT消息 }

break;

case WM_LBUTTONDOWN: //按下鼠标左键 { //SendMessage(hwnd,WM_LBUTTONDOWN,NULL,0);

ControlObject.DrawTruePoint(hwnd,point ); ControlObject.DrawAllPoint(hwnd );

if( bdrawline==0) { InvalidateRect (hwnd,NULL, 1) ;//刷新消息

}

InvalidateRect (hwnd,&rect, 1) ; //刷新消息 bdrawline=1; //标志画直线后已清除直线

} break;

case WM_RBUTTONDOWN: //按下鼠标右键

{

ControlObject.DrawFalsePoint(hwnd,point ); ControlObject.DrawAllPoint(hwnd );

InvalidateRect (hwnd, NULL, 1) ;//刷新消息 bdrawline=1;

} break;

case WM_RBUTTONDBLCLK: //双击鼠标右键 {

//SendMessage(hwnd,WM_COMMAND,ID_CLEAN_ALL,0); ControlObject.CleanAllUpDate( );

InvalidateRect (hwnd, NULL, 1) ; bdrawline=1; }

break;

case WM_KEYDOWN: //按下一个键

{

switch(LOWORD(wparam)) {

case VK_RETURN:

SendMessage(hwnd,WM_COMMAND,IDOK,0); break;

} } break;

//当用户选择一个菜单命令项，或当某个控件发送一条消息给它的父窗口 case WM_COMMAND:

{

switch( LOWORD(wparam) )

{

case ID_SET_CITY:

{

SendMessage(hwnd,WM_RBUTTONDBLCLK,NULL,0);

DialogBox(g_hinstance, (LPCTSTR)IDD_SETCITY,

hwnd,(DLGPROC)AboutCITYNUMBERSet);

for(int num=0;num{ point.x=CgaObject.randomInt(5,705); point.y=CgaObject.randomInt(50,470);

SendMessage(hwnd,WM_LBUTTONDOWN,NULL,0);

} } break;

case IDOK: //选择开始菜单

{

HDC hdc;

hdc=GetDC(hwnd); GetLocalTime(&systime);

beforehourtime=systime.wHour; beforeminutetime=systime.wMinute;

beforesecondtime=systime.wSecond;

beforemillisecondtime=systime.wMilliseconds;

SetTextColor(hdc,RGB(128,0,128));

TextOut(hdc,720,10,\"请稍等: 正在计算!\

strlen(\"请稍等: 正在计算!\"));

ReleaseDC (hwnd, hdc);

ControlObject.DrawLineWait( ); ControlObject.DrawLine( hwnd);

GetLocalTime(&systime);

afterhourtime=systime.wHour; afterminutetime=systime.wMinute; aftersecondtime=systime.wSecond;

aftermillisecondtime=systime.wMilliseconds;

bdrawline=0;

InvalidateRect (hwnd, NULL, 1) ;//刷新消息

} break;

case ID_DefaultMap ://选择默认地图菜单 case ID_RoundMap ://选择圆形地图菜单

{

//如果选择类型不变，不清空点

if(ControlObject.GetMapStyle( )==LOWORD(wparam)) {

break;

}

ControlObject.CleanAllUpDate( );//清空当前所有点 ControlObject.SetMapStyle( hwnd,wparam); InvalidateRect (hwnd, NULL, 1) ;

bdrawline=1; } break;

case ID_GA_SET: //选择遗传算法设置菜单

{

DialogBox(g_hinstance, (LPCTSTR)IDD_GA_BOX, hwnd, (DLGPROC)AboutGASet); }

break; case ID_ORDER_MUTATION : //选择基于次序的变异菜单

{ }

DrawMutationStyle=ID_ORDER_MUTATION; CgaObject.SetMutationStyle( hwnd,wparam);

break;

case ID_POSITION_MUTATION://选择基于位置的变异菜单

{ }

DrawMutationStyle=ID_POSITION_MUTATION; CgaObject.SetMutationStyle( hwnd,wparam);

break;

case ID_REVERSE_MUTATION://选择倒位变异菜单

{

DrawMutationStyle=ID_REVERSE_MUTATION; CgaObject.SetMutationStyle( hwnd,wparam);

} break;

case ID_PARTIALLY_MATCHED_CROSSOVER: { //选择部分匹配交叉菜单

DrawCrossoverStyle=ID_PARTIALLY_MATCHED_CROSSOVER; CgaObject.SetCrossoverStyle(hwnd,wparam);

} break;

case ID_ORDER_CROSSOVER://选择顺序交叉菜单

{ }

DrawCrossoverStyle=ID_ORDER_CROSSOVER; CgaObject.SetCrossoverStyle(hwnd,wparam);

break;

case ID_CYCLE_CROSSOVER://选择循环交叉菜单

{ }

DrawCrossoverStyle=ID_CYCLE_CROSSOVER; CgaObject.SetCrossoverStyle(hwnd,wparam);

break;

case ID_GREED_CROSSOVER://循环贪心交叉

{

DrawCrossoverStyle=ID_GREED_CROSSOVER; CgaObject.SetCrossoverStyle(hwnd,wparam);

}

break;

case ID_FIXED_CITY://固定城市的求解,主要用于测试

{ vector point30(30); int iallpoint[60]=

{

87,7, 91,83, 83,46, 71,44, 64,60,

68,58, 83,69, 87,76, 74,78, 71,71,

58,69, 54,62, 51,67, 37,84, 41,94,

2,99, 7,64, 22,60, 25,62, 18,54, 4,50, 13,40, 18,40, 24,42, 25,38, 41,26, 45,21, 44,35, 58,35, 62,32

};

for(int n=0;n<30;n++)

{

point30[n].x=iallpoint[2*n];

point30[n].y=iallpoint[2*n+1]; }

for(n=0;n<30;n++)

{

point30[n].x=point30[n].x+6; point30[n].y=point30[n].y+51; } for(n=0;n<30;n++) {

point.x=point30[n].x; point.y=point30[n].y;

SendMessage(hwnd,WM_LBUTTONDOWN,NULL,0); } }

break;

case ID_HELP_BOX://选择帮助菜单

{

DialogBox(g_hinstance, (LPCTSTR)IDD_HELP_BOX,

hwnd, (DLGPROC)AboutGASet); } //帮助对话框

break;

case ID_END://选择结束菜单 {

//SendMessage(hwnd,WM_COMMAND,ID_CLEAN_ALL,0);

ControlObject.CleanAllUpDate( );

InvalidateRect (hwnd, NULL, 1) ; bdrawline=1; }

break;

case ID_EXIT://选择退出菜单 }

{ SendMessage(hwnd,WM_CLOSE,NULL,0); } break; break; }

default:

break;

case WM_DESTROY: //结束应用程序

{

PostQuitMessage(0); return(0);

} break;

default: break; }

return (DefWindowProc(hwnd, msg, wparam, lparam)); }

/////////////////////////////////////////////////////////////////////////////

///////////////windows程序入口函数/////////////////////////////////////////// int WINAPI WinMain( HINSTANCE hinstance, HINSTANCE hprevinstance,

LPSTR lpcmdline, int ncmdshow)

{

WNDCLASSEX winclass; //窗口类 HWND hwnd; //窗口句柄 MSG msg; //设置窗口类结构

//消息

winclass.cbSize = sizeof(WNDCLASSEX); winclass.style = CS_SAVEBITS|CS_DBLCLKS|CS_HREDRAW | CS_VREDRAW; winclass.lpfnWndProc = WindowProc; winclass.cbClsExtra = 0; winclass.cbWndExtra = 0;

winclass.hInstance = hinstance; winclass.hIcon =LoadIcon(hinstance, MAKEINTRESOURCE(IDI_ICON1) ); winclass.hCursor = LoadCursor (NULL, IDC_ARROW) ;

winclass.hbrBackground= (HBRUSH)GetStockObject(WHITE_BRUSH);

winclass.lpszMenuName = MAKEINTRESOURCE(101); winclass.lpszClassName= WINDOW_CLASS_NAME;

winclass.hIconSm = LoadIcon(hinstance, MAKEINTRESOURCE(IDI_ICON1)); //注册窗口类

if (!RegisterClassEx(&winclass)) return(0); //创建窗口

if (!(hwnd = CreateWindowEx(NULL,

WINDOW_CLASS_NAME, \"遗传算法解TSP问题演示\

WS_OVERLAPPED|WS_CAPTION|WS_MINIMIZEBOX | WS_VISIBLE|WS_SYSMENU, 0,0, 1000,700, NULL, NULL, hinstance, NULL)

) )

return(0);

hinstance=g_hinstance;

while(TRUE)//不断从消息队列中获取消息

{

if (PeekMessage(&msg,NULL,0,0,PM_REMOVE)) {

if (msg.message == WM_QUIT) break; TranslateMessage(&msg);

DispatchMessage(&msg); }

}

return(msg.wParam); }

/////////////////////////////////////////////////////////////////////////////

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文