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