unit3.cpp

遗传算法求解tsp文题 里面包括了执行文件

//---------------------------------------------------------------------------
#include <vcl\vcl.h>
#include "Unit3.h"
int no_of_cities; // needs to be known by ops

#pragma hdrstop
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[]) {
  // bad implementation here!

  int edge_map[255][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(int 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(int 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(int 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(int i = 1; i < no_of_cities; i++) {
    int k = 0;
    for(int j = 0; j < 4; j++) {
      choice[j] = 255;
      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

    // 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(int 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
          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(int i = 0; i < no_of_cities; i++)
    if (q2[i] != 1) fail = 1;

  // copy to p1
  if (!fail) {
    for(int 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(int 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];
    for(int i = 0; i < no_of_cities; i++)
      if (p2[i] == p1[px]) {
        px = i;
        break;
      }
    if (q2[px] != 255) finish = 1;
  }
  for(int i = 0; i < no_of_cities; i++)
    if (q2[i] == 255)
      q2[i] = p1[i];

  for(int 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(int 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(int 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(int 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;
      }
    }
  }
}
//---------------------------------------------------------------------------