antsystem.h

遗传蚁群tsp算法源码

#pragma once

namespace ACO
{
	//#ifndef __ANTSYSTEM_H                                               
	//#define __ANTSYSTEM_H
	using namespace std;
#include <vector>


	extern CAntConstants gAntConstants;


	class CAnt
	{
	public:
		int currentCity;                //current City
		int nextCity;                    //Next City to Visit
		vector<int>visitedCities; //visited Cities
		vector<int>path;            //current Tour
		int pathIndex;               
		double tourLength;		
		CAnt()
		{
			visitedCities.resize(gAntConstants.MAX_CITIES * gAntConstants.MAX_CITIES);
			path.resize(gAntConstants.MAX_CITIES * gAntConstants.MAX_CITIES);
		}

		~CAnt()
		{
			visitedCities.resize(0);
			path.resize(0);
		}
	};

	class CAntSystem
	{
	public:
		const int MAX_CITIES;		//number of cities
		const int MAX_ANTS;       //number of ants		
		int ALPHA;                       //relative importance of pheromone trail
		int BETA;                         //relative importance of distance between cities
		double RHO;                   //evaporation coefficient
		int QVAL;	
		double INIT_PHEROMONE;//initial pheromone concentration
		

		int _curTime;                     //Number of epochs
		double _elapsedTime;      //Elapsed time in actual algorithm
		CAnt* _ants;               //Pointer to Ants
		CPoint*_cities;                 //Poiner to Cities

		double** _distance;         //Holds the distance between cities
		double** _pheromone;    //Array holds the pheromone concentration
		                                         //between cities
		double _bestSoFar;          //best Tour So Far
		double _worstSoFar;        //worst Tour So Far
		double _bestPossible;
		int _bestIndex;
		int _worstIndex;
		bool _ProblemSolved;        //Problem is Solved
		CChart* _graph;                //Pointer to Graph

		//-------------------------------------------------
		//  Constructor
		//-------------------------------------------------            
		CAntSystem(int CityNo,int AntNo,int Alpha=1,int Beta=1,double Rho=0.5):MAX_CITIES(CityNo),MAX_ANTS(AntNo),
			ALPHA(Alpha),BETA(Beta),RHO(Rho)
		{			
			QVAL= 100;		
			INIT_PHEROMONE = 1.0/MAX_CITIES;			
			//MAX_TOUR = MAX_CITIES*MAX_DISTANCE;
			_bestSoFar = CGlobals::INFINITY;
			_worstSoFar=0;
			_bestPossible=CGlobals::INFINITY;
			_bestIndex=0;
			_worstIndex=0;
			_ProblemSolved=false;
			//Ant ini
			_ants = new CAnt[MAX_ANTS];
			_cities = new CPoint[MAX_CITIES];
			_distance = new double*[MAX_CITIES];

			for(int i = 0;i<MAX_CITIES;i++)
			{
				_distance[i]=new double[MAX_CITIES];
			}

			_pheromone = new double*[MAX_CITIES];
			for(int i = 0;i<MAX_CITIES;i++)
			{
				_pheromone[i]=new double[MAX_CITIES];
			}

			_graph=NULL;
			_elapsedTime=0;
		}

		//-------------------------------------------------
		//  
		//-------------------------------------------------
		~CAntSystem()
		{

			delete[] _ants;
			delete[] _cities;

			for(int i = 0;i<MAX_CITIES;i++)
				delete[] _distance[i];
			delete[]  _distance;

			for(int i = 0;i<MAX_CITIES;i++)
				delete[] _pheromone[i];
			delete[]  _pheromone;			

		}

		void AttachGraph(CChart* pGraph)
		{
			this->_graph=pGraph;
		}

