wstsp.cpp

开发环境：Visual C++ .net2003 功能：利用遗传算法求解TSP问题。

#include "StdAfx.h"
#include ".\wstsp.h"
#include "WSRandom.h"
#include <fstream>
#include <algorithm>
using namespace std;

WSTSP::WSTSP(void)
{
}

WSTSP::~WSTSP(void)
{
}

/*
功能：计算两个城市间的距离
输入：输入两个城市的坐标(FLOAT型) 或 两个城市的坐标对象(CityPoint型)
输出：两个城市的距离值-->Float型
*/
FLOAT WSTSP::CityDistance(FLOAT _Ax, FLOAT _Ay, FLOAT _Bx, FLOAT _By)
{
	return sqrtf(pow(_Ax - _Bx, 2) + pow(_Ay - _By, 2));
}
FLOAT WSTSP::CityDistance(CityPoint _A, CityPoint _B)
{
	return CityDistance(_A.x, _A.y, _B.x, _B.y);
}

/*
功能：计算TSP的总路程长
输入：所有城市的坐标信息 类型:PCityInfo
输出：TSP的总路程长度-->Float型
*/
FLOAT WSTSP::TSPTotalDistance(PCityInfo _pCityInfo)
{
	FLOAT l_TotalDistance = 0;
	INT i;
	
	for(i = 0; i < _pCityInfo->m_CityNum - 1; ++i)
	{
		l_TotalDistance += CityDistance(
								_pCityInfo->m_pCities[ _pCityInfo->m_pCityOrder[i] ], 
								_pCityInfo->m_pCities[ _pCityInfo->m_pCityOrder[i+1] ]
								);
	}

	return l_TotalDistance + CityDistance(
								_pCityInfo->m_pCities[ _pCityInfo->m_pCityOrder[i] ], 
								_pCityInfo->m_pCities[ _pCityInfo->m_pCityOrder[0] ]
								);
}

/*
功能：从指定文件中读取城市坐标
输入：文件名-->PChar 城市信息对象-->CityInfo
输出：文件的读取状态，成功-->TRUE 失败-->FALSE

注：m_pCities和m_pCityOrder需为全局咚咚才能保证分配的地址空间不会被覆盖；
要不然，在函数返回时，为他们分配的地址空间将被收回。
*/
CityOrderDef g_pCityOrder;//由于Vector复制用的是深拷贝，所以此处有无无关紧要
PCityPoint g_pCities = NULL;//按从1开始的顺序
BOOL WSTSP::ReadCityInfoFromFile(PCHAR _FileName, CityInfo &_CityInfo)
{
	ifstream infile;
	infile.open(_FileName, ios::in);
	if(!infile.is_open()) return FALSE;

	INT l_CityNum = 0;
	bool needdec = false;
	CHAR l_ReadBuf[128] = {0};
	infile>>l_ReadBuf;
	if(strcmp(::strlwr(l_ReadBuf), "name") == 0)
	{
			/*
			NAME : att48
			COMMENT : 48 capitals of the US (Padberg/Rinaldi)
			TYPE : TSP
			DIMENSION : 48 <---
			EDGE_WEIGHT_TYPE : ATT
			NODE_COORD_SECTION
			*/
			infile.getline(l_ReadBuf, 255);//获得次要数据
			infile.getline(l_ReadBuf, 255);//获得次要数据
			infile.getline(l_ReadBuf, 255);//获得次要数据
			infile.getline(l_ReadBuf, 255);//获得城市个数
			int i = 0;
			while(l_ReadBuf[i++] != ':');//退出时已过了":"
			l_CityNum = atoi(l_ReadBuf+i);
			infile.getline(l_ReadBuf, 255);//获得次要数据
			infile.getline(l_ReadBuf, 255);//获得次要数据

			needdec = true;
	}
	else
	{
		l_CityNum = atoi(l_ReadBuf);
	}
	printf("城市个数：[%d]\n", l_CityNum);

	//infile>>l_CityNum;
	_CityInfo.m_CityNum = l_CityNum;
	//printf("%d\n", l_CityNum);//Test1

	g_pCities = (PCityPoint)malloc(sizeof(CityPoint)*l_CityNum);
	if(!g_pCities) return FALSE;//从全局来分配空间，以免该函数结束时将所用内存回收
	
	INT i;
	for(i = 0; i < l_CityNum; ++i) g_pCityOrder.push_back(i);
	_CityInfo.m_pCityOrder = g_pCityOrder;
	_CityInfo.m_pCities = g_pCities;//将所得之全局内存交给_CityInfo；保证能将内存交给外部使用
	char tmpvalue[255];
	for(i = 0; i < l_CityNum; ++i)
	{
		if(!infile) return FALSE;
		_CityInfo.m_pCityOrder[i] = i;
		infile>>tmpvalue>>_CityInfo.m_pCities[i].x>>_CityInfo.m_pCities[i].y;
		//if(needdec)--_CityInfo.m_pCityOrder[i];
		//printf("%d %f %f\n", _CityInfo.m_pCityOrder[i], _CityInfo.m_pCities[i].x, _CityInfo.m_pCities[i].y);//Test2
	}

	infile.close();
	return TRUE;
}

