Sources de tspgen 0.32 : résolution du problème du voyageur de commerce

/*==========================================================================
Project : tspgen 0.32
File    : Population.cpp
Purpose : Population
    - Population is a set of Groups
    - Group is a set of Individual that evolves with
      selection/crossover/mutation/optimization
    - Individual is a particular path between all the cities of the Traveling
      Salesman Problem
==========================================================================*/

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>

#include "Population.h"


/*========================================================================
============================ POPULATION ==================================
==========================================================================*/

/*========================================================================
Function : Population constructor
In :  iNbGroup :      nb of groups in the population
      iNbIndividual : nb of individuals in a group
      pTSP :          the TSP problem to solve
      pTspLog0 :      the log object
==========================================================================*/
Population::Population (int iInstance0,
                        int iNbGroup,
                        int iNbIndividual,
                        TSP * pTSP,
                        TspLog * pTspLog0,
                        char *sLogDir,
                        char *sLogBasename)
{
  int i;
  char sGroupFilename[255];

  iInstance = iInstance0;
  pTspLog = pTspLog0;
  pTspLog->StartFunction ("Population::Population", iInstance, LEVEL_DEBUG, 0);

  iPopulationSize = iNbGroup;
  List = new Group*[iPopulationSize];
  for (i = 0; i < iPopulationSize; i++)
  {
    sprintf (sGroupFilename, "%s/%s%03d.csv", sLogDir, sLogBasename, i);
    List[i] = new Group (i, iNbIndividual, pTSP, pTspLog, sGroupFilename);
  }

  pTspLog->EndFunction ("Population::Population", iInstance);
}

/*========================================================================
Function : Population destructor
==========================================================================*/
Population::~Population ()
{
  int i;

  pTspLog->StartFunction ("Population::~Population", iInstance, LEVEL_DEBUG, 0);

  for (i = 0; i < iPopulationSize; i++)
  {
    delete List[i];
  }
  delete[] List;

  pTspLog->EndFunction ("Population::~Population", iInstance);
}

/*========================================================================
Function : Initialization of a population
In : sInitMacro : the initialisation macro (sequence of operations)
==========================================================================*/
void Population::Init (char *sInitMacro)
{
  int i, iInstruction;

  char sInstruction[255];
  char sMessage[255];
  int iParam1, iParam2, iParam3, iParam4;
  bool bOk;

  pTspLog->StartFunction ("Population::Init", iInstance, LEVEL_DEBUG, 0);

  iInstruction = 0;
  // On décode la "macro" Init du fichier ini, qui contient une suite d'instructions du type :
  // Init=RandomInit;MonteCarloDistinctEvol(2); MakePheromoneMatrix; MonteCarloEvol (200, 15)
  while (DecodeMacro(sInitMacro, iInstruction, sInstruction, &iParam1, &iParam2, &iParam3, &iParam4))
  {
    bOk = false;

    // En cas de reprise du calcul on réutilise le fichier CSV généré la fois d'avant (sGroupFilename)
    if (strcmp(sInstruction, "Reprise") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        (List[i])->RandomInit ();// *****  Cela ne devrait pas etre nécessaire... *****
        (List[i])->ReadFromCSV ();
      }
      bOk = true;
    }
    // Initialisation par la méthode des plus proches voisins
    if (strcmp(sInstruction, "NearestNeighbourInit") == 0)
    {
      // The nearest neighbour method always give the same result
      (List[0])->NearestNeighbourInit ();
      (List[0])->WriteToCSV ();

      // the other groups are copied
      for (i = 1; i < iPopulationSize; i++)
      {
        (List[i])->Duplicate (List[0]);
      }
      bOk = true;
    }

    // Init au hasard
    if (strcmp(sInstruction, "RandomInit") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        (List[i])->RandomInit ();
      }
      bOk = true;
    }

    // Init au hasard
    if (strcmp(sInstruction, "OptInit") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        (List[i])->OptInit ();
      }
      bOk = true;
    }

    if (strcmp(sInstruction, "RandomEvol") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        //                       nb
        (List[i])->RandomEvol (iParam1);
      }
      bOk = true;
    }

    if (strcmp(sInstruction, "MonteCarloEvol") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        //                                nb, mutationtype
        (List[i])->MonteCarloEvol (iParam1, iParam2);
      }
      bOk = true;
    }

    if (strcmp(sInstruction, "MonteCarloDistinctEvol") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        //                                nb, mutationtype
        (List[i])->MonteCarloDistinctEvol (iParam1, iParam2);
      }
      bOk = true;
    }

    if (strcmp(sInstruction, "DarwinEvol") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        //                                nb, nbmutoptimisation, nbmaxmut, crossovertype
        (List[i])->DarwinEvol (iParam1, iParam2, iParam3, iParam4);
      }
      bOk = true;
    }

    if (strcmp(sInstruction, "MakePheromoneMatrix") == 0)
    {
      for (i = 0; i < iPopulationSize; i++)
      {
        (List[i])->MakePheromoneMatrix ();
      }
      bOk = true;
    }

    if (strcmp(sInstruction, "SortGroup") == 0)
    {
      Sort();
      bOk = true;
    }

    if (bOk)
    {
      WriteToCSV();
    }
    else
    {
      sprintf(sMessage, "Instruction inconnue : %s", sInstruction);
      pTspLog->ErrorMsg(sMessage);
    }

    iInstruction++;
  }

  pTspLog->EndFunction ("Population::Init", iInstance);
}

