ElitistSelection.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Elitist Selection Operator suitable for (mu,lambda) and (mu+lambda) selection
5  *
6  *
7  * \author O.Krause
8  * \date 2014
9  *
10  *
11  * \par Copyright 1995-2015 Shark Development Team
12  *
13  * <BR><HR>
14  * This file is part of Shark.
15  * <http://image.diku.dk/shark/>
16  *
17  * Shark is free software: you can redistribute it and/or modify
18  * it under the terms of the GNU Lesser General Public License as published
19  * by the Free Software Foundation, either version 3 of the License, or
20  * (at your option) any later version.
21  *
22  * Shark is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25  * GNU Lesser General Public License for more details.
26  *
27  * You should have received a copy of the GNU Lesser General Public License
28  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
29  *
30  */
31 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_OPERATORS_SELECTION_ELITIST_SELECTION_H
32 #define SHARK_ALGORITHMS_DIRECTSEARCH_OPERATORS_SELECTION_ELITIST_SELECTION_H
33 
34 #include <shark/LinAlg/Base.h>
36 #include <vector>
37 namespace shark {
38 
39 /// \brief Survival selection to find the next parent set
40 ///
41 /// Given a set of individuals, selects the mu best performing individuals.
42 /// The elements are ordered by a double value returned by the Extractor.
43 template< typename Extractor >
45 
46  /// \brief Selects individuals from the range of individuals.
47  ///
48  /// \param [in] it Iterator pointing to the first valid parent individual.
49  /// \param [in] itE Iterator pointing to the first invalid parent individual.
50  /// \param [in] out Iterator pointing to the first valid element of the output range.
51  /// \param [in] outE Iterator pointing to the first invalid element of the output range.
52  template<typename InIterator,typename OutIterator>
53  void operator()(
54  InIterator it, InIterator itE,
55  OutIterator out, OutIterator outE
56  ){
57  std::size_t outputSize = std::distance( out, outE );
58  std::vector<KeyValuePair<double, InIterator> > results = order(it, itE);
59  if(results.size() < outputSize){
60  throw SHARKEXCEPTION("[ElitistSelection] Input range must be bigger than output range");
61  }
62 
63  for(std::size_t i = 0; i != outputSize; ++i, ++out){
64  *out = *results[i].value;
65  }
66  }
67 
68  /// \brief Selects individuals from the range of individuals.
69  ///
70  /// Instead of using an output range, surviving individuals are marked as selected.
71  ///
72  /// \param [in] population The population where individuals are selected from
73  /// \param [in] mu number of individuals to select
74  template<typename Population>
75  void operator()(
76  Population& population,std::size_t mu
77  ){
78  SIZE_CHECK(population.size() >= mu);
79  typedef typename Population::iterator InIterator;
80  std::vector<KeyValuePair<double, InIterator> > results = order(population.begin(),population.end());
81 
82  for(std::size_t i = 0; i != mu; ++i){
83  results[i].value->select()=true;
84  }
85  for(std::size_t i = mu; i != results.size(); ++i){
86  results[i].value->select() = false;
87  }
88  }
89 private:
90  ///Returns a sorted range of pairs indicating, how often every individual won.
91  /// The best individuals are in the back of the range.
92  template<class InIterator>
93  std::vector<KeyValuePair<double, InIterator> > order(InIterator it, InIterator itE){
94  std::size_t size = std::distance( it, itE );
95  Extractor e;
96  std::vector<KeyValuePair<double, InIterator> > individuals(size);
97  for(std::size_t i = 0; i != size; ++i){
98  individuals[i].key = e(*(it+i));
99  individuals[i].value = it+i;
100  }
101  std::sort( individuals.begin(), individuals.end());
102  return individuals;
103  }
104 };
105 
106 }
107 
108 #endif