vers Labo Algo
Labo Algo

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


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


/*========================================================================
=========================== INDIVIDUAL ===================================
==========================================================================*/

/*========================================================================
Function : Individual constructor
==========================================================================*/
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;
  }
}

/*========================================================================
Function : Individual destructor
==========================================================================*/
Individual::~Individual ()
{
  delete[] Cities;
}

/*========================================================================
Function : Individual cloning
==========================================================================*/
void Individual::Duplicate (const Individual & I)
{
  int i;

  lfFitness = I.lfFitness;

  for (i = 0; i < iNbCities; i++)
  {
    Cities[i] = I.Cities[i];
  }
}

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

/*========================================================================
Function : Individual nearest neighbour init.
==========================================================================*/
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++)
  {
    // recherche de la ville proche
    b = 0;
    a = pTSP->Near (iCurrentCity, b);

    // Si déjà visitée dans le fils, on ne prend pas, on cherche la ville un peu plus loin
    while ((I_temp.FindCityPos (a) != -1) && (b < pTSP->iNbNear - 1))
    {
      //b=(b+1)%pTSP->iNbNear;
      b++;
      a = pTSP->Near (iCurrentCity, b);
    }

    // si on a déjà tout exploré les villes proches
    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;
  }

  //remise en ordre du parcours (début = 0)
  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];
  }
}

/*========================================================================
Function : Individual fitness evaluation
==========================================================================*/
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))
  {
    // arrondi pour les double
    lfFitness = (float) ((int) (lfFitness * 10000)) / 10000.;
  }
}

/*========================================================================
Function : Individual read from a file
==========================================================================*/
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 ();
}

/*========================================================================
Function : Write to a file in "CSV" format
==========================================================================*/
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");
}

/*========================================================================
Function : Print the individual to the html log file
==========================================================================*/
void Individual::LogRecord (int iCurrentIteration)
{
  int i;
  char sCity[10];
  char *sPath;

  // calcul de la longueur max de 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);
}

/*========================================================================
Function : finds the position of city iCity
==========================================================================*/
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;
  }
}

/*========================================================================
Function : recherche la prochaine ville non visitée (dans les deux sens)
==========================================================================*/
int Individual::FindNextUnvisitedCity (int iCurrentCity, Individual & I_temp)
{
  int a, a1, a2, ok1, ok2;

  a = FindCityPos (iCurrentCity);
  a1 = a;
  a2 = a;
  ok2 = 10;
  do
  {
    // on regarde dans les deux sens (a1 et a2)
    a1 = (a1 + 1) % iNbCities;
    a2 = (a2 - 1 + iNbCities) % iNbCities;

    // Si déjà visitée dans le fils, on ne prend pas
    // il faut que == -1
    ok1 = I_temp.FindCityPos (Cities[a1]);
    if (ok1 != -1)
    {
      ok2 = I_temp.FindCityPos (Cities[a2]);
    }
  }
  while ((ok1 != -1) || (ok1 != -1));
  if (ok1 == -1)
  {
    // on passe à la ville, pas sa position
    a = Cities[a1];
  }
  else
  {
    // on passe à la ville, pas sa position
    a = Cities[a2];
  }

  return a;
}

/*========================================================================
Function :
==========================================================================*/
void Individual::ExchangeCities (int iCity1, int iCity2)
{
  int i_temp;

  i_temp = Cities[iCity1];
  Cities[iCity1] = Cities[iCity2];
  Cities[iCity2] = i_temp;
}

/*========================================================================
Function : reverse the order of the path between cities i and j
==========================================================================*/
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--;
  }
}

/*========================================================================
Function : insère la ville i entre j et j+1
!!! CONDITION : i < j
==========================================================================*/
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;
}

/*========================================================================
Function : insère la ville i entre j et j+1
!!! CONDITION : i < j
==========================================================================*/
void Individual::Depl1CitiesInv (int i, int j)
{
  int a, b, i_temp;

  a = i;
  b = j;
/* DEBUG  printf("a= %d b=%d\n", a, b);*/

  i_temp = Cities[b];

  while (b > a)
  {
    Cities[b] = Cities[b - 1];
    b--;
  }
  Cities[a] = i_temp;
}

/*========================================================================
Function : insère la ville i et i+1 entre j et j+1
!!! CONDITION : i < j
==========================================================================*/
void Individual::Depl2Cities (int i, int j)
{
  int a, b, i_temp, i_temp1;

  a = i;
  b = j;

/* DEBUG printf("a= %d b=%d\n", a, b);*/

  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;
}

/*========================================================================
Function : insère la ville j et j+1 entre i et i+1
!!! CONDITION : i < j
==========================================================================*/
void Individual::Depl2CitiesInv (int i, int j)
{
  int b, i_temp, i_temp1;

  b = j + 1;
/* DEBUG  printf("a= %d b=%d\n", i, b);
  fflush(stdout);*/

  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;
}

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

