tspts.cpp

用禁忌搜索解决TSP问题

//author: yinhui
//Date  : 2007.06.15

//TSPSA.cpp

#include "StdAfx.h"
#include "tspts.h"
#include <math.h>
#include <algorithm>

#define MAX_SAME 40

void TabuSearch::Init()
{
	srand((unsigned)time(NULL));
	ComputeTotalDistace();
	CreateInitSolution(m_vecRouter);
}

void TabuSearch::ObtainParams(int nTabuLength, int nCandSize, int nIterCount, 
							 int nSameCount, VecCity vCitys, int nCityNum)
{
	m_nTabuLength = nTabuLength;
	m_nCandSize = nCandSize;
	m_nSameCount = nSameCount;
	m_nIterCount = nIterCount;
	m_vecCitys = vCitys;
	m_nCityNum = nCityNum;
}

void TabuSearch::CreateInitSolution(vecCityRouter& initRouter)
{
	for (int i=1; i<=m_nCityNum; i++)
	{
		initRouter.push_back(i);
		//m_vecRouter.push_back(i);
	}
	std::random_shuffle(initRouter.begin(), initRouter.end());
}

vecCityRouter TabuSearch::NextSolution()
{
	int fSwap, eSwap;
	vecCityRouter tempRouter;
	tempRouter = m_vecRouter;

	while (1)
	{
		fSwap = (rand()%m_nCityNum)-1;
		if (fSwap>=0)
			break;
	}

	while (1)
	{
		eSwap = (rand()%m_nCityNum)-1;
		if ((eSwap!=fSwap) && (eSwap>=0))
		{
			int temp = tempRouter[fSwap];
			int xx = tempRouter[eSwap];
			tempRouter[fSwap] = tempRouter[eSwap];
			tempRouter[eSwap] = temp;
			break;
		}
	}
	return tempRouter;
}

void TabuSearch::ComputeTotalDistace()
{
	std::vector<City>::iterator fCityIter;
	std::vector<City>::iterator eCityIter;

	Distance tempDist;

	for (fCityIter=m_vecCitys.begin(); fCityIter!=m_vecCitys.end(); fCityIter++)
	{
		for (eCityIter=m_vecCitys.begin(); eCityIter!=m_vecCitys.end(); eCityIter++)
		{
			ComputeDistance(*fCityIter, *eCityIter, tempDist);
			m_vecDistance.push_back(tempDist);
		}
	}
}

double TabuSearch::ComputeDistance(City& fCity, City& eCity, Distance& cityDist)
{
	double tempDist;

	float fCityX = fCity.m_corCity.m_fX;
	float fCityY = fCity.m_corCity.m_fY;
	float eCityX = eCity.m_corCity.m_fX;
	float eCityY = eCity.m_corCity.m_fY;

	tempDist = sqrt((fCityX-eCityX)*(fCityX-eCityX) +
		            (fCityY-eCityY)*(fCityY-eCityY));

	cityDist.m_nFromCity = fCity.m_nIndex;
	cityDist.m_nEndCity = eCity.m_nIndex;
	cityDist.m_fDist = (float)tempDist;

	return tempDist;
}

double TabuSearch::FindDistance(int fIndex, int eIndex)
{
	VecDistance::iterator tempIter;

	for (tempIter=m_vecDistance.begin(); tempIter!=m_vecDistance.end(); tempIter++)
	{
		if ((tempIter->m_nFromCity==fIndex) && (tempIter->m_nEndCity==eIndex))
		{
			return tempIter->m_fDist;
		}
	}
	return 0.0;
}

double TabuSearch::ComputeRouterDistance(vecCityRouter& curCityRou)
{
	vecCityRouter::iterator tempRouterIter;
	double allDist=0.0;

	for (tempRouterIter=curCityRou.begin(); tempRouterIter!=(curCityRou.end()-1); tempRouterIter++)
	{
		allDist += FindDistance(*tempRouterIter, *(tempRouterIter+1));
	}

	allDist += FindDistance(*(curCityRou.end()), *(curCityRou.begin()));
	return allDist;
}

