src/selection/linearRankSelection.h

   1 #ifndef __SELECTION_LINEAR_RANK_H
   2 #define __SELECTION_LINEAR_RANK_H
   3
   4 #include <map>
   5
   6 #include "chromosome.h"
   7 #include "generation.h"
   8 #include "fitness/fitness.h"
   9 #include "selection/selection.h"
  10
  11 using namespace std;
  12
  13 namespace genetic {
  14 //     namespace selection {
  15         /**
  16          * Linear Rank Selection class.
  17          * Based on the
  18          */
  19         template < typename _Chromosome >
  20         class LinearRankSelection : public Selection<_Chromosome> {
  21         public:
  22             /**
  23              * Type representing Fitness function
  24              */
  25             typedef Fitness<_Chromosome> GeneticFitness;
  26
  27             /**
  28              * Value type returned by the Fitness function
  29              */
  30             typedef typename GeneticFitness::ValueType FitnessValueType;
  31         protected:
  32             typedef typename std::multimap<FitnessValueType, _Chromosome> ChromosomeMap;
  33             typedef typename ChromosomeMap::iterator ChromosomeMapIterator;
  34
  35             /**
  36              * Calculates Ranks for the Chromosomes
  37              *
  38              * @return multimap containing ranked Chromosomes, where key is the
  39              *      rank value.
  40              */
  41             ChromosomeMap rankChromosomes() {
  42                 const unsigned int generationSize = this->generation.size();
  43                 FitnessValueType fitness = 0;
  44
  45                 ChromosomeMap generationFitness;
  46
  47                 for (unsigned int i = 0; i < generationSize; i++) {
  48                     fitness = this->checkChromosomeFitness(this->generation[i]);
  49                     generationFitness.insert(std::make_pair(fitness, this->generation[i]));
  50                 }
  51
  52                 // multimap is automatically sorted by key, so we don't need to
  53                 // sort it again
  54
  55                 // p(i) = (rank(i) / N*(N-1)), where rankedGeneration[i] = p(i)
  56                 ChromosomeMap rankedGeneration;
  57
  58                 unsigned int rank = generationSize;
  59                 double denominator = generationSize * (generationSize - 1);
  60
  61                 for (ChromosomeMapIterator it = generationFitness.begin(); it != generationFitness.end(); it++) {
  62 //                     cout << "rank: " << rank << " denominator: " << denominator << " res: " << (rank-1)/denominator << "\n";
  63                     rankedGeneration.insert(std::make_pair(rank--/denominator, it->second));
  64                 }
  65
  66                 return rankedGeneration;
  67             }
  68
  69             /**
  70              * Selection calculations should be done here.
  71              *
  72              * @return new Generation of Chromosome's that passed the Selection
  73              */
  74             virtual Generation<_Chromosome> do_draw() {
  75                 ChromosomeMap probabilities = rankChromosomes();
  76
  77                 unsigned int size = probabilities.size();
  78                 unsigned int denominator = size * (size - 1);
  79
  80                 std::vector<_Chromosome> selected;
  81
  82                 /** Random value used to draw chromosome */
  83                 FitnessValueType random = 0;
  84
  85                 while (size > 0) {
  86                     bool found = false;
  87                     random = (rand() % size) / (double)denominator;
  88
  89                     for (ChromosomeMapIterator it = probabilities.begin(); it != probabilities.end(); it++) {
  90 //                     cout << "Random: " << random << " First: " << it->first << "\n";
  91                         if (random < it->first) {
  92                             found = true;
  93                             selected.push_back(it->second);
  94                             break;
  95                         }
  96                         // When NaN occur, just get first Chromosome
  97                         else if (it->first != it->first) {
  98                             selected.push_back(probabilities.begin()->second);
  99                             found = true;
 100                             break;
 101                         }
 102                     }
 103
 104                     if (found) {
 105                         size--;
 106                     }
 107                 }
 108
 109                 return Generation<_Chromosome>(selected);
 110             }
 111         public:
 112             LinearRankSelection(Generation<_Chromosome> _generation, GeneticFitness& _fitness) :
 113                 Selection<_Chromosome>(_generation, _fitness) {
 114             }
 115         };
 116 //     }
 117 }
 118
 119 #endif /* __SELECTION_LINEAR_RANK_H */