/*
功能：随机生成若干个城市的坐标
输入：文件名-->PChar 城市数目-->Int
输出：文件的写入状态，成功-->TRUE 失败-->FALSE
*/
BOOL WSTSP::GenCityInfoToFile(PCHAR _FileName, INT _CityNum)
{
	ofstream outfile;
	outfile.open(_FileName, ios::out);
	if(!outfile.is_open()) return FALSE;

	WSRandom::Initial();
	INT i;
	outfile<<_CityNum<<endl;
	for(i = 0; i < _CityNum; ++i)
	{
		outfile<<i<<" "<<(FLOAT)(rand()%10000)/10.0<<" "<<(FLOAT)(rand()%10000)/10.0<<endl;
		//outfile<<i<<" "<<rand()%10000<<" "<<rand()%10000<<endl;
	}
	
	outfile.close();
	return TRUE;
}

/*
功能：交换两个变量的值
输入：变量1-->Int型 变量2-->Int型
输出：无
*/
VOID WSTSP::SwapValues(INT & _A, INT & _B)
{
	INT TMP = _A;
	_A = _B;
	_B = TMP;
}

/*
功能：产生随机的城市访问序列
输入：城市的信息-->CityInfo
输出：无
*/
VOID WSTSP::GenRandCityOrder(CityInfo &_CityInfo)
{
	random_shuffle(_CityInfo.m_pCityOrder.begin()+1, _CityInfo.m_pCityOrder.end());
}
VOID WSTSP::GenRandCityOrder(CityOrderDef &_CityOrder)
{
	random_shuffle(_CityOrder.begin()+1, _CityOrder.end());
}

/*
功能：将子序进行颠倒，用在GA的变异算法中
输入：城市次序的信息-->CityOrderDef
输出：无
*/
VOID WSTSP::ReverseSubOrder(CityOrderDef &_CityOrder)
{
	INT l_CityNum = _CityOrder.size();
	INT l_Max, l_Min;
	do{
		l_Max = WSRandom::GenRand(1, l_CityNum -1);
		l_Min = WSRandom::GenRand(1, l_CityNum -1);
	}while(l_Max == l_Min);

	if(l_Min > l_Max) SwapValues(l_Min, l_Max);
	ReverseSubOrder(l_Min, l_Max, _CityOrder);
}
VOID WSTSP::ReverseSubOrder(INT _Begin, INT _End, CityOrderDef & _CityOrder)
{	
	while(_Begin < _End) SwapValues(_CityOrder[_Begin++], _CityOrder[_End--]);
}
/*
功能：将子序进行颠倒，用在GA的变异算法中
输入：城市次序的信息-->CityOrderDef
输出：无
*/
VOID WSTSP::RearrangeSubOrder(CityOrderDef &_CityOrder)
{
	INT l_CityNum = _CityOrder.size();
	INT l_Max, l_Min;
	do{
		l_Max = WSRandom::GenRand(1, l_CityNum -1);
		l_Min = WSRandom::GenRand(1, l_CityNum -1);
	}while(l_Max == l_Min);

	if(l_Min > l_Max) SwapValues(l_Min, l_Max);
	RearrangeSubOrder(l_Min, l_Max, _CityOrder);
}
VOID WSTSP::RearrangeSubOrder(INT _Begin, INT _End, CityOrderDef & _CityOrder)
{	
	std::random_shuffle(_CityOrder.begin() + _Begin, _CityOrder.begin() + _End);
}

/*
功能：将两个城市的(子)序列进行比较
输入：2个城市子次序的信息-->CityOrderDef
输出：相同-->TRUE 不相同-->FALSE
*/
BOOL WSTSP::EqualOrders(CityOrderDef _A, CityOrderDef _B)
{
	INT l_OrderLen = _A.size();
	if(l_OrderLen != _B.size()) return FALSE;

	INT i;
	for(i = 0; i < l_OrderLen; ++i)
		if(_A[i] != _B[i]) return FALSE;

	return TRUE;
}

