From 12625bb2d19ee89abacc2456bff57dc22aa3a526 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Rafa=C5=82=20D=C5=82ugo=C5=82=C4=99cki?= Date: Sun, 29 Mar 2015 11:05:09 +0200 Subject: [PATCH] Finished Roulette Selection. --- Makefile.am | 1 + src/chromosome.h | 3 +- src/fitness/fitness.h | 38 +++++++++++ src/fitness/wsti.h | 31 +++++---- src/generation.h | 5 ++ src/generator/generation.h | 2 +- src/main.cpp | 24 ++++++- src/selection/roulette.h | 136 +++++++++++++++++++++++++++++++++++++ src/selection/selection.h | 40 +++++++++++ 9 files changed, 261 insertions(+), 19 deletions(-) create mode 100644 src/fitness/fitness.h create mode 100644 src/selection/roulette.h create mode 100644 src/selection/selection.h diff --git a/Makefile.am b/Makefile.am index 45fb872..c543161 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,5 +1,6 @@ AUTOMAKE_OPTIONS = gnu subdir-objects ACLOCAL_AMFLAGS = ${ACLOCAL_FLAGS} +AM_CXXFLAGS=-std=c++11 EXTRA_DIST = \ config.rpath diff --git a/src/chromosome.h b/src/chromosome.h index ebed835..e197f16 100644 --- a/src/chromosome.h +++ b/src/chromosome.h @@ -36,7 +36,8 @@ namespace genetic { : genes(chromosome.get()) { } - Chromosome& operator=(const Chromosome&){ + Chromosome& operator=(const Chromosome& chromosome){ + this->genes = chromosome.get(); return *this; } diff --git a/src/fitness/fitness.h b/src/fitness/fitness.h new file mode 100644 index 0000000..14b6487 --- /dev/null +++ b/src/fitness/fitness.h @@ -0,0 +1,38 @@ +#ifndef __FITNESS_FITNESS_H +#define __FITNESS_FITNESS_H + +#include "../chromosome.h" + +namespace genetic { + /** + * Base Fitness template class. It should be a base class for any custom + * fitness functions. + */ + template < typename _Chromosome, typename _Value = double > + class Fitness { + template friend class Selection ; + public: + typedef typename _Chromosome::GeneType GeneType; + typedef _Value ValueType; + protected: + _Chromosome chromosome; + + /* + * Some calculations here... + */ + virtual _Value do_calculate() = 0; + + public: + Fitness() {} + + Fitness(_Chromosome& _chromosome) + : chromosome(_chromosome.get()) { + } + + _Value calculate() { + return this->do_calculate(); + } + }; +} + +#endif /* __FITNESS_FITNESS_H */ diff --git a/src/fitness/wsti.h b/src/fitness/wsti.h index b93439f..fa303b0 100644 --- a/src/fitness/wsti.h +++ b/src/fitness/wsti.h @@ -5,43 +5,46 @@ #include "../gene.h" +#include "fitness.h" + using namespace std; namespace genetic { /** * Just an example Fitness function based on WSTI version. */ - template < typename _Chromosome > - class WSTI { + template + class WSTI : public Fitness<_Chromosome, _Value> { protected: - _Chromosome chromosome; - float span_start; float span_end; - double fenotype() { + _Value fenotype() { int _fenotype = 0; int ratio = 1; - for (unsigned int i = 0; i < chromosome.get().size(); i++) { - _fenotype = _fenotype + chromosome.get()[i].get() * ratio; + for (unsigned int i = 0; i < this->chromosome.get().size(); i++) { + _fenotype = _fenotype + this->chromosome.get()[i].get() * ratio; ratio = ratio * 2; } return _fenotype; } - double calculateFenotype() { + _Value calculateFenotype() { const unsigned int power2N = 1 << this->chromosome.get().size(); return span_start + (span_end - span_start) * this->fenotype() / power2N; } - public: - WSTI(_Chromosome& _chromosome, float start, float end) - : chromosome(_chromosome.get()), span_start(start), span_end(end) { - } - double calculate() { - double fenotype = this->calculateFenotype(); + _Value do_calculate() { + _Value fenotype = this->calculateFenotype(); return (exp(fenotype) * sin(3.1415 * fenotype) + 1) / fenotype; } + public: + WSTI(float start, float end) + : span_start(start), span_end(end) { + } + WSTI(_Chromosome& _chromosome, float start, float end) + : Fitness<_Chromosome>(_chromosome), span_start(start), span_end(end) { + } }; } diff --git a/src/generation.h b/src/generation.h index d36cd90..39b9577 100644 --- a/src/generation.h +++ b/src/generation.h @@ -32,6 +32,11 @@ namespace genetic { vector<_Chromosome> get() const { return this->chromosomes; } + + Generation& operator=(const Generation& generation){ + this->chromosomes = generation.get(); + return *this; + } }; } diff --git a/src/generator/generation.h b/src/generator/generation.h index a561d8e..a51e4b3 100644 --- a/src/generator/generation.h +++ b/src/generator/generation.h @@ -35,7 +35,7 @@ namespace genetic { public: /** - * Constructor. Initializes required variables and constans + * Constructor. Initializes required variables and constants * * @param generationSize Indicates size of the generation * @param generationSize Indicates size of the chromosome diff --git a/src/main.cpp b/src/main.cpp index 3eaea51..9388101 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -6,6 +6,8 @@ #include "generation.h" #include "generator/generation.h" +#include "selection/roulette.h" + #include "fitness/wsti.h" using namespace std; @@ -17,14 +19,30 @@ int main() { const int chromosomeSize = 11; const int generationSize = 20; + WSTI<_Chromosome> fitness(0.5, 2.5); generator::Generation<_Chromosome> generationGenerator(generationSize, chromosomeSize); Generation<_Chromosome> generation = generationGenerator.breed(); - for (unsigned int i = 0; i < generationSize; i++) { - WSTI<_Chromosome> fitness(generation.get()[i], 0.5, 2.5); + cout << "Generation:\n"; + for (unsigned int i = 0; i < generation.get().size(); i++) { + cout << "# "; + for (unsigned int j = 0; j < generation.get()[i].get().size(); j++) { + cout << generation.get()[i].get()[j].get(); + } + cout << "\n"; + } + + Roulette<_Chromosome> roulette(generation, fitness); + Generation<_Chromosome> newGeneration = roulette.draw(); - cout << "Fitness is equal to: " << fitness.calculate() << "\n"; + cout << "New Generation:\n"; + for (unsigned int i = 0; i < newGeneration.get().size(); i++) { + cout << "# "; + for (unsigned int j = 0; j < newGeneration.get()[i].get().size(); j++) { + cout << newGeneration.get()[i].get()[j].get(); + } + cout << "\n"; } return 0; diff --git a/src/selection/roulette.h b/src/selection/roulette.h new file mode 100644 index 0000000..93f1514 --- /dev/null +++ b/src/selection/roulette.h @@ -0,0 +1,136 @@ +#ifndef __SELECTION_ROULETTE_H +#define __SELECTION_ROULETTE_H + +#include +#include // std::pair +#include // std::sort +#include +#include +#include + +#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 calculateGenerationFitness( + Generation<_Chromosome> generation) { + vector generationFitness; + + for (unsigned int i = 0; i < generation.get().size(); i++) { + generationFitness.push_back(this->checkChromosomeFitness(generation.get()[i])); + } + + return generationFitness; + } + map normalizeFitness( + vector generationFitness) { + FitnessValueType min; + FitnessValueType max; + FitnessValueType offset; + map 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 normalizedFitness) { + + typedef typename std::map::iterator FitnessIterator; + + vector<_Chromosome> selected; + map 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 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 */ diff --git a/src/selection/selection.h b/src/selection/selection.h new file mode 100644 index 0000000..f519ca1 --- /dev/null +++ b/src/selection/selection.h @@ -0,0 +1,40 @@ +#ifndef __SELECTION_SELECTION_H +#define __SELECTION_SELECTION_H + +#include "chromosome.h" +#include "generation.h" +#include "../fitness/fitness.h" + +using namespace std; + +namespace genetic { +// namespace selection { + template < typename _Chromosome > + class Selection { + public: + typedef Fitness<_Chromosome> GeneticFitness; + typedef typename GeneticFitness::ValueType FitnessValueType; + protected: + Generation<_Chromosome> generation; + GeneticFitness& fitness; + + FitnessValueType checkChromosomeFitness(_Chromosome chromosome) { + this->fitness.chromosome = chromosome; + return fitness.calculate(); + } + + virtual Generation<_Chromosome> do_draw() = 0; + + public: + Selection(Generation<_Chromosome> _generation, GeneticFitness& _fitness) : + generation(_generation), fitness(_fitness) { + } + + Generation<_Chromosome> draw() { + return this->do_draw(); + } + }; +// } +} + +#endif /* __SELECTION_SELECTION_H */ -- 2.30.2