tsp1.cpp

用经典算法--模拟退火算法求解经典问题旅行商（Travel Sales Problem）问题。

                                                                                                                                                                                                                                                                                                                                                                                                             #include "stdlib.h"
#include "stdio.h"
#include "math.h"
#include "string.h"
#include "values.h"

#define no_of_cities 99
#define population 2000
#define cutoff 1.02
#define p_of_crossover 130
#define p_of_mutation 50
#define no_of_generation 32000
#define duration 500

//--- global variables ---
int debug;

long average_distance, minimum_distance;
int minimum_path;

int city[2][no_of_cities];
int map[no_of_cities][no_of_cities];
unsigned char old_generation[population][no_of_cities];
unsigned char meta_generation[population][no_of_cities];
// maximum no_of_cities 254
int fitness[population];
int no_of_offspring[population];

void output_result() {
  printf("\n[ minumum distance ] : %ld\n", minimum_distance);
  for(int i = 0; i < no_of_cities; i++)
    printf("%d\n", old_generation[minimum_path][i]);
  printf("==========");
}


void calculate_fitness() {
  int max = 0;
  for(int i = 0; i < population; i++) {
    fitness[i] = 0;
    for(int j = 1; j < no_of_cities; j++)
      fitness[i] += map[ old_generation[i][j] ][ old_generation[i][j+1] ];
    fitness[i] += map[ old_generation[i][no_of_cities] ][ old_generation[i][0] ];
    if (fitness[i] > max) max = fitness[i];
   }
  max *= cutoff;
  average_distance = 0;
  for(i = 0; i < population; i++) {
    average_distance += fitness[i];
    if (fitness[i] < minimum_distance) {
      minimum_distance = fitness[i];
      minimum_path = i;
    }
    fitness[i] = max - fitness[i];
  }
  average_distance /= population;
}

void generate_city_map() {
  for(int i = 0; i < no_of_cities; i++) {
    city[0][i] = rand() % 100;
    city[1][i] = rand() % 100;
  }
  for(i = 0; i < no_of_cities; i++)
    for(int j = 0; j < no_of_cities; j++)
      map[i][j] = sqrt((city[0][i] - city[0][j])*(city[0][i] - city[0][j])+
                       (city[1][i] - city[1][j])*(city[1][i] - city[1][j]));
}

void load_city_map() {
  char line[80];
  FILE * f = fopen("rat99.tsp", "rt");
  int t1, t2, t3;
  for(int i = 0; i < 99; i++) {
    fgets(line, 80, f);
    sscanf(line, "%d %d %d", &t1, &t2, &t3);
    city[0][i] = t2;
    city[1][i] = t3;
  }
  for(i = 0; i < no_of_cities; i++)
    for(int j = 0; j < no_of_cities; j++)
      map[i][j] = sqrt((city[0][i] - city[0][j])*(city[0][i] - city[0][j])+
                       (city[1][i] - city[1][j])*(city[1][i] - city[1][j]));
}

void initialize_population() {
  unsigned char tc[no_of_cities];
  for(int i = 0; i < no_of_cities; i++)
    tc[i] = (unsigned char)i;
  int p, q = 0;
  unsigned char temp;
  for(i = 0; i < population; i++) {
/*
    q = (q + 1) % no_of_cities;
    p = rand() % no_of_cities;
    temp = tc[p]; tc[p] = tc[q]; tc[q] = temp;
*/
    for(int j = 0; j < no_of_cities; j++)
      old_generation[i][j] = tc[j];
  }

}

void inv_op(unsigned char p[]) {
  // generate two random cut points
  int c1 = rand() % no_of_cities,
      c2 = rand() % no_of_cities;
  while (c1 == c2)
    c2 = rand() % no_of_cities;
  int t;
  if (c1 > c2) {
    t = c1; c1 = c2; c2 = t;
  }

  unsigned char t2;
  while (c1 < c2) {
    t2 = p[c1]; p[c1++] = p[c2]; p[c2--] = t2;
  }
}

