1 #ifndef __SELECTION_ROULETTE_H
2 #define __SELECTION_ROULETTE_H
5 #include <utility> // std::pair
10 #include "chromosome.h"
11 #include "selection.h"
16 // namespace selection {
18 * Selection class Roulette.
19 * Applies Selection on given Generation using Roulette method.
21 template < typename _Chromosome >
22 class RouletteSelection : public Selection<_Chromosome> {
25 * Parent Selection class
27 typedef Selection<_Chromosome> BaseType;
30 * Value type returned by the Fitness function
32 typedef typename BaseType::FitnessValueType FitnessValueType;
35 * Method used for calculating fitness of each Chromosome in
38 * @param generation Generation for which fitness will be calculated
39 * @return vector containing fitness value of each Chromosome in
40 * Generation. Values are set in the same order as they are in
43 vector<FitnessValueType> calculateGenerationFitness(
44 Generation<_Chromosome> generation) {
45 vector<FitnessValueType> generationFitness;
46 unsigned int generationSize = generation.size();
48 for (unsigned int i = 0; i < generationSize; i++) {
49 generationFitness.push_back(this->checkChromosomeFitness(generation[i]));
52 return generationFitness;
56 * Normalizes calculated fitness values of the generation.
58 * @param generationFitness fitness values of the generation
59 * @param chromosomeSize number of Gene's in the Chromosome.
61 * @return multimap containing normalized Fitness as a key and its
62 * Chromosome as the value
64 multimap<FitnessValueType, _Chromosome> normalizeFitness(
65 vector<FitnessValueType> generationFitness,
66 unsigned int chromosomeSize) {
69 FitnessValueType offset;
71 unsigned int fitnessSize = generationFitness.size();
73 /* we use multimap because it stores multiple values with the
76 multimap<FitnessValueType, _Chromosome> normalizedFitness;
78 min = max = generationFitness[0];
81 for (unsigned int i = 0; i < fitnessSize; i++) {
82 if(generationFitness[i] < min) {
83 min = generationFitness[i];
86 if(generationFitness[i] > max) {
87 max = generationFitness[i];
91 offset = (max - min) / (chromosomeSize - 1) - min;
93 for (unsigned int i = 0; i < fitnessSize; i++) {
94 normalizedFitness.insert(std::make_pair(generationFitness[i] + offset, this->generation[i]));
97 return normalizedFitness;
103 * @param normalizedFitness multimap containing normalized Fitness
104 * as a key and its Chromosome as the value
105 * @return new Generation of Chromosome's that passed the Selection
107 Generation<_Chromosome> spinRoulette(
108 multimap<FitnessValueType, _Chromosome> normalizedFitness) {
110 typedef typename std::multimap<FitnessValueType, _Chromosome>::iterator FitnessIterator;
112 vector<_Chromosome> selected;
113 multimap<FitnessValueType, _Chromosome> probabilities;
115 unsigned int size = this->generation.size();
116 const unsigned int power2N = 1 << this->generation[0].size();
118 /** Random value used to draw chromosome */
119 FitnessValueType random = 0;
121 /** Position on the roulette wheele */
122 FitnessValueType position = 0;
124 FitnessValueType fitnessSum = 0;
126 // Calculate sum of normalized fitnesses, in order to calculate probabilities
127 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
128 fitnessSum += it->first;
131 // Calculate probabilities for fitnesses
132 for (FitnessIterator it = normalizedFitness.begin(); it != normalizedFitness.end(); it++) {
133 position += (it->first / fitnessSum * power2N);
134 probabilities.insert(std::make_pair(position, it->second));
138 * Spin the Roulette until we draw as many chromosomes as in the
139 * original generation.
143 random = (rand() % power2N);
145 for (FitnessIterator it = probabilities.begin(); it != probabilities.end(); it++) {
146 if (random < it->first) {
148 selected.push_back(it->second);
151 // When NaN occur, just get first Chromosome
152 else if (it->first != it->first) {
153 selected.push_back(probabilities.begin()->second);
163 return Generation<_Chromosome>(selected);
167 * Draws new Generation using Roulette method
169 * @return new Generation of Chromosome's that passed the Selection
171 Generation<_Chromosome> do_draw() {
172 multimap<FitnessValueType, _Chromosome> normalizedFitness;
174 normalizedFitness = this->normalizeFitness(
175 this->calculateGenerationFitness(this->generation),
176 this->generation[0].size()
179 return spinRoulette(normalizedFitness);
184 * Class constructor. Initializes class with values.
186 * @param _generation Generation that will be checked against this
188 * @param _fitness Fitness method to calculate fitness of Chromosomes
190 RouletteSelection(Generation<_Chromosome> _generation, genetic::Fitness<_Chromosome>& _fitness) :
191 Selection<_Chromosome>(_generation, _fitness) {
192 this->generation = _generation;
193 this->fitness = _fitness;
199 #endif /* __SELECTION_ROULETTE_H */