遗传算法解决TSP问题-C--版(带注释).docx

//遗传算法解决简单TSP问题，（VC6.0）
//一、定义头文件(defines.h)
#ifndef DEFINES_H
#define DEFINES_H

///////////////////////////////// DEFINES ///////////////////////////////////////
//窗口定义大小
#define WINDOW_WIDTH 500
#define WINDOW_HEIGHT 500
//城市数量及城市在窗口显示的大小
#define NUM_CITIES 20
#define CITY_SIZE 5
//变异概率，交叉概率及种群数量
#define MUTATION_RATE 0.2
#define CROSSOVER_RATE 0.75
#define POP_SIZE 40

//倍数
#define NUM_BEST_TO_ADD 2

//最小容许误差
#define EPSILON 0.000001

#endif
//二、一些用得到的小函数(utils.h)
// utils.h: interface for the Cutils class.
//头文件名
//////////////////////////////////////////////////////////////////////
#ifndef UTILS_H
#define UTILS_H

#include <stdlib.h>
#include <math.h>
#include <sstream>
#include <string>
#include <iostream>

using namespace std;
//--------定义一些随机函数--------

//----定义随机整数，随机[x,y]之间的整数---
inline int RandInt(int x, int y)
{
return rand()%(y-x+1)+x;
}

//--------------随机产生0到1之间的小数----------
inline float RandFloat()
{
return rand()/(RAND_MAX + 1.0);
}

//-----------------随机产生0和1-------------

inline bool RandBool()
{
if (RandInt(0,1))
return true;
else
return false;
}

//-----定义一些方便的小功能包括：整形转字符型，浮点型转字符型---
string itos(int arg);
//converts an float to a std::string
string ftos (float arg);

//限制大小
void Clamp(double &arg, double min, double max);
void Clamp(int &arg, int min, int max);

#endif
//三、地图头文件（CmapTSP）

#ifndef CMAPTSP_H
#define CMAPTSP_H//如果没有定义那么就定义
//////////////////////////////////////////////////
//类名：CmapTSP.h
//
//描述：封装地图数据、城市坐标以及适应度计算。
/////////////////////////////////////////////////
#include <vector>

#include "utils.h"
#include "defines.h"

using namespace std;

const double pi=3.1415926535897;

//------CoOrd结构体，保存每个城市的坐标--------

struct CoOrd//没有括号
{
float x, y;
CoOrd(){}
CoOrd(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);

//该函数计算出排列成环形后的最佳路径，答案是显而易见的（环形多边形周长）
void CalculateBestPossibleRoute();

public:
//城市坐标
vector<CoOrd> 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_width, const int new_Height);

//给一个有效的周游路径，返回该路径长度
double GetTourLength(const vector<int> &route);

double BestPossibleRoute()const{return m_dBestPossibleRoute;}
};

#endif

//四、遗传算法头文件（CgaTSP）

#ifndef CGATSP_H
#define CGATSP_H

#include <vector>
#include <windows.h>
#include <fstream>
#include <algorithm>
#include <iostream>

#include "mapTSP.h"
#include "defines.h"
#include "utils.h"

using namespace std;

//----------基因组结构体(包含旅行路径和其适应度函数)----------
struct SGenome
{
//周游城市路径，（基因组）
vector<int> vecCities;

//他的适应度分数
double dFitness;

//构造函数
SGenome ():dFitness(0){}
SGenome(int nc):dFitness(0)
{
vecCities = GrabPermutation(nc);
}
//随机创建一个周游路径
vector<int> GrabPermutation (int &limit);

//在GrabPermutation中使用
bool TestNumber(const vector<int> &vec, const int &number);

};

//--------CgaTSP类---------------

