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