#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include "Group.h"
Group::Group (int iInstance0,
int iNbIndividual,
TSP *pTSP,
TspLog *pTspLog0,
char *sGroupFilename0)
{
int i;
iInstance = iInstance0;
pTspLog = pTspLog0;
pTspLog->StartFunction ("Group::Group", iInstance, LEVEL_DEBUG, 0);
iGroupSize = iNbIndividual;
strcpy(sGroupFilename, sGroupFilename0);
List = new Individual*[iGroupSize];
for (i = 0; i < iGroupSize; i++)
{
List[i] = new Individual (pTSP, this, pTspLog);
}
InitSelectionArray ();
pI = new Individual (pTSP, this, pTspLog);
pI2 = new Individual (pTSP, this, pTspLog);
aPheromone = new int[pTSP->iNbCities * pTSP->iNbCities];
bPheromoneOk = false;
pTspLog->EndFunction ("Group::Group", iInstance);
}
Group::~Group ()
{
int i;
pTspLog->StartFunction ("Group::~Group", iInstance, LEVEL_DEBUG, 0);
DeleteSelectionArray ();
for (i = 0; i < iGroupSize; i++)
{
delete List[i];
}
delete[] List;
delete pI;
delete pI2;
delete aPheromone;
pTspLog->EndFunction ("Group::~Group", iInstance);
}
void Group::Exchange (int iIndex1,
int iIndex2)
{
pI_Temp = List[iIndex2];
List[iIndex2] = List[iIndex1];
List[iIndex1] = pI_Temp;
}
bool Group::Belongs (Individual & I)
{
int i;
for (i = 0; i < iListCount; i++)
{
if (List[i]->lfFitness == I.lfFitness)
{
return true;
}
}
return false;
}
int Group::Reinsert (Individual & I)
{
bool bSorted = false;
int iNewPos = -1;
int j;
if (iListCount == 0)
{
*List[0] = I;
iListCount++;
iNewPos = 0;
}
else
{
if (I.lfFitness > List[iListCount - 1]->lfFitness)
{
if (!Belongs (I))
{
iNewPos = 0;
bSorted = false;
do
{
if (I.lfFitness > List[iNewPos]->lfFitness)
{
if (iListCount < iGroupSize)
{
iListCount++;
}
for (j = iListCount - 1; j > iNewPos; j--)
{
Exchange (j, j - 1);
}
*List[iNewPos] = I;
bSorted = true;
}
else
{
iNewPos++;
}
}
while ((!bSorted) && (iNewPos < iListCount));
}
}
else if (iListCount < iGroupSize)
{
if (!Belongs (I))
{
iListCount++;
iNewPos = iListCount - 1;
*List[iNewPos] = I;
}
}
}
return iNewPos;
}
void Group::RandomInit ()
{
int i;
pTspLog->StartFunction ("Group::RandomInit", iInstance, LEVEL_DEBUG, iGroupSize);
for (i = 0; i < iGroupSize; i++)
{
List[i]->RandomInit ();
List[i]->Eval ();
}
iListCount = iGroupSize;
Sort ();
pTspLog->EndFunction ("Group::RandomInit", iInstance);
}
void Group::OptInit ()
{
int i;
double lfBestFitness;
pTspLog->StartFunction ("Group::OptInit", iInstance, LEVEL_DEBUG, iGroupSize);
lfBestFitness = 0;
for (i = 0; i < iGroupSize; i++)
{
List[i]->RandomInit ();
List[i]->Optimize2ChangeCompl ();
List[i]->Eval ();
if ( (i==0) || (List[i]->lfFitness > lfBestFitness) )
{
lfBestFitness = List[i]->lfFitness;
List[i]->LogRecord (i + 1);
}
}
iListCount = iGroupSize;
Sort ();
pTspLog->EndFunction ("Group::OptInit", iInstance);
}
void Group::NearestNeighbourInit ()
{
int i, iNewPos;
RandomInit ();
pTspLog->StartFunction ("Group::NearestNeighbourInit", iInstance, LEVEL_DEBUG, pI2->iNbCities);
for (i = 0; i < pI2->iNbCities; i++)
{
pI->NearestNeighbourInit (*pI2, i);
pI->Eval ();
iNewPos = Reinsert (*pI);
if (iNewPos == 0)
{
pI->LogRecord (i + 1);
}
}
pTspLog->EndFunction ("Group::NearestNeighbourInit", iInstance);
}
void Group::InitSelectionArray ()
{
int i;
SelectionArray = new int[iGroupSize];
for (i = 0; i < iGroupSize; i++)
{
SelectionArray[i] = (int) (sqrt ((i + 1.0) / (iGroupSize)) * (RAND_MAX));
}
}
void Group::DeleteSelectionArray ()
{
delete[]SelectionArray;
}
int Group::GetRandSelectionArrayIndex ()
{
int a, iRand;
iRand = rand ();
a = 0;
while (iRand > SelectionArray[a])
{
a++;
}
return a;
}
void Group::Select (int *a, int *b)
{
SelectOne (a);
do
{
SelectOne (b);
}
while ((*b) == (*a));
}
void Group::SelectOne (int *a)
{
*a = GetRandSelectionArrayIndex ();
}
void Group::RandomEvol (int iNbIndividual)
{
int i, iNewPos;
char sMessage[255];
pTspLog->StartFunction ("Group::RandomEvol", iInstance, LEVEL_DEBUG, iNbIndividual);
for (i = 0; i < iNbIndividual; i++)
{
if (i % 100 == 0)
{
sprintf (sMessage, "itération %d / %d", i + 1, iNbIndividual);
pTspLog->ScreenMsg(sMessage);
}
pI->RandomInit ();
pI->Eval ();
iNewPos = Reinsert (*pI);
if (iNewPos == 0)
{
pI->LogRecord (i + 1);
}
else if (iNewPos != -1)
{
sprintf (sMessage, "(%d)", iNewPos);
pTspLog->ScreenMsg(sMessage);
}
}
pTspLog->EndFunction ("Group::RandomEvol", iInstance);
}
void Group::MonteCarloEvol (int iNbIndividual, int iMutationType)
{
int i, a;
char sMessage[255];
pTspLog->StartFunction ("Group::MonteCarloEvol", iInstance, LEVEL_DEBUG, iNbIndividual);
for (i = 0; i < iNbIndividual; i++)
{
if (i % 1000 == 0)
{
sprintf (sMessage, "itération %d / %d", i + 1, iNbIndividual);
pTspLog->ScreenMsg(sMessage);
}
SelectOne (&a);
pI->Duplicate (*List[a]);
{
pI->Mutate (iMutationType);
if (i % 10 == 0)
{
pI->Mutate (iMutationType);
}
if (i % 50 == 0)
{
pI->Mutate (iMutationType);
}
}
pI->Optimize ();
pI->Eval ();
if (pI->lfFitness > List[a]->lfFitness)
{
pI->OptimizeFinal ();
if (!Belongs (*pI))
{
List[a]->Duplicate (*pI);
if ((a == 0) || (pI->lfFitness > List[0]->lfFitness))
{
pI->LogRecord (i + 1);
}
else
{
sprintf (sMessage, "(%d)", a);
pTspLog->ScreenMsg(sMessage);
}
Sort ();
}
}
}
pTspLog->EndFunction ("Group::MonteCarloEvol", iInstance);
}
void Group::MonteCarloDistinctEvol (int iNbIndividual, int iMutationType)
{
int i, a;
double bestFitness;
char sMessage[255];
pTspLog->StartFunction ("Group::MonteCarloDistinctEvol", iInstance, LEVEL_DEBUG, iNbIndividual);
bestFitness = List[0]->lfFitness;
for (a = 0; a < iGroupSize; a++)
{
sprintf (sMessage, "Individual %d / %d", a+1, iGroupSize);
pTspLog->ScreenMsg(sMessage);
for (i = 0; i < iNbIndividual; i++)
{
if (i % 1000 == 0)
{
sprintf (sMessage, "itération %d / %d", i + 1, iNbIndividual);
pTspLog->ScreenMsg(sMessage);
}
pI->Duplicate (*List[a]);
{
pI->Mutate (iMutationType);
if (i % 10 == 0)
{
pI->Mutate (iMutationType);
}
if (i % 50 == 0)
{
pI->Mutate (iMutationType);
}
}
pI->Optimize ();
pI->Eval ();
if ( (pI->lfFitness > List[a]->lfFitness) && (!Belongs (*pI)) )
{
pI->OptimizeFinal ();
if (!Belongs (*pI))
{
List[a]->Duplicate (*pI);
if (pI->lfFitness > bestFitness)
{
bestFitness = pI->lfFitness;
pI->LogRecord (i + 1);
}
}
}
}
}
Sort ();
pTspLog->EndFunction ("Group::MonteCarloDistinctEvol", iInstance);
}
void Group::DarwinEvol (int iNbIndividual,
int iNbMutationOptimization,
int iNbMaxMutation,
int iCrossoverType)
{
int i, a, b, iIter;
int iLeastParent, iBestParent;
double lfFitnessBeforeOpt;
char sMessage[255];
int iCrossoverTypeCalc;
pTspLog->StartFunction ("Group::DarwinEvol", iInstance, LEVEL_DEBUG, iNbIndividual);
for (i = 0; i < iNbIndividual; i++)
{
if (i % 100 == 0)
{
sprintf (sMessage, "itération %d / %d", i + 1, iNbIndividual);
pTspLog->ScreenMsg(sMessage);
}
Select (&a, &b);
if (List[a]->lfFitness > List[b]->lfFitness)
{
iLeastParent = b;
iBestParent = a;
}
else
{
iLeastParent = a;
iBestParent = b;
}
if (iCrossoverType == -1)
{
iCrossoverTypeCalc = (int) (((5) * (rand () / (RAND_MAX + 1.0))));
pI->Crossover (*List[a], *List[b], *pI2, iCrossoverTypeCalc);
}
else
{
pI->Crossover (*List[a], *List[b], *pI2, iCrossoverType);
}
pI->Eval ();
if (MonteCarloOptimization (List[iLeastParent]->lfFitness, MUT_2_CHANGE, iNbMutationOptimization, iNbMaxMutation))
{
pI->OptimizeFinal ();
}
if (MonteCarloOptimization (List[iLeastParent]->lfFitness, MUT_PHEROM_2, iNbMutationOptimization, iNbMaxMutation))
{
pI->OptimizeFinal ();
}
if (MonteCarloOptimization (List[iLeastParent]->lfFitness, MUT_REPLI, iNbMutationOptimization, iNbMaxMutation))
{
pI->OptimizeFinal ();
}
if (pI->lfFitness > List[iLeastParent]->lfFitness)
{
if (!Belongs (*pI))
{
if (pI->lfFitness > List[0]->lfFitness)
{
pI->LogRecord (i + 1);
}
else
{
sprintf (sMessage, "(%d)", iLeastParent);
pTspLog->ScreenMsg(sMessage);
}
if (pI->lfFitness > List[iBestParent]->lfFitness)
{
if (iBestParent == 0)
{
iIter = 20;
}
else
{
iIter = 1;
}
lfFitnessBeforeOpt = pI->lfFitness;
MonteCarloOptimization (List[iLeastParent]->lfFitness, MUT_REPLI,
iNbMutationOptimization * iIter,
iNbMaxMutation * iIter);
MonteCarloOptimization (List[iLeastParent]->lfFitness, MUT_PHEROM_2,
iNbMutationOptimization * iIter,
iNbMaxMutation * iIter);
pI->OptimizeFinal ();
if ((pI->lfFitness > lfFitnessBeforeOpt) && (pI->lfFitness > List[0]->lfFitness))
{
pTspLog->DebugMsg ("Apres optimisation");
pI->LogRecord (i + 1);
}
}
if (!Belongs (*pI))
{
List[iLeastParent]->Duplicate (*pI);
}
Sort ();
}
}
}
pTspLog->EndFunction ("Group::DarwinEvol", iInstance);
}
bool Group::MonteCarloOptimization (float lfMinScore,
int iMutationType,
int iNbMutationOptimization,
int iNbMaxMutation)
{
int j, k;
j = 0;
k = 0;
do
{
pI2->Duplicate (*pI);
if (j > 0)
{
pI2->Mutate (0);
if (j > iNbMaxMutation / 3)
{
pI2->Mutate (iMutationType);
}
if (j > 2 * iNbMaxMutation / 3)
{
pI2->Mutate (iMutationType);
}
}
pI2->Optimize ();
pI2->Eval ();
if (pI2->lfFitness > pI->lfFitness)
{
pI->Duplicate (*pI2);
if (j > 0)
{
k++;
}
}
j++;
}
while ((pI->lfFitness > lfMinScore) && (j < iNbMaxMutation)
&& (k < iNbMutationOptimization));
return (pI->lfFitness > lfMinScore);
}
void Group::Sort ()
{
int i, j;
for (i = 0; i < iListCount; i++)
{
for (j = i + 1; j < iListCount; j++)
{
if ((*List[i]).lfFitness < (*List[j]).lfFitness)
{
Exchange (i, j);
}
}
}
}
void Group::WriteToCSV ()
{
int i;
FILE *fGroup;
pTspLog->StartFunction ("Group::WriteToCSV", iInstance, LEVEL_DEBUG, iListCount);
fGroup = fopen (sGroupFilename, "w");
if (fGroup != NULL)
{
fprintf (fGroup, "%d\n", iGroupSize);
for (i = 0; i < iGroupSize; i++)
{
(List[i])->Write (fGroup);
}
fclose (fGroup);
}
else
{
char sMessage[255];
sprintf(sMessage, "*** Erreur : impossible d'écrire le fichier %s\n", sGroupFilename);
pTspLog->ErrorMsg(sMessage);
}
pTspLog->EndFunction ("Group::WriteToCSV", iInstance);
}
void Group::ReadFromCSV ()
{
int i;
FILE *fGroup;
char sLine[MAX_LENLINE];
pTspLog->StartFunction ("Group::ReadFromCSV", iInstance, LEVEL_DEBUG, 0);
fGroup = fopen (sGroupFilename, "r");
if (fGroup != NULL)
{
fgets (sLine, MAX_LENLINE, fGroup);
iGroupSize = atoi (sLine);
iListCount = iGroupSize;
for (i = 0; i < iGroupSize; i++)
{
(List[i])->Read (fGroup);
}
fclose (fGroup);
}
else
{
char sMessage[255];
sprintf(sMessage, "*** Erreur : impossible de lire le fichier %s\n", sGroupFilename);
pTspLog->ErrorMsg(sMessage);
}
Sort ();
pTspLog->EndFunction ("Group::ReadFromCSV", iInstance);
}
void Group::Duplicate (Group * G)
{
int i;
for (i = 0; i < iGroupSize; i++)
{
(List[i])->Duplicate (*(G->List[i]));
}
iListCount = G->iListCount;
}
void Group::MakePheromoneMatrix ()
{
int i, j;
int iCurrentCity, iLastCity;
pTspLog->StartFunction ("Group::MakePheromoneMatrix", iInstance, LEVEL_DEBUG, pI2->iNbCities);
for (i = 0; i < pI2->iNbCities; i++)
{
for (j = 0; j < pI2->iNbCities; j++)
{
aPheromone[i * (pI2->iNbCities) + j] = 0;
}
}
for (i = 0; i < iGroupSize; i++)
{
iLastCity = List[i]->Cities[pI2->iNbCities - 1];
for (j = 0; j < pI2->iNbCities; j++)
{
iCurrentCity = List[i]->Cities[j];
aPheromone[(iCurrentCity * (pI2->iNbCities)) + iLastCity]++;
aPheromone[(iLastCity * (pI2->iNbCities)) + iCurrentCity]++;
iLastCity = iCurrentCity;
}
}
bPheromoneOk = true;
pTspLog->EndFunction ("Group::MakePheromoneMatrix", iInstance);
}