/*
功能：将两个城市的子序进行交换，用在GA的交叉算法中
输入：4个城市次序的信息-->CityOrderDef
输出：无
*/
BOOL WSTSP::CrossSubOrder(CityOrderDef _CityOrderPa, CityOrderDef _CityOrderPb, CityOrderDef & _CityOrderSa, CityOrderDef & _CityOrderSb)
{
	INT l_CityNum = _CityOrderPa.size();
	INT l_Min, l_Max;
	do{
		l_Max = WSRandom::GenRand(1, l_CityNum -2);
		l_Min = WSRandom::GenRand(1, l_CityNum -2);//0号为起点,不动它
	}while(l_Max == l_Min);
	if(l_Min > l_Max) SwapValues(l_Min, l_Max);
	//printf("[%d, %d]\n" , l_Min, l_Max);
	
	return CrossSubOrder(l_Min, l_Max, _CityOrderPa, _CityOrderPb, _CityOrderSa, _CityOrderSb);

}
BOOL WSTSP::CrossSubOrder(INT _Begin, INT _End, CityOrderDef _CityOrderPa, CityOrderDef _CityOrderPb, CityOrderDef & _CityOrderSa, CityOrderDef & _CityOrderSb)
{
	INT l_CityNum = _CityOrderPa.size();
	if(l_CityNum != _CityOrderPb.size()) return FALSE;
	
	PBOOL l_OrderPaState = (PBOOL)malloc(sizeof(BOOL)*l_CityNum);
	PBOOL l_OrderPbState = (PBOOL)malloc(sizeof(BOOL)*l_CityNum);//记录城市的序列状态，是否在交叉时被提取
	memset(l_OrderPaState, 0, sizeof(BOOL)*l_CityNum);
	memset(l_OrderPbState, 0, sizeof(BOOL)*l_CityNum);//0-->没被调用

	//提取基因并登记
	INT i;

	_CityOrderSa.clear();
	_CityOrderSb.clear();
	for(i = _Begin; i <= _End; ++i)
	{
		_CityOrderSa.push_back(_CityOrderPa[i]);
		l_OrderPaState[_CityOrderPa[i]] = TRUE;

		_CityOrderSb.push_back(_CityOrderPb[i]);
		l_OrderPbState[_CityOrderPb[i]] = TRUE;
	}

	//Show(_CityOrderPb);
	//Show(_CityOrderPa);
	//Show(_CityOrderSb);
	//Show(_CityOrderSa);

	//交叉运算
	INT j;
	i = 0;
	while(i < l_CityNum)
	{
		if( l_OrderPaState[ _CityOrderPb[i] ] )
		{
			_CityOrderPb.erase( _CityOrderPb.begin() + i );
			--l_CityNum;
		}
		else ++i;
	}//抽完了Pa中的基因,下面开始填充

	//Show(_CityOrderPb);

	j = 0;
	for(i = _Begin; i <= _End; ++i)	_CityOrderPb.insert( _CityOrderPb.begin() + i, _CityOrderSa[j++]);
	l_CityNum = _CityOrderPb.size();
	i = 0;
	while(i < l_CityNum)
	{
		if( l_OrderPbState[ _CityOrderPa[i] ] )
		{
			_CityOrderPa.erase( _CityOrderPa.begin() + i );
			--l_CityNum;
		}
		else ++i;
	}//抽完了Pb中的基因,下面开始填充

	//Show(_CityOrderPa);

	j = 0;
	for(i = _Begin; i <= _End; ++i) _CityOrderPa.insert( _CityOrderPa.begin() + i, _CityOrderSb[j++]);

	_CityOrderSa.clear();
	_CityOrderSb.clear();
	_CityOrderSa = _CityOrderPa;
	_CityOrderSb = _CityOrderPb;
	return TRUE;
}

/*
功能：获取当前城市编号的下一个城市编号
输入：城市序列-->CityOrderDef 当前城市号-->INT
输出：当前城市的下一个城市编号-->INT
错误：输出结果为-1；
*/
INT  WSTSP::GetRightIndex_Greedy(CityOrderDef _CityOrder, INT _CurCityNum)
{
	INT l_CityNum = _CityOrder.size();
	INT i, j;
	BOOL l_Find = FALSE;
	for(i = 0; i < l_CityNum; ++i)
	{
		j = _CityOrder[i];
		if(_CurCityNum == _CityOrder[i])
		{
			l_Find = TRUE;
			break;
		}
	}

	if(l_Find)
	{
		if(i == l_CityNum-1) return _CityOrder[0];
		else return _CityOrder[i + 1];
	}

	return -1;