		//-------------------------------------------------
		//  
		//-------------------------------------------------
		double DistanceA_to_B(CPoint a,CPoint b)
		{
			double x_distance = a.x - b.x;
			double y_distance = a.y - b.y;
			return sqrt(x_distance*x_distance + y_distance*y_distance);
		}
		//-------------------------------------------------
		// Calculate_bestPossibleRoute 
		//-------------------------------------------------
		void CalculateBestPossibleRoute()
		{
			_bestPossible = 0;
			double x_distance=0;
			double y_distance=0;
			for(int i = 0;i<MAX_CITIES-1;i++)
			{
				_bestPossible+=DistanceA_to_B(_cities[i],_cities[i+1]);
			}

			_bestPossible+=DistanceA_to_B(_cities[MAX_CITIES-1],_cities[0]);
		}

		//-------------------------------------------------
		//  
		//-------------------------------------------------
		void Init( CRect rect )
		{
			int from, to, ant;
			const int margin = 0;
			double radius;
			int offset = 10;
			int width = rect.right - rect.left;
			int height = rect.bottom-rect.top;


			if(width < height)
			{
				radius = width-offset;
			}
			else
			{
				radius=height-offset;
			}
			
			CPoint midPoint;
			midPoint.x = rect.left + width/2+offset;
			midPoint.y = rect.top + height/2 ;
			//midPoint.x = rect.right- radius+offset;
			//midPoint.y = rect.top + height/2 ;
			double SegmentSize= 2*CGlobals::PI/MAX_CITIES;
			double angle=0;

			/* Create the _cities and their locations */
			for (from = 0 ; from < MAX_CITIES ; from++) {

				/* Randomly place _cities around the grid */
				if (gAntConstants.PM == pmRandom)
				{
					//_cities[from].x = RandomInteger( 0,MAX_DISTANCE );
					//_cities[from].y = RandomInteger( 0,MAX_DISTANCE );
				}
				else if(gAntConstants.PM==pmCircular)
				{
					_cities[from].x = (int)(midPoint.x + sin(angle)*radius/2);
					_cities[from].y = (int)(midPoint.y +cos(angle)*radius/2);
					angle+=SegmentSize;
				}

				for (to = 0 ; to < MAX_CITIES ; to++) {
					_distance[from][to] = 0.0;
					_pheromone[from][to] = INIT_PHEROMONE;
				}

			}

			// Compute the _distances for each of the _cities on the map /
			for ( from = 0 ; from < MAX_CITIES ; from++) 
			{
				for ( to = 0 ; to < MAX_CITIES ; to++) 
				{
					if ((to != from) && (_distance[from][to] == 0.0)) 
					{
						int xd = abs(_cities[from].x - _cities[to].x);
						int yd = abs(_cities[from].y - _cities[to].y);

						_distance[from][to] = sqrt( ((double)xd * xd) + (yd * yd) );
						_distance[to][from] = _distance[from][to];
					}
				}
			}

			// Initialize the _ants /
			to = 0;
			for ( ant = 0 ; ant < MAX_ANTS ; ant++ )
			{
				// Distribute the _ants to each of the _cities uniformly 
				if (to == MAX_CITIES)
					to = 0;
				_ants[ant].currentCity = to++;

				for ( from = 0 ; from < MAX_CITIES ; from++ )
				{
					_ants[ant].visitedCities[from] = 0;
					_ants[ant].path[from] = -1;
				}

				_ants[ant].pathIndex = 1;
				_ants[ant].path[0] = _ants[ant].currentCity;
				_ants[ant].nextCity = -1;
				_ants[ant].tourLength = 0.0;

				// Load the ant's current city into VisitedCities List 
				_ants[ant].visitedCities[_ants[ant].currentCity] = 1;

			}
			this->CalculateBestPossibleRoute();
		}
		//-------------------------------------------------
		//  
		//-------------------------------------------------
		void RestartAntSystem( void )
		{
			int ant, i, to=0;

			for ( ant = 0 ; ant < MAX_ANTS ; ant++ ) {

				if (_ants[ant].tourLength < _bestSoFar) {
					_bestSoFar = _ants[ant].tourLength;
					_bestIndex = ant;
				}

				if (_ants[ant].tourLength > _worstSoFar) {
					_worstSoFar = _ants[ant].tourLength;
					_worstIndex = ant;
				}

				if(abs(_bestSoFar - _bestPossible) <0.0005)
					_ProblemSolved=true;

				_ants[ant].nextCity = -1;
				_ants[ant].tourLength = 0.0;

				for (i = 0 ; i < MAX_CITIES ; i++) {
					_ants[ant].visitedCities[i] = 0;
					_ants[ant].path[i] = -1;
				}

				if (to == MAX_CITIES) to = 0;
				_ants[ant].currentCity = to++;

				_ants[ant].pathIndex = 1;
				_ants[ant].path[0] = _ants[ant].currentCity;

				_ants[ant].visitedCities[_ants[ant].currentCity] = 1;

			}

		}


