wstabosearchalogrithm.cpp

开发环境：Visual C++ .net2003 功能：利用禁忌搜索思想求解TSP问题。

#include "StdAfx.h"
#include ".\wstabosearchalogrithm.h"
#include <fstream>
using namespace std;
WSTaboSearchAlogrithm::WSTaboSearchAlogrithm(void)
{	
	WSRandom::Initial();
}

WSTaboSearchAlogrithm::~WSTaboSearchAlogrithm(void)
{
}
BOOL WSTaboSearchAlogrithm::Initial(PCHAR p_InFileName, PCHAR p_OutFileName, INT p_TaboMode, INT p_TaboLen, INT p_SearchTimes, INT p_SearchSteps)
{
	if(p_TaboMode <=1 ) p_TaboMode = 1;
	else if(p_TaboMode >= 2) p_TaboMode = 2;
	else p_TaboMode = 2;
	m_TaboMode = p_TaboMode;

	switch(m_TaboMode)
	{
	case 1:{Initial1(p_InFileName, p_OutFileName, p_TaboLen, p_SearchTimes, p_SearchSteps); break;}
	case 2:{Initial2(p_InFileName, p_OutFileName, p_TaboLen, p_SearchTimes, p_SearchSteps); break;}
	}
	return TRUE;
	
}
/*
功能：初始化以目标值为禁忌的对象
*/
BOOL WSTaboSearchAlogrithm::Initial1(PCHAR p_InFileName, PCHAR p_OutFileName, INT p_TaboLen, INT p_SearchTimes, INT p_SearchSteps)
{
	//从文件中读取城市信息
	WSTSP::ReadCityInfoFromFile(p_InFileName, m_BaseCityInfo.m_CityInfo);
	m_OutFileName = p_OutFileName;

	//设置禁忌表的长度
	if(p_TaboLen <= 0) m_TaboTableLen = m_BaseCityInfo.m_CityInfo.m_CityNum;
	else m_TaboTableLen = p_TaboLen;

	m_BaseCityInfo.m_distance = WSTSP::TSPTotalDistance(&(m_BaseCityInfo.m_CityInfo));

	//初始化禁忌表
	m_CurBestRoute.m_CityInfo = m_BaseCityInfo.m_CityInfo;
	WSTSP::GenRandCityOrder(m_CurBestRoute.m_CityInfo.m_pCityOrder);
	m_CurBestRoute.m_distance = WSTSP::TSPTotalDistance(&(m_CurBestRoute.m_CityInfo));

	m_BestRoute = m_CurBestRoute;

	INT i;	
	for(i = 0; i < m_TaboTableLen; ++i)	m_TaboTable.push_back(m_CurBestRoute);

	//设置终止准则
	if(p_SearchSteps == 0)
	{
		m_SearchSteps = 0;
		m_SearchTimes = p_SearchTimes;
	}
	else
	{
		m_SearchSteps = p_SearchSteps;
		m_SearchTimes = 0;
	}
	
	return TRUE;
}

