#include "stdafx.h"
|
#include "AnnealingTSP.h"
|
#include <math.h>
|
#include <float.h>
|
|
CAnnealingTSP::CAnnealingTSP(void)
|
{
|
Reset();
|
}
|
|
CAnnealingTSP::~CAnnealingTSP(void)
|
{
|
Reset();
|
}
|
|
void CAnnealingTSP::Reset()
|
{
|
m_vecPathCurrent.clear();
|
|
m_dTemperature = 1000.0; // * The current temperature.
|
m_dTotalDistanceCurrent = DBL_MAX; // * The length of the current path.
|
}
|
|
void CAnnealingTSP::SetPathData(const VectorPathData& vecPathData, const SPathData& ptStart)
|
{
|
if ((int)vecPathData.size()<1) return;
|
|
Reset();
|
|
CGreedyTSP::SetPathData(vecPathData, ptStart);
|
|
m_vecPathCurrent.resize(m_nPathCount);
|
}
|
|
bool CAnnealingTSP::anneal(double d)
|
{
|
if (m_dTemperature < 1.0E-4)
|
{
|
if (d > 0.0)
|
return true;
|
else
|
return false;
|
}
|
|
double random = double(rand())/(1.0*RAND_MAX);
|
|
if (random < exp(d / m_dTemperature))
|
return true;
|
else
|
return false;
|
}
|
|
double CAnnealingTSP::getLength(int i, int j)
|
{
|
int c1 = m_vecPathCurrent[i % m_nPathCount];
|
int c2 = m_vecPathCurrent[j % m_nPathCount];
|
|
return m_pPathGraph[c1][c2];
|
}
|
|
double CAnnealingTSP::CalculateTSP()
|
{
|
if (m_nPathCount<1) return -1.0;
|
|
if (m_nPathCount<2)
|
{
|
return (m_dTotalDistance=GetTotalDistance());
|
}
|
|
srand((unsigned)time(NULL));
|
int nCycle = 1;
|
int nSameCount = 0;
|
|
// copy path result
|
m_vecPathCurrent = m_vecPathResult;
|
m_dTotalDistanceCurrent = m_dTotalDistance;
|
|
while (nSameCount<50)
|
{
|
// make adjustments to city order(annealing)
|
for (int j2 = 0; j2 < m_nPathCount * m_nPathCount; j2++)
|
{
|
int i1 = rand() % m_nPathCount;
|
int j1 = rand() % m_nPathCount;
|
|
double d = getLength(i1, i1 + 1) + getLength(j1, j1 + 1) - getLength(i1, j1) - getLength(i1 + 1, j1 + 1);
|
|
if (anneal(d))
|
{
|
if (j1 < i1)
|
{
|
int k1 = i1;
|
i1 = j1;
|
j1 = k1;
|
}
|
|
for (; j1 > i1; j1--)
|
{
|
int i2 = m_vecPathCurrent[i1 + 1];
|
m_vecPathCurrent[i1 + 1] = m_vecPathCurrent[j1];
|
m_vecPathCurrent[j1] = i2;
|
i1++;
|
}
|
}
|
}
|
|
// See if this improved anything
|
m_dTotalDistanceCurrent = GetTotalDistance(m_vecPathCurrent);
|
|
if (m_dTotalDistanceCurrent < m_dTotalDistance)
|
{
|
m_vecPathResult = m_vecPathCurrent;
|
m_dTotalDistance = m_dTotalDistanceCurrent;
|
nSameCount = 0;
|
}
|
else
|
{
|
nSameCount++;
|
}
|
|
m_dTemperature = m_dDelta * m_dTemperature;
|
|
nCycle++;
|
}
|
|
|
SortingPathResult();
|
|
return m_dTotalDistance;
|
}
|
