tsp_mmas.cpp

TSP的智能算法

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

//
// TSP_MMAS.cpp :interface for TPS_MMAS class
////////////////////////////////////////////////////////////
#include"stdafx.h"
#include"TSP.h"
#include"TSP_MMAS.h"

#include"TSP_node.h"
#include "TSP_Ant.h"
#include "TSP_DATA.h"

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


TSP_MMAS::TSP_MMAS():m_aTau(NULL), m_aDist(NULL), m_aVis(NULL),
  m_dTau0(-0.5), m_nBeta(2), m_dRho(0.2), m_dQ0(0.9), m_nM(100), m_nTMax(2000),m_nAlpha(1),
  m_aTau_Max(0.0),m_aTau_Min(0.0)
{
}

TSP_MMAS::~TSP_MMAS()
{
	if (m_aTau != NULL)	// all done in group!
	{
		// destroy 2D matrices
		int nDim = GetDim();
		for (int i=0; i<nDim; i++)
		{
			delete[] m_aTau[i];
			delete[] m_aDist[i];
			delete[] m_aVis[i];
		}
		delete[] m_aTau;
		delete[] m_aDist;
		delete[] m_aVis;
	}
	DestroyAnts();
}

void TSP_MMAS::Initialize()
{
	int nDim =GetDim();

	if (m_aTau == NULL)	// all done in group!
	{
		int i=0, j=0;
		// create 2D matrices
		if (nDim != 0)
		{
			m_aTau		= new double*[nDim];
			m_aDist		= new int*[nDim];
			m_aVis		= new double*[nDim];
		}

		for ( i=0; i<nDim; i++)
		{
			m_aTau[i]	= new double[nDim];
			m_aDist[i]	= new int[nDim];
			m_aVis[i]	= new double[nDim];
		}
		for (i=0; i<nDim; i++)
		{
			for (j=0; j<nDim; j++)
			{
//				SetDistAt(i, j, ComputeDistance(GetNodeAt(i), GetNodeAt(j)));
				SetDistAt(i, j, m_pTSPData->GetWeightAt(i, j));
				SetVisAt(i, j, 1.0/GetDistAt(i, j));  //可见度
			}
		}
	}
	if (m_aAnts.GetSize() != GetM())
		CreateAnts();

	m_aTau_Min=1/(2*GetM());
	if ((m_dTau0 < 0.0) && (nDim != 0))
	{
		m_dTau0 =1.0/(m_dRho * ComputeNNTour()) ;
	}
}

void TSP_MMAS::CreateAnts()
{
	if (GetDim() == 0)	// no use for ants
		return;

	DestroyAnts();		// in case recreating

	// ant initialization
	m_aAnts.SetSize(GetM());

	for (int i=0; i<GetM(); i++)
	{
		// chose a city to host the ant
		int nRand = rand() % GetDim();

		// create the ant
		TSP_Ant* pAnt = new TSP_Ant(nRand);
		m_aAnts.SetAt(i, pAnt);
	}
}

void TSP_MMAS::DestroyAnts()
{
	int nAnts = m_aAnts.GetSize();
	for (int i=0; i<nAnts; i++)
	{
		TSP_Ant* pAnt = m_aAnts.GetAt(i);
		delete pAnt;
	}
	m_aAnts.RemoveAll();
}

