?? antsystem.h
字號:
#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?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -