EPTournamentSelection.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief EP-Tournament selection operator.
5  *
6  *
7  * \author T.Voss
8  * \date 2010-2011
9  *
10  *
11  * \par Copyright 1995-2017 Shark Development Team
12  *
13  * <BR><HR>
14  * This file is part of Shark.
15  * <http://shark-ml.org/>
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_EP_TOURNAMENT_H
32 #define SHARK_ALGORITHMS_DIRECTSEARCH_OPERATORS_SELECTION_EP_TOURNAMENT_H
33 
34 #include <shark/LinAlg/Base.h>
36 #include <vector>
37 namespace shark {
38 
39 /// \brief Survival and mating selection to find the next parent set.
40 ///
41 /// For a given Tournament size k, every individual is compared to k other individuals
42 /// The ranking of the individuals is given by the template argument.
43 /// The individuals which won the most tournaments are selected
44 template< typename Ordering >
46 
47  /// \brief Selects individuals from the range of individuals.
48  ///
49  /// \param [in] it Iterator pointing to the first valid parent individual.
50  /// \param [in] itE Iterator pointing to the first invalid parent individual.
51  /// \param [in] out Iterator pointing to the first valid element of the output range.
52  /// \param [in] outE Iterator pointing to the first invalid element of the output range.
53  template<typename InIterator,typename OutIterator>
54  void operator()(
55  rng_type& rng,
56  InIterator it, InIterator itE,
57  OutIterator out, OutIterator outE
58  ){
59  std::size_t outputSize = std::distance( out, outE );
60  std::vector<KeyValuePair<int, InIterator> > results = performTournament(rng, it, itE);
61  SHARK_RUNTIME_CHECK(results.size() > outputSize, "Input range must be bigger than output range");
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  rng_type& rng,
77  Population& population,std::size_t mu
78  ){
79  SHARK_RUNTIME_CHECK(population.size() >= mu, "Population Size must be at least mu");
80  typedef typename Population::iterator InIterator;
81  std::vector<KeyValuePair<int, InIterator> > results = performTournament(rng, population.begin(),population.end());
82 
83 
84  for(std::size_t i = 0; i != mu; ++i){
85  individualPerform[i].value->select() = true;
86  }
87  for(std::size_t i = mu; i != results.size()-1; ++i){
88  individualPerform[i].value->select() = false;
89  }
90  }
91 
92  /// \brief Size of the tournament. 4 by default.
93  std::size_t tournamentSize;
94 private:
95  ///Returns a sorted range of pairs indicating, how often every individual won.
96  /// The best individuals are in the front of the range.
97  template<class InIterator>
98  std::vector<KeyValuePair<int, InIterator> > performTournament(rng_type& rng, InIterator it, InIterator itE){
99  std::size_t size = std::distance( it, itE );
100  UIntVector selectionProbability(size,0.0);
101  std::vector<KeyValuePair<int, InIterator> > individualPerformance(size);
102  Ordering smaller;
103  for( std::size_t i = 0; i != size(); ++i ) {
104  individualPerformance[i].value = it+i;
105  for( std::size_t round = 0; round < tournamentSize; round++ ) {
106  std::size_t idx = random::discrete(rng, 0,size-1 );
107  if(smaller(*it, *(it+idx)){
108  individualPerformance[i].key -= 1;
109  }
110  }
111  }
112 
113  std::sort( individualPerformance.begin(), individualPerformance.end());
114  return individualPerformance;
115  }
116 };
117 
118 }
119 
120 #endif