遗传算法解决TSP问题,C++版(带注释)

1、/遗传算法解决简单TSP问题，（VC6.0）/一、定义头文件(defines.h)#ifndef DEFINES_H #define DEFINES_H/ DEFINES /窗口定义大小#define WINDOW_WIDTH500#define WINDOW_HEIGHT500/城市数量及城市在窗口显示的大小#define NUM_CITIES20#define CITY_SIZE 5/变异概率，交叉概率及种群数量#defineMUTATION_RATE0.2#defineCROSSOVER_RATE0.75#definePOP_SIZE 40/倍数#define NUM_BEST_TO_A

2、DD2/最小容许误差#define EPSILON0.000001#endif/二、一些用得到的小函数(utils.h)/ utils.h: interface for the Cutils class./头文件名/#ifndef UTILS_H #define UTILS_H#include #include #include #include #include using namespace std;/-定义一些随机函数-/-定义随机整数，随机x,y之间的整数-inline int RandInt(int x, int y)return rand()%(y-x+1)+x;/-随机产生0到1

3、之间的小数-inline float RandFloat()return rand()/(RAND_MAX + 1.0);/-随机产生0和1-inline bool RandBool()if (RandInt(0,1)return true;elsereturn false;/-定义一些方便的小功能包括：整形转字符型，浮点型转字符型-string itos(int arg);/converts an float to a std:stringstring ftos (float arg);/限制大小void Clamp(double &arg, double min, double max);

4、void Clamp(int &arg, int min, int max);#endif /三、地图头文件（CmapTSP）#ifndef CMAPTSP_H#define CMAPTSP_H/如果没有定义那么就定义/类名：CmapTSP.h/描述：封装地图数据、城市坐标以及适应度计算。/#include #include utils.h#include defines.husing namespace std;const double pi=3.1415926535897;/-CoOrd结构体，保存每个城市的坐标-struct CoOrd/没有括号float x, y;CoOrd()CoO

5、rd(float a,float b):x(a),y(b);/-CmapTSP类，封装地图数据，城市坐标，以及适应度计算-class CmapTSP private:/城市数目int m_NumCities;/地图长度和宽度int m_MapWidth;int m_MapHeight;/可能最好路径double m_dBestPossibleRoute;/把所有城市组成一个环形void CreateCitiesCircular();/用勾股定理计算两个城市A和B之间的距离double CalculateA_to_B(const CoOrd &city1, const CoOrd &city2)

6、;/该函数计算出排列成环形后的最佳路径，答案是显而易见的（环形多边形周长）void CalculateBestPossibleRoute();public:/城市坐标vector m_vecCityCoOrds;/构造函数，当创建一个实例时，城市坐标即被创建，并计算出可能的最佳路径CmapTSP(int w, int h, int nc):m_MapWidth(w),m_MapHeight(h),m_NumCities(nc)CreateCitiesCircular();CalculateBestPossibleRoute();/改变窗口坐标时void Resize(const int new

7、_width, const int new_Height);/给一个有效的周游路径，返回该路径长度double GetTourLength(const vector &route);double BestPossibleRoute()constreturn m_dBestPossibleRoute;#endif /四、遗传算法头文件（CgaTSP）#ifndef CGATSP_H #define CGATSP_H#include #include #include #include #include #include mapTSP.h#include defines.h#include uti

8、ls.husing namespace std;/-基因组结构体(包含旅行路径和其适应度函数)-struct SGenome/周游城市路径，（基因组）vector vecCities;/他的适应度分数double dFitness;/构造函数SGenome ():dFitness(0)SGenome(int nc):dFitness(0)vecCities = GrabPermutation(nc);/随机创建一个周游路径vector GrabPermutation (int &limit);/在GrabPermutation中使用bool TestNumber(const vector &v

9、ec, const int &number);/-CgaTSP类-class CgaTSPprivate:/声明基因组实例vector m_vecPopulation;/地图类的实例CmapTSP* m_pMap;/交叉及变异概率double m_dMutationRate;double m_dCrossoverRate;/整个种群的总适应度分数double m_dTotalFitness;/在此之前找到的最短路径double m_dShortestRoute;/在此之前找到的最长周游路径double m_dLongestRoute;/种群中基因组的数目int m_iPopSize;/染色体长

10、度int m_iChromoLength;/新一代中适应度分数最高的成员int m_iFittestGenome;/表明已经到了那一代int m_iGeneration;/帮助了解长须当前是否进入绘图阶段bool m_bStarted;/交换变异(Exchange Mutation)void MutateEM(vector &chromo);/部分匹配杂交void CrossoverPMX(const vector &mum, const vector &dad, vector &baby1,vector &baby2);SGenome& RouletteWheelSelection();/适

11、应度函数中用到的函数void CalculatePopulationsFitness();void CalculateBestWorstAvtot();void Reset();void CreateStartingPopulation();public:/构造函数（初始化）CgaTSP(double mut_rat, double cross_rat, int pop_size, int NumCities, int map_width, int map_height):m_dMutationRate(mut_rat), m_dCrossoverRate(cross_rat), m_iPop

12、Size(pop_size), m_iFittestGenome(0), m_iGeneration(0), m_dShortestRoute(999999999), m_dLongestRoute(0), m_iChromoLength(NumCities), m_bStarted(false)/设置地图m_pMap = new CmapTSP(map_width, map_height, NumCities);CreateStartingPopulation();/析构函数CgaTSP()delete m_pMap;void Run(HWND hwnd);voidEpoch(); void

13、 Render(HDC surface, int cx, int cy); void Resize(int cxClient, int cyClient) m_pMap-Resize(cxClient, cyClient); /供使用的方法void Stop()m_bStarted = false;bool Started()return m_bStarted;#endif /五、一个其实没有用的头文件（StdAfx.h）#if !defined(AFX_STDAFX_H_A9DB83DB_A9FD_11D0_BFD1_444553540000_INCLUDED_)#define AFX_ST

14、DAFX_H_A9DB83DB_A9FD_11D0_BFD1_444553540000_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000#define WIN32_LEAN_AND_MEAN/ Exclude rarely-used stuff from Windows headers#include #endif/-源文件-/-/一、utils.cpp/ utils.cpp: implementation of the Cutils class./#include utils.h#include / Constructi

15、on/Destruction/-itos讲一个整数变换成字符串-string itos(int arg)ostringstream buffer;/把整形发送到bufferbuffer arg;/获取字符串return buffer.str();/-把浮点型转换为字符串型-string ftos(float arg)ostringstream buffer;buffer arg;return buffer.str();/限制范围void Clamp(double &arg, double min, double max)if (argmax)arg = max;void Clamp( int

16、&arg, int min, int max)if (arg max)arg = max;/二、mapTSP.cpp/ mapTSP.cpp: implementation of the CmapTSP class./#include mapTSP.h/ Construction/Destruction/-把城市排列成圆圈-(已改正)void CmapTSP:CreateCitiesCircular()const int margin = 50;/边缘double radius;/圆半径if (m_MapHeightm_MapWidth)radius = (m_MapHeight / 2) -

17、 margin;elseradius = (m_MapWidth / 2) - margin;CoOrd origin(m_MapWidth/2, m_MapHeight/2);/原点double SegmentSize = 2 * pi / m_NumCities;/角度double angle = 0;/起始角度vector vecCities;/城市向量while (angle2*pi)CoOrd ThisCity;/声明对象ThisCity.x = radius * sin(angle) + origin.x;/犯错误处少乘radius *ThisCity.y = radius * c

18、os(angle) + origin.y;m_vecCityCoOrds.push_back(ThisCity);angle += SegmentSize;/-计算两个城市之间的路径-double CmapTSP:CalculateA_to_B(const CoOrd &city1, const CoOrd &city2)double xDist = city1.x - city2.x;double yDist = city1.y - city2.y;return sqrt(xDist*xDist + yDist*yDist);/-计算最佳路径- void CmapTSP:CalculateB

19、estPossibleRoute()m_dBestPossibleRoute = 0;for (int city=0; citym_vecCityCoOrds.size()-1; +city)m_dBestPossibleRoute += CalculateA_to_B(m_vecCityCoOrdscity, m_vecCityCoOrdscity+1);m_dBestPossibleRoute += EPSILON;/加入误差m_dBestPossibleRoute += CalculateA_to_B(m_vecCityCoOrds0, m_vecCityCoOrdsm_vecCityC

20、oOrds.size()-1);/少减个1，size()-1/-屏幕坐标变化时-void CmapTSP:Resize(const int new_width, const int new_height)m_MapWidth = new_width;m_MapHeight = new_height;m_vecCityCoOrds.clear();CreateCitiesCircular();CalculateBestPossibleRoute();/-得到一条路线的距离长度-double CmapTSP:GetTourLength(const vector &route)double Tota

21、lDistance = 0;for (int i=0; iroute.size()-1; +i)int city1 = routei;int city2 = routei+1;TotalDistance += CalculateA_to_B(m_vecCityCoOrdscity1, m_vecCityCoOrdscity2);/dont forget this is a closed loop so we need to add in the distance /from the last city visited back to the firstint last = routeroute

22、.size()-1;int first = route0;TotalDistance += CalculateA_to_B(m_vecCityCoOrdslast, m_vecCityCoOrdsfirst);return TotalDistance;/ mapTSP.cpp: implementation of the CmapTSP class./三、gaTSP.cpp/ gaTSP.cpp: implementation of the CgaTSP class./#include stdafx.h#include gaTSP.h/ Construction/Destruction/-/-

23、结构体函数-/-/该函数检查给定的一个整数是否包含在给定的一个向量里边bool SGenome:TestNumber(const vector &vec, const int &number)for (int i=0; ivec.size(); i+)if (veci = number)return true;return false;/给定一个整数，该函数返回随机排列的路径/vector SGenome:GrabPermutation(int &limit)vector vecPerm;for (int i=0; ilimit; i+)int NextPossibleNumber = Ran

24、dInt(0, limit-1);while (TestNumber(vecPerm, NextPossibleNumber)NextPossibleNumber = RandInt(0,limit-1);vecPerm.push_back(NextPossibleNumber);return vecPerm;/-/-类内函数-/-/该函数计算每个基因的适应度分数void CgaTSP:CalculatePopulationsFitness()for (int i=0; iGetTourLength(m_vecPopulationi.vecCities);m_vecPopulationi.dF

25、itness = TourLength;if (TourLengthm_dLongestRoute)m_dLongestRoute = TourLength;for (int j=0; jm_iPopSize; j+)m_vecPopulationj.dFitness = m_dLongestRoute - m_vecPopulationj.dFitness;/-轮盘选择,选择一个-SGenome& CgaTSP:RouletteWheelSelection()double fSlice = RandFloat() * m_dTotalFitness;double cfTotal = 0.0;

26、int SelectedGenome = 0;for (int i=0; ifSlice)SelectedGenome = i;break;return m_vecPopulationSelectedGenome;/-随机选择区间，用来交叉和变异-void ChooseSection(int &beg, int &end, const int vec_size, const int min_span)beg = RandInt(0, vec_size-1-min_span); end = beg;while (endbeg)end = RandInt(0, vec_size-1);/-变异-已

27、改正void CgaTSP:MutateEM(vector &chromo)if (RandFloat()m_dMutationRate) return;int pos1 = RandInt(0, chromo.size()-1); int pos2 = pos1;while (pos1 = pos2)/双等号pos2 = RandInt(0, chromo.size()-1);swap(chromopos1, chromopos2); /-交叉-void CgaTSP:CrossoverPMX(const vector &mum, const vector &dad, vector &bab

28、y1, vector &baby2)baby1 = mum;baby2 = dad;if (RandFloat()m_dCrossoverRate)|(mum = dad)return;int beg = RandInt(0, mum.size()-2);int end = beg;while(end=beg)end = RandInt(0, mum.size()-1);/遍历每个基因地址下标vector:iterator posGene1, posGene2;for (int pos=beg; posend+1; pos+)int gene1 = mumpos;int gene2 = dad

29、pos;if (gene1 != gene2)posGene1 = find(baby1.begin(),baby2.end(),gene1);posGene2 = find(baby1.begin(), baby1.end(), gene2);swap(*posGene1, *posGene2);/and in baby2posGene1 = find(baby2.begin(), baby2.end(), gene1);posGene2 = find(baby2.begin(), baby2.end(), gene2);swap(*posGene1, *posGene2);/-产生初始群体

30、-void CgaTSP:CreateStartingPopulation()m_vecPopulation.clear();for (int i=0; im_iPopSize; i+)m_vecPopulation.push_back(SGenome(m_iChromoLength);m_iGeneration = 0;m_dShortestRoute = 9999999;m_iFittestGenome = 0;m_bStarted= false;/-运行-void CgaTSP:Run(HWND hwnd)CreateStartingPopulation();m_bStarted = t

31、rue;/-重置所有变量为新的一代-void CgaTSP:Reset()m_dShortestRoute= 999999999;m_dLongestRoute= 0;m_dTotalFitness= 0;/-组合在一起-void CgaTSP:Epoch()/为新的一代重置Reset(); CalculatePopulationsFitness();if (m_dShortestRoute BestPossibleRoute()m_bStarted = false;return;/创建一个临时的向量作为新的种群vector vecNewPop;/加入上一代的精英for (int i=0; i

32、NUM_BEST_TO_ADD; +i)vecNewPop.push_back(m_vecPopulationm_iFittestGenome);while (vecNewPop.size() != m_iPopSize)SGenome mum = RouletteWheelSelection();SGenome dad = RouletteWheelSelection();SGenome baby1, baby2;CrossoverPMX(mum.vecCities, dad.vecCities, baby1.vecCities, baby2.vecCities);MutateEM(baby

33、1.vecCities);MutateEM(baby2.vecCities);vecNewPop.push_back(baby1);vecNewPop.push_back(baby2);m_vecPopulation = vecNewPop;+m_iGeneration;/-Rander函数把函数信息从文本和图像中输出winproc-void CgaTSP:Render(HDC surface, int cx, int cy)for (int city_num=0; city_numm_vecCityCoOrds.size(); +city_num)int x = (int)m_pMap-m_

34、vecCityCoOrdscity_num.x;/浮点型转换整形int y = (int)m_pMap-m_vecCityCoOrdscity_num.y;/画圆Ellipse(surface, x-CITY_SIZE, y+CITY_SIZE, x+CITY_SIZE, y-CITY_SIZE);/画出每代中最优的路线vector route = m_vecPopulationm_iFittestGenome.vecCities;/运行的时候只显示路线if(m_iGeneration!=0)/到了那一代MoveToEx(surface, (int)m_pMap-m_vecCityCoOrds

35、route0.x, (int)m_pMap-m_vecCityCoOrdsroute0.y, NULL); for (int i=1; im_vecCityCoOrdsroutei.x; int CityY = (int)m_pMap-m_vecCityCoOrdsroutei.y; LineTo(surface, CityX, CityY); if(NUM_CITIESm_vecCityCoOrdsroute0.x, (int)m_pMap-m_vecCityCoOrdsroute0.y);/输出文本string sGen = itos(m_iGeneration);sGen = Gener

36、ation: + sGen;TextOut(surface, 5, 5,sGen.c_str(), sGen.size();if (!m_bStarted)string Start = Press Return to start a new run;TextOut(surface, cx/2 - (Start.size() * 3), cy - 20, Start.c_str(), Start.size();elsestring Start = Space to stop;TextOut(surface, cx/2 - (Start.size() * 3), cy - 20, Start.c_

37、str(), Start.size();/四、（其实没用，可以不用管）#include stdafx.h/五、（主函数）main/ 第四章_简单TSP.cpp : Defines the entry point for the application./#include #include #include #include #include gaTSP.h#include defines.husing namespace std;/-窗口标题和应用程序标题-char*szApplicationName = 简单TSP;char*szWindowClassName = TSP类;/指向TSP的指

38、针CgaTSP* g_pTSP;/-WinProc-/窗口过程/-LRESULT CALLBACK WindowProc(HWND hwnd, UINT msg, WPARAM wparam, LPARAM lparam)/声明设备描述表和绘图结构HDC hdc;PAINTSTRUCT ps;/定义窗口尺寸static int cxClient, cyClient;/建立缓冲区，（防止显示图像时画面闪烁）static HDC hdcBackBuffer;static HBITMAP hBitmap;static HBITMAP hOldBitmap;/消息处理switch(msg)case W

39、M_CREATE:/启动随机发生器srand(unsigned) time(NULL);/得到客户窗口尺寸RECT rect;GetClientRect(hwnd, &rect);cxClient = rect.right;cyClient = rect.bottom;/创建一个兼容的缓冲HDC/hdcBackBuffer = createCompatibleDC(NULL);hdcBackBuffer = CreateCompatibleDC(NULL);HDC hdc = GetDC(hwnd);hBitmap = CreateCompatibleBitmap(hdc, cxClient,cyClient);ReleaseDC(hwnd, hdc);hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);/创建TSP类所有对象的全局实例g_pTSP = new CgaTSP(MUTATION_RATE, CROSSOVER_RATE, POP_SIZE, NUM_