Added classes: Algorithm, Crossover, Mutation. Fixed Roulette.

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

diff --git a/src/selection/roulette.h b/src/selection/roulette.h
index 93f1514ab05c59a64ebc8d33f299242edee82eff..a4f1fd289ad8e2b2e58c4dcbef44e00e8eb87f6f 100644 (file)
--- a/src/selection/roulette.h
+++ b/src/selection/roulette.h
@@ -31,14 +31,16 @@ namespace genetic {
 
                 return generationFitness;
             }
-            map<FitnessValueType, _Chromosome> normalizeFitness(
-                vector<FitnessValueType> generationFitness) {
+            multimap<FitnessValueType, _Chromosome> normalizeFitness(
+                vector<FitnessValueType> generationFitness,
+                unsigned int chromosomeSize) {
                 FitnessValueType min;
                 FitnessValueType max;
                 FitnessValueType offset;
-                map<FitnessValueType, _Chromosome> normalizedFitness;
+                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 +52,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;
@@ -63,15 +65,21 @@ namespace genetic {
              * Spins the Roulette
              */
             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 +90,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:
+                        else if (it->first != it->first) {
+                            selected.push_back(probabilities.begin()->second);
+                            found = true;
+                            break;
+                        }
                     }
+
                     if (found) {
                         size--;
                     }
@@ -111,10 +127,11 @@ namespace genetic {
              * Draws random 
              */
             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);
@@ -125,9 +142,6 @@ namespace genetic {
                 Selection<_Chromosome>(_generation, _fitness) {
                 this->generation = _generation;
                 this->fitness = _fitness;
-
-                time_t t;
-                srand((unsigned)time(&t));
             }
         };
 //     }