include/selection/rouletteSelection.h

   1 #ifndef __SELECTION_ROULETTE_H
   2 #define __SELECTION_ROULETTE_H
   3
   4 #include <vector>
   5 #include <utility>      // std::pair
   6 #include <map>
   7
   8 #include "chromosome.h"
   9 #include "selection.h"
  10
  11 namespace genetic {
  12 //     namespace selection {
  13         /**
  14          * Selection class Roulette.
  15          * Applies Selection on given Generation using Roulette method.
  16          */
  17         template < typename _Chromosome >
  18         class RouletteSelection : public Selection<_Chromosome> {
  19         public:
  20             /**
  21              * Parent Selection class
  22              */
  23             typedef Selection<_Chromosome> BaseType;
  24
  25             /**
  26              * Value type returned by the Fitness function
  27              */
  28             typedef typename BaseType::FitnessValueType FitnessValueType;
  29         protected:
  30             /**
  31              * Method used for calculating fitness of each Chromosome in
  32              * Generation.
  33              *
  34              * @param generation Generation for which fitness will be calculated
  35              * @return vector containing fitness value of each Chromosome in
  36              *      Generation. Values are set in the same order as they are in
  37              *      the Generation.
  38              */
  39             std::vector<FitnessValueType> calculateGenerationFitness(
  40                 const Generation<_Chromosome>& generation) {
  41                 std::vector<FitnessValueType> generationFitness;
  42                 const unsigned int generationSize = generation.size();
  43
  44                 for (unsigned int i = 0; i < generationSize; i++) {
  45                     generationFitness.push_back(this->checkChromosomeFitness(generation[i]));
  46                 }
  47
  48                 return generationFitness;
  49             }
  50
  51             /**
  52              * Normalizes calculated fitness values of the generation.
  53              *
  54              * @param generationFitness fitness values of the generation
  55              * @param chromosomeSize number of Gene's in the Chromosome.
  56              *
  57              * @return multimap containing normalized Fitness as a key and its
  58              *      Chromosome as the value
  59              */
  60             std::multimap<FitnessValueType, _Chromosome> normalizeFitness(
  61                 const std::vector<FitnessValueType>& generationFitness,
  62                 unsigned int chromosomeSize) {
  63                 FitnessValueType min;
  64                 FitnessValueType max;
  65                 FitnessValueType offset;
  66
  67                 const unsigned int fitnessSize = generationFitness.size();
  68
  69                 /* we use multimap because it stores multiple values with the
  70                  * same key
  71                  */
  72                 std::multimap<FitnessValueType, _Chromosome> normalizedFitness;
  73
  74                 min = max = generationFitness[0];
  75                 offset = 0;
  76
  77                 for (unsigned int i = 0; i < fitnessSize; i++) {
  78                     if(generationFitness[i] < min) {
  79                         min = generationFitness[i];
  80                     }
  81
  82                     if(generationFitness[i] > max) {
  83                         max = generationFitness[i];
  84                     }
  85                 }
  86
  87                 offset = (max - min) / (chromosomeSize - 1) - min;
  88
  89                 for (unsigned int i = 0; i < fitnessSize; i++) {
  90                     normalizedFitness.insert(std::make_pair(generationFitness[i] + offset, this->generation[i]));
  91                 }
  92
  93                 return normalizedFitness;
  94             }
  95
  96             /**
  97              * Spins the Roulette
  98              *
  99              * @param normalizedFitness multimap containing normalized Fitness
 100              *      as a key and its Chromosome as the value
 101              * @return new Generation of Chromosome's that passed the Selection
 102              */
 103             Generation<_Chromosome> spinRoulette(
 104                 const std::multimap<FitnessValueType, _Chromosome>& normalizedFitness) {
 105
 106                 typedef typename std::multimap<FitnessValueType, _Chromosome>::iterator FitnessIterator;
 107
 108                 std::vector<_Chromosome> selected;
 109                 std::multimap<FitnessValueType, _Chromosome> probabilities;
 110
 111                 unsigned int size = this->generation.size();
 112                 const unsigned int power2N = 1 << this->generation[0].size();
 113
 114                 /** Random value used to draw chromosome */
 115                 FitnessValueType random = 0;
 116
 117                 /** Position on the roulette wheele */
 118                 FitnessValueType position = 0;
 119
 120                 FitnessValueType fitnessSum = 0;
 121
 122                 // Calculate sum of normalized fitnesses, in order to calculate probabilities
 123                 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
 124                     fitnessSum += it->first;
 125                 }
 126
 127                 // Calculate probabilities for fitnesses
 128                 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
 129                     position += (it->first / fitnessSum * power2N);
 130                     probabilities.insert(std::make_pair(position, it->second));
 131                 }
 132
 133                 /*
 134                  * Spin the Roulette until we draw as many chromosomes as in the
 135                  * original generation.
 136                  */
 137                 while (size > 0) {
 138                     bool found = false;
 139                     random = (rand() % power2N);
 140
 141                     for (FitnessIterator it = probabilities.begin(); it != probabilities.end(); it++) {
 142                         if (random < it->first) {
 143                             found = true;
 144                             selected.push_back(it->second);
 145                             break;
 146                         }
 147                         // When NaN occur, just get first Chromosome
 148                         else if (it->first != it->first) {
 149                             selected.push_back(probabilities.begin()->second);
 150                             found = true;
 151                             break;
 152                         }
 153                     }
 154
 155                     if (found) {
 156                         size--;
 157                     }
 158                 }
 159                 return Generation<_Chromosome>(selected);
 160             }
 161
 162             /**
 163              * Draws new Generation using Roulette method
 164              *
 165              * @return new Generation of Chromosome's that passed the Selection
 166              */
 167             Generation<_Chromosome> do_draw() {
 168                 std::multimap<FitnessValueType, _Chromosome> normalizedFitness;
 169
 170                 normalizedFitness = this->normalizeFitness(
 171                     this->calculateGenerationFitness(this->generation),
 172                     this->generation[0].size()
 173                 );
 174
 175                 return spinRoulette(normalizedFitness);
 176             }
 177
 178         public:
 179             /**
 180              * Class constructor. Initializes class with values.
 181              *
 182              * @param _generation Generation that will be checked against this
 183              *      Selection
 184              * @param _fitness Fitness method to calculate fitness of Chromosomes
 185              */
 186             RouletteSelection(const Generation<_Chromosome>& _generation, genetic::Fitness<_Chromosome>& _fitness) :
 187                 Selection<_Chromosome>(_generation, _fitness) {
 188             }
 189         };
 190 //     }
 191 }
 192
 193 #endif /* __SELECTION_ROULETTE_H */