		//-------------------------------------------------------------------
		//AntProduct
		//------------------------------------------------------------------
		double AntProduct( int from, int to )
		{
			return (( pow( _pheromone[from][to], ALPHA ) *pow( (1.0 / _distance[from][to]), BETA ) ));
		}


		//-------------------------------------------------------------------
		// Select Next City
		//------------------------------------------------------------------
		int GetNextCity( int ant )
		{
			int from, to;
			double denom=0.0;

			// Choose the next city to visit 
			from = _ants[ant].currentCity;

			//Work out denominator of formula
			for (to = 0 ; to < MAX_CITIES ; to++) {
				if (_ants[ant].visitedCities[to] == 0) {
					denom += AntProduct( from, to );
				}
			}	

			do {

				double p;

				to++;
				if (to >= MAX_CITIES) to = 0;
				if ( _ants[ant].visitedCities[to] == 0 ) 
				{

					p = AntProduct(from, to)/denom;
					if (RandomFloat() < p ) 
						break;
				}

			} while (1);
			return to;
		}


		//-------------------------------------------------------------------
		//SimulateAnts
		//------------------------------------------------------------------

		int SimulateAnts( void )
		{
			int k;
			int moving = 0;

			for (k = 0 ; k < MAX_ANTS ; k++) {

				/* Ensure this ant still has _cities to visit */
				if (_ants[k].pathIndex < MAX_CITIES) {

					_ants[k].nextCity = GetNextCity( k );
					_ants[k].visitedCities[_ants[k].nextCity] = 1;
					_ants[k].path[_ants[k].pathIndex++] = _ants[k].nextCity;
					_ants[k].tourLength += _distance[_ants[k].currentCity][_ants[k].nextCity];

					/* Handle the final case (last city to first) */
					if (_ants[k].pathIndex == MAX_CITIES) {
						_ants[k].tourLength += 
							_distance[_ants[k].path[MAX_CITIES-1]][_ants[k].path[0]];
					}

					_ants[k].currentCity = _ants[k].nextCity;
					moving++;
				}

			}

			return moving;
		}


		//-------------------------------------------------------------------
		//UpdateTrails
		//------------------------------------------------------------------

		void UpdateTrails( void )
		{
			int from, to, i, ant;

			/* _pheromone Evaporation */
			for (from = 0 ; from < MAX_CITIES ; from++) {

				for (to = 0 ; to < MAX_CITIES ; to++) {

					if (from != to) {

						_pheromone[from][to] *= (1.0 - RHO);

						if (_pheromone[from][to] < 0.0) _pheromone[from][to] = 0;

					}

				}

			}

			// Add new _pheromone to the trails

			// Look at the tours of each ant
			for (ant = 0 ; ant < MAX_ANTS ; ant++) {

				// Update each leg of the tour given the tour length
				for (i = 0 ; i < MAX_CITIES ; i++) {

					if (i < MAX_CITIES-1) {
						from = _ants[ant].path[i];
						to = _ants[ant].path[i+1];
					} else {
						from = _ants[ant].path[i];
						to = _ants[ant].path[0];
					}

					_pheromone[from][to] += (QVAL / _ants[ant].tourLength);
					_pheromone[to][from] = _pheromone[from][to];

				}

			}

			for (from = 0 ; from < MAX_CITIES ; from++)
			{
				for (to = 0 ; to < MAX_CITIES ; to++) 
				{
					_pheromone[from][to] *= RHO;
				}
			}

		}



