unit_main.cpp

针对TSP问题

/*
  Version History
  ver 1.00 Dec  9, 1997 Official Release
  ver 1.01 Dec 10, 1997 Add a write button

  Flags:

  TForm1->AS_start : if a valid instance ready
  cities->loaded   : if a TSP file loaded (Global Var: AS)
*/
//---------------------------------------------------------------------------
#include <vcl\vcl.h>
#pragma hdrstop

#include "Unit_Main.h"
//---------------------------------------------------------------------------
#pragma link "titlebar"
#pragma link "Digits"
#pragma resource "*.dfm"
TASForm *ASForm;
//---------------------------------------------------------------------------
cities::cities(int nc, int na, double pa, double pb, double pe, double pq, double pt) {
  nofc = nc;
  nofa = na;
  alpha = pa;
  beta = pb;
  evaporation = pe;
  Q = pq;
  tolerance = pt;
  best_length = MAXDOUBLE;
  cycle_count_when_best_found = 0;

  tao = new double * [nofc];
  visibility = new double * [nofc];
  city = new double * [nofc];
  ants = new int *[nofa];
  allowed = new int * [nofa];
  lengths = new double [nofa],
  prob = new double[nofc];
  best_solution = new int[nofc];
  for(int i = 0; i < nofc; i++) {
    tao[i] = new double[nofc];
    visibility[i] = new double[nofc];
    city[i] = new double[2];
  }

  for(int i = 0; i < nofa; i++) {
    ants[i] = new int[nofc];
    allowed[i] = new int[nofc];
  }

}

cities::~cities() {
  for(int i = 0; i < nofc; i++) {
    delete tao[i];
    delete visibility[i];
    delete city[i];
  }

  for(int i = 0; i < nofa; i++) {
    delete ants[i];
    delete allowed[i];
  }
  delete tao, visibility, city, ants, allowed, lengths, prob, best_solution;
}

void cities::change_p(double pa, double pb, double pe, double pq, double pt) {
  alpha = pa;
  beta = pb;
  evaporation = pe;
  Q = pq;
  tolerance = pt;
}

void cities::generate_city_map() {
  // add a CheckBox to randomize
  if (ASForm->CheckBox_random->Checked) {
    unsigned int tt = GetTickCount();
    char line[80];
    itoa(tt, line, 10);
    ASForm->Edit_seed->Text = line;
    srand(tt);
  } else
    srand(ASForm->Edit_seed->Text.ToInt());

  for(int i = 0; i < nofc; i++) {
    city[i][0] = (rand() % 10000) / 10000.0;
    city[i][1] = (rand() % 10000) / 10000.0;
  }
}

void cities::load_city_map(AnsiString pf, AnsiString tf) {
  loaded = true;
  file_loaded = pf;

  // open the city points file
  char line[81];
  FILE * f = fopen(pf.c_str(), "rt");
  // skip the number of cities
  fgets(line, 80, f);
  double x1, y1;
  for(int i = 0; i < nofc; i++) {
    fgets(line, 80, f);
    sscanf(line, "%lf %lf", &x1, &y1);
    city[i][0] = x1;
    city[i][1] = y1;
  }
  fclose(f);

  // get the optimal solution
  optimal_solution = new int[nofc];
  f = fopen(tf.c_str(), "rt");
  for(int i = 0; i < nofc; i++) {
    fgets(line, 80, f);
    sscanf(line, "%d", &optimal_solution[i]);
    optimal_solution[i]--; // start with city(1) rather than (0)
  }
  fclose(f);

  // calculate the optimal length
  optimal_length = 0;
  for(int i = 0; i < nofc - 1; i++) {
    optimal_length +=
      sqrt(
      (city[ optimal_solution[i] ][0] - city[ optimal_solution[i+1] ][0]) *
      (city[ optimal_solution[i] ][0] - city[ optimal_solution[i+1] ][0]) +
	  (city[ optimal_solution[i] ][1] - city[ optimal_solution[i+1] ][1]) *
	  (city[ optimal_solution[i] ][1] - city[ optimal_solution[i+1] ][1])
      );
  }
  optimal_length +=
    sqrt(
    (city[ optimal_solution[nofc-1] ][0] - city[ optimal_solution[0] ][0]) *
    (city[ optimal_solution[nofc-1] ][0] - city[ optimal_solution[0] ][0]) +
	(city[ optimal_solution[nofc-1] ][1] - city[ optimal_solution[0] ][1]) *
	(city[ optimal_solution[nofc-1] ][1] - city[ optimal_solution[0] ][1])
    );
}

