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

算法的软件实现 发环境介绍 本文中的所有算法是在 + 操作平台上进行开发的，并结合 行编程。 1、 + 介 + 微软公司最新出品的功能最为强大的可视化开放工具，是计算机界公认的最优秀的应用开发工具之一。 基本类库使得开发 用程序比以往任何时候都要容易。 +作为一种程序设计语言，它同时也是一个集成开发工具，提供了软件代码自动生成和可视化的 资源编辑功能。 2、 + 优势 (1) (2) (3) (4) (5)支持。 (6)生的可执行文件体积小巧、运行速度快。 3、 ，即标准模板库，是一个具有工业强度的，高效的 C+程序库。它被容纳于 C+标准程序库 （ C+ 中 ，是 +标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大 C+程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。这种现象有些类似于 +中的 ，或者是 + 但是它比二者具有更强的优势。更加值得一提的是，它具备以下 几个区别于其它软件库的优点： (1)互换的编程模块能够提供比传统组件设 是 否 世代进化 图 传算法解 计方法丰富得多的组合方式。 (2)户界面等专业领域开发组件的基础。 开始 产生城市 对城市进行编码 初始化遗传算 法的相关参数 计算每个个体的适应值 是否符合终止 条件？ 输出正确的 果 选择 交叉 变异 轮盘赌选择 普通选择 X X 基于次序的变异 基于位置的变异 倒位 变异 (3)以在不损失效率的情况下实现对组件的概括。与此形成鲜明对照的是，其它一些具有复杂继承层次和大量使用虚函数的 C+库结构则通常会降低效率。 法实现的流程图 本设计的具体流程图如图 法的各个模块及其详细设计思路 1城市生成模块 用户可以点击鼠标左键产生城市，也可以选择菜单栏的设置城市选项，通过输入城市数目来随机生成城市。当然，如 果用户选择错了城市，可以在该城市上点击鼠标右键来清除城市。如果用户要清除所有的城市，可以双击鼠标右键或选择菜单栏的结束选项，都可以清除所有的城市。其设计设计思路如图 按下鼠标左键 按下鼠标右键 选择菜单栏的设置城市选项 选择菜单栏的结束选项 图 市生成模块的设计思路 最后的效果如图 程序检测鼠标移动的具体信息 程序将点的信息存入一个点向量中 调用画图函数画点 (即设置城市 ) 将点向量中要除去的点找出来 重新画点 向量中的所有点 ( 此时该删除的点 已从点向量中删除 ) 用一个变量记入要产生的城市数 循环调用鼠标左键点击消息直到达到要求的城市数 重新画地图 ( 即清除了所有的点 ) 图 果 根据具体的需要，用户可以选择不同的地图，本设计提供的地图有：基于直角坐标系的地图和圆形地图，这两个地图由不同的类来产生。其中类 图 角坐标地图 图 形地图 3. 遗传算法解 在具体的应用中，用户可以根据具体情况来设置 遗传算法的相关参数，这些参数包括： 交叉率：控制程序进行交叉的次数，在本设计中，先随机生成一个 数，如果这个数大于交叉率，则不交叉，如果这个数小于交叉率，则进行交叉。具体实现如下： ,1000)/1000; if( # # #地图类 # DC 0;/画地图 / =0;/保存格式为地图中的位置 =0;/清除 有点 /在地图上画点（参数为实际位置） =0; /将地图上已存在的点（参数为实际位置）删除 =0; /保存 数为实际位置 )到向量 =0; /删除 数为实际位置 )到向量 =0; /获得所有已点击的点的位置 (实际值 ) )=0; ;/地图中的位置 ; /函数对象 / _ ( &( ( &( ; / 四 直角坐标地图类 #10 # 6 ( );/保存格式为地图中的位置 );/清除 有点 /在地图上画点 (参数为实际位置 ) ; /将地图上已存在的点 (参数为实际位置 )删除 ; ;/保存 数为实际位置 )到向量 ;/删除 数为实际位置 )到向量 /获得所有已点击的点的位置 (实际值 ) ); ( ; / #(DC ,128,128); /创建画笔 x = 0 ; x /该点的半径 ;/if(20) (n= x=x+m; y=y+n; ; x=x+n; y=y+m; ; / /在地图上画点 /在地图上画点 (参数为实际位置 )/ ; if(20) ; ,55,0,0); /选择对象进 , /画圆点 / /添加和减少点 (在地图位置 )到向量 /保存 数为实际位置 )到向量 / !=0 & , )!= ) /保证点不重复 ; / /清除一个指定的点 / if( : ); /获得该点附近的像素点 if(=0 ) , , ); ) / /将地图上已存在的点 (参数为实际位置 )删除 /擦掉该点 (重画所有的点和地图 )/ n=; if(n=) /没找到则向量大小不变 ; n=0;n ) / /将地图与实际位置之间转换 / x= y=(20) 1; 1; 6; 51; / /地图位置转换为实际位置 / ; 1; );/获得所有已点 击的点的位置 (实际值 ) ; / #() / do 0); 20= 305,24,44 , 365 ,84, 402, 21, 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, 63 ,46, 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 ; n=0;n :n=-3; x=x+m; y=y+n; /获得该点附近的点 x=x+n; y=y+m; /获得该点附近的点 , ,); ) 1; 1; * / /在地图上画点或将地点上以存在的点从地图上删除 / /在地图上画点 (参数为实际位置 )/ 1; 1; ; ; 55,0,0) ); ; (x+5, (y+5) ; ; / /将地图上已存在的点（参数为实际位置）重画 / n=; if(n=) /在其他地区 (60 个之外 )点击右键则向量大小不变 n=0;n:1; 1; ,; ) / /获得所有已点击的点的位置 / ) / 六 控制 类 #; ; ;/交叉类型 );/初始化数据 (开始 ) /( );/获得当前地图类型 ,变异率 ,种群大小 ,最大世代数 );/清除所有点 /显示其它与鼠标位置或地图相关信息 ;/画出所有的点 DC ( );/画线的准备 ;/画线 ) /获得交叉概率 ) /获得变异概率 )/获得种群大小 ) /获得世代数 /获得城市数 n) /设置世代进化类型 n; )/获得世代进化类型 ;/交叉率 ;/种群大小 ;/城市数目 *; /初始化数据 / ):30), 0),0), & ) / #;/交叉类型 /提供提示和帮助信息 / /创建一个对话框显示提示信息 欢迎进入遗传算法解 题演示系统 !, 遗传算法解 题演示实验 , ;/ / /帮助 / /* */ / /获得当前地图类型 / ) / /设置地图类型 / ; ) & ; ; / /遗传算法信息 / /依次 :交叉率 ,变异率 ,种群大小 ,最大世代数 . if( 0| 1) 0| 1 ) / /清除所有点 / /( ) ; / /显示其它与鼠标位置或地图相关信息 / 0; ,0,255) ); 50,10,遗传算法解 题演示地图 , 遗传算法解 题演示地图 ) ); ,0,0) ); 0,500, 注意 : 点击鼠标左键设置城市点 ,点击鼠标右键清空一个点。 , 注意 : 点击鼠标左键设置城市点 ,点击鼠标右键清空一个点。 ) ); 2,530, 点击菜单开始或 进行寻路 ,详细信息请选菜单中帮助。 , 点击菜单开始或 进行寻路 ,详细信息请选菜单中帮助。 ) ); /算法运行时间显示模块 / ,128,128); /创建画笔 10,180,960,340); ,0,0) ); 80,170,算法运行时间 ,算法运行时间 ) ); 30,190,算法启动前时间 :,算法启动前时间 :) ); %d 时 ,%d 分 ,%d 秒 ,%d 微秒 , 30,210,; 30,240,算法结束时间 :,算法结束时间 :) ); %d 时 ,%d 分 ,%d 秒 ,%d 微秒 , 30,260,; ; () ); 30,120,;/ 1 ) / 当前未准备好所有的点 50,120, 总距离 : 0 , 总距离 : 0 ); 总距离 :%d, ) ); 50,120,; /显示连线总长 /默认地图才显示坐标 /获得地图上的点位置 700*420 1!= /测试点在有效区没有 ,0,0); /没在无效 区域则为黑笔，只是显示坐标点的颜色 55,0,0); /在无效区域则为红笔 当前鼠标的横坐标 :