/*
功能：初始化城市对格式的禁忌对象
*/
BOOL WSTaboSearchAlogrithm::Initial2(PCHAR p_InFileName, PCHAR p_OutFileName, INT p_TaboLen, INT p_SearchTimes, INT p_SearchSteps)
{
	//从文件中读取城市信息
	WSTSP::ReadCityInfoFromFile(p_InFileName, m_BaseCityInfo.m_CityInfo);
	m_OutFileName = p_OutFileName;

	//设置禁忌表的长度
	if(p_TaboLen <= 0) m_TaboTableLen = m_BaseCityInfo.m_CityInfo.m_CityNum;
	else m_TaboTableLen = p_TaboLen;

	m_BaseCityInfo.m_distance = WSTSP::TSPTotalDistance(&(m_BaseCityInfo.m_CityInfo));

	//初始化禁忌表
	m_CurBestRoute.m_CityInfo = m_BaseCityInfo.m_CityInfo;
	WSTSP::GenRandCityOrder(m_CurBestRoute.m_CityInfo.m_pCityOrder);
	m_CurBestRoute.m_distance = WSTSP::TSPTotalDistance(&(m_CurBestRoute.m_CityInfo));
	m_BestRoute = m_CurBestRoute;

	CityPeer l_CityPeer;
	l_CityPeer.i = 0; l_CityPeer.j = 1;
	WSTSP::SwapTwoCity(m_CurBestRoute.m_CityInfo.m_pCityOrder, 0, 1);

	m_CurBestRoute.m_distance = WSTSP::TSPTotalDistance(&(m_CurBestRoute.m_CityInfo));
	if(m_CurBestRoute.m_distance > m_BestRoute.m_distance) m_CurBestRoute = m_BestRoute;
	else m_BestRoute = m_CurBestRoute;

	//禁忌（0，1）对
	INT i;	
	for(i = 0; i < m_TaboTableLen; ++i) m_TTCityPeer.push_back(l_CityPeer);

	//设置终止准则
	if(p_SearchSteps == 0)
	{
		m_SearchSteps = 0;
		m_SearchTimes = p_SearchTimes;
	}
	else
	{
		m_SearchSteps = p_SearchSteps;
		m_SearchTimes = 0;
	}
	
	return TRUE;
}

/*
功能：生成当前路径的相邻路径子集合。产生方法：随机法。
*/
BOOL WSTaboSearchAlogrithm::GenNeborCityOrder()
{
	CityRouter l_CityRoute;

	INT i = 0;
	while(i++ < m_TaboTableLen)
	{
		l_CityRoute = m_CurBestRoute;
		WSTSP::SwapTwoCity(l_CityRoute.m_CityInfo.m_pCityOrder);
		l_CityRoute.m_distance = WSTSP::TSPTotalDistance(&(l_CityRoute.m_CityInfo));
		m_NeborRoutes.push_back(l_CityRoute);
	}//做了m_TaboTableLen次后完成一轮相邻寻找

	return TRUE;
}
/*
功能：生成当前路径的相邻路径子集合。产生方法：随机法。存储格式为交换的城市对。
*/
BOOL WSTaboSearchAlogrithm::GenNeborCityOrder2()
{
	CityPeerInfo l_CityPeerInfo;
	CityRouter l_NeborCityRoute;

	INT i = 0;
	while(i++ < m_TaboTableLen)
	{
		do{
			l_CityPeerInfo.m_CityPeer.i = WSRandom::GenRand(0, m_BestRoute.m_CityInfo.m_CityNum - 1);
			l_CityPeerInfo.m_CityPeer.j = WSRandom::GenRand(0, m_BestRoute.m_CityInfo.m_CityNum - 1);
		}while(l_CityPeerInfo.m_CityPeer.i == l_CityPeerInfo.m_CityPeer.j);

		l_NeborCityRoute = m_CurBestRoute;
		WSTSP::SwapTwoCity(l_NeborCityRoute.m_CityInfo.m_pCityOrder, l_CityPeerInfo.m_CityPeer.i, l_CityPeerInfo.m_CityPeer.j);
		l_CityPeerInfo.m_Distance = WSTSP::TSPTotalDistance(&(l_NeborCityRoute.m_CityInfo));

		m_TTNeborCityPeer.push_back(l_CityPeerInfo);
	}//做了m_TaboTableLen次后完成一轮相邻寻找
	return TRUE;
}
/*
功能：从当前最佳路径的相邻集合中挑选下一个能担当当前路径的路径
*/
BOOL WSTaboSearchAlogrithm::GetNextRoute()
{
	INT l_BestRouteNum = WSTSP::GetBestRoute(m_NeborRoutes);

	//如果这个解比当前最佳解还要好，说明以前从未见过
	if(m_NeborRoutes[l_BestRouteNum].m_distance < m_BestRoute.m_distance)
	{
		//设置目前为止前最佳路径
		m_BestRoute = m_NeborRoutes[l_BestRouteNum];

		//设置下一次的当前路径
		m_CurBestRoute = m_BestRoute;

		//将禁忌表中最后一个弹出来，并将该路径加入
		m_TaboTable.pop_back();
		m_TaboTable.insert(m_TaboTable.begin(), m_BestRoute);
		m_NeborRoutes.clear();
		return TRUE;
	}

	INT i;
	BOOL l_bFind = TRUE;

	while(!m_NeborRoutes.empty())
	{
		l_bFind = TRUE;
		for(i = 0; i < m_TaboTableLen; ++i)
		{
			if(m_NeborRoutes[l_BestRouteNum].m_distance == m_TaboTable[i].m_distance// &&	WSTSP::EqualOrders(m_NeborRoutes[l_BestRouteNum].m_CityInfo.m_pCityOrder, m_TaboTable[i].m_CityInfo.m_pCityOrder)
				)
			{
				//说明这个路径在禁忌表中，需要抛弃这个选择
				m_NeborRoutes.erase(m_NeborRoutes.begin() + l_BestRouteNum);
				l_bFind = FALSE;
				break;
			}
		}
		//如果未在禁忌表中出现过，则作为当前路径，且将其加入禁忌表
		if(l_bFind) 
		{
			//设置下一次的当前路径
			m_CurBestRoute = m_NeborRoutes[l_BestRouteNum];

			//将禁忌表中最后一个弹出来，并将该路径加入
			m_TaboTable.pop_back();
			m_TaboTable.insert(m_TaboTable.begin(), m_NeborRoutes[l_BestRouteNum]);
			m_NeborRoutes.clear();
			return TRUE;
		}
		l_BestRouteNum = WSTSP::GetBestRoute(m_NeborRoutes);
	}

	m_NeborRoutes.clear();

	return FALSE;
}

