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-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_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 fitness relation is governed by the double value returned by Extractor, which can be the fitness or a
43 /// domination rank. The individuals which won the most torunaments are selected
44 template< typename Extractor >
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  DefaultRngType& 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  if(results.size() < outputSize){
62  throw SHARKEXCEPTION("[EPTournamentSelection] Input range must be bigger than output range");
63  }
64 
65  for(std::size_t i = 0; i != outputSize; ++i, ++out){
66  *out = *results[i].value;
67  }
68  }
69 
70  /// \brief Selects individuals from the range of individuals.
71  ///
72  /// Instead of using an output range, surviving individuals are marked as selected.
73  ///
74  /// \param [in] population The population where individuals are selected from
75  /// \param [in] mu number of individuals to select
76  template<typename Population>
77  void operator()(
78  DefaultRngType& rng,
79  Population& population,std::size_t mu
80  ){
81  SIZE_CHECK(population.size() >= mu);
82  typedef typename Population::iterator InIterator;
83  std::vector<KeyValuePair<int, InIterator> > results = performTournament(rng, population.begin(),population.end());
84 
85 
86  for(std::size_t i = 0; i != mu; ++i){
87  individualPerform[i].value->select() = true;
88  }
89  for(std::size_t i = mu; i != results.size()-1; ++i){
90  individualPerform[i].value->select() = false;
91  }
92  }
93 
94  /// \brief Size of the tournament. 4 by default.
95  std::size_t tournamentSize;
96 private:
97  ///Returns a sorted range of pairs indicating, how often every individual won.
98  /// The best individuals are in the front of the range.
99  template<class InIterator>
100  std::vector<KeyValuePair<int, InIterator> > performTournament(DefaultRngType& rng, InIterator it, InIterator itE){
101  std::size_t size = std::distance( it, itE );
102  UIntVector selectionProbability(size,0.0);
103  std::vector<KeyValuePair<int, InIterator> > individualPerformance(size);
104  Extractor e;
105  for( std::size_t i = 0; i != size(); ++i ) {
106  individualPerformance[i].value = it+i;
107  for( std::size_t round = 0; round < tournamentSize; round++ ) {
108  std::size_t idx = discrete(rng, 0,size-1 );
109  if(e(*it) < e(*(it+idx)){
110  individualPerformance[i].key -= 1;
111  }
112  }
113  }
114 
115  std::sort( individualPerformance.begin(), individualPerformance.end());
116  return individualPerformance;
117  }
118 };
119 
120 }
121 
122 #endif