chromo.cc

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

// chromo.cc
// Implementation of class Chromo
// Thomas Pederson, 950505

#include "chromo.h"
#include <stdlib.h>

Chromo::Chromo(unsigned int _chromoLength, Gene *_genePool[])
{
   chromoLength = _chromoLength;
   genePool = _genePool;
   myGenePool = new (Gene *)[chromoLength];
   myEval = -1.0;
   myModEval = -1.0;
}

Chromo::~Chromo()
{
   delete [] myGenePool;
}

// Copy constructor.
Chromo& Chromo::operator=(Chromo& original)
{
   if (this == &original)
      return *this;
   delete [] myGenePool;
   chromoLength = original.chromoLength;
   myGenePool = new (Gene *)[chromoLength];
   for (int i = 0; i < chromoLength; i++)
      myGenePool[i] = original.myGenePool[i];
   myEval = original.myEval;
}

// Chromosome initialization.
void Chromo::init()
{
   int i, j;
   
   for (i = 1; i < (chromoLength - 1); i++)
      myGenePool[i] = (Gene *)0;
   myGenePool[0] = genePool[0];
   myGenePool[chromoLength - 1] = genePool[chromoLength - 1];
   
   for (i = 1; i < (chromoLength - 1); i++)
   {
      while (myGenePool[(j = myRand())] != (Gene *)0)
	 continue;
      myGenePool[j] = genePool[i];
   }
}

// Calculates (if necessary) and returns chromosome evaluation.
eval_t Chromo::eval()
{
   if (myEval == -1.0)
   {
      myEval = 0.0;
      for (int i = 0; i < (chromoLength - 1); i++)
	 myEval += myGenePool[i]->distanceTo(*myGenePool[i + 1]);
   }
   return myEval;
}

// Mates this chromosome with partner resulting in two new offsprings, child1 and child2.
void Chromo::mate(float _crossover, cross_t crossoverType,
		  float _mutation, Chromo& partner,
		  Chromo& child1, Chromo& child2)
{
   if (rand() <= (_crossover * RAND_MAX))
      child1.crossover(crossoverType, *this, partner);
   else
      child1 = *this;
   if (rand() <= (_mutation * RAND_MAX))
      child1.mutate();
   
   if (rand() <= (_crossover * RAND_MAX))
      child2.crossover(crossoverType, partner, *this);
   else
      child2 = partner;
   
   if (rand() <= (_mutation * RAND_MAX))
      child2.mutate();
}

// Prints chromosome information to stream.
ostream& operator<<(ostream& outStr, Chromo& chromo)
{
   for (int i = 0; i < chromo.chromoLength; i++)
      cout << "[" << i << "]: " << *(chromo.myGenePool[i]) << endl;
   cout << "Distance:    " << chromo.myEval << endl;
   return outStr;
}

// Keeping track of used genes during crossover.
int Chromo::isUsed(Gene *gene, Gene *usedGene[], int noOfUsedGenes)
{
   for (int i = 0; i < noOfUsedGenes; i++)
      if (usedGene[i] == gene)
	 return 1;
   return 0;
}

// Performs crossover using parent1 and parent2 as templates.
// This chromosome is assigned the result.
void Chromo::crossover(cross_t crossoverType, Chromo& parent1, Chromo& parent2)
{
   int i, j, k, l;
   int curGene = 0;
   Gene *usedGene[chromoLength];
   
   usedGene[0] = (myGenePool[0] = parent1.myGenePool[0]);
   usedGene[chromoLength - 1] = (myGenePool[chromoLength - 1] =
				 parent1.myGenePool[chromoLength - 1]);
   if (crossoverType == fixedPos)
   {
      j = 1;
      for (i = 1; i < (chromoLength - 1); i++)
      {
	 if (rand() % 2)
	 {
	    usedGene[j] = (myGenePool[i] = parent1.myGenePool[i]);
	    j++;
	 }
	 else
	    myGenePool[i] = (Gene *)0;
      }
   }
   else // crossoverType == fixedPosSeq
   {
      int left, right;
      Gene *tmpGene;
      
      left = ((rand() % (chromoLength - 3)) + 1);
      right = ((rand() % (chromoLength - (2 + left))) + left + 1);
      
      j = 1;
      for (i = 1; i < (chromoLength - 1); i++)
      {
	 if (i >= left && i <= right)
	 {
	    usedGene[j] = (myGenePool[i] = parent1.myGenePool[i]);
	    j++;
	 }
	 else
	    myGenePool[i] = (Gene *)0;
      }
   }
   
   curGene = 0;
   for (k = 0; k < chromoLength; k++)
   {
      if (myGenePool[k] == (Gene *)0)
      {
	 for (l = curGene; l < chromoLength; l++)
	 {
	    if (!(isUsed(parent2.myGenePool[l], usedGene, j)))
	    {
	       myGenePool[k] = parent2.myGenePool[l];
	       curGene = (l + 1);
	       break;
	    }
	 }
      }
   }

   myEval = -1.0;
}

// Performs mutation on this chromosome.
void Chromo::mutate()
{
   int left, right, i, s;
   Gene *tmpGene;
   
   left = ((rand() % (chromoLength - 3)) + 1);
   right = ((rand() % (chromoLength - (2 + left))) + left + 1);
   
   for (i = left; i <= right; i++)
   {
      tmpGene = myGenePool[i];
      s = left + rand() % (right - left);
      myGenePool[i] = myGenePool[s];
      myGenePool[s] = tmpGene;
   }

   myEval = -1.0;
}

// Modified random generator.
unsigned int Chromo::myRand()
{
   return ((rand() % (chromoLength - 2)) + 1);
}