float TabuSearch::GetNowDistance()
{
	float dist;
	dist = (float)ComputeRouterDistance(m_vecRouter);
	return dist;
}

float TabuSearch::DoOneSearch(float t)
{
	double currDist = ComputeRouterDistance(m_vecRouter);
	vecCityRouter nextRouter = NextSolution();
	double nextDist = ComputeRouterDistance(nextRouter);

	double random = (double)rand()/(double)RAND_MAX;
	if ((nextDist-currDist) < 1.0e-6)
	{
		m_vecRouter = nextRouter;
	}
	/*else if (exp((currDist-nextDist)/t) > random)
	{
		m_vecRouter = nextRouter;
	}*/
		
	return (float)nextDist;
}

void TabuSearch::TSPTabuSearch(CListBox *pLB)
{
	pLB->ResetContent();
	CString strDisplay, strValue;
	strDisplay = "城市个数：";
	strValue.Format("%d\n", m_nCityNum);
	strDisplay += strValue;
	pLB->InsertString(0,strDisplay);

	int nIterCount = 0;    //对迭代次数计数
	int nSameCount = 0;    //对最优解重复次数计数
	int nCandCount = 0;    //候选解总个数
	int i = 0;

	listTabuList tl;
	TabuListItem tlItem;

	double dNowDist = ComputeRouterDistance(m_vecRouter);
	tlItem.length = dNowDist;
	tlItem.count = MAXTABUCOUNT;
	tl.push_back(tlItem);

	vecCityRouter vecNextRouter;

	double dBestDist = dNowDist;
	double tempDist = 0;
	double countDist = dNowDist;    //记录相同解

	
	strDisplay = "初始距离：";
	strValue.Format("%f\n", dBestDist);
	strDisplay += strValue;
	pLB->InsertString(0, strDisplay);

	while (nIterCount<m_nIterCount && nSameCount<m_nSameCount)
	{
		while (nCandCount<m_nCandSize)
		{
			nCandCount++;
            vecNextRouter = NextSolution();
			dNowDist = ComputeRouterDistance(vecNextRouter);

			listTabuList::iterator iterList;
			for (iterList=tl.begin(); iterList!=tl.end(); iterList++)
			{
				tempDist = iterList->length;
				if ((abs(dNowDist-tempDist)) < 1.0e-8)
				{//如果距离已在禁忌表中
					(iterList->count)--;
					if (iterList->count == 0)
					{//如果已满足特赦条件
						tl.erase(iterList);
						nCandCount--;
					}
					break;
				}else
				{//如果距离不在禁忌表中
					tlItem.length = dNowDist;
					tlItem.count = MAXTABUCOUNT;

					if (tl.size() < m_nTabuLength)
					{//如果禁忌表未满
						tl.push_back(tlItem);
					}
					else
					{//如果禁忌表已满,从表头删除一个元素
						tl.pop_front();
						tl.push_back(tlItem);
					}
				}
			}//end for (iterList=tl.begin(); iterList!=tl.end(); iterList++)

			//从候选集中选择最优解
			if (dNowDist < dBestDist)
			{//当前解更忧
				dBestDist = dNowDist;
				m_vecRouter = vecNextRouter;
			}
			strDisplay = "当前最优解：";
	        strValue.Format("%f\n", dBestDist);
	        strDisplay += strValue;
	        pLB->InsertString(0, strDisplay);

		}//end while (nCandCount<m_nCandSize)
		if (abs(countDist-dBestDist) < 1.0e-8)
		{//相同解又出现
			nSameCount++;
		}
		else
		{
			nSameCount = 0;
			countDist = dBestDist;
		}
		
		nIterCount++;
	}//end while (nIterCount<m_nIterCount && nSameCount<m_nSameCount)
}