tsp1.cpp

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

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

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

  delete[] q1, q2;
}

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

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

  for(int i = c1; i <= c2; i++) {
    q1[i] = p1[i];
    q2[i] = p2[i];
  }

  int t1 = (c2 + 1) % no_of_cities,
      t2 = t1;
  unsigned char tc;
  while (t1 != c1) {
    tc = p2[t2];
    int finish = 0;
    while (!finish) {
      finish = 1;
      for(int i = c1; i <= c2; i++) {
        if (tc == q1[i]) {
          finish = 0;
          t2 = (t2 + 1) % no_of_cities,
          tc = p2[t2];
          break;
        }
      }
    }
    q1[t1] = tc;
    t1 = (t1 + 1) % no_of_cities;
    t2 = (t2 + 1) % no_of_cities;
  }

  t1 = (c2 + 1) % no_of_cities;
  t2 = t1;
  while (t1 != c1) {
    tc = p1[t2];
    int finish = 0;
    while (!finish) {
      finish = 1;
      for(int i = c1; i <= c2; i++) {
        if (tc == q2[i]) {
          finish = 0;
          t2 = (t2 + 1) % no_of_cities,
          tc = p1[t2];
          break;
        }
      }
    }
    q2[t1] = tc;
    t1 = (t1 + 1) % no_of_cities;
    t2 = (t2 + 1) % no_of_cities;
  }

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

  delete[] q1, q2;
}

void pmx_op(unsigned char p1[], unsigned char p2[]) {
  // 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;
  for(int i = c1; i <= c2; i++) {
    t2 = p1[i]; p1[i] = p2[i]; p2[i] = t2;
  }

  for(i = 0; i < c1; i++) {
    for(int j = c1; j <= c2; j++) {
      if (p1[i] == p1[j]) {
        unsigned char t = p2[j];
        int finish = 0;
        while (!finish) {
          finish = 1;
          for(int k = c1; k <= c2; k++)
            if (t == p1[k]) {
              t = p2[k];
              finish = 0;
              break;
            }
        }
        p1[i] = t;
      }
      if (p2[i] == p2[j]) {
        unsigned char t = p1[j];
        int finish = 0;
        while (!finish) {
          finish = 1;
          for(int k = c1; k <= c2; k++)
            if (t == p2[k]) {
              t = p1[k];
              finish = 0;
              break;
            }
        }
        p2[i] = t;
      }
    }
  }

  for(i = c2 + 1; i < no_of_cities; i++) {
    for(int j = c1; j <= c2; j++) {
      if (p1[i] == p1[j])  {
        unsigned char t = p2[j];
        int finish = 0;
        while (!finish) {
          finish = 1;
          for(int k = c1; k <= c2; k++)
            if (t == p1[k]) {
              t = p2[k];
              finish = 0;
              break;
            }
        }
        p1[i] = t;
      }
      if (p2[i] == p2[j]) {
        unsigned char t = p1[j];
        int finish = 0;
        while (!finish) {
          finish = 1;
          for(int k = c1; k <= c2; k++)
            if (t == p2[k]) {
              t = p1[k];
              finish = 0;
              break;
            }
        }
        p2[i] = t;
      }
    }
  }
}

void generate_meta_generation() {
  long sum = 0;
  for(int i = 0; i < population; i++)
    sum += fitness[i];
  float temp, err = 0;
  int n = 0;
  for(i = 0; i < population; i++) {
    temp = (float)fitness[i] / sum * population;
    no_of_offspring[i] = floor(temp);
    err += (temp - floor(temp));
    if (err > 1) {
      no_of_offspring[i]++;
      err--;
    }
    n += no_of_offspring[i];
  }
  // adjust to match the population
  no_of_offspring[population - 1] += (population - n);
  n = 0;
  for(i = 0; i < population; i++) {
    for(int j = 0; j < no_of_offspring[i]; j++) {
      for(int k = 0; k < no_of_cities; k++)
        meta_generation[n][k] = old_generation[i][k];
      n++;
    }
  }

  // shuffle the meta generation
  unsigned char tc;
  for(i = 0; i < population; i++) {
    n = rand() % population;
    // swap
    for(int j = 0; j < no_of_cities; j++) {
      tc = meta_generation[i][j];
      meta_generation[i][j] = meta_generation[n][j];
      meta_generation[n][j] = tc;
    }
  }

  int p;
  for(i = 0; i < population - 1; i+=2) {
    p = rand() % 1000;
    if (p < p_of_crossover) {
//      er_op(meta_generation[i], meta_generation[i + 1]);
//      pmx_op(meta_generation[i], meta_generation[i + 1]);
//      ox_op(meta_generation[i], meta_generation[i + 1]);
//      cx_op(meta_generation[i], meta_generation[i + 1]);
      switch (rand() % 4) {
      case 0 : er_op(meta_generation[i], meta_generation[i + 1]); break;
      case 1 : pmx_op(meta_generation[i], meta_generation[i + 1]); break;
      case 2 : ox_op(meta_generation[i], meta_generation[i + 1]); break;
      case 3 : cx_op(meta_generation[i], meta_generation[i + 1]); break;
    }
  }

  for(i = 0; i < population; i++) {
    p = rand() % 1000;
    if (p < p_of_mutation)
      inv_op(meta_generation[i]);
  }
  memmove(old_generation, meta_generation, population * no_of_cities);

}

void main() {
/*
  unsigned char p1[9] = {0,1,2,3,4,5,6,7,8},
                p2[9] = {3,0,1,7,6,5,8,2,4};
  er_op(p1, p2);
  for(int i = 0; i < no_of_cities; i++)
    printf("%d->", p1[i]);
  printf("\n");
  int ch = getc(stdin);
*/

  debug = 0;
  int repeat = 0;
  long old_minimum_distance;
  minimum_distance = MAXLONG;
  old_minimum_distance = minimum_distance;
//  randomize();
  generate_city_map();
  load_city_map();
  initialize_population();
  calculate_fitness();
  printf("---\n");
  for(int i = 0; i < no_of_generation; i++) {
    if (i > 4) debug = 1;
    printf("> (%5d) [before %ld] - %ld -", i, average_distance, minimum_distance);
    generate_meta_generation();
    old_minimum_distance = minimum_distance;
    calculate_fitness();
    printf(" [after %ld] (%5d)\n", average_distance, repeat);
    if (old_minimum_distance == minimum_distance)
      repeat++;
    else
      repeat = 0;
    if (repeat > duration)
      break;
  }
  output_result();
/*
  // print all population
  for(i = 0; i < population; i++) {
    printf("[%4d] : ", i);
    for(int j = 0; j < no_of_cities; j++)
      printf("%2d ", (int)old_generation[i][j]);
    printf("\n");
  }
*/
/*
  printf("\n\n\n");
  unsigned char t1[no_of_cities], t2[no_of_cities];
  for(int i = 0; i < no_of_cities; i++) {
    t1[i] = (unsigned char)i;
    t2[i] = (unsigned char)i*2 % no_of_cities;
  }
  for(i = 0; i < no_of_cities - 1; i++) {
    for(int j = i + 1; j < no_of_cities - 1; j++) {
      pmx_op(t1, t2);
      for(int k = 0; k < no_of_cities; k++)
        printf("[%1d] ", (int)(t1[k]));
      printf("\n");
      for(k = 0; k < no_of_cities; k++)
        printf("[%1d] ", (int)(t2[k]));
      printf("\n\n");
      while(!kbhit()); getch();
    }
  }
*/
}