TSP问题的遗传算法求解方案--源程序清单(旅行商问题，包含算法介绍，源程序，测试结果) 本文关键词：源程序，算法，求解，遗传，清单
TSP问题的遗传算法求解方案--源程序清单(旅行商问题，包含算法介绍，源程序，测试结果) 本文简介：TSP问题的遗传算法求解方案算法的软件实现4.1开发环境介绍本文中的所有算法是在VisualC++6.0的操作平台上进行开发的，并结合STL进行编程。1、VisualC++6.0简介VisualC++6.0是微软公司最新出品的功能最为强大的可视化开放工具，是计算机界公认的最优秀的应用开发工具之一。M
TSP问题的遗传算法求解方案--源程序清单(旅行商问题，包含算法介绍，源程序，测试结果) 本文内容：
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).经过类属编程方法精心组织的，可互换的编程模块能够提供比传统组件设
开始
初始化遗传算法的相关参数
计算每个个体的适应值
产生城市
对城市进行编码
是否符合终止
条件？
输出正确的
TSP结果
是
GEN=GEN+1
选择
交叉
变异
否
世代进化
轮盘赌选择
普通选择
GX
CX
OX
PMX
基于次序的变异
基于位置的变异
倒位
变异
图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(randomInt(0,1000))/1000;
if(pick
#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
//将地图上已存在的点（参数为实际位置）删除
virtual
void
SmearPonit(HWND
hwnd,const
POINT
//保存POINT(参数为实际位置)到向量
virtual
void
AddPoint(const
POINT
//删除POINT(参数为实际位置)到向量
virtual
void
SubPoint(const
POINT
//获得所有已点击的点的位置(实际值)
virtual
vector
GetAllClickPoint(
)=0;
protected:
POINT
beginpoint;//实际位置
vector
vecpoint;//地图中的位置
};
///////////////////函数对象//////////////////////////////////////////////////
class
equal_point{
public:
equal_point()
{
}
equal_point(const
POINT
}
bool
operator()(const
POINT
}
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
GetRealPoint
(const
POINT//地图POINT实际位置
protected:
//找到该点附近的像素点iarea为该点的半径
vector
FindAroundPoint(const
POINT
};
/////////////////////////////////////////////////////////////////////////////
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
DefaultMap::FindAroundPoint(const
POINT
vector
vecroundpoint;
temppoint.x
=point.x-6
;//
判断点是否在有效区域//-51
temppoint.y
=point.y-51
;//-51
if(temppoint.x700||temppoint.y>420)
{
return
vecroundpoint;
}
iarea=abs(iarea);//防止iarea小于零
for(int
n=-iarea;n-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//
判断点是否在有效区域
int
cy
=point.y-51;
if(cx700||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
if(
vecpoint.size()!=0
}
//保证点不重复
vecpoint.push_back(
tempoint
);
}
/////////////////////////////////////////////////////////////////////////////
//////////////清除一个指定的点///////////////////////////////////////////////
void
DefaultMap::SubPoint(const
POINT
vector
::iterator
Iter1;
vecroundpoint=FindAroundPoint(point,2);
//获得该点附近的像素点