unit_main.cpp

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

/*
  Version History
  ver 1.00 Dec  9, 1997 Official Release

  Flags:

*/
//---------------------------------------------------------------------------
#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 np,
               double cf, int du, double pofc, double pofm,
               int m, int nofg) {
  // set the global variable no_of_cities required by op
  no_of_cities = nc;

  nofc = nc;
  population = np;
  cutoff = cf;
  duration = du;
  p_of_crossover = pofc;
  p_of_mutation = pofm;
  op = m;
  no_of_generation = nofg;
  count_of_gen = 0;

  best_length = MAXDOUBLE;
  minimum_distance = MAXDOUBLE;

  old_generation = new unsigned char *[population];
  meta_generation = new unsigned char *[population];

  fitness = new double[population];
  no_of_offspring = new int[population];

  city = new double * [nofc];
  map = new double * [nofc];
  best_solution = new unsigned char[nofc];

  for(int i = 0; i < nofc; i++) {
    city[i] = new double[2];
    map[i] = new double[nofc];
  }
  for(int i = 0; i < population; i++) {
    old_generation[i] = new unsigned char[nofc];
    meta_generation[i] = new unsigned char[nofc];
  }
}

cities::~cities() {
  for(int i = 0; i < nofc; i++) {
    delete city[i];
    delete map[i];
  }
  for(int i = 0; i < population; i++) {
    delete old_generation[i];
    delete meta_generation[i];
  }
  delete old_generation,
         meta_generation,
  		 fitness,
         no_of_offspring,
         city,
         map,
         best_solution;
}

void cities::calculate_fitness() {
  bool best_updated = false;
  double max = 0;
  for(int i = 0; i < population; i++) {
    fitness[i] = 0;
    for(int j = 0; j < nofc - 1; j++)
      fitness[i] += map[ old_generation[i][j] ][ old_generation[i][j+1] ];
    fitness[i] += map[ old_generation[i][nofc - 1] ][ old_generation[i][0] ];
    if (fitness[i] > max) max = fitness[i];
  }

  max *= cutoff;
  average_distance = 0;
  for(int i = 0; i < population; i++) {
    average_distance += fitness[i];
    if (fitness[i] < minimum_distance) {
      minimum_distance = fitness[i];
      best_child = i;
      best_updated = true;
    }
    fitness[i] = max - fitness[i];
  }
  average_distance /= population;

  // update the best solution
  if (best_updated)
    for(int i = 0; i < nofc; i++)
      best_solution[i] = old_generation[best_child][i];
}

void cities::change_p(double cf, int du, double pofc, double pofm, int nofg) {
  cutoff = cf;
  duration = du;
  p_of_crossover = pofc;
  p_of_mutation = pofm;
  no_of_generation = nofg;
}

void cities::setup_map() {
  for(int i = 0; i < nofc; i++)
    for(int j = 0; j < nofc; j++)
      map[i][j] = sqrt((city[i][0] - city[j][0])*(city[i][0] - city[j][0])+
                       (city[i][1] - city[j][1])*(city[i][1] - city[j][1]));
}

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;
  }
  setup_map();
}

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 unsigned char[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])
    );
  setup_map();
}

void cities::initialize_population() {
  unsigned char * tc = new unsigned char[nofc];
  for(int i = 0; i < nofc; i++)
    tc[i] = (unsigned char)i;
  int p, q = 0;
  unsigned char temp;
  for(int i = 0; i < population; i++)
    for(int j = 0; j < nofc; j++)
      old_generation[i][j] = tc[j];
}

