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 <algorithm>    // std::sort
   7 #include <map>
   8 #include <cstdlib>
   9 #include <iostream>
  10
  11 #include "chromosome.h"
  12 #include "selection.h"
  13
  14 using namespace std;
  15
  16 namespace genetic {
  17 //     namespace selection {
  18         template < typename _Chromosome >
  19         class Roulette : public Selection<_Chromosome> {
  20         public:
  21             typedef Selection<_Chromosome> BaseType;
  22             typedef typename BaseType::FitnessValueType FitnessValueType;
  23         protected:
  24             vector<FitnessValueType> calculateGenerationFitness(
  25                 Generation<_Chromosome> generation) {
  26                 vector<FitnessValueType> generationFitness;
  27
  28                 for (unsigned int i = 0; i < generation.get().size(); i++) {
  29                     generationFitness.push_back(this->checkChromosomeFitness(generation.get()[i]));
  30                 }
  31
  32                 return generationFitness;
  33             }
  34             multimap<FitnessValueType, _Chromosome> normalizeFitness(
  35                 vector<FitnessValueType> generationFitness,
  36                 unsigned int chromosomeSize) {
  37                 FitnessValueType min;
  38                 FitnessValueType max;
  39                 FitnessValueType offset;
  40                 multimap<FitnessValueType, _Chromosome> normalizedFitness;
  41
  42                 min = max = generationFitness[0];
  43                 offset = 0;
  44
  45                 for (unsigned int i = 0; i < generationFitness.size(); i++) {
  46                     if(generationFitness[i] < min) {
  47                         min = generationFitness[i];
  48                     }
  49
  50                     if(generationFitness[i] > max) {
  51                         max = generationFitness[i];
  52                     }
  53                 }
  54
  55                 offset = (max - min) / (chromosomeSize - 1) - min;
  56
  57                 for (unsigned int i = 0; i < generationFitness.size(); i++) {
  58                     normalizedFitness.insert(std::make_pair(generationFitness[i] + offset, this->generation.get()[i]));
  59                 }
  60
  61                 return normalizedFitness;
  62             }
  63
  64             /**
  65              * Spins the Roulette
  66              */
  67             Generation<_Chromosome> spinRoulette(
  68                 multimap<FitnessValueType, _Chromosome> normalizedFitness) {
  69
  70                 typedef typename std::multimap<FitnessValueType, _Chromosome>::iterator FitnessIterator;
  71
  72                 vector<_Chromosome> selected;
  73                 multimap<FitnessValueType, _Chromosome> probabilities;
  74
  75                 unsigned int size = this->generation.get().size();
  76                 const unsigned int power2N = 1 << this->generation.get()[0].get().size();
  77
  78                 /** Random value used to draw chromosome */
  79                 FitnessValueType random = 0;
  80
  81                 /** Position on the roulette wheele */
  82                 FitnessValueType position = 0;
  83
  84                 FitnessValueType fitnessSum = 0;
  85
  86                 // Calculate sum of normalized fitnesses, in order to calculate probabilities
  87                 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
  88                     fitnessSum += it->first;
  89                 }
  90
  91                 // Calculate probabilities for fitnesses
  92                 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
  93                     position += (it->first / fitnessSum * power2N);
  94                     probabilities.insert(std::make_pair(position, it->second));
  95                 }
  96
  97                 /*
  98                  * Spin the Roulette until we draw as many chromosomes as in the
  99                  * original generation.
 100                  */
 101                 while (size > 0) {
 102                     bool found = false;
 103                     random = (rand() % power2N);
 104
 105                     for (FitnessIterator it = probabilities.begin(); it != probabilities.end(); it++) {
 106                         if (random < it->first) {
 107                             found = true;
 108                             selected.push_back(it->second);
 109                             break;
 110                         }
 111                         // When NaN occur, just get first Chromosome
 112                         else if (it->first != it->first) {
 113                             selected.push_back(probabilities.begin()->second);
 114                             found = true;
 115                             break;
 116                         }
 117                     }
 118
 119                     if (found) {
 120                         size--;
 121                     }
 122                 }
 123                 return Generation<_Chromosome>(selected);
 124             }
 125
 126             /**
 127              * Draws random
 128              */
 129             Generation<_Chromosome> do_draw() {
 130                 multimap<FitnessValueType, _Chromosome> normalizedFitness;
 131
 132                 normalizedFitness = this->normalizeFitness(
 133                     this->calculateGenerationFitness(this->generation),
 134                     this->generation.get()[0].get().size()
 135                 );
 136
 137                 return spinRoulette(normalizedFitness);
 138             }
 139
 140         public:
 141             Roulette(Generation<_Chromosome> _generation, genetic::Fitness<_Chromosome>& _fitness) :
 142                 Selection<_Chromosome>(_generation, _fitness) {
 143                 this->generation = _generation;
 144                 this->fitness = _fitness;
 145             }
 146         };
 147 //     }
 148 }
 149
 150 #endif /* __SELECTION_ROULETTE_H */