		//-------------------------------------------------------------------
		//
		//------------------------------------------------------------------
		void DrawCities(CMemDC* pMemDC)
		{
			int citRad=5;
			for(int i = 0;i<MAX_CITIES;i++)
			{
				pMemDC->Ellipse(_cities[i].x - citRad,_cities[i].y - citRad,_cities[i].x + citRad,_cities[i].y +citRad);
			}
		}

		//-------------------------------------------------------------------
		//
		//------------------------------------------------------------------
		void DrawEdges(CMemDC* pMemDC)
		{
			const int colStep = 255;
			double phLow=1110;
			double phHi = 0;
			double phTemp;
			CPen* oldPen;
			CPen pen;

			//iteratate through _pheromone and find highest and lowest
			for(int i = 0;i<MAX_CITIES;i++)
			{
				for(int j=0;j<MAX_CITIES;j++)
				{
					if(i!=j)
					{
						phTemp = _pheromone[i][j];
						if(phTemp>phHi)
						{
							phHi=phTemp;
						}

						if(phTemp<phLow)
						{
							phLow= phTemp;
						}

					}
				}//inner
			}//outer

			double phStep = (phHi )/colStep;

			for(int i = 0;i<MAX_CITIES;i++)
			{
				for(int j=0;j<MAX_CITIES;j++)
				{
					if(i!=j)
					{
						if(_pheromone[i][j]>INIT_PHEROMONE)
						{
							CPoint ctFrom = _cities[i];
							CPoint ctTo = _cities[j];


							double pher = (_pheromone[i][j]/(phHi))*255;

							//Select the pen
							CColor color;
							color.SetRed((int)(255-pher));
							color.SetGreen((int)(255-pher));
							color.SetBlue((int)(255));							
							CPen pen(PS_SOLID,1,color);						
							oldPen=pMemDC->SelectObject(&pen);
							pMemDC->MoveTo(ctFrom.x,ctFrom.y);
							pMemDC->LineTo(ctTo.x,ctTo.y);					
							pMemDC->SelectObject(oldPen);
						}//if pher<INIT__pheromone

					}
				}//inner
			}//outer
			//Now Write Debug Info
			gFont.SetBold(true);
			gFont.SetUnderline(true);
			pMemDC->SelectObject(gFont);
			char buffer[100];
			sprintf(buffer,"Epoch = %d",_curTime);
			pMemDC->TextOut(52,10,buffer,(int)strlen(buffer));
			gFont.SetBold(false);
			gFont.SetUnderline(false);				
			pMemDC->SelectObject(gFont);

			if(_bestSoFar!=CGlobals::INFINITY)
			{
				sprintf(buffer,"Best  SoFar = %.2f",this->_bestSoFar);
				pMemDC->SetTextColor(CColor::blue);
				pMemDC->TextOut(52,30,buffer,(int)strlen(buffer));
				
			


				sprintf(buffer,"Best Possible = %.2f",this->_bestPossible);
				pMemDC->SetTextColor(CColor::green);
				pMemDC->TextOut(52,50,buffer,(int)strlen(buffer));

				sprintf(buffer,"Elapsed Time = %.2f(ms)",this->_elapsedTime);
				pMemDC->SetTextColor(CColor::black);
				pMemDC->TextOut(52,70,buffer,(int)strlen(buffer));

			}			

			if(this->_graph!=NULL )
			{							
				_graph->SetRange(0,_curTime+50,0,_worstSoFar+1);
				_graph->SetXYValue(_curTime,_bestSoFar,_curTime,0);
				_graph->SetXYValue(_curTime,_bestPossible,_curTime,1);				
			}
		}
	};


}//namespace