tsp_ant.cpp

TSP的智能算法

///////////////////////////////////////////////////////////
// This virsion is AntSystem 1.0
// author: zhaochaoqing ChongQing University
//
//the author can be contacted at:
//   Email: [e-mail]
//
////////////////////////////////////////////////////////////

//
// TSP_Ant.h :interface for TPS_Ant class
////////////////////////////////////////////////////////////

#include"stdafx.h"
#include "TSP.h"
#include "TSP_Ant.h"
#include "TSP_node.h"
#include"TSP_ACS.h"
#include"TSP_MMAS.h"

#include "TSP_Generic.h"
#include "TSP_AS.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

TSP_Ant::TSP_Ant(/*int nID, */int nHomeID)
{
//	m_nID			= nID;
	m_nHomeID		= nHomeID;
	m_nTourLength	= 0;
}

TSP_Ant::TSP_Ant(const TSP_Ant & ant) //拷贝构造
{
//	m_nID			= ant.nID;
	m_nHomeID		= ant.m_nHomeID;
	m_nTourLength	= ant.m_nTourLength;

	// copy the tour?  //TDO : necessary?
}

CList<int, int>* TSP_Ant::GetTour()
{
	return & m_lTour;
}

TSP_Ant::~TSP_Ant()
{
	m_lTour.RemoveAll();
}

const TSP_Ant & TSP_Ant::operator=(const TSP_Ant & ant)
{
//	m_nID			= ant.nID;
	m_nHomeID		= ant.m_nHomeID;
	m_nTourLength	= ant.m_nTourLength;

	// copy the tour?  //TDO : necessary?
	return *this;
}

void TSP_Ant::SetHome(int nHome)
{
	m_nHomeID = nHome;
}

void TSP_Ant::GlobalUpdate(TSP_AS *pAS)
{
	POSITION pos = m_lTour.GetHeadPosition();
	int nodei = m_lTour.GetNext(pos);
	int nodefirst = nodei, nodej;

	while (pos != NULL)
	{
		nodej = m_lTour.GetNext(pos);

		// global pheromone update rule
		pAS->SetTauAt(nodei, nodej, pAS->GetTauAt(nodei, nodej) + pAS->GetQ()/m_nTourLength);

		// symmetric case
		pAS->SetTauAt(nodej, nodei, pAS->GetTauAt(nodei, nodej));

		nodei = nodej;
	}
	// last to first尾结点接首结点;
	pAS->SetTauAt(nodej, nodefirst, pAS->GetTauAt(nodej, nodefirst) + pAS->GetQ()/m_nTourLength);

	// symmetric case
	pAS->SetTauAt(nodefirst, nodej, pAS->GetTauAt(nodej, nodefirst));

}


double TSP_Ant::BuildTour(TSP_AS *pAS)
{
	// reset tour info
	m_lTour.RemoveAll();
	m_nTourLength = 0;

	// add home city first
	m_lTour.AddTail(m_nHomeID);

	int i = m_nHomeID;
	int j = -1;
	POSITION posJ = NULL;

	// create a tabu list storing cities not yet visited
	CList<int, int> lToVisit;

	int node = -1;
 	for (int city=0; city < pAS->GetDim(); city++)
	{
		if (city != m_nHomeID)
		{
			lToVisit.AddTail(city);
		}
	}

	while (!lToVisit.IsEmpty())
	{
		// find the sum over all remaining nodes
		double dSum = 0;
		POSITION pos = NULL;
		int u = 0;

		pos = lToVisit.GetHeadPosition();
		while (pos != NULL)
		{
			u = lToVisit.GetNext(pos);
			dSum += pow(pAS->GetTauAt(i, u), (double)pAS->GetAlpha()) 
				    * pow(pAS->GetVisAt(i, u),(double)pAS->GetBeta());
		}

		// probability matrix
		int nVisitSize = lToVisit.GetCount();
		double* aProbs = new double[nVisitSize];

		// calculate accumulated probabilities
		pos = lToVisit.GetHeadPosition();
		int nIdx = 0;
		double dCurSum = 0.0;

		while (pos != NULL)
		{
			u = lToVisit.GetNext(pos);
			//返回的是连标中pos所指的元素并将pos指向下一个元素，
			//调用GetNext后pos的值就改变了

			double dRatio = (pow(pAS->GetTauAt(i, u),(double)pAS->GetAlpha()) * 
							 pow(pAS->GetVisAt(i, u),(double)pAS->GetBeta())) / dSum;
			dCurSum += dRatio;

			aProbs[nIdx] = dCurSum;

			nIdx++;
		}

	
		double dProb = rand() / (RAND_MAX+1.0);

		for (nIdx = 0; nIdx < nVisitSize; nIdx++)
		{
			// go from the back since the probs are larger there
			// stop if we have low enough

			double dMyProb = aProbs[nIdx];
			if (dProb <= (dMyProb+0.00001))
			{
				posJ = lToVisit.FindIndex(nIdx);	// we want the last one that was above
				j = lToVisit.GetAt(posJ);
				break;
			}
		}
		if ((j==i) || (j==-1))	// means take the largest
		{
			posJ = lToVisit.FindIndex(nVisitSize-1);	// we want the last one that was above
			j = lToVisit.GetAt(posJ);
		}

		// now we add the new node to the tour and remove from unvisited list
		m_lTour.AddTail(lToVisit.GetAt(posJ));

		lToVisit.RemoveAt(posJ);

		i = j;

		// cleanup
		delete[] aProbs;
	}

	// we finished calculating the tour, now find its length

	POSITION pos = m_lTour.GetHeadPosition();
	int nodei = m_lTour.GetNext(pos);
	int nodefirst = nodei;
	int nodej = -1;

	while (pos != NULL)
	{
		nodej = m_lTour.GetNext(pos);

		m_nTourLength += pAS->GetDistAt(nodei, nodej);

		nodei = nodej;
	}
	// last to first;
	m_nTourLength += pAS->GetDistAt(nodej, nodefirst);

	return m_nTourLength;
}

