travel.cc

Genetic Algorithm (GA) based solver for the Traveling Salesman Problem

#include "global.h"
#include "gene.h"
#include "chromo.h"
#include "pop.h"
#include <string.h>
#include <stdlib.h>
#include <stream.h>
#include <fstream.h>
#include <sys/types.h>
#include <time.h>

const int MINARGS = 10;

void usage(char *progName)
{
  cerr << "Usage: " << progName << endl;
  cerr << "  popSize       (1 <= popSize <= " << MAXINT << ")" << endl;
  cerr << "  generations   (1 <= generations <= " << MAXINT << ")" << endl;
  cerr << "  crossover     (0.0000 <= crossover <= 1.0000)" << endl;
  cerr << "  crossoverType (0 (= fixedPos)," << endl
    <<    "                 1 (= fixedPosSeq))" << endl;
  cerr << "  mutation      (0.0000 <= mutation <= 1.0000)" << endl;
  cerr << "  deletionType  (0 (= deleteAll)," << endl
    << "                 1 (= steadyDelete))" << endl;
  cerr << "  elitismValue  only used if deletionType = deleteAll" << endl
    << "                (0 <= elitismValue <= popSize)" << endl;
  cerr << "  fitnessType   (0 (= evaluation)," << endl
    <<    "                 1 (= windowing)," << endl
      <<  "                 2 (= linearNorm))" << endl;
  cerr << "  fitnessParam  if fitnessType = evaluation" << endl
    << "                   this is not used" << endl;
  cerr << "                if fitnessType = windowing" << endl
    << "                   this is the guarding value" << endl
      << "                   (1.0000 <= fitnessParam <= maxDist)" << endl;
  cerr << "                if fitnessType = linearNorm" << endl
    << "                   this is the decrease value (%)" << endl
      << "                   (0.0000 <= fitnessParam <= 100.0000)" << endl;
  cerr << "  seed          (0 (= random) <= seed <= " << MAXINT << ")" << endl;
  cerr << "  [initfile]    (default value = `genes.dat')" << endl << endl;
  cerr << "Value limit: maxDist * genes * popSize <= " << MAXDOUBLE << endl;
  cerr << "      where  maxDist = the maximal Eucledian distance " << endl
    <<    "                       between two genes in initfile" << endl
      <<  "               genes = number of genes in initfile + 1" << endl;
}

int main(int argc, char *argv[], char **envp)
{
  unsigned int chromoLength;

  char *progName;
  char *dataFile;
  char buf1[nameLength + 1];
  char buf2[nameLength + 1];
  char buf3[nameLength + 1];
  coord_t x,y;
  unsigned int i, j;

  if ((progName = strchr(argv[0], '/')) == (char *)0)
    progName = argv[0];
  else
    progName++;
  if (argc <= MINARGS)
    {
      cerr << "Error: Wrong number of arguments" << endl;
      usage(progName);
      return 1;
    }
  
  int popSize = atoi(argv[1]);
  int generations = atoi(argv[2]);
  float crossover = atof(argv[3]);
  cross_t crossoverType = (cross_t)(atoi(argv[4]));
  float mutation = atof(argv[5]);
  delete_t deletionType = (delete_t)(atoi(argv[6]));
  int elitismValue = atoi(argv[7]);
  fitness_t fitnessType = (fitness_t)(atoi(argv[8]));
  eval_t fitnessParam = atof(argv[9]);
  int seed = atoi(argv[10]);
 
  if (argc == (MINARGS + 1))
    dataFile = "genes.dat";
  else
    dataFile = argv[MINARGS + 1];

  ifstream dataStr(dataFile);
  if (!dataStr)
    {
      cerr << "Error: Couldn't find gene data file `" << dataFile <<
	"'" << endl;
      usage(progName);
      return 1;
    }
  
  i = 0;
  while (dataStr.getline(buf1, nameLength))
    i++;

  chromoLength = (unsigned int)i + 1;

  dataStr.seekg(0, ios::beg);
  dataStr.clear();
  
  Gene *genePool[chromoLength];

  for (i = 0; i < (chromoLength - 1); i++)
    {
      if (!(dataStr.getline(buf1, nameLength, '\t')))
	break;
      if (!(dataStr.getline(buf2, nameLength, ',')))
	{
	  cerr << "Error: Bad format or unexpected end of file at line " <<
	    i << " in file `" << dataFile << "'" << endl;
	  break;
	}
      if (!(dataStr.getline(buf3, nameLength)) && !(dataStr.eof()))	  
	{
	  cerr << "Error: Bad format or unexpected end of file at line " <<
	    i << " in file `" << dataFile << "'" << endl;
	  break;
	}
      x = (coord_t) atof(buf2);
      y = (coord_t) atof(buf3);
      genePool[i] = new Gene(buf1, x, y, i, chromoLength);
      if (i == 0)
	genePool[(chromoLength - 1)] = new Gene(buf1, x, y, (chromoLength - 1),
						chromoLength);
//      cout << *genePool[i] << endl;      
    }

  for (i = 0; i < chromoLength; i++)
    for (j = 0; j < chromoLength; j++)
      genePool[i]->calculateDistanceTo(*genePool[j]);
/*
  for (i = 0; i < chromoLength; i++)
    cout << *genePool[i] << endl;
*/
/*
  for (i = 0; i < chromoLength; i++)
    for (j = 0; j < chromoLength; j++)
      cout << "[" << i << "," << j << "] " <<
	genePool[i]->getName() << "-" <<
	  genePool[j]->getName() << ": " <<
	    genePool[i]->distanceTo(*genePool[j]) << endl;
*/

  if (seed == 0)
    {
      time_t tv;
      time(&tv);
      srand(tv);
      cout << "Using seed: " << tv << endl;
    }
  else
    srand(seed);

//******************* Main Evolution Loop **********************

  Pop *myPop = new Pop(popSize, chromoLength, genePool);
  Pop *myNewPop;

  int k;

cout << "Data:" << endl;

  for (k = 0; k < generations; k++)
    {
      myPop->fitness(fitnessType, fitnessParam);
	cout << k << " "
	  << myPop->fitnessAverage() << " "
	    << myPop->bestFitness() << endl;
//      cout << "[" << k <<"] average: "
//	<< myPop->fitnessAverage()
//	  << "    best: " << myPop->bestFitness() << endl;

      myNewPop = myPop->newPop(fitnessType, fitnessParam, crossover,
			       crossoverType, mutation, deletionType,
			       elitismValue);
      if (deletionType == deleteAll)
	{
	  delete myPop;
	  myPop = myNewPop; 
	}
    }

cout << "End of Data" << endl;
  cout << "Best solution:" << endl;
//  for (k = 0; k < chromoLength; k++)
//    {
  cout << myPop->bestChromo() << endl; 

//}
  
  delete myPop;
  return 0;
}