vers Labo Algo
Labo Algo

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


/*==========================================================================
Project : tspgen 0.32
File    : Group.cpp
Purpose : Group
    - 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 "Group.h"


/*========================================================================
============================== GROUP =====================================
==========================================================================*/

/*========================================================================
Function : Group constructor
In :  iInstance0 : instance number (for logs)
      iNbIndividual : nb of individuals in the group
      pTSP : the TSP problem to solve
      pTspLog0 : Tsplog object
      sGroupFilename0 : Name of the CSV filename
==========================================================================*/
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);
  // création de la liste des individus du groupe
  List = new Individual*[iGroupSize];
  for (i = 0; i < iGroupSize; i++)
  {
    List[i] = new Individual (pTSP, this, pTspLog);
  }

  // tableau pour la sélection des individus
  InitSelectionArray ();

  // individus temporaires (utilisés pour le calcul)
  pI = new Individual (pTSP, this, pTspLog);
  pI2 = new Individual (pTSP, this, pTspLog);

  // tableau des phéromones (meilleures arêtes)
  aPheromone = new int[pTSP->iNbCities * pTSP->iNbCities];
  bPheromoneOk = false;

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

/*========================================================================
Function : Group destructor
==========================================================================*/
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);
}

/*========================================================================
Function : Exchange positions between 2 individuals in the group
In :  int iIndex1 : position de l'individu 1 dans le groupe
      int iIndex2 : position de l'individu 2 dans le groupe
==========================================================================*/
void Group::Exchange (int iIndex1,
                      int iIndex2)
{
  pI_Temp = List[iIndex2];
  List[iIndex2] = List[iIndex1];
  List[iIndex1] = pI_Temp;
}

/*========================================================================
Function : Test if an individual belongs to the group
In : Individual & I : the individual to test
Returns : true if the individual belongs, false otherwise
==========================================================================*/
bool Group::Belongs (Individual & I)
{
  int i;

  // we assume that for sufficient number of cities,
  // two distinct individuals cannot have the same length
  for (i = 0; i < iListCount; i++)
  {
    if (List[i]->lfFitness == I.lfFitness)
    {
      return true;
    }
  }

  return false;
}

/*========================================================================
Function : Reinsertion of an Individual in the Group, ie inserting the new
      Individual in the population
In : Individual & I : the individual to insert in the group
Returns : the position of the new Individual in the Group
==========================================================================*/
int Group::Reinsert (Individual & I)
{
  bool bSorted = false;
  int iNewPos = -1;
  int j;

  // if there is no individual in the group
  if (iListCount == 0)
  {
    *List[0] = I;
    iListCount++;
    iNewPos = 0;
  }
  else
  {
    // if the individual can be inserted in the group
    if (I.lfFitness > List[iListCount - 1]->lfFitness)
    {
      if (!Belongs (I))
      {
        iNewPos = 0;
        bSorted = false;

        do
        {
          if (I.lfFitness > List[iNewPos]->lfFitness)
          {
            //if there is not enough individuals in the group
            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));
      }
    }
    // if it can't be inserted, but if there is not enough individuals in the group
    else if (iListCount < iGroupSize)
    {
      if (!Belongs (I))
      {
        iListCount++;
        iNewPos = iListCount - 1;
        *List[iNewPos] = I;
      }
    }
  }

  return iNewPos;
}

/*========================================================================
Function : Group random initialization
==========================================================================*/
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);
}

/*========================================================================
Function : Group random + 2-opt initialization
==========================================================================*/
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);
}

/*========================================================================
Function : Group nearest neigbour initialization
==========================================================================*/
void Group::NearestNeighbourInit ()
{
  int i, iNewPos;

  RandomInit (); // Ne devrait pas être nécessaire AAAAAAAAAAAAAAAAAAAA

  pTspLog->StartFunction ("Group::NearestNeighbourInit", iInstance, LEVEL_DEBUG, pI2->iNbCities);

  for (i = 0; i < pI2->iNbCities; i++)
  {
    pI->NearestNeighbourInit (*pI2, i);
    pI->Eval ();

    // Pas d'optimisation dans cette méthode !
    iNewPos = Reinsert (*pI);
    if (iNewPos == 0)
    {
      pI->LogRecord (i + 1);
    }
  }

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

/*========================================================================
Function : Initialisation of the selection array
==========================================================================*/
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));  // Plus de chaces pour les premiers
  }
}

