#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include "Individual.h"
Individual::Individual (TSP * pTSP0, Group * pGroup0, TspLog * pTspLog0)
{
int i;
pTspLog = pTspLog0;
lfFitness = 0;
pTSP = pTSP0;
pGroup = pGroup0;
iNbCities = pTSP->iNbCities;
Cities = new int[iNbCities];
for (i = 0; i < iNbCities; i++)
{
Cities[i] = i;
}
}
Individual::~Individual ()
{
delete[] Cities;
}
void Individual::Duplicate (const Individual & I)
{
int i;
lfFitness = I.lfFitness;
for (i = 0; i < iNbCities; i++)
{
Cities[i] = I.Cities[i];
}
}
void Individual::RandomInit ()
{
int i, a, b;
for (i = 0; i < iNbCities; i++)
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
ExchangeCities (a, b);
}
}
void Individual::NearestNeighbourInit (Individual & I_temp, int iStartCity)
{
int i, a, b, iCurrentPos, iCurrentCity, iPosCityZero;
for (i = 0; i < iNbCities; i++)
{
I_temp.Cities[i] = -1;
}
iCurrentCity = iStartCity;
I_temp.Cities[0] = iCurrentCity;
for (iCurrentPos = 1; iCurrentPos < iNbCities; iCurrentPos++)
{
b = 0;
a = pTSP->Near (iCurrentCity, b);
while ((I_temp.FindCityPos (a) != -1) && (b < pTSP->iNbNear - 1))
{
b++;
a = pTSP->Near (iCurrentCity, b);
}
if (b == pTSP->iNbNear - 1)
{
do
{
a = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
}
while (I_temp.FindCityPos (a) != -1);
}
iCurrentCity = a;
I_temp.Cities[iCurrentPos] = iCurrentCity;
}
iPosCityZero = I_temp.FindCityPos (0);
for (i = iPosCityZero; i < iNbCities; i++)
{
Cities[i - iPosCityZero] = I_temp.Cities[i];
}
for (i = 0; i < iPosCityZero; i++)
{
Cities[i + iNbCities - iPosCityZero] = I_temp.Cities[i];
}
}
void Individual::Eval ()
{
int i;
lfFitness = 0;
for (i = 0; i < iNbCities - 1; i++)
{
lfFitness -= pTSP->Distance (Cities[i], Cities[i + 1]);
}
lfFitness -= pTSP->Distance (Cities[iNbCities - 1], Cities[0]);
if (!(pTSP->bTSPLIB))
{
lfFitness = (float) ((int) (lfFitness * 10000)) / 10000.;
}
}
void Individual::Read (FILE * fGroup)
{
char sLine[MAX_LENLINE + 1];
char *sCity;
int i;
fgets (sLine, MAX_LENLINE, fGroup);
sCity = strtok (sLine, "-\n");
for (i = 0; i < iNbCities; i++)
{
sCity = strtok (NULL, "-\n");
if (sCity != NULL)
{
Cities[i] = atoi (sCity);
}
else
{
pTspLog->ErrorMsg("*** Erreur : impossible de lire correctement l'individu\n");
}
}
Eval ();
}
void Individual::Write (FILE * fGroup)
{
int i;
fprintf (fGroup, "%.5f-", lfFitness);
for (i = 0; i < iNbCities; i++)
{
if ((Cities[i]) >= 0)
{
fprintf (fGroup, "%d-", Cities[i]);
}
}
fprintf (fGroup, "\n");
}
void Individual::LogRecord (int iCurrentIteration)
{
int i;
char sCity[10];
char *sPath;
sprintf (sCity, "%d-", iNbCities);
sPath = (char *) malloc (strlen (sCity) * sizeof (char) * iNbCities);
strcpy (sPath, "");
for (i = 0; i < iNbCities; i++)
{
if ((Cities[i]) >= 0)
{
sprintf (sPath, "%s%d-", sPath, Cities[i]);
}
}
pTspLog->LogRecord (iCurrentIteration, sPath, lfFitness, pTSP->iNbCities,
pTSP->bDefaultProblem, pTSP->bTSPLIB,
pTSP->getCitiesPosX (), pTSP->getCitiesPosY ());
free (sPath);
}
int Individual::FindCityPos (int iCity)
{
int i;
bool bFound;
bFound = false;
i = 0;
while ((!bFound) && (i < iNbCities))
{
bFound = (Cities[i] == iCity);
i++;
}
if (bFound)
{
return i - 1;
}
else
{
return -1;
}
}
int Individual::FindNextUnvisitedCity (int iCurrentCity, Individual & I_temp)
{
int a, a1, a2, ok1, ok2;
a = FindCityPos (iCurrentCity);
a1 = a;
a2 = a;
ok2 = 10;
do
{
a1 = (a1 + 1) % iNbCities;
a2 = (a2 - 1 + iNbCities) % iNbCities;
ok1 = I_temp.FindCityPos (Cities[a1]);
if (ok1 != -1)
{
ok2 = I_temp.FindCityPos (Cities[a2]);
}
}
while ((ok1 != -1) || (ok1 != -1));
if (ok1 == -1)
{
a = Cities[a1];
}
else
{
a = Cities[a2];
}
return a;
}
void Individual::ExchangeCities (int iCity1, int iCity2)
{
int i_temp;
i_temp = Cities[iCity1];
Cities[iCity1] = Cities[iCity2];
Cities[iCity2] = i_temp;
}
void Individual::ReverseCities (int i, int j)
{
int a, b;
if (i < j)
{
a = i;
b = j;
}
else
{
a = j;
b = i;
}
while (a < b)
{
ExchangeCities (a, b);
a++;
b--;
}
}
void Individual::Depl1Cities (int i, int j)
{
int a, b, i_temp;
a = i;
b = j;
i_temp = Cities[a];
while (a < b)
{
Cities[a] = Cities[a + 1];
a++;
}
Cities[b] = i_temp;
}
void Individual::Depl1CitiesInv (int i, int j)
{
int a, b, i_temp;
a = i;
b = j;
i_temp = Cities[b];
while (b > a)
{
Cities[b] = Cities[b - 1];
b--;
}
Cities[a] = i_temp;
}
void Individual::Depl2Cities (int i, int j)
{
int a, b, i_temp, i_temp1;
a = i;
b = j;
i_temp = Cities[a];
i_temp1 = Cities[a + 1];
while (a < b - 1)
{
Cities[a] = Cities[a + 2];
a++;
}
Cities[b - 1] = i_temp;
Cities[b] = i_temp1;
}
void Individual::Depl2CitiesInv (int i, int j)
{
int b, i_temp, i_temp1;
b = j + 1;
i_temp = Cities[b - 1];
i_temp1 = Cities[b];
while (b > i + 1)
{
Cities[b] = Cities[b - 2];
b--;
}
Cities[i] = i_temp;
Cities[i + 1] = i_temp1;
}
void Individual::Crossover (Individual & I1, Individual & I2,
Individual & I_temp, int iCrossoverType)
{
switch (iCrossoverType)
{
case 0:
CrossoverKFP (I1, I2, I_temp);
break;
case 1:
CrossoverPMX (I1, I2, I_temp);
break;
case 2:
CrossoverOX (I1, I2, I_temp);
break;
case 3:
CrossoverCX (I1, I2, I_temp);
break;
case 4:
CrossoverAA (I1, I2, I_temp);
break;
}
}
void Individual::CrossoverKFP (Individual & I1, Individual & I2,
Individual & I_temp)
{
int i, iCurrentCity, iCurrentPos, a, b, iPosCityZero;
double d_a, d_b, p_a, p_b;
for (i = 0; i < iNbCities; i++)
{
I_temp.Cities[i] = -1;
}
iCurrentCity = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
I_temp.Cities[0] = iCurrentCity;
for (iCurrentPos = 1; iCurrentPos < iNbCities; iCurrentPos++)
{
a = I1.FindCityPos (iCurrentCity);
b = I2.FindCityPos (iCurrentCity);
do
{
a = (a + 1) % iNbCities;
}
while (I_temp.FindCityPos (I1.Cities[a]) != -1);
a = I1.Cities[a];
do
{
b = (b + 1) % iNbCities;
}
while (I_temp.FindCityPos (I2.Cities[b]) != -1);
b = I2.Cities[b];
d_a = pTSP->Distance (iCurrentCity, a);
d_b = pTSP->Distance (iCurrentCity, b);
p_a = d_a * rand ();
p_b = d_b * rand ();
if (p_a < p_b)
{
iCurrentCity = a;
}
else
{
iCurrentCity = b;
}
I_temp.Cities[iCurrentPos] = iCurrentCity;
}
iPosCityZero = I_temp.FindCityPos (0);
for (i = iPosCityZero; i < iNbCities; i++)
{
Cities[i - iPosCityZero] = I_temp.Cities[i];
}
for (i = 0; i < iPosCityZero; i++)
{
Cities[i + iNbCities - iPosCityZero] = I_temp.Cities[i];
}
}
void Individual::CrossoverPMX (Individual & I1, Individual & I2,
Individual & I_temp)
{
int i, iX1, iX2, iX_temp, a, iPosCityZero;
iX1 = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
iX2 = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
if (iX1 > iX2)
{
iX_temp = iX1;
iX1 = iX2;
iX2 = iX_temp;
}
for (i = 0; i < iNbCities; i++)
{
I_temp.Cities[i] = I1.Cities[i];
}
for (i = iX1; i <= iX2; i++)
{
a = I1.FindCityPos (I2.Cities[i]);
I_temp.ExchangeCities (a, i);
}
iPosCityZero = I_temp.FindCityPos (0);
for (i = iPosCityZero; i < iNbCities; i++)
{
Cities[i - iPosCityZero] = I_temp.Cities[i];
}
for (i = 0; i < iPosCityZero; i++)
{
Cities[i + iNbCities - iPosCityZero] = I_temp.Cities[i];
}
}
void Individual::CrossoverCX (Individual & I1, Individual & I2,
Individual & I_temp)
{
int i, iDep, iNext;
i = 0;
do
{
i++;
iDep = 1 + (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0))));
iNext = I2.FindCityPos (I1.Cities[iDep]);
}
while ((iDep == iNext) && (i < 10));
for (i = 0; i < iNbCities; i++)
{
Cities[i] = I1.Cities[i];
}
for (i = iDep; iNext != iDep; iNext = I2.FindCityPos (I1.Cities[i]))
{
Cities[i] = I2.Cities[i];
i = iNext;
}
Cities[i] = I2.Cities[i];
}
void Individual::CrossoverOX (Individual & I1, Individual & I2,
Individual & I_temp)
{
int i, j, iX1, iX2, iX_temp, iS1, iS2, iPosCity, iPosCityZero, iDec;
iX1 = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
iX2 = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
for (i = 0; i < iNbCities; i++)
{
Cities[i] = I1.Cities[i];
}
if (iX1 > iX2)
{
iX_temp = iX1;
iX1 = iX2;
iX2 = iX_temp;
}
for (j = iX1; j <= iX2; j++)
{
iPosCity = FindCityPos (I2.Cities[j]);
if (j <= iPosCity)
iDec = iPosCity - j;
else
iDec = iPosCity - j + iNbCities;
if (iDec <= iX1)
{
iS1 = iX1 - iDec;
iS2 = iNbCities;
}
else
{
iS1 = 0;
iS2 = iX1 - iDec + iNbCities;
}
for (i = 0; i < iS1; i++)
{
I_temp.Cities[i] = Cities[(i + iDec) % iNbCities];
}
for (i = iS1; i < iX1; i++)
{
I_temp.Cities[i] = Cities[(i + iDec + j - iX1) % iNbCities];
}
for (i = j; i < iS2; i++)
{
I_temp.Cities[i] = Cities[(i + iDec) % iNbCities];
}
for (i = iS2; i < iNbCities; i++)
{
I_temp.Cities[i] = Cities[(i + iDec + j - iX1) % iNbCities];
}
for (i = 0; i < iNbCities; i++)
{
Cities[i] = I_temp.Cities[i];
}
}
iPosCityZero = I_temp.FindCityPos (0);
for (i = iPosCityZero; i < iNbCities; i++)
{
Cities[i - iPosCityZero] = I_temp.Cities[i];
}
for (i = 0; i < iPosCityZero; i++)
{
Cities[i + iNbCities - iPosCityZero] = I_temp.Cities[i];
}
}
void Individual::CrossoverAA (Individual & I1, Individual & I2,
Individual & I_temp)
{
int i, iCurrentCity, iCurrentPos, a, b, iPosCityZero;
double d_a, d_b, p_a, p_b;
for (i = 0; i < iNbCities; i++)
{
I_temp.Cities[i] = -1;
}
iCurrentCity = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
I_temp.Cities[0] = iCurrentCity;
for (iCurrentPos = 1; iCurrentPos < iNbCities; iCurrentPos++)
{
a = I1.FindNextUnvisitedCity (iCurrentCity, I_temp);
b = I2.FindNextUnvisitedCity (iCurrentCity, I_temp);
d_a = pGroup->aPheromone[iCurrentCity * iNbCities + a];
d_b = pGroup->aPheromone[iCurrentCity * iNbCities + b];
p_a = d_a * rand ();
p_b = d_b * rand ();
if (p_a < p_b)
{
iCurrentCity = a;
}
else
{
iCurrentCity = b;
}
I_temp.Cities[iCurrentPos] = iCurrentCity;
}
iPosCityZero = I_temp.FindCityPos (0);
for (i = iPosCityZero; i < iNbCities; i++)
{
Cities[i - iPosCityZero] = I_temp.Cities[i];
}
for (i = 0; i < iPosCityZero; i++)
{
Cities[i + iNbCities - iPosCityZero] = I_temp.Cities[i];
}
}
void Individual::Mutate (int iType)
{
int a, b, iNear, i, j, i_temp, best_indice, n_i, n_j, iCompt, iCompt2;
float f, d, best_d;
int iCentre, iVoisinage;
switch (iType)
{
case MUT_2_CHANGE :
do
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
}
while ((b == a));
ReverseCities (a, b);
break;
case MUT_NEAR_2_CHANGE :
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
do
{
f = (rand () / (RAND_MAX + 1.0));
f = f * f / 25;
iNear = (int) (((pTSP->iNbNear) * f));
b = FindCityPos (pTSP->Near (Cities[a], iNear));
}
while ((b == 0) || (b == a));
ReverseCities (a, b);
break;
case MUT_2_SWAP:
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
ExchangeCities (a, b);
break;
case MUT_NEAR_2_SWAP:
do
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
i = 0;
do
{
b = FindCityPos (pTSP->Near (a, i));
i++;
}
while ((b == 0));
}
while ((b == a) || (b == (a + 1) % iNbCities));
ExchangeCities ((a + 1) % iNbCities, b);
break;
case MUT_NEAR_2_KFP:
i = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = -1;
best_d = 0;
for (iNear = 0; iNear < 15; iNear++)
{
j = FindCityPos (pTSP->Near (Cities[i], iNear));
if ((j != 0) && (j != i) && (j != (i + 1) % iNbCities)
&& (j != (i - 1) % iNbCities))
{
if (i < j)
{
d = pTSP->Distance (Cities[i], Cities[(j + 1) % iNbCities])
+ pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[j])
- pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[i])
- pTSP->Distance (Cities[j], Cities[(j + 1) % iNbCities]);
}
else
{
d = pTSP->Distance (Cities[j], Cities[(i + 1) % iNbCities])
+ pTSP->Distance (Cities[(j + iNbCities - 1) % iNbCities], Cities[i])
- pTSP->Distance (Cities[(j + iNbCities - 1) % iNbCities], Cities[j])
- pTSP->Distance (Cities[i], Cities[(i + 1) % iNbCities]);
}
if (b == -1)
{
best_d = d;
b = j;
}
else
{
if (d < best_d)
{
best_d = d;
b = j;
}
}
}
}
ReverseCities (i, b);
break;
case MUT_NEAR_SCRAMBLE_SWAP:
iCentre = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
iVoisinage = (int) (sqrt (iNbCities) * 2);
for (iNear = 0; iNear < iVoisinage; iNear++)
{
i = FindCityPos (pTSP->Near (Cities[iCentre], iNear));
j = FindCityPos (pTSP-> Near (Cities[iCentre], (int) (((5) * (rand () / (RAND_MAX + 1.0)) + 1))));
if (((i + iNbCities + 1) % iNbCities != 0) && (j != 0))
{
ReverseCities ((i + iNbCities + 1) % iNbCities, j);
}
}
break;
case MUT_NEAR_SCRAMBLE_CHANGE:
iCentre = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
iVoisinage = (int) (sqrt (iNbCities) * 5);
for (iNear = 0; iNear < iVoisinage; iNear++)
{
i = (iCentre + iNear + 1) % iNbCities;
j = FindCityPos (pTSP->Near (Cities[i], 0));
ReverseCities ((i + iNbCities + 1) % iNbCities, j);
}
break;
case MUT_4_CHANGE:
do
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
}
while ((b == a));
ReverseCities (a, b);
do
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
}
while ((b == a));
ReverseCities (a, b);
break;
case MUT_DEPL_1:
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
do
{
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
}
while ((b == a));
if (b < a)
{
i = a;
a = b;
b = i;
}
Depl1Cities (a, b);
break;
case MUT_DEPL_2:
for (j = 0; j < 2; j++)
{
do
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
}
while ((b == a));
if (b < a)
{
i = a;
a = b;
b = i;
}
Depl2Cities (a, b);
}
break;
case MUT_DEPL_4 :
do
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
}
while ((b == a));
i_temp = 0;
do
{
i = FindCityPos (pTSP->Near (Cities[a], i_temp));
i_temp++;
}
while (abs (a - i) % iNbCities < 10);
i_temp = 0;
do
{
j = FindCityPos (pTSP->Near (Cities[b], i_temp));
i_temp++;
}
while (abs (b - j) % iNbCities < 10);
if (i < a)
{
i_temp = a;
a = i;
i = i_temp;
}
if (j < b)
{
i_temp = b;
b = j;
j = i_temp;
}
Depl2Cities (a, i);
Depl2Cities (b, j);
break;
case MUT_PHEROM_1:
for (i = 0; i < 3; i++)
{
a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
do
{
b = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
}
while (GainPherom (a, b) < 0);
ReverseCities (a, b);
}
break;
case MUT_PHEROM_2:
for (a = iNbCities; a > 1; a--)
{
for (b = a + 1; b < iNbCities; b++)
{
if (GainPherom (a, b) > 0)
{
ReverseCities (a, b);
}
}
}
break;
case MUT_REPLI :
i = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
best_indice = -1;
best_d = -lfFitness;
for (iCompt = 1; iCompt < iNbCities; iCompt++)
{
if (abs((iCompt-i)%iNbCities) > 15)
{
d = pTSP->Distance (Cities[i], Cities[iCompt]);
if (d < best_d)
{
best_d = d;
best_indice = iCompt;
}
}
}
if (best_indice != -1)
{
if (best_indice < i)
{
n_i = i;
i = best_indice;
}
else
{
n_i = best_indice;
}
j = i + (int) (((n_i-i - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
best_indice = -1;
best_d = -lfFitness;
for (iCompt = 1; iCompt < iNbCities; iCompt++)
{
if ( (iCompt < i) || (iCompt > n_i) )
{
d = pTSP->Distance (Cities[j], Cities[iCompt]);
if (d < best_d)
{
best_d = d;
best_indice = iCompt;
}
}
}
if (best_indice != -1)
{
n_j = best_indice;
if (n_j > i)
{
iCompt2 = 0;
for (iCompt = 0; iCompt <= i; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = n_i; iCompt <= n_j; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = j; iCompt <= n_i-1; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = i+1; iCompt <= j -1; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = n_j+1; iCompt < iNbCities; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
}
else
{
iCompt2 = 0;
for (iCompt = 0; iCompt <= n_j; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = j; iCompt <= n_i-1; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = i+1; iCompt <= j-1; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = n_j+1; iCompt <= i; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
for (iCompt = n_i; iCompt < iNbCities; iCompt++)
{
pGroup->pI_Temp->Cities[iCompt2] = Cities[iCompt];
iCompt2++;
}
}
Duplicate (*(pGroup->pI_Temp));
}
}
break;
}
}
bool Individual::Optimize ()
{
return Optimize2ChangeCompl ();
}
void Individual::OptimizeFinal ()
{
OptimizeSwapCompl ();
Optimize1DeplCompl ();
Optimize();
Eval ();
}
bool Individual::Optimize2ChangeCompl ()
{
int i, j;
bool bOptimized, bOptimizedOnce;
double d;
bOptimizedOnce = false;
do
{
bOptimized = false;
for (i = 1; i < iNbCities; i++)
{
for (j = i + 1; j < iNbCities; j++)
{
if (i != j)
{
d = Gain2Change (i, j);
if (d < -0.00001)
{
ReverseCities (i, j);
bOptimized = true;
bOptimizedOnce = true;
}
}
}
}
}
while (bOptimized);
return bOptimizedOnce;
}
bool Individual::Optimize1DeplCompl ()
{
int i, j;
bool bOptimized, bOptimizedOnce;
double d;
bOptimizedOnce = false;
do
{
bOptimized = false;
for (i = 1; i < iNbCities - 2; i++)
{
for (j = i + 2; j < iNbCities; j++)
{
if (j + 1 - iNbCities < i - 1)
{
d = Gain1Depl (i, j);
if (d < -0.00001)
{
Depl1Cities (i, j);
bOptimized = true;
bOptimizedOnce = true;
}
d = Gain1DeplInv (i, j);
if (d < -0.00001)
{
Depl1CitiesInv (i, j);
bOptimized = true;
bOptimizedOnce = true;
}
}
}
}
}
while (bOptimized);
return bOptimizedOnce;
}
bool Individual::OptimizeSwapCompl ()
{
int i, j;
bool bOptimized, bOptimizedOnce;
double d;
bOptimizedOnce = false;
do
{
bOptimized = false;
for (i = 1; i < iNbCities; i++)
{
for (j = i + 1; j < iNbCities; j++)
{
if (i + 1 < j - 1)
{
d = pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[j])
+ pTSP->Distance (Cities[j], Cities[(i + iNbCities + 1) % iNbCities])
+ pTSP->Distance (Cities[(j + iNbCities - 1) % iNbCities], Cities[i])
+ pTSP->Distance (Cities[i], Cities[(j + iNbCities + 1) % iNbCities])
- pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[i])
- pTSP->Distance (Cities[i], Cities[(i + iNbCities + 1) % iNbCities])
- pTSP->Distance (Cities[(j + iNbCities - 1) % iNbCities], Cities[j])
- pTSP->Distance (Cities[j], Cities[(j + iNbCities + 1) % iNbCities]);
if (d < -0.00001)
{
ExchangeCities (i, j);
bOptimized = true;
bOptimizedOnce = true;
}
}
}
}
}
while (bOptimized);
return bOptimizedOnce;
}
double Individual::Gain2Change (int i, int j)
{
return pTSP->Distance (Cities[i], Cities[(j + 1) % iNbCities])
+ pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[j])
- pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[i])
- pTSP->Distance (Cities[j], Cities[(j + 1) % iNbCities]);
}
double Individual::GainPherom (int i, int j)
{
return pGroup->aPheromone[Cities[i] * iNbCities + Cities[(j + 1) % iNbCities]]
+ pGroup->aPheromone[Cities[(i + iNbCities - 1) % iNbCities] * iNbCities + Cities[j]]
- pGroup->aPheromone[Cities[(i + iNbCities - 1) % iNbCities] * iNbCities + Cities[i]]
- pGroup->aPheromone[Cities[j] * iNbCities + Cities[(j + 1) % iNbCities]];
}
double Individual::Gain1Depl (int i, int j)
{
return pTSP->Distance (Cities[j], Cities[i])
+ pTSP->Distance (Cities[i], Cities[(j + 1) % iNbCities])
+ pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[(i + 1) % iNbCities])
- pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[i])
- pTSP->Distance (Cities[i], Cities[(i + 1) % iNbCities])
- pTSP->Distance (Cities[j], Cities[(j + 1) % iNbCities]);
}
double Individual::Gain1DeplInv (int i, int j)
{
return pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[j])
+ pTSP->Distance (Cities[j], Cities[i])
+ pTSP->Distance (Cities[(j + iNbCities - 1) % iNbCities], Cities[(j + 1) % iNbCities])
- pTSP->Distance (Cities[(i + iNbCities - 1) % iNbCities], Cities[i])
- pTSP->Distance (Cities[(j + iNbCities - 1) % iNbCities], Cities[j])
- pTSP->Distance (Cities[j], Cities[(j + 1) % iNbCities]);
}