/*========================================================================
Function : 1 point crossover whith Heuristic (algorithm from Karoly F. Pal)
==========================================================================*/
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++)
  {
    // recherche de la ville suivant iCurrentCity
    a = I1.FindCityPos (iCurrentCity);
    b = I2.FindCityPos (iCurrentCity);

    // Si déjà visitée dans le fils, on ne prend pas
    do
    {
      a = (a + 1) % iNbCities;
    }
    while (I_temp.FindCityPos (I1.Cities[a]) != -1);
    // on passe à la ville, pas sa position
    a = I1.Cities[a];

    do
    {
      b = (b + 1) % iNbCities;
    }
    while (I_temp.FindCityPos (I2.Cities[b]) != -1);
    b = I2.Cities[b];

    // calcul des distances => probabilités de choix entre a et b
    d_a = pTSP->Distance (iCurrentCity, a);
    d_b = pTSP->Distance (iCurrentCity, b);

    p_a = d_a * rand ();
    p_b = d_b * rand ();

    // si la ville "a" a eu plus de chance que "b"
    if (p_a < p_b)
    {
      iCurrentCity = a;
    }
    else
    {
      iCurrentCity = b;
    }
    I_temp.Cities[iCurrentPos] = iCurrentCity;
  }

  //remise en ordre du parcours (début = 0)
  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];
  }
}

/*========================================================================
Function :  crossover PMX 2 points
Author :  Michaël Trabbia <michael.trabbia@enst.fr>
==========================================================================*/
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++)
  {
    // recherche de la ville i dans le parent I2
    a = I1.FindCityPos (I2.Cities[i]);
    I_temp.ExchangeCities (a, i);
  }

  //remise en ordre du parcours (début = 0)
  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];
  }
}

/*========================================================================
Function :  crossover CX (Cycle Cross Over)
Author :  Michaël Trabbia <michael.trabbia@enst.fr>
==========================================================================*/
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];

}

/*========================================================================
Function :  crossover OX (Order Cross Over)
Author :  Michaël Trabbia <michael.trabbia@enst.fr>
==========================================================================*/
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];
    }
  }

  //remise en ordre du parcours (début = 0)
  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];
  }
}

/*========================================================================
Function : Special crossover
==========================================================================*/
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;
  }

  // on commence par une ville au hasard
  iCurrentCity = (int) (((iNbCities) * (rand () / (RAND_MAX + 1.0))));
  I_temp.Cities[0] = iCurrentCity;

  for (iCurrentPos = 1; iCurrentPos < iNbCities; iCurrentPos++)
  {
    // recherche de la ville suivant iCurrentCity
    a = I1.FindNextUnvisitedCity (iCurrentCity, I_temp);
    b = I2.FindNextUnvisitedCity (iCurrentCity, I_temp);

    /* DEBUG d_a = (pGroup->aPheromone[iCurrentCity*iNbCities + a] > 0);
      d_b = (pGroup->aPheromone[iCurrentCity*iNbCities + b] > 0); */
    d_a = pGroup->aPheromone[iCurrentCity * iNbCities + a];
    d_b = pGroup->aPheromone[iCurrentCity * iNbCities + b];

    // chance identique si different de 0 ?

    p_a = d_a * rand ();
    p_b = d_b * rand ();
    /* DEBUG  p_a = RAND_MAX/2;
    p_b = rand();
    */

    // si la ville "a" a eu plus de chance que "b"
    if (p_a < p_b)
    {
      iCurrentCity = a;
    }
    else
    {
      iCurrentCity = b;
    }
    I_temp.Cities[iCurrentPos] = iCurrentCity;
  }

  //remise en ordre du parcours (début = 0)
  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];
  }
}

