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

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).经过类属编程方法精心组织的，可互换的编程模块能够提供比传统组件设 是 否 世代进化 图4.1 遗传算法解TSP的具体流程图 计方法丰富得多的组合方式。 (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(ra