void TSP_MMAS::ComputeTour()
{
	int i,j;
	int nDim=GetDim();
//	int Avg=nDim/2+1;

	if(m_aTau==NULL)
		Initialize();

	if(m_aAnts.GetSize() != GetM())
		CreateAnts();

	for (i=0; i<nDim; i++)
	{
		for (int j=0; j<nDim; j++)
		{
			SetTauAt(i, j, m_dTau0);
		}
	}

	int nLPlus = 1000000;
	for(i=0; i<GetM(); i++)
	{
		// chose a city to host the ant
		int nRand = rand() % nDim;
		m_aAnts.GetAt(i)->SetHome(nRand);
	}

	for(int t=0;t<GetTMax();t++)
	{
		int nBestTourLen	= nLPlus;		// best this time
		int nBestTourAnt	= -1;
		int *nTourLen=new int[GetM()];
		int nMaxTourLen=0;

		for(i=0; i<GetM(); i++)
		{
			TSP_Ant* pAnt = m_aAnts.GetAt(i);			// current ant

			nTourLen[i] = pAnt->BuildTour(this);		// build tour
			if(i>=2 && nTourLen[i]>=nTourLen[i-1])
			{
				nMaxTourLen=nTourLen[i];
			}
			else
			{
				nMaxTourLen=nTourLen[i-1];
			}
			// in case we find an improve tour this time
			if(nTourLen[i] < nBestTourLen)
			{
				nBestTourLen = nTourLen[i];
				nBestTourAnt = i;				
			}
		}

		if(nBestTourLen != nLPlus)
		{
			nLPlus = nBestTourLen;

			TSP_Ant* pAnt = m_aAnts.GetAt(nBestTourAnt);
			CList<int, int>* plBestTour = pAnt->GetTour();

			// make a copy of the best tour
			m_lBestTour.RemoveAll();
			POSITION pos = plBestTour->GetHeadPosition();

			while(pos != NULL)
			{
				m_lBestTour.AddTail(plBestTour->GetNext(pos));
			}
			m_aTau_Max=1/((1-m_dRho)*nBestTourLen);
			if(m_aTau_Min>=m_aTau_Max)
				m_aTau_Min=m_aTau_Max;

			if(t==0)
			{
				for(i=0;i<nDim;i++)
				{
					for(j=0;j<nDim;j++)
					{
						SetTauAt(i,j,m_aTau_Max);
					}
				}
			}

			cout<<nLPlus<<"  路径如下："<<endl;
			cout<<"迭代次数: "<<t+1<<endl;
			POSITION pss=m_lBestTour.GetHeadPosition();
			for(int k=0;k<m_lBestTour.GetCount();k++)
			{
				int node=m_lBestTour.GetNext(pss);
				cout<<node+1<<"->";
			}
			cout<<endl;
		}

		if(t > 0)
		{
			POSITION pos = m_lBestTour.GetHeadPosition();
			int nodei = m_lBestTour.GetNext(pos);
			int nodefirst = nodei, nodej;
			while(pos != NULL)
			{
				nodej = m_lBestTour.GetNext(pos);
				// global pheremone update rule
				
				SetTauAt(nodei, nodej, (1-GetRho())*GetTauAt(nodei, nodej) + GetRho()/nLPlus);
				
				// symmetric case
				SetTauAt(nodej, nodei, GetTauAt(nodei, nodej));				
				nodei = nodej;
			}
			// last to first;
			SetTauAt(nodei, nodej, (1-GetRho())*GetTauAt(nodej, nodefirst) + GetRho()/nLPlus);
	
			// symmetric case
			SetTauAt(nodefirst, nodej, GetTauAt(nodej, nodefirst));

			for (int nCount1=0; nCount1<nDim; nCount1++)
			{
				for (int nCount2=0; nCount2<GetDim(); nCount2++)
				{
					SetTauAt(nCount1, nCount2, (1-m_dRho)*GetTauAt(nCount1, nCount2));
				}
			}


			for(i=0;i<nDim;i++)
				for(j=0;j<nDim;j++)
				{
					double dTau=GetTauAt(i,j);
					if(dTau>=m_aTau_Max)
						SetTauAt(i,j,m_aTau_Max);
					else if(dTau<=m_aTau_Min)
						SetTauAt(i,j,m_aTau_Min);
				}
		
		}
		if(t==500)
		{
			for (int nCount1=0; nCount1<nDim; nCount1++)
			{
				for (int nCount2=0; nCount2<GetDim(); nCount2++)
				{
					SetTauAt(nCount1, nCount2, m_aTau_Max);
				}
			}
		}
	}
}