/*========================================================================
Function : mutation (ie perturbation) of an individual
==========================================================================*/
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)
  {
    /* Reverse the path between cities == 2-change */
  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 :
    // on prend 1 ville au harsard
    a = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));

    do
    {
      // on prend une ville "proche" (la iNear ième)
      f = (rand () / (RAND_MAX + 1.0));
      f = f * f / 25;
      iNear = (int) (((pTSP->iNbNear) * f));
      // b est cette ville proche
      b = FindCityPos (pTSP->Near (Cities[a], iNear));
    }
    while ((b == 0) || (b == a));
    ReverseCities (a, b);
    break;

    /* Swap 2 cities */
  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;

    /* Mutation heuristique Karoly F. Pal */
  case MUT_NEAR_2_KFP:
    // on prend 1 ville au harsard i
    i = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
    b = -1;
    best_d = 0;

    // Pour les villes proches de 1 à 15, on cherche le meilleur gain
    for (iNear = 0; iNear < 15; iNear++)
    {
      // j est la iNear ième ville proche
      j = FindCityPos (pTSP->Near (Cities[i], iNear));

      // on ne change pas la ville zéro ni les villes adjacentes
      if ((j != 0) && (j != i) && (j != (i + 1) % iNbCities)
          && (j != (i - 1) % iNbCities))
      {
        if (i < j)
        {
          // on calcule le gain en échangeant les villes
          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
        {
          // on calcule le gain en échangeant les villes
          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;

    /* Mélange des points voisins */
  case MUT_NEAR_SCRAMBLE_SWAP:
    // on prend 1 ville au harsard i
    iCentre = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
    iVoisinage = (int) (sqrt (iNbCities) * 2);

    // On mélange les villes proches
    for (iNear = 0; iNear < iVoisinage; iNear++)
    {
      // i est la iNear ième ville proche du centre du mélange
      i = FindCityPos (pTSP->Near (Cities[iCentre], iNear));
      // j est une ville proche de i
      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);
      }
//          Optimize4ChangeNearLocal(iCentre);
    }
    break;

    /* Mélange des points voisins */
  case MUT_NEAR_SCRAMBLE_CHANGE:
    // on prend 1 ville au harsard i
    iCentre = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
    iVoisinage = (int) (sqrt (iNbCities) * 5);

    // On mélange les villes proches
    for (iNear = 0; iNear < iVoisinage; iNear++)
    {
      // i est la iNear ième ville proche du centre du mélange
      i = (iCentre + iNear + 1) % iNbCities;
      // j est une ville proche de i
      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 :
      // on choisit une ville au hasard dans le parcours
      i = (int) (((iNbCities - 1) * (rand () / (RAND_MAX + 1.0)) + 1));

      // on recherche n_i proche de i en distance mais éloigné de plus de 15 dans le parcours
      // (repli)
      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]);

/* DEBUG          printf("iCompt = %d d = %f \n", iCompt, d);
          fflush(stdout);*/

          if (d < best_d)
          {
            best_d = d;
            best_indice = iCompt;
          }
        }
      }

/* DEBUG      printf("i = %d best_indice = %d (%d) best_d = %f\n", i, best_indice, Cities[best_indice], best_d);
      fflush(stdout);*/

      if (best_indice != -1)
      {
        if (best_indice < i)
        {
          n_i = i;
          i = best_indice;
        }
        else
        {
          n_i = best_indice;
        }
        // on a maintenant i < n_i et n_i proche de i

        // on cherche j tel que j entre i et n_i
        j = i + (int) (((n_i-i - 1) * (rand () / (RAND_MAX + 1.0)) + 1));
/* DEBUG        printf(" i = %d  j = %d  n_i = %d\n", i, j, n_i);
        fflush(stdout);*/

        // on cherche n_j proche de j mais hors de i, n_i
        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]);

/* DEBUG           printf("iCompt = %d d = %f \n", iCompt, d);
            fflush(stdout);*/

            if (d < best_d)
            {
              best_d = d;
              best_indice = iCompt;
            }
          }
        }

/* DEBUG       printf("j = %d best_indice = %d (%d) best_d = %f\n", j, best_indice, Cities[best_indice], best_d);
        fflush(stdout);*/

        if (best_indice != -1)
        {
          n_j = best_indice;

/* DEBUG         printf("i=%d (%d), j=%d (%d), ni=%d (%d), nj=%d (%d)\n", i, Cities[i], j, Cities[j], n_i, Cities[n_i], n_j, Cities[n_j]);
          fflush(stdout);*/

          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;
  }
}

/*========================================================================
Function : local optimization (2-opt)
==========================================================================*/
bool Individual::Optimize ()
{
  return Optimize2ChangeCompl ();
}

/*========================================================================
Function : local optimizations
==========================================================================*/
void Individual::OptimizeFinal ()
{
  OptimizeSwapCompl ();
  Optimize1DeplCompl ();
  Optimize();

  Eval ();   // Est-ce nécessaire ? AAAAAAAAAAA
}

/*========================================================================
Function : systematic local optimization (2-opt)
==========================================================================*/
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;
}

/*========================================================================
Function : systematic local optimization (1-depl)
==========================================================================*/
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;
}

/*========================================================================
Function : systematic local optimization (2-opt)
==========================================================================*/
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;
}

/*========================================================================
Function : 2-opt gain
==========================================================================*/
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]);
}

/*========================================================================
Function : 2-opt gain
==========================================================================*/
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]];
}

/*========================================================================
Function : 1-depl gain
==========================================================================*/
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]);
}

/*========================================================================
Function : 1-depl gain
==========================================================================*/
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]);
}

vers Labo Algo
Labo Algo

Alexandre Aupetit, Mai 2004