BOOL WSTaboSearchAlogrithm::GetNextRoute2()
{
	INT l_BestRouteNum = WSTSP::GetBestRoute(m_TTNeborCityPeer);

	//如果这个解比当前最佳解还要好，说明以前从未见过
	if(m_TTNeborCityPeer[l_BestRouteNum].m_Distance < m_BestRoute.m_distance)
	{
		//设置目前为止前最佳路径
		WSTSP::SwapTwoCity(m_BestRoute.m_CityInfo.m_pCityOrder, m_TTCityPeer[l_BestRouteNum].i, m_TTCityPeer[l_BestRouteNum].j);
		m_BestRoute.m_distance = m_TTNeborCityPeer[l_BestRouteNum].m_Distance;

		//设置下一次的当前路径
		m_CurBestRoute = m_BestRoute;

		//将禁忌表中最后一个弹出来，并将该路径加入
		m_TTCityPeer.pop_back();
		m_TTCityPeer.insert(m_TTCityPeer.begin(), m_TTNeborCityPeer[l_BestRouteNum].m_CityPeer);
		m_TTNeborCityPeer.clear();
		return TRUE;
	}

	INT i;
	BOOL l_bFind = TRUE;

	while(!m_TTNeborCityPeer.empty())
	{
		l_bFind = TRUE;
		for(i = 0; i < m_TaboTableLen; ++i)
		{
			if(m_TTNeborCityPeer[l_BestRouteNum].m_CityPeer.EqualPeer(m_TTCityPeer[i]) )
			{
				//说明这个路径在禁忌表中，需要抛弃这个选择
				m_TTNeborCityPeer.erase(m_TTNeborCityPeer.begin() + l_BestRouteNum);
				l_bFind = FALSE;
				break;
			}
		}

		//如果未在禁忌表中出现过，则作为当前路径，且将其加入禁忌表
		if(l_bFind) 
		{
			//设置下一次的当前路径
			WSTSP::SwapTwoCity(m_CurBestRoute.m_CityInfo.m_pCityOrder,
								m_TTNeborCityPeer[l_BestRouteNum].m_CityPeer.i,
								m_TTNeborCityPeer[l_BestRouteNum].m_CityPeer.j);

			m_CurBestRoute.m_distance = m_TTNeborCityPeer[l_BestRouteNum].m_Distance;

			//将禁忌表中最后一个弹出来，并将该路径加入
			m_TTCityPeer.pop_back();
			m_TTCityPeer.insert(m_TTCityPeer.begin(), m_TTNeborCityPeer[l_BestRouteNum].m_CityPeer);
			m_TTNeborCityPeer.clear();
			return TRUE;
		}
		l_BestRouteNum = WSTSP::GetBestRoute(m_TTNeborCityPeer);
	}

	m_TTNeborCityPeer.clear();

	return FALSE;
}
/*
功能：禁忌搜索工作一步
注意：可能在一次搜索中得到的所有的相邻路径都在禁忌表中，这时需要重新搜索相邻路径。
*/
BOOL WSTaboSearchAlogrithm::SearchOneStep()
{
	switch(m_TaboMode)
	{
	case 1:
		{
			do{
				GenNeborCityOrder();
			}while(!GetNextRoute());
			ShowBestRoute();
			break;
		}
	case 2:
		{
			do{
				GenNeborCityOrder2();
			}while(!GetNextRoute2());
			ShowBestRoute();
			break;
		}	

	return TRUE;
	}
}
/*
功能：开始运行禁忌搜索。
*/
BOOL WSTaboSearchAlogrithm::RunTaboSearch()
{
	//按时间计算
	if(m_SearchSteps == 0)
	{
		int l_Start = clock();
		int l_Delta = 1000*m_SearchTimes;
		do{
			SearchOneStep();
		}while(l_Delta > clock() - l_Start);
	}
	else
	{
		INT i;
		for(i = 0; i < m_SearchSteps; ++i) SearchOneStep();
	}
	return TRUE;
}