/*========================================================================
Function : Destruction of the selection array
==========================================================================*/
void Group::DeleteSelectionArray ()
{
  delete[]SelectionArray;
}

/*========================================================================
Function : Random index (0 < a < iListCount) in the selection array
==========================================================================*/
int Group::GetRandSelectionArrayIndex ()
{
  int a, iRand;

  iRand = rand ();
  a = 0;
  while (iRand > SelectionArray[a])
  {
    a++;
  }
  return a;
}

/*========================================================================
Function : Selection of 2 Individuals for reproduction
In/out : a : index of the first selected individual  in the group
         b : index of the second selected individual in the group
==========================================================================*/
void Group::Select (int *a, int *b)
{
  SelectOne (a);
  do
  {
    SelectOne (b);
  }
  while ((*b) == (*a));
}

/*========================================================================
Function : Selection of 1 Individual for mutation
In/out : a : index of the selected individual in the group
==========================================================================*/
void Group::SelectOne (int *a)
{
  *a = GetRandSelectionArrayIndex ();
}

/*========================================================================
Function : Group random evolution
In : iNbIndividual : nb d'itérations
==========================================================================*/
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);
}

/*========================================================================
Function : Group Monte Carlo evolution (mutation of an individual, and
              reinsertion in the group if possible)
In : iNbIndividual : nb of iterations
     iMutationType : type of mutation
==========================================================================*/
void Group::MonteCarloEvol (int iNbIndividual, int iMutationType)
{
  int i, a;
  char sMessage[255];

  pTspLog->StartFunction ("Group::MonteCarloEvol", iInstance, LEVEL_DEBUG, iNbIndividual);

  // pour le nb d'itérations prévues
  for (i = 0; i < iNbIndividual; i++)
  {
    if (i % 1000 == 0)
    {
      sprintf (sMessage, "itération %d / %d", i + 1, iNbIndividual);
      pTspLog->ScreenMsg(sMessage);
    }
    // choisit au hasard un individue
    SelectOne (&a);
    // mute une copie de cet individu
    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 ();

    // s'il est meilleur que le parent, le remplace
    if (pI->lfFitness > List[a]->lfFitness)
    {
      pI->OptimizeFinal ();
      if (!Belongs (*pI))
      {
        List[a]->Duplicate (*pI);
        // si record
        if ((a == 0) || (pI->lfFitness > List[0]->lfFitness))
        {
          pI->LogRecord (i + 1);
        }
        else
        {
          sprintf (sMessage, "(%d)", a);
          pTspLog->ScreenMsg(sMessage);
        }
        //AAAAAAAAA => faire une fonction type reinsert pour éviter Sort
        Sort ();
      }
    }
  }

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

/*========================================================================
Function : Group Monte Carlo distinct evolution (each indivudual evolves
independently from the others of the group)
In : iNbIndividual : nb of iterations
     iMutationType : type of mutation
==========================================================================*/
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;
  // pour chaque individu de la population
  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);
      }
      // effectue une ou plusieurs mutations sur une copie
      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 ();

      // si la copie modifiée est meilleure que l'original
      if ( (pI->lfFitness > List[a]->lfFitness) && (!Belongs (*pI)) )
      {
        pI->OptimizeFinal ();

        // remplace
        if (!Belongs (*pI))
        {
          List[a]->Duplicate (*pI);
          if (pI->lfFitness > bestFitness)
          {
            bestFitness = pI->lfFitness;
            pI->LogRecord (i + 1);
          }
        }
      }
    }
  }

  Sort ();

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

