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 // cout << "rank: " << rank << " denominator: " << denominator << " res: " << (rank-1)/denominator << "\n";
63 rankedGeneration.insert(std::make_pair(rank--/denominator, it->second));
66 return rankedGeneration;
70 * Selection calculations should be done here.
72 * @return new Generation of Chromosome's that passed the Selection
74 virtual Generation<_Chromosome> do_draw() {
75 ChromosomeMap probabilities = rankChromosomes();
77 unsigned int size = probabilities.size();
78 unsigned int denominator = size * (size - 1);
80 std::vector<_Chromosome> selected;
82 /** Random value used to draw chromosome */
83 FitnessValueType random = 0;
87 random = (rand() % size) / (double)denominator;
89 for (ChromosomeMapIterator it = probabilities.begin(); it != probabilities.end(); it++) {
90 // cout << "Random: " << random << " First: " << it->first << "\n";
91 if (random < it->first) {
93 selected.push_back(it->second);
96 // When NaN occur, just get first Chromosome
97 else if (it->first != it->first) {
98 selected.push_back(probabilities.begin()->second);
109 return Generation<_Chromosome>(selected);
112 LinearRankSelection(Generation<_Chromosome> _generation, GeneticFitness& _fitness) :
113 Selection<_Chromosome>(_generation, _fitness) {
119 #endif /* __SELECTION_LINEAR_RANK_H */