1 #ifndef __SELECTION_LINEAR_RANK_H
2 #define __SELECTION_LINEAR_RANK_H
6 #include "chromosome.h"
7 #include "generation.h"
8 #include "fitness/fitness.h"
9 #include "selection/selection.h"
14 // namespace selection {
16 * Linear Rank Selection class.
19 template < typename _Chromosome >
20 class LinearRankSelection : public Selection<_Chromosome> {
23 * Type representing Fitness function
25 typedef Fitness<_Chromosome> GeneticFitness;
28 * Value type returned by the Fitness function
30 typedef typename GeneticFitness::ValueType FitnessValueType;
32 typedef typename std::multimap<FitnessValueType, _Chromosome> ChromosomeMap;
33 typedef typename ChromosomeMap::iterator ChromosomeMapIterator;
36 * Calculates Ranks for the Chromosomes
38 * @return multimap containing ranked Chromosomes, where key is the
41 ChromosomeMap rankChromosomes() {
42 const unsigned int generationSize = this->generation.size();
43 FitnessValueType fitness = 0;
45 ChromosomeMap generationFitness;
47 for (unsigned int i = 0; i < generationSize; i++) {
48 fitness = this->checkChromosomeFitness(this->generation[i]);
49 generationFitness.insert(std::make_pair(fitness, this->generation[i]));
52 // multimap is automatically sorted by key, so we don't need to
55 // p(i) = (rank(i) / N*(N-1)), where rankedGeneration[i] = p(i)
56 ChromosomeMap rankedGeneration;
58 unsigned int rank = generationSize;
59 double denominator = generationSize * (generationSize - 1);
61 for (ChromosomeMapIterator it = generationFitness.begin(); it != generationFitness.end(); it++) {
62 rankedGeneration.insert(std::make_pair(rank--/denominator, it->second));
65 return rankedGeneration;
69 * Selection calculations should be done here.
71 * @return new Generation of Chromosome's that passed the Selection
73 virtual Generation<_Chromosome> do_draw() {
74 ChromosomeMap probabilities = rankChromosomes();
76 unsigned int size = probabilities.size();
77 unsigned int denominator = size * (size - 1);
79 std::vector<_Chromosome> selected;
81 /** Random value used to draw chromosome */
82 FitnessValueType random = 0;
86 random = (rand() % size) / (double)denominator;
88 for (ChromosomeMapIterator it = probabilities.begin(); it != probabilities.end(); it++) {
89 if (random < it->first) {
91 selected.push_back(it->second);
94 // When NaN occur, just get first Chromosome
95 else if (it->first != it->first) {
96 selected.push_back(probabilities.begin()->second);
107 return Generation<_Chromosome>(selected);
110 LinearRankSelection(Generation<_Chromosome> _generation, GeneticFitness& _fitness) :
111 Selection<_Chromosome>(_generation, _fitness) {
117 #endif /* __SELECTION_LINEAR_RANK_H */