/*========================================================================
Function : Evolution of a population
In : sEvolMacro : the evolution macro (sequence of operations)
     iNbCycles : nb of repetitios of the macro
     bGroupRepartition : use or not the repartition of iterations (more iterations
      for best groups)
==========================================================================*/
void Population::Evolve (char *sEvolMacro,
                         int iNbCycles,
                         bool bGroupRepartition)
{
  int i, j, iNbIter;
  char sMessage[255];

  int iInstruction;
  char sInstruction[255];
  int iParam1, iParam2, iParam3, iParam4;
  bool bOk;

  pTspLog->StartFunction ("Population::Evolve", iInstance, LEVEL_DEBUG, iNbCycles);

  // main loop
  for (j = 0; j < iNbCycles; j++)
  {
    sprintf(sMessage, "===== Debut du loop %d / %d =====", j+1, iNbCycles);
    pTspLog->DebugMsg (sMessage);

    iInstruction = 0;
    // On décode la "macro" Init du fichier ini, qui contient une suite d'instructions du type :
    // Init=RandomInit;MonteCarloDistinctEvol(2); MakePheromoneMatrix; MonteCarloEvol (200, 15)
    while (DecodeMacro(sEvolMacro, iInstruction, sInstruction, &iParam1, &iParam2, &iParam3, &iParam4))
    {
      bOk = false;

      // Evolution au hasard
      if (strcmp(sInstruction, "RandomEvol") == 0)
      {
        for (i = 0; i < iPopulationSize; i++)
        {
          //                       nb
          (List[i])->RandomEvol (iParam1);
        }
        bOk = true;
      }

      // Evolution avec mutation + optimisation (proche recuit simulé)
      if (strcmp(sInstruction, "MonteCarloEvol") == 0)
      {
        for (i = 0; i < iPopulationSize; i++)
        {
          if (bGroupRepartition)
          {
            iNbIter = (int) (iParam1 * (iPopulationSize - i) * (iPopulationSize - i) * (iPopulationSize - i))
                               / (iPopulationSize * iPopulationSize * iPopulationSize * iPopulationSize);
          }
          else
          {
            iNbIter = iParam1;
          }
          //                                nb, mutationtype
          (List[i])->MonteCarloEvol (iNbIter, iParam2);
        }
        bOk = true;
      }

      // Evolution par algorithme génétique
      if (strcmp(sInstruction, "DarwinEvol") == 0)
      {
        for (i = 0; i < iPopulationSize; i++)
        {
          if (bGroupRepartition)
          {
            iNbIter = (int) (iParam1 * (iPopulationSize - i) * (iPopulationSize - i) * (iPopulationSize - i))
                               / (iPopulationSize * iPopulationSize * iPopulationSize * iPopulationSize);
          }
          else
          {
            iNbIter = iParam1;
          }
          //                                nb, nbmutoptimisation, nbmaxmut, crossovertype
          (List[i])->DarwinEvol (iNbIter, iParam2, iParam3, iParam4);
        }
        bOk = true;
      }

      // Evolution avec mutation + optimisation, avec un nb fixe d'évolutions par individu
      if (strcmp(sInstruction, "MonteCarloDistinctEvol") == 0)
      {
        for (i = 0; i < iPopulationSize; i++)
        {
          //                                nb, mutationtype
          (List[i])->MonteCarloDistinctEvol (iParam1, iParam2);
        }
        bOk = true;
      }

      // Mise à jour de la "matrice des phéromones" = meilleurs arêtes
      if (strcmp(sInstruction, "MakePheromoneMatrix") == 0)
      {
        for (i = 0; i < iPopulationSize; i++)
        {
          (List[i])->MakePheromoneMatrix ();
        }
        bOk = true;
      }

      // tri entre les groupes
      if (strcmp(sInstruction, "SortGroup") == 0)
      {
        Sort();
        bOk = true;
      }

      // on enregistre troujours si c'est OK
      if (bOk)
      {
        WriteToCSV();
      }
      else
      {
        sprintf(sMessage, "Instruction inconnue : %s", sInstruction);
        pTspLog->ErrorMsg(sMessage);
      }

      iInstruction++;
    }

    pTspLog->DebugMsg ("Fin du loop");
  }
  pTspLog->EndFunction ("Population::Evolve", iInstance);
}

