LinearRanking.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Roulette-Wheel-Selection based on fitness-rank-based selection probability assignment.
5  *
6  * The algorithm is described in: James E. Baker. Adaptive Selection
7  * Methods for Genetic Algorithms. In John J. Grefenstette (ed.):
8  * Proceedings of the 1st International Conference on Genetic
9  * Algorithms (ICGA), pp. 101-111, Lawrence Erlbaum Associates, 1985
10  *
11  *
12  *
13  * \author T.Voss
14  * \date 2010-2011
15  *
16  *
17  * \par Copyright 1995-2015 Shark Development Team
18  *
19  * <BR><HR>
20  * This file is part of Shark.
21  * <http://image.diku.dk/shark/>
22  *
23  * Shark is free software: you can redistribute it and/or modify
24  * it under the terms of the GNU Lesser General Public License as published
25  * by the Free Software Foundation, either version 3 of the License, or
26  * (at your option) any later version.
27  *
28  * Shark is distributed in the hope that it will be useful,
29  * but WITHOUT ANY WARRANTY; without even the implied warranty of
30  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31  * GNU Lesser General Public License for more details.
32  *
33  * You should have received a copy of the GNU Lesser General Public License
34  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
35  *
36  */
37 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_OPERATORS_SELECTION_LINEARRANKING_H
38 #define SHARK_ALGORITHMS_DIRECTSEARCH_OPERATORS_SELECTION_LINEARRANKING_H
39 
42 #include <vector>
43 
44 namespace shark {
45 
46 /**
47  * \brief Implements a fitness-proportional selection scheme for mating selection that
48  * scales the fitness values linearly before carrying out the actual selection.
49  *
50  * The algorithm is described in: James E. Baker. Adaptive Selection
51  * Methods for Genetic Algorithms. In John J. Grefenstette (ed.):
52  * Proceedings of the 1st International Conference on Genetic
53  * Algorithms (ICGA), pp. 101-111, Lawrence Erlbaum Associates, 1985
54  *
55  */
56 template<typename Extractor >
59  etaMax = 1.1;
60  }
61  /// \brief Selects individualss from the range of parent and offspring individuals.
62  ///
63  /// The operator carries out the following steps:
64  /// - Calculate selection probabilities of parent and offspring individualss
65  /// according to their rank.
66  /// - Carry out roulette wheel selection on the range of parent and
67  /// offspring individualss until the output range is filled.
68  ///
69  /// \param [in] individuals Iterator pointing to the first valid individual.
70  /// \param [in] individualsE Iterator pointing to the first invalid individual.
71  /// \param [in] out Iterator pointing to the first valid element of the output range.
72  /// \param [in] outE Iterator pointing to the first invalid element of the output range.
73  ///
74  template<typename InIterator,typename OutIterator>
75  void operator()(
76  DefaultRngType& rng,
77  InIterator individuals,
78  InIterator individualsE,
79  OutIterator out,
80  OutIterator outE
81  ) const{
82 
83  //compute rank of each individual
84  std::size_t size = std::distance( individuals, individualsE );
85  std::vector<KeyValuePair<double, InIterator> > individualsPerformance(size);
86 
87  for( std::size_t i = 0; i != size; ++i, ++individuals ) {
88  Extractor e;
89  individualsPerformance[i].value = individuals;
90  individualsPerformance[i].key = e(*individuals);
91  }
92  std::sort( individualsPerformance.begin(), individualsPerformance.end());
93 
94  RealVector selectionProbability(size);
95  double a = 2. * (etaMax - 1.)/(size - 1.);
96  for( std::size_t i = 0; i != size; ++i ) {
97  selectionProbability[i] = (etaMax - a*i);
98  }
99  selectionProbability /=sum(selectionProbability);
100 
102  for( ; out != outE; ++out ){
103  InIterator individuals = rws(rng, individualsPerformance.begin(), individualsPerformance.end(), selectionProbability)->value;
104  *out = *individuals;
105  }
106  }
107 
108  /// \brief Selective pressure, parameter in [1,2] conrolling selection strength. 1.1 by default
109  double etaMax;
110 
111 };
112 }
113 
114 #endif