TSP Problem - Part 2 - Local Optimization and Meta Heuristics

// Take a tour array
// Return running time
double twoOpt(int *tour) {
 clock_t start, end;

 if (LOG) {
  fprintf(debfp, "2 Opt local optimization...\n");
 }
 if (DEBUG)
  printf("2 Opt local optimization...\n");

 start = clock();

 int bestGain = INT_MAX;
 int best_i;
 int best_j;
 int gain;
 double ct = 0.0;
 int count = 0;
 // Continue until no improvements are possible
 while (bestGain != 0) {
  bestGain = 0;
  for (int i = 1; i < dimension; i++) {
   int j = i + 2;
   for (; j < dimension; j++) {
    gain = compute_gain(tour, i, j);
    // Search for the biggest gain
    if (gain < bestGain) {
     bestGain = gain;
     best_i = i;
     best_j = j;
    }
   }
  }
  count++;

  if (DEBUG2OPT)
   printf("Best optimization %d->%d and %d->%d = %d\n", tour[best_i],
     tour[best_i + 1], tour[best_j], tour[best_j + 1], bestGain);

  if (LOG) {
   fprintf(debfp, "Best optimization %d->%d and %d->%d = %d\n",
     tour[best_i], tour[best_i + 1], tour[best_j], tour[best_j
       + 1], bestGain);
  }

  if (bestGain != 0) {
   if (DEBUG2OPT)
    printf("SWAP");

   // Swap cities
   swap(tour, best_i + 1, best_j);
   // Reverse path
   reverseArray(tour, best_i + 1, best_j);
  }
 }

 end = clock();
 ct = ((end - start) / ((double) CLOCKS_PER_SEC)) * 1000.0;
 return ct;
}

int *simulatedAnnealing(int *tour, int remainingMS, int startTemp,
  double delta, int iteration) {
 int *current = (int *) calloc(sizeof(int), dimension + 2);
 int *best = (int *) calloc(sizeof(int), dimension + 2);
 int *next = (int *) calloc(sizeof(int), dimension + 2);

 clock_t start, end;

 current = tour;
 next = tour;
 best = current;
 double temp = startTemp;
 int diff = 0;

 int iter = iteration;
 if(randomSeed==0)
   randomSeed = time(NULL);
 
 srand(randomSeed);

 double random = 0.0;
 int lenNext = 0;
 int lenCurrent = 0;
 int lenBest = length(current);

 if (DEBUGSA) {
  printf("SA: Random seed: %d\n Remaining time: %d\n", randomSeed, remainingTime);
 }

 while (temp > 0 && remainingMS > 0) {

  while (iter > 0) {
   // Start clock
   start = clock();
   next = doubleBridge(current); // Diversification
   twoOpt(next); // Intensification
   lenNext = length(next);
   lenCurrent = length(current);
   diff = lenNext - lenCurrent;

   if (DEBUGSA) {
    printf("SA: Difference between next[%d] and current[%d] = %d\n", lenNext, lenCurrent, diff);
   }

   if (diff < 0) {
    current = next;
    if(lenNext < lenBest)
    {
     if(tourCheck(next, lenNext))
     {
      if(lenNext < bestknown)
      {
       printf("Stopped something wrong!");
       getchar();
      }
      copy(next, best, dimension + 2);
      printf("*** NEW BEST: %d\n", lenNext);
      lenBest = lenNext;
     } else
     {
      printf("Wrong tour!\n");
     }

    }
   } else {
    random = (rand() / ((double)RAND_MAX));
    if (DEBUGSA) {
     printf("SA: Generated random: %2.3f\n", random);
    }
    // Stochastic decision
    if (random < exp(-diff / temp)) {
     // current = next
     if (DEBUGSA) {
      printf("Current = next");
     }
     copy(next, current, dimension + 2);
    } else {
     // keep current
    }
   }
   // Compute remaining time
   end = clock();
   remainingMS -= (((end - start) / ((double) CLOCKS_PER_SEC))
     * 1000.0);

   iter--;
  }
  iter = iteration;
  temp = temp * delta;
 }
 return best;
}