/*========================================================================
Function : Sorts all the groups according to their fitness
           (Bubble sort, I know, but it is so easy to write !)
==========================================================================*/
void Population::Sort ()
{
  int i, j, groupe_i, groupe_j, elem_i, elem_j, iGroupSize;

  iGroupSize = (List[0]->iGroupSize);
  pTspLog->StartFunction ("Population::Sort", iInstance, LEVEL_DEBUG, (iPopulationSize * iGroupSize));

  // pour tous les éléments de tous les groupes, i et j
  for (i = 0; i < (iPopulationSize * iGroupSize); i++)
  {
    for (j = i + 1; j < (iPopulationSize * iGroupSize); j++)
    {
      // calcule le n° du groupe de i et de j
      groupe_i = ((int) i) / ((int) iGroupSize);
      groupe_j = ((int) j) / ((int) iGroupSize);

      // calcule le n° d'élement de i et de j
      elem_i = i % iGroupSize;
      elem_j = j % iGroupSize;

      // Si i est moins bon que j on l'échange
      if (List[groupe_i]->List[elem_i]->lfFitness  < List[groupe_j]->List[elem_j]->lfFitness)
      {
        // si même groupe il suffit de l'échanger dans le groupe
        if (groupe_i == groupe_j)
        {
          List[groupe_i]->Exchange (elem_i, elem_j);
        }
        // sinon il faut échanger entre les groupes
        else
        {
          // on ne fait l'échange que si l'élément n'appartient pas déjà à l'autre groupe
          if ((!(List[groupe_i]->Belongs (*(List[groupe_j]->List[elem_j]))))
              && (!(List[groupe_j]-> Belongs (*(List[groupe_i]->List[elem_i])))))
          {
            (List[groupe_i]->pI)->Duplicate (*(List[groupe_i]->List[elem_i]));
            (List[groupe_i]->List[elem_i])->Duplicate (*(List[groupe_j]->List[elem_j]));
            (List[groupe_j]->List[elem_j])->Duplicate (*(List[groupe_i]->pI));
          }
        }
      }
    }
  }
  pTspLog->EndFunction ("Population::Sort", iInstance);
}

/*========================================================================
Function : Write all the groups in their CSV files
==========================================================================*/
void Population::WriteToCSV()
{
  int i;

  for (i = 0; i < iPopulationSize; i++)
  {
    (List[i])->WriteToCSV ();
  }
}

