+#ifndef __SELECTION_ROULETTE_H
+#define __SELECTION_ROULETTE_H
+
+#include <vector>
+#include <utility> // std::pair
+#include <algorithm> // std::sort
+#include <map>
+#include <cstdlib>
+#include <iostream>
+
+#include "chromosome.h"
+#include "selection.h"
+
+using namespace std;
+
+namespace genetic {
+// namespace selection {
+ template < typename _Chromosome >
+ class Roulette : public Selection<_Chromosome> {
+ public:
+ typedef Selection<_Chromosome> BaseType;
+ typedef typename BaseType::FitnessValueType FitnessValueType;
+ protected:
+ vector<FitnessValueType> calculateGenerationFitness(
+ Generation<_Chromosome> generation) {
+ vector<FitnessValueType> generationFitness;
+
+ for (unsigned int i = 0; i < generation.get().size(); i++) {
+ generationFitness.push_back(this->checkChromosomeFitness(generation.get()[i]));
+ }
+
+ return generationFitness;
+ }
+ map<FitnessValueType, _Chromosome> normalizeFitness(
+ vector<FitnessValueType> generationFitness) {
+ FitnessValueType min;
+ FitnessValueType max;
+ FitnessValueType offset;
+ map<FitnessValueType, _Chromosome> normalizedFitness;
+
+ min = max = generationFitness[0];
+
+ for (unsigned int i = 0; i < generationFitness.size(); i++) {
+ if(generationFitness[i] < min) {
+ min = generationFitness[i];
+ }
+
+ if(generationFitness[i] > max) {
+ max = generationFitness[i];
+ }
+ }
+
+ offset = (max - min) / (generationFitness.size() - 1) - min;
+
+ for (unsigned int i = 0; i < generationFitness.size(); i++) {
+ normalizedFitness[generationFitness[i] + offset] = this->generation.get()[i];
+ }
+
+ return normalizedFitness;
+ }
+
+ /**
+ * Spins the Roulette
+ */
+ Generation<_Chromosome> spinRoulette(
+ map<FitnessValueType, _Chromosome> normalizedFitness) {
+
+ typedef typename std::map<FitnessValueType, _Chromosome>::iterator FitnessIterator;
+
+ vector<_Chromosome> selected;
+ map<FitnessValueType, _Chromosome> probabilities;
+
+ unsigned int size = this->generation.get().size();
+ double random = 0;
+
+ FitnessValueType fitnessSum = 0;
+
+ // Calculate sum of normalized fitnesses, in order to calculate probabilities
+ for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
+ fitnessSum += it->first;
+ }
+
+ // Calculate probabilities for fitnesses
+ for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
+ probabilities[it->first / fitnessSum] = it->second;
+ }
+
+ /*
+ * Spin the Roulette until we draw as many chromosomes as in the
+ * original generation.
+ */
+ while (size) {
+ bool found = false;
+ random = (rand() % 10000) / 100000.0;
+
+ for (FitnessIterator it = probabilities.begin(); it != probabilities.end(); it++) {
+ if (it->first > random) {
+ found = true;
+ selected.push_back(it->second);
+ break;
+ }
+ }
+ if (found) {
+ size--;
+ }
+ }
+ return Generation<_Chromosome>(selected);
+ }
+
+ /**
+ * Draws random
+ */
+ Generation<_Chromosome> do_draw() {
+ map<FitnessValueType, _Chromosome> normalizedFitness;
+
+ normalizedFitness = this->normalizeFitness(
+ this->calculateGenerationFitness(this->generation)
+ );
+
+ return spinRoulette(normalizedFitness);
+ }
+
+ public:
+ Roulette(Generation<_Chromosome> _generation, genetic::Fitness<_Chromosome>& _fitness) :
+ Selection<_Chromosome>(_generation, _fitness) {
+ this->generation = _generation;
+ this->fitness = _fitness;
+
+ time_t t;
+ srand((unsigned)time(&t));
+ }
+ };
+// }
+}
+
+#endif /* __SELECTION_ROULETTE_H */