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