Add documentation for Algorithm, Condition and Roulette.

[genetic.git] / src / selection / roulette.h

diff --git a/src/selection/roulette.h b/src/selection/roulette.h
index 93f1514ab05c59a64ebc8d33f299242edee82eff..7f2d2401cd9f58c00e8a2f149099183d429d4e3b 100644 (file)
--- a/src/selection/roulette.h
+++ b/src/selection/roulette.h
@@ -3,7 +3,6 @@
 
 #include <vector>
 #include <utility>      // std::pair
-#include <algorithm>    // std::sort
 #include <map>
 #include <cstdlib>
 #include <iostream>
@@ -15,12 +14,25 @@ using namespace std;
 
 namespace genetic {
 //     namespace selection {
+        /**
+         * Selection class Roulette.
+         * Applies Selection on given Generation using Roulette method.
+         */
         template < typename _Chromosome >
         class Roulette : public Selection<_Chromosome> {
         public:
             typedef Selection<_Chromosome> BaseType;
             typedef typename BaseType::FitnessValueType FitnessValueType;
         protected:
+            /**
+             * Method used for calculating fitness of each Chromosome in
+             * Generation.
+             *
+             * @param generation Generation for which fitness will be calculated
+             * @return vector containing fitness value of each Chromosome in
+             *      Generation. Values are set in the same order as they are in
+             *      the Generation.
+             */
             vector<FitnessValueType> calculateGenerationFitness(
                 Generation<_Chromosome> generation) {
                 vector<FitnessValueType> generationFitness;
@@ -31,14 +43,30 @@ namespace genetic {
 
                 return generationFitness;
             }
-            map<FitnessValueType, _Chromosome> normalizeFitness(
-                vector<FitnessValueType> generationFitness) {
+
+            /**
+             * Normalizes calculated fitness values of the generation.
+             *
+             * @param generationFitness fitness values of the generation
+             * @param chromosomeSize number of Gene's in the Chromosome.
+             *
+             * @return multimap containing normalized Fitness as a key and its
+             *      Chromosome as the value
+             */
+            multimap<FitnessValueType, _Chromosome> normalizeFitness(
+                vector<FitnessValueType> generationFitness,
+                unsigned int chromosomeSize) {
                 FitnessValueType min;
                 FitnessValueType max;
                 FitnessValueType offset;
-                map<FitnessValueType, _Chromosome> normalizedFitness;
+
+                /* we use multimap because it stores multiple values with the
+                 * same key
+                 */
+                multimap<FitnessValueType, _Chromosome> normalizedFitness;
 
                 min = max = generationFitness[0];
+                offset = 0;
 
                 for (unsigned int i = 0; i < generationFitness.size(); i++) {
                     if(generationFitness[i] < min) {
@@ -50,10 +78,10 @@ namespace genetic {
                     }
                 }
 
-                offset = (max - min) / (generationFitness.size() - 1) - min;
+                offset = (max - min) / (chromosomeSize - 1) - min;
 
                 for (unsigned int i = 0; i < generationFitness.size(); i++) {
-                    normalizedFitness[generationFitness[i] + offset] = this->generation.get()[i];
+                    normalizedFitness.insert(std::make_pair(generationFitness[i] + offset, this->generation.get()[i]));
                 }
 
                 return normalizedFitness;
@@ -61,17 +89,27 @@ namespace genetic {
 
             /**
              * Spins the Roulette
+             *
+             * @param normalizedFitness multimap containing normalized Fitness
+             *      as a key and its Chromosome as the value
+             * @return new Generation of Chromosome's that passed the selection
              */
             Generation<_Chromosome> spinRoulette(
-                map<FitnessValueType, _Chromosome> normalizedFitness) {
+                multimap<FitnessValueType, _Chromosome> normalizedFitness) {
 
-                typedef typename std::map<FitnessValueType, _Chromosome>::iterator FitnessIterator;
+                typedef typename std::multimap<FitnessValueType, _Chromosome>::iterator FitnessIterator;
 
                 vector<_Chromosome> selected;
-                map<FitnessValueType, _Chromosome> probabilities;
+                multimap<FitnessValueType, _Chromosome> probabilities;
 
                 unsigned int size = this->generation.get().size();
-                double random = 0;
+                const unsigned int power2N = 1 << this->generation.get()[0].get().size();
+
+                /** Random value used to draw chromosome */
+                FitnessValueType random = 0;
+
+                /** Position on the roulette wheele */
+                FitnessValueType position = 0;
 
                 FitnessValueType fitnessSum = 0;
 
@@ -82,24 +120,32 @@ namespace genetic {
 
                 // Calculate probabilities for fitnesses
                 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
-                    probabilities[it->first / fitnessSum] = it->second;
+                    position += (it->first / fitnessSum * power2N);
+                    probabilities.insert(std::make_pair(position, it->second));
                 }
 
                 /*
                  * Spin the Roulette until we draw as many chromosomes as in the
                  * original generation.
                  */
-                while (size) {
+                while (size > 0) {
                     bool found = false;
-                    random = (rand() % 10000) / 100000.0;
+                    random = (rand() % power2N);
 
                     for (FitnessIterator it = probabilities.begin(); it != probabilities.end(); it++) {
-                        if (it->first > random) {
+                        if (random < it->first) {
                             found = true;
                             selected.push_back(it->second);
                             break;
                         }
+                        // When NaN occur, just get first Chromosome
+                        else if (it->first != it->first) {
+                            selected.push_back(probabilities.begin()->second);
+                            found = true;
+                            break;
+                        }
                     }
+
                     if (found) {
                         size--;
                     }
@@ -108,26 +154,31 @@ namespace genetic {
             }
 
             /**
-             * Draws random 
+             * Draws new Generation using Roulette method
              */
             Generation<_Chromosome> do_draw() {
-                map<FitnessValueType, _Chromosome> normalizedFitness;
+                multimap<FitnessValueType, _Chromosome> normalizedFitness;
 
                 normalizedFitness = this->normalizeFitness(
-                    this->calculateGenerationFitness(this->generation)
+                    this->calculateGenerationFitness(this->generation),
+                    this->generation.get()[0].get().size()
                 );
 
                 return spinRoulette(normalizedFitness);
             }
 
         public:
+            /**
+             * Class constructor. Initializes class with values.
+             *
+             * @param _generation Generation that will be checked against this
+             *      Selection
+             * @param _fitness Fitness method to calculate fitness of Chromosomes
+             */
             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));
             }
         };
 //     }