class CgaTSP
{
private:
//声明基因组实例
vector<SGenome> m_vecPopulation;

//地图类的实例
CmapTSP* m_pMap;

//交叉及变异概率
double m_dMutationRate;
double m_dCrossoverRate;

//整个种群的总适应度分数
double m_dTotalFitness;

//在此之前找到的最短路径
double m_dShortestRoute;

//在此之前找到的最长周游路径
double m_dLongestRoute;

//种群中基因组的数目
int m_iPopSize;

//染色体长度
int m_iChromoLength;

//新一代中适应度分数最高的成员
int m_iFittestGenome;

//表明已经到了那一代
int m_iGeneration;

//帮助了解长须当前是否进入绘图阶段
bool m_bStarted;

//交换变异(Exchange Mutation)
void MutateEM(vector<int> &chromo);

//部分匹配杂交
void CrossoverPMX(const vector<int> &mum,
const vector<int> &dad,
vector<int> &baby1,
vector<int> &baby2);

SGenome& RouletteWheelSelection();

//适应度函数中用到的函数
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_iPopSize(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);

void Epoch();
void 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_STDAFX_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 <windows.h>

#endif

//////////////////////////////----------------源文件---------------///////////////////////////////-
//一、utils.cpp
// utils.cpp: implementation of the Cutils class.
//
//////////////////////////////////////////////////////////////////////

#include "utils.h"

#include <math.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//--------itos讲一个整数变换成字符串-----------
string itos(int arg)
{
ostringstream buffer;

//把整形发送到buffer
buffer << arg;

//获取字符串
return buffer.str();
}

//---------把浮点型转换为字符串型----------
string ftos(float arg)
{
ostringstream buffer;

buffer << arg;

return buffer.str();
}

//限制范围
void Clamp(double &arg, double min, double max)
{
if (arg<min)
{
arg = min;
}
if (arg>max)
{
arg = max;
}
}

void Clamp( int &arg, int min, int max)
{
if (arg < min)
{
arg = min;
}

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_MapHeight<m_MapWidth)
{
radius = (m_MapHeight / 2) - margin;
}
else
{
radius = (m_MapWidth / 2) - margin;
}
CoOrd origin(m_MapWidth/2, m_MapHeight/2);//原点
double SegmentSize = 2 * pi / m_NumCities;//角度
double angle = 0;//起始角度
vector<CoOrd> vecCities;//城市向量
while (angle<2*pi)
{
CoOrd ThisCity;//声明对象

ThisCity.x = radius * sin(angle) + origin.x;//犯错误处少乘radius *
ThisCity.y = radius * cos(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::CalculateBestPossibleRoute()
{
m_dBestPossibleRoute = 0;

for (int city=0; city<m_vecCityCoOrds.size()-1; ++city)
{

m_dBestPossibleRoute += CalculateA_to_B(m_vecCityCoOrds[city], m_vecCityCoOrds[city+1]);

m_dBestPossibleRoute += EPSILON;//加入误差

}
m_dBestPossibleRoute += CalculateA_to_B(m_vecCityCoOrds[0], m_vecCityCoOrds[m_vecCityCoOrds.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<int> &route)
{
double TotalDistance = 0;

for (int i=0; i<route.size()-1; ++i)
{
int city1 = route[i];
int city2 = route[i+1];

TotalDistance += CalculateA_to_B(m_vecCityCoOrds[city1], m_vecCityCoOrds[city2]);
}

//don't forget this is a closed loop so we need to add in the distance
//from the last city visited back to the first
int last = route[route.size()-1];
int first = route[0];

TotalDistance += CalculateA_to_B(m_vecCityCoOrds[last], m_vecCityCoOrds[first]);

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
//////////////////////////////////////////////////////////////////////
/////////----------------------------------------------
/////////------------结构体函数------------------------
/////////----------------------------------------------
///////////////////////////////////////////////////////
//该函数检查给定的一个整数是否包含在给定的一个向量里边

bool SGenome::TestNumber(const vector<int> &vec, const int &number)
{
for (int i=0; i<vec.size(); i++)
{
if (vec[i] == number)
{
return true;
}
}
return false;
}

//////////////////////////////////////////////////////////
//给定一个整数，该函数返回随机排列的路径
////////////////////////////////////////////////////////

vector<int> SGenome::GrabPermutation(int &limit)
{
vector<int> vecPerm;

for (int i=0; i<limit; i++)
{
int NextPossibleNumber = RandInt(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; i<m_iPopSize; i++)
{
//对于每一个城市求其路径
double TourLength =
m_pMap->GetTourLength(m_vecPopulation[i].vecCities);

m_vecPopulation[i].dFitness = TourLength;

if (TourLength<m_dShortestRoute)
{
m_dShortestRoute = TourLength;

m_iFittestGenome = i;
}

if (TourLength>m_dLongestRoute)
{
m_dLongestRoute = TourLength;
}
}
for (int j=0; j<m_iPopSize; j++)
{
m_vecPopulation[j].dFitness =
m_dLongestRoute - m_vecPopulation[j].dFitness;
}

}

//-------------------轮盘选择,选择一个--------------------
SGenome& CgaTSP::RouletteWheelSelection()
{
double fSlice = RandFloat() * m_dTotalFitness;

double cfTotal = 0.0;

int SelectedGenome = 0;

for (int i=0; i<m_iPopSize; i++)
{
cfTotal += m_vecPopulation[i].dFitness;
if (cfTotal>fSlice)
{
SelectedGenome = i;
break;
}
}
return m_vecPopulation[SelectedGenome];

}

//--------随机选择区间，用来交叉和变异---------
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 (end<beg)
{
end = RandInt(0, vec_size-1);
}
}

//----------变异--------------已改正
void CgaTSP::MutateEM(vector<int> &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(chromo[pos1], chromo[pos2]);
}

//----------------交叉-------------------
void CgaTSP::CrossoverPMX(const vector<int> &mum,
const vector<int> &dad,
vector<int> &baby1,
vector<int> &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<int>::iterator posGene1, posGene2;

for (int pos=beg; pos<end+1; pos++)
{
int gene1 = mum[pos];
int gene2 = dad[pos];
if (gene1 != gene2)
{
posGene1 = find(baby1.begin(),baby2.end(),gene1);
posGene2 = find(baby1.begin(), baby1.end(), gene2);

swap(*posGene1, *posGene2);

//and in baby2
posGene1 = find(baby2.begin(), baby2.end(), gene1);
posGene2 = find(baby2.begin(), baby2.end(), gene2);

swap(*posGene1, *posGene2);
}
}

}

//----------产生初始群体------------------
void CgaTSP::CreateStartingPopulation()
{
m_vecPopulation.clear();
for (int i=0; i<m_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 = true;
}

//---------重置所有变量为新的一代----------

void CgaTSP::Reset()
{
m_dShortestRoute = 999999999;
m_dLongestRoute = 0;
m_dTotalFitness = 0;
}

//-----------------组合在一起---------------

void CgaTSP::Epoch()
{
//为新的一代重置
Reset();

CalculatePopulationsFitness();
if ((m_dShortestRoute <= m_pMap->BestPossibleRoute()))
{
m_bStarted = false;

return;
}

//创建一个临时的向量作为新的种群
vector<SGenome> vecNewPop;

//加入上一代的精英
for (int i=0; i<NUM_BEST_TO_ADD; ++i)
{
vecNewPop.push_back(m_vecPopulation[m_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(baby1.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_num<m_pMap->m_vecCityCoOrds.size(); ++city_num)
{
int x = (int)m_pMap->m_vecCityCoOrds[city_num].x;//浮点型转换整形
int y =