double TSP_Ant::BuildTour(TSP_ACS * pACS)
{
	// first try - no candidate lists

	// reset tour info
	m_lTour.RemoveAll();
	m_nTourLength = 0.0;

	// add home city first
	m_lTour.AddTail(m_nHomeID);

	int i = m_nHomeID;
	int j = -1;
	POSITION posJ = NULL;

	// create a tabu list storing cities not yet visited
	CList<int, int> lToVisit;

	int node = -1;
	for (int city=0; city<pACS->GetDim(); city++)
	{
		if (city != m_nHomeID)
		{
			lToVisit.AddTail(city);
		}
	}

	while (!lToVisit.IsEmpty())
	{
		// Choose which formula to follow
		double dQ = (rand() % 101) / 100.0;

		if (dQ <= pACS->GetQ0())
		{
			double dMax = -1.0;
			int nMaxCity = -1;
			POSITION posMaxCity = NULL;

			POSITION pos = lToVisit.GetHeadPosition();// 返回的是链表头元素的位置 
			POSITION posPrev = pos;

			int u = 0;
			double dArg = 0.0;

			while (pos != NULL)
			{
				u = lToVisit.GetNext(pos);//返回的是连标中pos所指的元素并将pos指向下一个元素   
                                          // 调用GetNext后pos的值就改变了   

				dArg = pACS->GetTauAt(i, u) * pow(pACS->GetVisAt(i, u),(double)pACS->GetBeta());

				if (dArg > dMax)
				{
					dMax = dArg;
					nMaxCity = u;
					posMaxCity = posPrev;
				}
				posPrev = pos;
			}

			// we now know the next city to visit
			j = nMaxCity;
			posJ = posMaxCity;
		}
		else
		{
			// find the sum over all remaining nodes
			double dSum = 0;
			POSITION pos = NULL;
			int u = 0;

			pos = lToVisit.GetHeadPosition();
			while (pos != NULL)
			{
				u = lToVisit.GetNext(pos);
				dSum += pow(pACS->GetTauAt(i, u),(double)pACS->GetAlpha()) * pow(pACS->GetVisAt(i, u),(double)pACS->GetBeta());
			}

			// probability matrix
//			CArray<double,double> aProbs;
//			aProbs.SetSize(lToVisit.GetCount());
			int nVisitSize = lToVisit.GetCount();
			double* aProbs = new double[nVisitSize];

			// calculate accumulated probabilities
			pos = lToVisit.GetHeadPosition();
			int nIdx = 0;
			double dCurSum = 0.0;

			while (pos != NULL)
			{
				u = lToVisit.GetNext(pos);

				double dRatio = (pow(pACS->GetTauAt(i, u),(double)pACS->GetAlpha ()) * pow(pACS->GetVisAt(i, u),(double)pACS->GetBeta()))/dSum;
				dCurSum += dRatio;

//				aProbs.SetAt(nIdx, dCurSum);
				aProbs[nIdx] = dCurSum;
				nIdx++;
			}
			
			// find the desired next node
			double dProb = rand() / (RAND_MAX+1.0);

//			for (nIdx = 0; nIdx < aProbs.GetSize(); nIdx++)
			for (nIdx = 0; nIdx < nVisitSize; nIdx++)
			{
//				double dMyProb = aProbs.GetAt(nIdx);
				double dMyProb = aProbs[nIdx]+0.000001;
				if (dProb <= dMyProb)
				{
					posJ = lToVisit.FindIndex(nIdx);	// we want the last one that was above
					j = lToVisit.GetAt(posJ);
					break;
				}
			}
			if ((j==i) || (j==-1))	// means take the largest
			{
				posJ = lToVisit.FindIndex(nVisitSize-1);	// we want the last one that was above
				j = lToVisit.GetAt(posJ);
			}

			delete[] aProbs;
		}

		// now we add the new node to the tour 
		m_lTour.AddTail(lToVisit.GetAt(posJ));

		lToVisit.RemoveAt(posJ);  //remove from unvisited list

		// do local update of pheremones
		pACS->SetTauAt(i, j, (1 - pACS->GetRho()) * pACS->GetTauAt(i,j) 
			+ pACS->GetRho() * pACS->GetTau0());

		// symmetric case
	//	if (pACS->IsSymmetric())
		pACS->SetTauAt(j, i, pACS->GetTauAt(i, j));

		// set i to j
		i = j;
	}
	// we finished calculating the tour, now find its length

	POSITION pos = m_lTour.GetHeadPosition();
	int nodei = m_lTour.GetNext(pos);
	int nodefirst = nodei;
	int nodej = -1;

	while (pos != NULL)
	{
		nodej = m_lTour.GetNext(pos);

		m_nTourLength += pACS->GetDistAt(nodei, nodej);

		nodei = nodej;
	}
	// last to first;
	m_nTourLength += pACS->GetDistAt(nodej, nodefirst);

	return m_nTourLength;
}

