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