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;
33 * Type representing mapped Chromosome by its Rank value
35 typedef typename std::multimap<FitnessValueType, _Chromosome> ChromosomeMap;
37 /** Iterator for ChromosomeMap */
38 typedef typename ChromosomeMap::iterator ChromosomeMapIterator;
41 * Calculates Ranks for the Chromosomes
43 * @return multimap containing ranked Chromosomes, where key is the
46 ChromosomeMap rankChromosomes() {
47 const unsigned int generationSize = this->generation.size();
48 FitnessValueType fitness = 0;
50 ChromosomeMap generationFitness;
52 for (unsigned int i = 0; i < generationSize; i++) {
53 fitness = this->checkChromosomeFitness(this->generation[i]);
54 generationFitness.insert(std::make_pair(fitness, this->generation[i]));
57 // multimap is automatically sorted by key, so we don't need to
60 // p(i) = (rank(i) / N*(N-1)), where rankedGeneration[i] = p(i)
61 ChromosomeMap rankedGeneration;
63 unsigned int rank = generationSize;
64 double denominator = generationSize * (generationSize - 1);
66 for (ChromosomeMapIterator it = generationFitness.begin(); it != generationFitness.end(); it++) {
67 rankedGeneration.insert(std::make_pair(rank--/denominator, it->second));
70 return rankedGeneration;
74 * Invokes Selection calculations of the Linear Rank Selection
76 * @return new Generation of Chromosome's that passed the Selection
78 virtual Generation<_Chromosome> do_draw() {
79 ChromosomeMap probabilities = rankChromosomes();
81 unsigned int size = probabilities.size();
82 unsigned int denominator = size * (size - 1);
84 std::vector<_Chromosome> selected;
86 /** Random value used to draw chromosome */
87 FitnessValueType random = 0;
91 random = (rand() % size) / (double)denominator;
93 for (ChromosomeMapIterator it = probabilities.begin(); it != probabilities.end(); it++) {
94 if (random < it->first) {
96 selected.push_back(it->second);
99 // When NaN occur, just get first Chromosome
100 else if (it->first != it->first) {
101 selected.push_back(probabilities.begin()->second);
112 return Generation<_Chromosome>(selected);
115 LinearRankSelection(Generation<_Chromosome> _generation, GeneticFitness& _fitness) :
116 Selection<_Chromosome>(_generation, _fitness) {
122 #endif /* __SELECTION_LINEAR_RANK_H */