double TSP_Ant::BuildTour(TSP_MMAS* pMMAS)
{
	m_lTour.RemoveAll();
	m_nTourLength=0.0;

	m_lTour.AddTail(m_nHomeID);

	int i=m_nHomeID;
	int j=-1;
	POSITION posJ=NULL;

	CList<int,int> lToVisit;

	int node=-1;
	for(int city=0;city<pMMAS->GetDim();city++)
	{
		if(city != m_nHomeID)
		{
			lToVisit.AddTail(city);
		}
	}

	while(!lToVisit.IsEmpty())
	{
		double dQ0=(rand()%101)/100;
		if(dQ0 <= pMMAS->GetQ0())
		{
			double dMax=-1.0;
			int nMaxCity=-1;
			POSITION posMaxCity=NULL;

			POSITION pos=lToVisit.GetHeadPosition();
			POSITION posPrev=pos;

			int u=0;
			double dArg=0.0;

			while(pos != NULL)
			{
				u=lToVisit.GetNext(pos);

				dArg=pMMAS->GetTauAt(i,u)*pow(pMMAS->GetVisAt(i,u),(double)pMMAS->GetBeta());
				if(dArg>dMax)
				{
					dMax=dArg;
					nMaxCity=u;
					posMaxCity=posPrev;
				}
				posPrev = pos;
			}
			j=nMaxCity;
			posJ=posMaxCity;
		}		
		else
		{
			double dSum=0.0;
			POSITION pos=NULL;
			int u=0;

			pos=lToVisit.GetHeadPosition();
			while(pos != NULL)
			{
				u=lToVisit.GetNext(pos);
				dSum += pow(pMMAS->GetTauAt(i,u),(double)pMMAS->GetAlpha())*pow(pMMAS->GetTauAt(i,u),(double)pMMAS->GetBeta());
			}

			int nVisitSize=lToVisit.GetCount();
			double* aProbs=new double[nVisitSize];

			pos=lToVisit.GetHeadPosition();
			int Index=0;
			double dCurSum=0.0;

			while(pos !=NULL)
			{
				u=lToVisit.GetNext(pos);
				double Ratio=pow(pMMAS->GetTauAt(i,u),(double)pMMAS->GetAlpha())*pow(pMMAS->GetTauAt(i,u),(double)pMMAS->GetBeta())/dSum;
				dCurSum +=Ratio;
				aProbs[Index]=dCurSum;
				Index++;				
			}
			double prob=rand()/(RAND_MAX+1.0);

			for(Index=0;Index<nVisitSize;Index++)
			{
				double MyProb=aProbs[Index];
				if(prob<(MyProb+0.00001))
				{
					posJ=lToVisit.FindIndex(Index);
					j=lToVisit.GetAt(posJ);
					break;					
				}
			}
			if ((j==i) || (j==-1))	
			{
				posJ = lToVisit.FindIndex(nVisitSize-1);
				j = lToVisit.GetAt(posJ);
			}

			delete[] aProbs;			
		}
		m_lTour.AddTail(lToVisit.GetAt(posJ));
		lToVisit.RemoveAt(posJ);
		//pMMAS->SetTauAt(i, j, (1 - pMMAS->GetRho()) * pMMAS->GetTauAt(i,j) 
		//	+ pMMAS->GetRho() * pMMAS->GetTau0());

		// symmetric case
		//pMMAS->SetTauAt(j, i, pMMAS->GetTauAt(i, j));
		i=j;
	}
	POSITION pos = m_lTour.GetHeadPosition();
	int nodei = m_lTour.GetNext(pos);
	int nodefirst = nodei;
	int nodej = -1;

	while (pos != NULL)
	{
		nodej = m_lTour.GetNext(pos);

		m_nTourLength += pMMAS->GetDistAt(nodei, nodej);

		nodei = nodej;
	}
	// last to first;
	m_nTourLength += pMMAS->GetDistAt(nodej, nodefirst);

	return m_nTourLength;

}