/*========================================================================
Function : Decode the specified instruction in the macro - for use in a while statement
In :  sMacro0 : the macro string (i.e : DarwinEvol(10); MonteCarloEvol(100, 15)
      iMacroNum : the number of the instruction to decode
Out : sFunctionName : name of the function (instruction) in the macro (ex : MonteCarloEvol)
      iParam1 : parameter #1 of the function (ex : 100)
      iParam2 : parameter #2 of the function (ex : 15)
      iParam3 : parameter #3 of the function
      iParam4 : parameter #4 of the function
Returns : true if the instruction exists, false if this is the end of the macro
==========================================================================*/
bool DecodeMacro(char *sMacro0,
                 int iMacroNum,
                 char *sFunctionName,
                 int *iParam1,
                 int *iParam2,
                 int *iParam3,
                 int *iParam4)
{
  char sMacro[255];
  char *sParam;
  char *sParam2;
  bool bOk;
  int i;

  bOk = false;
  strcpy(sFunctionName, "<undefined>");
  *iParam1 = -1;
  *iParam2 = -1;
  *iParam3 = -1;
  *iParam4 = -1;

  strcpy(sMacro, sMacro0);
  sParam=strtok(sMacro, ";");
  bOk = (sParam!=NULL);

  if (bOk)
  {
    if (iMacroNum > 0)
    {
      i = 0;
      while ( (i<iMacroNum) && (sParam!=NULL) )
      {
        sParam=strtok(NULL, ";\n");
        i++;
      }
      bOk = ((i == iMacroNum) && (sParam != NULL) );
    }
  }

  // décomposition des paramètres de l'instruction de la macro
  if (bOk)
  {
    // nom de la fonction
    sParam2=strtok(sParam, " (,)\n");
    if (sParam2 != NULL)
    {
      strcpy(sFunctionName, sParam2);
    }
    else
    {
      bOk = false;
    }

    // paramètres de la fonction
    if (sParam2 != NULL)
    {
      sParam2=strtok(NULL, " (,)\n");
      *iParam1 = GetValue(sParam2);
    }
    if (sParam2 != NULL)
    {
      sParam2=strtok(NULL, " (,)\n");
      *iParam2 = GetValue(sParam2);
    }
    if (sParam2 != NULL)
    {
      sParam2=strtok(NULL, " (,)\n");
      *iParam3 = GetValue(sParam2);
    }
    if (sParam2 != NULL)
    {
      sParam2=strtok(NULL, " (,)\n");
      *iParam4 = GetValue(sParam2);
    }
  }
  return bOk;
}

/*========================================================================
Function : Decode special variables (returns the values)
      Variable names begins with "%". Ex : MonteCarloEvol(100, %MUT_2_CHANGE)
In : sValue : the string of the variable or value in the macro (ex : 100 or %MUT_2_CHANGE)
Returns : the value (integer)
==========================================================================*/
int GetValue(char *sValue)
{
  int iResult;
  char sVariable[255];

  iResult = -1;
  if (sValue != NULL)
  {
    // si commence par un %, c'est une variable
    if ( (strlen(sValue)>1) && (sValue[0] == '\%') )
    {
      // enlève le %
      strcpy(sVariable, sValue+1);
      // recherche la variable
      if (strcmp(sVariable, "MUT_2_CHANGE") == 0)
      {
        iResult = MUT_2_CHANGE;
      }
      if (strcmp(sVariable, "MUT_NEAR_2_CHANGE") == 0)
      {
        iResult = MUT_NEAR_2_CHANGE;
      }
      if (strcmp(sVariable, "MUT_2_SWAP") == 0)
      {
        iResult = MUT_2_SWAP;
      }
      if (strcmp(sVariable, "MUT_NEAR_2_SWAP") == 0)
      {
        iResult = MUT_NEAR_2_SWAP;
      }
      if (strcmp(sVariable, "MUT_NEAR_2_KFP") == 0)
      {
        iResult = MUT_NEAR_2_KFP;
      }
      if (strcmp(sVariable, "MUT_NEAR_SCRAMBLE_SWAP") == 0)
      {
        iResult = MUT_NEAR_SCRAMBLE_SWAP;
      }
      if (strcmp(sVariable, "MUT_NEAR_SCRAMBLE_CHANGE") == 0)
      {
        iResult = MUT_NEAR_SCRAMBLE_CHANGE;
      }
      if (strcmp(sVariable, "MUT_4_CHANGE") == 0)
      {
        iResult = MUT_4_CHANGE;
      }
      if (strcmp(sVariable, "MUT_DEPL_1") == 0)
      {
        iResult = MUT_DEPL_1;
      }
      if (strcmp(sVariable, "MUT_DEPL_1") == 0)
      {
        iResult = MUT_DEPL_1;
      }
      if (strcmp(sVariable, "MUT_DEPL_2") == 0)
      {
        iResult = MUT_DEPL_2;
      }
      if (strcmp(sVariable, "MUT_DEPL_4") == 0)
      {
        iResult = MUT_DEPL_4;
      }
      if (strcmp(sVariable, "MUT_PHEROM_1") == 0)
      {
        iResult = MUT_PHEROM_1;
      }
      if (strcmp(sVariable, "MUT_PHEROM_2") == 0)
      {
        iResult = MUT_PHEROM_2;
      }
      if (strcmp(sVariable, "MUT_REPLI") == 0)
      {
        iResult = MUT_REPLI;
      }
    }
    // sinon c'est une valeur simple
    else
    {
      iResult = atoi(sValue);
    }
  }

  return iResult;
}