VOID WSTaboSearchAlogrithm::ShowBestRoute()
{
	INT i;
	FLOAT l_DeltaTime;
	static int l_CurTime = clock();
	static int l_Step = 0;
	++l_Step;
	l_DeltaTime = ((FLOAT)(clock() - l_CurTime))/1000;

	//printf("当前最佳路径：");
	////for( i = 0; i < m_BaseCityInfo.m_CityInfo.m_CityNum; ++i)
	////{
	////	printf("%2d ", m_BestRoute.m_CityInfo.m_pCityOrder[i]);
	////}
	//printf("路径长：%8.2f\n", m_BestRoute.m_distance);

	//格式化输出
	ofstream outfile;
	outfile.open(m_OutFileName, ios::app);
	outfile<<l_Step<<" "<<l_DeltaTime<<" "<<m_BestRoute.m_distance<<endl;

	/*
	//非格式化输出
	//ofstream outfile;
	//outfile.open(m_OutFileName, ios::app);
	//outfile<<"当前最佳路径：";
	//for( i = 0; i < m_BaseCityInfo.m_CityInfo.m_CityNum; ++i)
	//{
	//	outfile<<m_BestRoute.m_CityInfo.m_pCityOrder[i]<<" ";
	//}
	//outfile<<"路径长："<<m_BestRoute.m_distance<<endl;
	*/
}

VOID WSTaboSearchAlogrithm::ShowBestRouteInfo()
{
	ofstream outfile;
	CHAR l_OutFileName[255] = {0};
	sprintf(l_OutFileName, "%s_Route.txt", m_OutFileName);
	outfile.open(l_OutFileName, ios::out);
	for(int i = 0; i < m_BaseCityInfo.m_CityInfo.m_CityNum; ++i)
	{
		outfile<<m_BestRoute.m_CityInfo.m_pCities[ m_BestRoute.m_CityInfo.m_pCityOrder[i] ].x<<" "<<
			m_BestRoute.m_CityInfo.m_pCities[ m_BestRoute.m_CityInfo.m_pCityOrder[i] ].y<<endl;
	}
	outfile.close();
}