pop.cc

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

// pop.cc
// Implementation of class Pop
// Thomas Pederson, 950505

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

Pop::Pop(int _popSize, unsigned int _chromoLength, Gene *_genePool[])
{
   chromoLength = _chromoLength;
   genePool = _genePool;
   popSize = _popSize;
   eval = 0;
   myChromoPool = new (Chromo *)[popSize];
   for (int i = 0; i < popSize; i++)
   {
      myChromoPool[i] = new Chromo(chromoLength, genePool);
      myChromoPool[i]->init();
   }
}
Pop::~Pop()
{
   delete [] myChromoPool;
}

// Population initialization.
void Pop::init()
{
   eval = 0;
   for (int i = 0; i < popSize; i++)
      myChromoPool[i]->init();
}

// Returns a suitable parent using Roulette Wheel Selection.
Chromo& Pop::getParent()
{
   int i, slump;
   
   slump = rand() % (int)eval;
   i = 0;
   while ((i < popSize) && (myChromoPool[i]->getModEval() < slump))
      i++;
   return *myChromoPool[i];
}

// Sorts chromosome pool in fitness order.
void Pop::quickSort(int start, int finish)
{
   int left, right;
   Chromo *tmpChromo;
   eval_t startVal;
   
   left = start;
   right = finish;
   startVal = myChromoPool[(start + finish) / 2]->eval();
   do
   {
      while (myChromoPool[left]->eval() < startVal)
	 left++;
      while (myChromoPool[right]->eval() > startVal)
	 right--;
      if (left <= right)
      {
	 tmpChromo = myChromoPool[left];
	 myChromoPool[left] = myChromoPool[right];
	 myChromoPool[right] = tmpChromo;
	 left++;
	 right--;
      }
   }
   while (left < right);
   if (start < right)
      quickSort(start, right);
   if (left < finish)
      quickSort(left, finish); 
}

// Returns the modified fitness of the best cromosome in the population.
eval_long_t Pop::fitness(fitness_t fitnessType, eval_t fitnessParam)
{
   if (eval == 0)
   {
      int i;
      eval_t tmpEval, minEval, maxEval;
      
      quickSort(0, popSize - 1);
      
      minEval = myChromoPool[0]->eval();
      maxEval = myChromoPool[popSize - 1]->eval();
      eval = 0;

      if (fitnessType == evaluation)
	 for (i = 0; i < popSize; i++)
	    eval = myChromoPool[i]->setModEval(eval + maxEval + minEval -
					       myChromoPool[i]->eval());
      else if (fitnessType == windowing)
      {
	 eval_t guardedEval;
	 
	 minEval;
	 for (i = 0; i < popSize; i++)
	 {
	    if ((guardedEval = (maxEval - myChromoPool[i]->eval()))
		< fitnessParam)
	       guardedEval = fitnessParam;
	    eval = myChromoPool[i]->setModEval(eval + guardedEval);
	 }
      }
      
      else // fitnessType == linearNorm
      {
	 eval_t tmpEval;
	 
	 eval = 0;
	 tmpEval = 100;
	 for (i = 0; i < popSize; i++)
	 {
	    if (tmpEval <= 0)
	    {
	       for (int j = i; j < popSize; j++)
		  myChromoPool[j]->setModEval(eval);
	       i = j; // break outer loop
	    }
	    else
	    {
	       eval = myChromoPool[i]->setModEval(eval + tmpEval);
	       tmpEval -= fitnessParam;
	    }
	 }
      }
   }

   return eval;
}

// Creates a new population using this population as a parent pool
// and returns a pointer to the new population.
// If deletionType == deleteAll, the user of this class has to
// delete this population (the new one is really a _new_ one).
// If deletionType == steadyDelete, the old population is altered
// and thus, requires no further action by the user.
Pop *Pop::newPop(fitness_t fitnessType, eval_t fitnessParam,
		 float crossover, cross_t crossoverType, float mutation,
		 delete_t deletionType, int elitismValue)
{
   Pop *nPop;
   if (deletionType == deleteAll)
   {
      int i;
      
      nPop = new Pop(popSize, chromoLength, genePool);
      for (i = 0; (i < elitismValue) && (i < popSize); i++)
	 *(nPop->myChromoPool[i]) = *(myChromoPool[i]);  // copying elite
      
      for (i = elitismValue; i < popSize; i += 2)
	 if (i == (popSize - 1))
	 {
	    Chromo *tmpChild = new Chromo(chromoLength, genePool);
	    getParent().mate(crossover, crossoverType, mutation, 
			     getParent(), *(nPop->myChromoPool[i]),
			     *tmpChild);
	    delete tmpChild;
	 }
	 else
	    getParent().mate(crossover, crossoverType, mutation,
			     getParent(), *(nPop->myChromoPool[i]),
			     *(nPop->myChromoPool[i + 1]));   
   }
   else // deletionType == steadyDelete
   {
      int i;      
      
      Chromo *tmp1 = new Chromo(chromoLength, genePool);
      Chromo *tmp2 = new Chromo(chromoLength, genePool);
      for (i = 0; i < popSize; i += 2)
      {
	 getParent().mate(crossover, crossoverType, mutation,
			  getParent(), *tmp1, *tmp2);
	 if (i != (popSize - 1))
	    *(myChromoPool[popSize - 2]) = *tmp1;
	 *(myChromoPool[popSize - 1]) = *tmp2;
	 
	 eval = 0;
	 fitness(fitnessType, fitnessParam); // resort
      }
      delete tmp1;
      delete tmp2;
      
      nPop = this;
   }
   
   return nPop;
}

// Returns the average chromosome fitness of the population.
eval_t Pop::fitnessAverage()
{
   eval_long_t sum = 0;
   for (int i = 0; i < popSize; i++)
      sum += myChromoPool[i]->getEval();
   return (sum / popSize);
}

// Prints population information to stream.
ostream& operator<<(ostream& outStr, Pop& pop)
{
   cout << "population size:   " << pop.popSize << endl;
   cout << "chromosome length: " << pop.chromoLength << endl;
   cout << "total evaluation:  " << pop.eval << endl;
   cout << "chromosome 0:" << endl;
   for (int i = 0; i < 1; i++)
      cout << *(pop.myChromoPool[i]) << endl;
   
   return outStr;
}