void cities::ini_visibility_and_tao() {
  for(int i = 0; i < nofc; i++) {
    for(int j = 0; j < nofc; j++) {
	  // a little bit waste of time
	  if (i != j) {
        visibility[i][j] = (city[i][0] - city[j][0])*(city[i][0] - city[j][0]) +
                           (city[i][1] - city[j][1])*(city[i][1] - city[j][1]);
        visibility[i][j] = 1 / sqrt(visibility[i][j]);
      } else
        visibility[i][j] = 0;

      tao[i][j] = 1.0;
    }
  }
}

bool cities::one_cycle() {
  // put every city in each ant's alloed list
  for(int i = 0; i < nofa; i++)
    for (int j = 0; j < nofc; j++)
      allowed[i][j] = j;

  // assign the starting town to ants randomly
  // and eliminate this town from allowed[][]
  // add a CheckBox to select different ini configuratiion
  // int temp;
  for(int i = 0; i < nofa; i++) {
    ants[i][0] = i % nofc;
    // temp = allowed[i][ [ants[i][0] ];
    allowed[i][ ants[i][0] ] = allowed[i][nofc - 1];
    // allowed[i][nofc - 1] = temp;
  }
  // remember to re-initialize the random generator
  srand(GetTickCount());

  int tc = 0, 	// time & position counter (unnecessary, use x)
      which_t;	// which town is the next?

  double dice, sum_p;
  // main cycle
  for(int x = 0; x < nofc - 1; x++) {
    for(int i = 0; i < nofa; i++) {
      // decide which town should ant(i) go
      // (1) calculate the summation of all probabilities
      sum_p = 0;
      for(int j = 0; j < nofc - tc - 1; j++) {
        prob[j] = pow( tao[ ants[i][tc] ][ allowed[i][j] ], alpha) *
                  pow( visibility[ ants[i][tc] ][ allowed[i][j] ], beta);
        sum_p += prob[j];
      }

      // (2) roll a dice and decide which town to go
      dice = ((double)rand() / RAND_MAX) * sum_p;
      for(int j = 0; j <nofc -tc - 1; j++) {
        dice -= prob[j];
        if (dice < 0) {
          which_t = j;
          break;
        }
      }

      // (3) put the next town in ant(i)'s tabu list
      //     and eliminate this town from the ant's allowed list
      ants[i][tc + 1] = allowed[i][which_t];
      // temp = allowed[i][which_t];
      allowed[i][which_t] = allowed[i][nofc - tc - 2];
      // allowed[i][nofc - tc - 2] = temp;
    } // end of each ant in a time unit
    tc++;
  } // end of one cycle

  // compute the length found by each ant
  double min_length = MAXDOUBLE;
  best_ant = 0;
  for(int i = 0; i < nofa; i++) {
    lengths[i] = 0;
    for(int j = 0; j < nofc - 1; j++)
      // the inverse computation can be eliminated
      lengths[i] += 1 / visibility[ ants[i][j] ][ ants[i][j+1] ];
    lengths[i] += 1 / visibility[ ants[i][nofc-1] ][ ants[i][0] ];
    if (min_length > lengths[i]) {
      best_ant = i;
      min_length = lengths[i];
    }
  }

  // update the tao, note to remian the symmetry
  for(int i = 0; i < nofc; i++)
    for(int j = 0; j < nofc; j++)
      tao[i][j] *= evaporation;

  for(int i = 0; i < nofa; i++) {
    for(int j = 0; j < nofc - 1; j++) {
      tao[ ants[i][j] ][ ants[i][j+1] ] += Q / lengths[i];
      tao[ ants[i][j+1] ][ ants[i][j] ] += Q / lengths[i];
    }
    tao[ ants[i][nofc - 1] ][ ants[i][0] ] += Q / lengths[i];
    tao[ ants[i][0] ][ ants[i][nofc - 1] ] += Q / lengths[i];
  }

  // check for stagnation
  bool stagnation = true;
  for(int i = 0; i < nofa - 1; i++) {
    if (fabs(lengths[i] - lengths[i + 1]) > tolerance) {
      stagnation = false;
      break;
    }
  }
  if (nofa == 1)
    stagnation = false;

  // update the best solution
  if (lengths[best_ant] < best_length) {
    cycle_count_when_best_found = ASForm->step_count;
    best_length = lengths[best_ant];
    for(int i = 0; i < nofc; i++)
      best_solution[i] = ants[best_ant][i];
  }

  return stagnation;
}