/*========================================================================
Function : Group darwinian evolution
In : iNbIndividual : nb of iterations
     iNbMutationOptimization : nb of "simulated anealing" iterations
     iNbMaxMutation : nb max of winning mutations
     iCrossoverType : type of crossover
==========================================================================*/
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);

    // quel est le moins bon parent ?
    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))));  //NB_CROSSOVER
      //DEBUG printf ("%d ", iCrossoverTypeCalc);
      pI->Crossover (*List[a], *List[b], *pI2, iCrossoverTypeCalc);       //pI2 = temp

    }
    else
    {
      pI->Crossover (*List[a], *List[b], *pI2, iCrossoverType); //pI2 = temp
    }
    // crossover parent a et b => enfant pI
    pI->Eval ();

    // mini recuit simulé
    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 ();
    }

    // si l'enfant est meilleur que le moins bon des parents,
    if (pI->lfFitness > List[iLeastParent]->lfFitness)
    {
      // et si ce n'est pas non plus le meilleur parent...
      if (!Belongs (*pI))
      {
        if (pI->lfFitness > List[0]->lfFitness)
        {
          // record
          pI->LogRecord (i + 1);
        }
        else
        {
          // affichage du n° du parent amélioré
          sprintf (sMessage, "(%d)", iLeastParent);
          pTspLog->ScreenMsg(sMessage);
        }

        // s'il est meilleur que le meilleur parent, on continue le "recuit"
        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);    //AAAAAAAA
          }
        }

        if (!Belongs (*pI))
        {
          // on remplace le moins bon des parents par l'enfant
          List[iLeastParent]->Duplicate (*pI);
        }

        // on remet en ordre la liste des éléments du groupe
        Sort ();
      }
    }
  }
  pTspLog->EndFunction ("Group::DarwinEvol", iInstance);
}

/*========================================================================
Function : recherche locale avec mutation
In : lfMinScore : the fitness of the original individual
     iMutationType : type of mutation
     iNbMutationOptimization
     iNbMaxMutation : nb of mutations
Returns : true if the fitness is etter than the original individual
==========================================================================*/
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);
      }
/* DEBUG      printf(":");
      fflush(stdout);*/
    }

    // optimisation de pI
    pI2->Optimize ();
    pI2->Eval ();
    // si meilleur
    if (pI2->lfFitness > pI->lfFitness)
    {
      pI->Duplicate (*pI2);
      if (j > 0)
      {
        k++;
/* DEBUG        printf ("#");
        fflush (stdout);*/
      }
    }
    j++;
  }
  while ((pI->lfFitness > lfMinScore) && (j < iNbMaxMutation)
         && (k < iNbMutationOptimization));

  return (pI->lfFitness > lfMinScore);
}

/*========================================================================
Function : Sorts the group according to their fitness
            (Bubble sort, I know, but it is so easy to write !)
==========================================================================*/
void Group::Sort ()
{
  int i, j;

//  pTspLog->StartFunction ("Group::Sort", iInstance, LEVEL_DEBUG, iListCount);

  for (i = 0; i < iListCount; i++)
  {
    for (j = i + 1; j < iListCount; j++)
    {
      if ((*List[i]).lfFitness < (*List[j]).lfFitness)
      {
        Exchange (i, j);
      }
    }
  }
//  pTspLog->EndFunction ("Group::Sort", iInstance);
}

/*========================================================================
Function : Writes all the individuals of the group to a file in the CSV
            format (character separated text file)
==========================================================================*/
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);
}

/*========================================================================
Function : Read a group individuals in at CSV file
==========================================================================*/
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);
}

/*========================================================================
Function : Group duplication
In : G : the group to copy
==========================================================================*/
void Group::Duplicate (Group * G)
{
  int i;

  for (i = 0; i < iGroupSize; i++)
  {
    (List[i])->Duplicate (*(G->List[i]));
  }

  iListCount = G->iListCount;
}

/*========================================================================
Function : Pheromone Matrix
==========================================================================*/
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;
    }
  }

  // pour chaque élément
  for (i = 0; i < iGroupSize; i++)
  {
    iLastCity = List[i]->Cities[pI2->iNbCities - 1];
    // pour chaque ville
    for (j = 0; j < pI2->iNbCities; j++)
    {
      iCurrentCity = List[i]->Cities[j];
      aPheromone[(iCurrentCity * (pI2->iNbCities)) + iLastCity]++;
      aPheromone[(iLastCity * (pI2->iNbCities)) + iCurrentCity]++;
      iLastCity = iCurrentCity;
    }
  }

/*DEBUG
  for (i=0; i<pI2->iNbCities; i++)
  {
    for (j=0; j<pI2->iNbCities; j++)
    {
      printf("%d ", aPheromone[i*(pI2->iNbCities) + j]);
      fflush(stdout);
    }
  }
*/
  // on peut utiliser la matrice des phéromones
  bPheromoneOk = true;

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


vers Labo Algo
Labo Algo

Alexandre Aupetit, Mai 2004