void er_op(unsigned char p1[], unsigned char p2[]) {
  int edge_map[no_of_cities][5];
  for(int i = 0; i < no_of_cities; i++) {
    edge_map[i][0] = 0; // no_of_edges
    edge_map[i][1] = 255;
    edge_map[i][2] = 255;
    edge_map[i][3] = 255;
    edge_map[i][4] = 255;
  }

  // generate edge_map with overlap
  for(i = 1; i < no_of_cities - 1; i++) {
    edge_map[ p1[i] ][ ++edge_map[ p1[i] ][0] ] = p1[i + 1];
    edge_map[ p1[i] ][ ++edge_map[ p1[i] ][0] ] = p1[i - 1];
    edge_map[ p2[i] ][ ++edge_map[ p2[i] ][0] ] = p2[i + 1];
    edge_map[ p2[i] ][ ++edge_map[ p2[i] ][0] ] = p2[i - 1];
  }
  edge_map[ p1[0] ][ ++edge_map[ p1[0] ][0] ] = p1[1];
  edge_map[ p1[0] ][ ++edge_map[ p1[0] ][0] ] = p1[no_of_cities - 1];
  edge_map[ p2[0] ][ ++edge_map[ p2[0] ][0] ] = p2[1];
  edge_map[ p2[0] ][ ++edge_map[ p2[0] ][0] ] = p2[no_of_cities - 1];
  edge_map[ p1[no_of_cities - 1] ][ ++edge_map[ p1[no_of_cities - 1] ][0] ] = p1[0];
  edge_map[ p1[no_of_cities - 1] ][ ++edge_map[ p1[no_of_cities - 1] ][0] ] = p1[no_of_cities - 2];
  edge_map[ p2[no_of_cities - 1] ][ ++edge_map[ p2[no_of_cities - 1] ][0] ] = p2[0];
  edge_map[ p2[no_of_cities - 1] ][ ++edge_map[ p2[no_of_cities - 1] ][0] ] = p2[no_of_cities - 2];


  // eliminate overlap
  for(i = 0; i < no_of_cities; i++) {
    for(int j = 1; j < 4; j++) {
      for(int k = j + 1; k <= 4; k++) {
        if ((edge_map[i][j] != 255) &&
            (edge_map[i][j] == edge_map[i][k])) {
          // -255 => -0, 255 => empty
          if (edge_map[i][j] == 0)
            edge_map[i][j] = -255;
          else
            edge_map[i][j] = -edge_map[i][j];
          edge_map[i][k] = 255;
          edge_map[i][0]--;
        }
      }
    }

    if (edge_map[i][0] == 2)
      for(int j = 1; j <= 4; j++)
        if (edge_map[i][j] < 0) {
          // case of -0
          if (edge_map[i][j] == -255)
            edge_map[i][j] = 0;
          else
            edge_map[i][j] = -edge_map[i][j];
        }
  }

  // generate offspring
  // q1 -> offspring
  // q2 -> temporary variable
  unsigned char * q1 = new unsigned char[no_of_cities],
                * q2 = new unsigned char[no_of_cities];

  int choice[4];
  for(i = 0; i < no_of_cities; i++)
    q2[i] = (unsigned char)255;
  q1[0] = p1[0];
  q2[ q1[0] ] = (unsigned char)1; // city[ q1[0] ] has been selected

  for(i = 1; i < no_of_cities; i++) {
    int k = 0;
//if (debug)  printf("-s %d %d", i, q1[i - 1]);
    for(int j = 0; j < 4; j++) {
      choice[j] = 255;
/*
if (debug) {
  for(i = 0; i < no_of_cities; i++)
    if (p1[i] == 255) printf("--!!--");
}
*/
//if (debug)      printf("%d", q1[i - 1]);
      if (edge_map[ q1[i - 1] ][j + 1] != 255) {
        if (edge_map[ q1[i - 1] ][j + 1] != -255) {
          if (q2[ abs(edge_map[ q1[i - 1] ][j + 1]) ] == 255) { // hasn't been selected yet
            choice[j] = edge_map[ q1[i - 1] ][j + 1];      // [1] - [4]
            k++;
          }
        } else {
          // the case of -0 (-255)
          if (q2[ 0 ] == 255) { // hasn't been selected yet
            choice[j] = -255; // edge_map[ q1[i - 1] ][j + 1];
            k++;
          }
        }
      }
    } // end for
//if (debug)  printf("-e");

    // only valid choice will reach here

    int finish = 0;
//  if (edge_map[ q1[i - 1] ][0] == 3) { // only when three choices there will be negative
//  if (k == 3) { // only when three choices there will be negative
    // find if any negative choice
    for(j = 0; j < 4; j++) {
      if (choice[j] < 0) {
        // case of negative 0
        if (choice[j] == -255) {
          q1[i] = 0;
          q2[ 0 ] = 1;
        } else {
          q1[i] = -choice[j]; // warning happens here; only one neg
//if (debug) printf("%d", q1[i]);
          q2[ -choice[j] ] = 1;
        }
        finish = 1;
      }
    }

    if (!finish) {
      int min_edge = 5, px  = -1;
      for(int j = 0; j < 4; j++) {
        if (choice[j] != 255) {
          if (edge_map[ choice[j] ][0] < min_edge) {
            min_edge = edge_map[ choice[j] ][0];
            px = choice[j];
          } else
            if (edge_map[ choice[j] ][0] == min_edge) {
              if ((rand() % 10) > 5) {
                min_edge = edge_map[ choice[j] ][0];
                px = choice[j];
              }
            }
        }
      }
      if (px == -1) break; // find no valid edges
      q1[i] = (unsigned char)px; // warning happens here; only one neg
      q2[ px ] = 1;
    }

  }

  // check for validaty
  int fail = 0;
  for(i = 0; i < no_of_cities; i++)
    if (q2[i] != 1) fail = 1;

  // copy to p1
  if (!fail) {
    for(i = 0; i < no_of_cities; i++)
      p1[i] = q1[i];
  }

  delete[] q1, q2;
}


void cx_op(unsigned char p1[], unsigned char p2[]) {
  unsigned char * q1 = new unsigned char[no_of_cities],
                * q2 = new unsigned char[no_of_cities];

  for(int i = 0; i < no_of_cities; i++) {
   q1[i] = 255;
   q2[i] = 255;
  }

  int finish = 0;
  int px = 0;
  while (!finish) {
    q1[px] = p1[px];
    for(int i = 0; i < no_of_cities; i++)
      if (p1[i] == p2[px]) {
        px = i;
        break;
      }
    if (q1[px] != 255) finish = 1;
  }
  for(i = 0; i < no_of_cities; i++)
    if (q1[i] == 255)
      q1[i] = p2[i];

  finish = 0;
  px = 0;
  while (!finish) {
    q2[px] = p2[px];