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             map<FitnessValueType, _Chromosome> normalizeFitness(
  35                 vector<FitnessValueType> generationFitness) {
  36                 FitnessValueType min;
  37                 FitnessValueType max;
  38                 FitnessValueType offset;
  39                 map<FitnessValueType, _Chromosome> normalizedFitness;
  40
  41                 min = max = generationFitness[0];
  42
  43                 for (unsigned int i = 0; i < generationFitness.size(); i++) {
  44                     if(generationFitness[i] < min) {
  45                         min = generationFitness[i];
  46                     }
  47
  48                     if(generationFitness[i] > max) {
  49                         max = generationFitness[i];
  50                     }
  51                 }
  52
  53                 offset = (max - min) / (generationFitness.size() - 1) - min;
  54
  55                 for (unsigned int i = 0; i < generationFitness.size(); i++) {
  56                     normalizedFitness[generationFitness[i] + offset] = this->generation.get()[i];
  57                 }
  58
  59                 return normalizedFitness;
  60             }
  61
  62             /**
  63              * Spins the Roulette
  64              */
  65             Generation<_Chromosome> spinRoulette(
  66                 map<FitnessValueType, _Chromosome> normalizedFitness) {
  67
  68                 typedef typename std::map<FitnessValueType, _Chromosome>::iterator FitnessIterator;
  69
  70                 vector<_Chromosome> selected;
  71                 map<FitnessValueType, _Chromosome> probabilities;
  72
  73                 unsigned int size = this->generation.get().size();
  74                 double random = 0;
  75
  76                 FitnessValueType fitnessSum = 0;
  77
  78                 // Calculate sum of normalized fitnesses, in order to calculate probabilities
  79                 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
  80                     fitnessSum += it->first;
  81                 }
  82
  83                 // Calculate probabilities for fitnesses
  84                 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
  85                     probabilities[it->first / fitnessSum] = it->second;
  86                 }
  87
  88                 /*
  89                  * Spin the Roulette until we draw as many chromosomes as in the
  90                  * original generation.
  91                  */
  92                 while (size) {
  93                     bool found = false;
  94                     random = (rand() % 10000) / 100000.0;
  95
  96                     for (FitnessIterator it = probabilities.begin(); it != probabilities.end(); it++) {
  97                         if (it->first > random) {
  98                             found = true;
  99                             selected.push_back(it->second);
 100                             break;
 101                         }
 102                     }
 103                     if (found) {
 104                         size--;
 105                     }
 106                 }
 107                 return Generation<_Chromosome>(selected);
 108             }
 109
 110             /**
 111              * Draws random
 112              */
 113             Generation<_Chromosome> do_draw() {
 114                 map<FitnessValueType, _Chromosome> normalizedFitness;
 115
 116                 normalizedFitness = this->normalizeFitness(
 117                     this->calculateGenerationFitness(this->generation)
 118                 );
 119
 120                 return spinRoulette(normalizedFitness);
 121             }
 122
 123         public:
 124             Roulette(Generation<_Chromosome> _generation, genetic::Fitness<_Chromosome>& _fitness) :
 125                 Selection<_Chromosome>(_generation, _fitness) {
 126                 this->generation = _generation;
 127                 this->fitness = _fitness;
 128
 129                 time_t t;
 130                 srand((unsigned)time(&t));
 131             }
 132         };
 133 //     }
 134 }
 135
 136 #endif /* __SELECTION_ROULETTE_H */