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