tsp_as.cpp

TSP的智能算法

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

//
// TSP_AS.cpp :interface for TPS_AS class
////////////////////////////////////////////////////////////


#include "stdafx.h"
#include "TSP.h"
#include "TSP_AS.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_AS::TSP_AS()
{
	// arrays数组初始化，原来声明的是二级指针
	m_aTau	= NULL;
	m_aDist = NULL;
	m_aVis  = NULL;

	// constants
	m_dTau0		= 10e-6;

	m_nAlpha	= 1;
	m_nBeta		= 5;
	m_dRho		= 0.5;
	m_nM		= 10;		// temp

	m_nE		= 5;
	m_nQ		= 100;

	m_nTMax		= 2000;
}

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

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

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

		for (int i=0; i<nDim; i++)
		{
			m_aTau[i]	= new double[nDim];
			m_aDist[i]	= new int[nDim];
			m_aVis[i]	= new double[nDim];
		}
	}

	m_nM = nDim;		// m=n
}

void TSP_AS::ComputeTour()
{
	// 得到问题的规模, 如果没有问题就退出
	
	int nDim = GetDim();
	//if (nDim == 0)
	//	return -1;

	if (m_aTau == NULL)
	{
		Initialize();
	}

	int nCount1 = 0, nCount2 = 0;

	// 数据初始化，初始激素，弧长和可见度
	for (nCount1=0; nCount1<nDim; nCount1++)
	{
		for (int nCount2=0; nCount2<nDim; nCount2++)
		{
			SetTauAt(nCount1, nCount2, m_dTau0);
			SetDistAt(nCount1, nCount2, m_pTSPData->GetWeightAt(nCount1, nCount2));

			SetVisAt(nCount1, nCount2, 1.0/GetDistAt(nCount1, nCount2));
		}
	}

	// 蚂蚁初始化
	CTypedPtrArray<CPtrArray, TSP_Ant*> aAnts;
	aAnts.SetSize(m_nM);

	for (nCount1=0; nCount1<m_nM; nCount1++)
	{
		// 设置蚂蚁的初始位置
		int nRand = rand() % nDim;

		// create the ant
		TSP_Ant* pAnt = new TSP_Ant(nRand);

		aAnts.SetAt(nCount1, pAnt);
	}

	// 将最短路径设置为一个很大的数
	int nLPlus = 1000000;

	// main loop    主循环
	for (int t=0; t<m_nTMax; t++)
	{
		int k				= 0;
		int nBestTourLen	= nLPlus;		// 每次循环中的最优路径
		int nBestTourAnt	= -1;
		int nTourLen		= -1;

		// build tour for each ant
		for (k=0; k<m_nM; k++)
		{
			TSP_Ant * pAnt = aAnts.GetAt(k);			// current ant

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

			// in case we find an improve tour this time
			if (nTourLen < nBestTourLen)
			{
				nBestTourLen = nTourLen;
				nBestTourAnt = k;					
			}
		}

		// check if improved tour is found
		if (nBestTourLen != nLPlus)
		{
			nLPlus = nBestTourLen;

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

			cout<<"至该迭代次数的最优解为："<<nLPlus<<endl;
			cout<<"迭代次数: "<<t+1<<endl;

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

			while (pos != NULL)
			{
				m_lBestTour.AddTail(plBestTour->GetNext(pos));
			}
		}
		

		// update edge pheromone trails

		// first we go through each edge and decay the pheremone
		for (nCount1=0; nCount1<nDim; nCount1++)
		{
			for (int nCount2=0; nCount2<GetDim(); nCount2++)
			{
				SetTauAt(nCount1, nCount2, (1-m_dRho)*GetTauAt(nCount1, nCount2));
			}
		}

		// then we ask each ant to contribute to the edges it visited
		for (k=0; k<GetM(); k++)
		{
			TSP_Ant* pAnt = aAnts.GetAt(k);			// current ant
			pAnt->GlobalUpdate(this);
		}

		// then we introduce elitist ants on the best tour
		POSITION pos = m_lBestTour.GetHeadPosition();
		int nodei = m_lBestTour.GetNext(pos);
		int nodefirst = nodei, nodej;

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

			// global pheromone update rule
			SetTauAt(nodei, nodej, GetTauAt(nodei, nodej) + GetE()*GetQ()/nLPlus);

			// symmetric case
		//	if (IsSymmetric())
				SetTauAt(nodej, nodei, GetTauAt(nodei, nodej));

			nodei = nodej;
		}
		// last to first;
		SetTauAt(nodej, nodefirst, GetTauAt(nodej, nodefirst) + GetE()*GetQ()/nLPlus);

	
		SetTauAt(nodefirst, nodej, GetTauAt(nodej, nodefirst));

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

	}
	// end main loop

	// destroy ants
	for (nCount1=0; nCount1<GetM(); nCount1++)
	{
		TSP_Ant* pAnt = aAnts.GetAt(nCount1);
		delete pAnt;
	}
	aAnts.RemoveAll();

	// return our tour length
	//cout<<nLPlus<<endl;
}