--- /dev/null
+#ifndef __SELECTION_ROULETTE_H
+#define __SELECTION_ROULETTE_H
+
+#include <vector>
+#include <utility> // std::pair
+#include <map>
+#include <cstdlib>
+#include <iostream>
+
+#include "chromosome.h"
+#include "selection.h"
+
+using namespace std;
+
+namespace genetic {
+// namespace selection {
+ /**
+ * Selection class Roulette.
+ * Applies Selection on given Generation using Roulette method.
+ */
+ template < typename _Chromosome >
+ class RouletteSelection : public Selection<_Chromosome> {
+ public:
+ /**
+ * Parent Selection class
+ */
+ typedef Selection<_Chromosome> BaseType;
+
+ /**
+ * Value type returned by the Fitness function
+ */
+ 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;
+ unsigned int generationSize = generation.size();
+
+ for (unsigned int i = 0; i < generationSize; i++) {
+ generationFitness.push_back(this->checkChromosomeFitness(generation[i]));
+ }
+
+ return 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;
+
+ unsigned int fitnessSize = generationFitness.size();
+
+ /* 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 < fitnessSize; i++) {
+ if(generationFitness[i] < min) {
+ min = generationFitness[i];
+ }
+
+ if(generationFitness[i] > max) {
+ max = generationFitness[i];
+ }
+ }
+
+ offset = (max - min) / (chromosomeSize - 1) - min;
+
+ for (unsigned int i = 0; i < fitnessSize; i++) {
+ normalizedFitness.insert(std::make_pair(generationFitness[i] + offset, this->generation[i]));
+ }
+
+ return normalizedFitness;
+ }
+
+ /**
+ * 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(
+ multimap<FitnessValueType, _Chromosome> normalizedFitness) {
+
+ typedef typename std::multimap<FitnessValueType, _Chromosome>::iterator FitnessIterator;
+
+ vector<_Chromosome> selected;
+ multimap<FitnessValueType, _Chromosome> probabilities;
+
+ unsigned int size = this->generation.size();
+ const unsigned int power2N = 1 << this->generation[0].size();
+
+ /** Random value used to draw chromosome */
+ FitnessValueType random = 0;
+
+ /** Position on the roulette wheele */
+ FitnessValueType position = 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++) {
+ 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 > 0) {
+ bool found = false;
+ random = (rand() % power2N);
+
+ for (FitnessIterator it = probabilities.begin(); it != probabilities.end(); it++) {
+ 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--;
+ }
+ }
+ return Generation<_Chromosome>(selected);
+ }
+
+ /**
+ * Draws new Generation using Roulette method
+ *
+ * @return new Generation of Chromosome's that passed the Selection
+ */
+ Generation<_Chromosome> do_draw() {
+ multimap<FitnessValueType, _Chromosome> normalizedFitness;
+
+ normalizedFitness = this->normalizeFitness(
+ this->calculateGenerationFitness(this->generation),
+ this->generation[0].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
+ */
+ RouletteSelection(Generation<_Chromosome> _generation, genetic::Fitness<_Chromosome>& _fitness) :
+ Selection<_Chromosome>(_generation, _fitness) {
+ this->generation = _generation;
+ this->fitness = _fitness;
+ }
+ };
+// }
+}
+
+#endif /* __SELECTION_ROULETTE_H */
projects / genetic.git / blobdiff