tsp_acs.cpp

TSP的智能算法

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

//
// TSP_ACS.cpp :interface for TPS_ACS class
////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "TSP.h"
#include "TSP_ACS.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_ACS::TSP_ACS()
: m_aTau(NULL), m_aDist(NULL), m_aVis(NULL),
  m_dTau0(-0.5), m_nBeta(2), m_dRho(0.1), m_dQ0(0.9), m_nM(100), m_nTMax(1000),m_nAlpha(1)
{
}

TSP_ACS::~TSP_ACS()
{
	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();
}

// This asssumes we cannot modify the world (i.e. world document is static)
void TSP_ACS::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];
		}

		// initialize distance & visibility arrays
		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();

	// initialize the NNH tour & Tau0
	if ((m_dTau0 < 0.0) && (nDim != 0))
	{
		m_dTau0 = 1.0/(nDim * ComputeNNTour());
	}
}

void TSP_ACS::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_ACS::DestroyAnts()
{
	// destroy ants
	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_ACS::ComputeTour()
{
	// counters & constants
	int i=0, j=0;
	int nDim = GetDim();

	// get size, quit if no nodes or not properly initialized

	if (m_aTau == NULL)
		Initialize();	// in case not previously done

	// ant initialization if number of ants changed from last Initialize()
	if (m_aAnts.GetSize() != GetM())
		CreateAnts();

	// data initialization (reset tau to tau0)
	for (i=0; i<nDim; i++)
	{
		for (int j=0; j<nDim; j++)
		{
			SetTauAt(i, j, m_dTau0);
		}
	}

	// shortest tour so far
	int nLPlus = 100000.0;

	//TDO : should this also be done after each time iteration???

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

	// main loop
	for(int t=0; t<GetTMax(); t++)
	{
		int nBestTourLen	= nLPlus;		// best this time
		int nBestTourAnt	= -1;
		int nTourLen		= -1;

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

			nTourLen = pAnt->BuildTour(this);		// build tour

			// in case we find an improve tour this time
			if(nTourLen < nBestTourLen)
			{
				nBestTourLen = nTourLen;
				nBestTourAnt = i;
				//cout<<nBestTourLen<<"->"<<endl;
			}
		}

		// check if improved tour is found
		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));
			}
			
			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;
		}

		// update edge pheromone trails
		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(nodej, nodefirst, (1-GetRho())*GetTauAt(nodej, nodefirst) + GetRho()/nLPlus);

		// symmetric case
		SetTauAt(nodefirst, nodej, GetTauAt(nodej, nodefirst));
	}

}