void cities::generate_meta_generation() {
  double sum = 0;
  for(int i = 0; i < population; i++)
    sum += fitness[i];
  double temp, err = 0;
  int n = 0;
  for(int i = 0; i < population; i++) {
    temp = 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(int i = 0; i < population; i++) {
    for(int j = 0; j < no_of_offspring[i]; j++) {
      for(int k = 0; k < nofc; k++)
        meta_generation[n][k] = old_generation[i][k];
      n++;
    }
  }

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

  double p;
  for(int i = 0; i < population - 1; i+=2) {
    p = (double)rand() / RAND_MAX;
    if (p < p_of_crossover) {
      switch (op) {
        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(int i = 0; i < population; i++) {
    p = (double)rand() / RAND_MAX;
    if (p < p_of_mutation)
      inv_op(meta_generation[i]);
  }

  // move meta_generation to old_generation
  for(int i = 0; i < population; i++)
    memmove(old_generation[i], meta_generation[i], nofc);
}

bool cities::one_cycle() {
  bool stalled = false;
  int repeat = 0;

  for(int i = 0; i < no_of_generation; i++) {
    generate_meta_generation();
    old_minimum_distance = minimum_distance;
    calculate_fitness();
    count_of_gen++;
    ASForm->Digits1->Increase();
    if (old_minimum_distance == minimum_distance)
      repeat++;
    else
      repeat = 0;
    if (repeat > duration) {
      stalled = true;
      break;
    }
  }
  return stalled;
}

void cities::paint_result() {
  // draw the black background
  TColor tcr = 0;
  TRect tr;
  tr.Left = 1;
  tr.Right = 400;
  tr.Top = 1;
  tr.Bottom = 400;
  ASForm->Canvas->Brush->Color = clBlack;
  ASForm->Canvas->FillRect(tr);

  // draw the cities
  ASForm->Canvas->Brush->Color = clWhite;
  for(int i = 0; i < nofc; i++) {
    tr.Left = city[i][0] * 400 - 2;
    tr.Right = city[i][0] * 400 + 2;
    tr.Top = city[i][1] * 400 - 2;
    tr.Bottom = city[i][1] * 400 + 2;
    ASForm->Canvas->FillRect(tr);
  }

  ASForm->Canvas->Pen->Mode = pmCopy;
  ASForm->Canvas->Pen->Color = clYellow;
  ASForm->Canvas->MoveTo(city[ best_solution[0] ][0] * 400,
                         city[ best_solution[0] ][1] * 400);
  for(int i = 1; i < nofc; i++) {
    ASForm->Canvas->LineTo(city[ best_solution[i] ][0] * 400,
                           city[ best_solution[i] ][1] * 400);
  }
  ASForm->Canvas->LineTo(city[ best_solution[0] ][0] * 400,
                         city[ best_solution[0] ][1] * 400);
}

//---------------------------------------------------------------------------
__fastcall TASForm::TASForm(TComponent* Owner)
	: TForm(Owner)
{
  AS_start = false;
  output_file = fopen("ga.out", "at");
}

//---------------------------------------------------------------------------
void __fastcall TASForm::Button_goClick(TObject *Sender)
{
  Digits1->Value = 0;
  AS_start = false;
  Repaint();
  if (ComboBox_op->ItemIndex == -1)
    ComboBox_op->ItemIndex = 0;

  AS = new cities(	Edit_cities->Text.ToInt(), 			// number of cities
            		Edit_pop->Text.ToInt(), 			// population
            		Edit_cutoff->Text.ToDouble(),		// cutoff
            		Edit_duration->Text.ToInt(),		// duration
            		Edit_pofc->Text.ToDouble(),	 		// p. of crossover
            		Edit_pofm->Text.ToDouble(),			// p. of mutation
                    ComboBox_op->ItemIndex,			    // operator
                    Edit_steps->Text.ToInt());		    // number of steps
  AS->loaded = false;
  AS->generate_city_map();
  AS->initialize_population();
  AS->calculate_fitness();

  StatusBar->Panels->Items[0]->Text = "";
  StatusBar->Panels->Items[1]->Text = "";
  StatusBar->Panels->Items[2]->Text = "";
  StatusBar->Panels->Items[3]->Text = "";
  Button_step->Enabled = true;
  Button_load->Enabled = true;
  Button_write->Enabled = false;
}

//---------------------------------------------------------------------------
void __fastcall TASForm::Button_stepClick(TObject *Sender)
{
  Button_write->Enabled = true;
  // change the parameters
  AS->change_p(	Edit_cutoff->Text.ToDouble(),		// cutoff
            	Edit_duration->Text.ToInt(),		// duration
            	Edit_pofc->Text.ToDouble(),	 		// p. of crossover
            	Edit_pofm->Text.ToDouble(),		    // p. of mutation
                Edit_steps->Text.ToInt());		    // number of steps

  char line[80];
  bool stalled;

  StatusBar->Panels->Items[0]->Text = "";
  Screen->Cursor = crHourGlass;

  if (stalled = AS->one_cycle()) {
    StatusBar->Panels->Items[0]->Text = "S";
  }

  Screen->Cursor = crDefault;

  // update the status bar
  AnsiString ts = (int)(AS->minimum_distance*1000)/1000.0;
  ts = "B: " + ts;
  StatusBar->Panels->Items[2]->Text = ts;

  if (AS->loaded) {
    double dt = (AS->minimum_distance - AS->optimal_length) / AS->optimal_length;
    ts = (int)(dt * 1000)/10.0;
    ts = "D: " + ts + "%";
    StatusBar->Panels->Items[3]->Text = ts;
  }

  AS_start = true;
  ASForm->Paint();
  ASForm->Update();
}
//---------------------------------------------------------------------------
void __fastcall TASForm::Button_loadClick(TObject *Sender)
{
  Digits1->Value = 0;
  AS_start = false;
  // execute OpenDialog and Get the City Points & Optimal Solution
  OpenDialog1->Title = "Open a city points file";
  OpenDialog1->Filter = "City Points|*.tsp";
  if (!OpenDialog1->Execute())
    return;
  AnsiString pf = OpenDialog1->FileName;

  OpenDialog1->Title = "Open the optimal solution file";
  OpenDialog1->Filter = "Optimal Solution|*.opt";
  OpenDialog1->FileName = "";
  if (!OpenDialog1->Execute())
    return;
  AnsiString tf = OpenDialog1->FileName;

  // Get the number of cities
  char line[81];
  FILE * f = fopen(pf.c_str(), "rt");
  fgets(line, 80, f);
  line[ strlen(line) - 1] = NULL; // eliminate the new line character
  Edit_cities->Text = line;
  fclose(f);

  // initialization
  Repaint();
  AS = new cities(	Edit_cities->Text.ToInt(), 			// number of cities
            		Edit_pop->Text.ToInt(), 			// population
            		Edit_cutoff->Text.ToDouble(),		// cutoff
            		Edit_duration->Text.ToInt(),		// duration
            		Edit_pofc->Text.ToDouble(),	 		// p. of crossover
            		Edit_pofm->Text.ToDouble(),			// p. of mutation
                    ComboBox_op->ItemIndex,			    // operator
                    Edit_steps->Text.ToInt());		    // number of steps

  AS->load_city_map(pf, tf);
  AS->initialize_population();
  AS->calculate_fitness();
  Button_step->Enabled = true;

  // display the optimal solution
  AnsiString ts = (int)(AS->optimal_length*1000)/1000.0;
  ts = "Op: " + ts;
  StatusBar->Panels->Items[3]->Text = ts;
  StatusBar->Panels->Items[1]->Text = "";
  StatusBar->Panels->Items[2]->Text = "";
  Button_load->Enabled = false;
  Button_write->Enabled = false;
}
//---------------------------------------------------------------------------
void __fastcall TASForm::Show_About(TObject *Sender)
{
  AboutBox->ShowModal();
}
//---------------------------------------------------------------------------
void __fastcall TASForm::FormPaint(TObject *Sender)
{
  if (AS_start)
    AS->paint_result();
}
//---------------------------------------------------------------------------
void __fastcall TASForm::Change(TObject *Sender)
{
  ASForm->Repaint();
  ASForm->Update();
}
//---------------------------------------------------------------------------
void __fastcall TASForm::write_result(TObject *Sender)
{
  if (!AS_start)
    return;

  char line[256];
  if (AS->loaded)
    sprintf(line, "%3d %5d %.2lf %.2lf %.2lf %.2lf - %.4lf %5d %.4lf %s\n",
                  AS->nofc, AS->population,
                  AS->cutoff, AS->p_of_crossover, AS->p_of_mutation,
   				  AS->best_length, AS->count_of_gen,
                  AS->optimal_length, AS->file_loaded);
  else
    sprintf(line, "%3d %5d %.2lf %.2lf %.2lf %.2lf - %.4lf %5d %.4lf R(%s)\n",
                  AS->nofc, AS->population,
                  AS->cutoff, AS->p_of_crossover, AS->p_of_mutation,
   				  AS->best_length, AS->count_of_gen,
  				  0.0, Edit_seed->Text.c_str());
  fputs(line, output_file);
}
//---------------------------------------------------------------------------