IndicatorBasedSelection.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Indicator-based selection strategy for multi-objective selection.
5  *
6  *
7  *
8  * \author T.Voss
9  * \date 2010
10  *
11  *
12  * \par Copyright 1995-2015 Shark Development Team
13  *
14  * <BR><HR>
15  * This file is part of Shark.
16  * <http://image.diku.dk/shark/>
17  *
18  * Shark is free software: you can redistribute it and/or modify
19  * it under the terms of the GNU Lesser General Public License as published
20  * by the Free Software Foundation, either version 3 of the License, or
21  * (at your option) any later version.
22  *
23  * Shark is distributed in the hope that it will be useful,
24  * but WITHOUT ANY WARRANTY; without even the implied warranty of
25  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26  * GNU Lesser General Public License for more details.
27  *
28  * You should have received a copy of the GNU Lesser General Public License
29  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
30  *
31  */
32 #ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_OPERATORS_SELECTION_INDICATOR_BASED_SELECTION_H
33 #define SHARK_ALGORITHMS_DIRECT_SEARCH_OPERATORS_SELECTION_INDICATOR_BASED_SELECTION_H
34 
37 
38 #include <map>
39 #include <vector>
40 
41 namespace shark {
42 
43 /**
44 * \brief Implements the well-known indicator-based selection strategy.
45 *
46 * See
47 * Kalyanmoy Deb and Amrit Pratap and Sameer Agarwal and T. Meyarivan,
48 * A Fast Elitist Multi-Objective Genetic Algorithm: NSGA-II,
49 * IEEE Transactions on Evolutionary Computation
50 * Year 2000, Volume 6, p. 182-197
51 *
52 * \tparam Indicator The second-level sorting criterion.
53 */
54 template<typename Indicator>
56 
57  /** \cond */
58  template<typename T>
59  struct view_reference {
60  T * mep_value;
61  public:
62  typedef RealVector FitnessType;
63 
64  view_reference() : mep_value( NULL ){}
65  view_reference(T & value) : mep_value( &value ){}
66 
67  operator T & ()
68  {
69  return( *mep_value );
70  }
71 
72  operator const T & () const
73  {
74  return( *mep_value );
75  }
76 
77  view_reference<T> operator=( const T & rhs )
78  {
79  *mep_value = rhs;
80  return *this;
81  }
82 
83 
84  RealVector const& penalizedFitness() const{
85  return mep_value->penalizedFitness();
86  }
87 
88  RealVector const& unpenalizedFitness() const{
89  return mep_value->unpenalizedFitness();
90  }
91 
92  bool& selected(){
93  return mep_value->selected();
94  }
95  };
96  /** \endcond */
97 
98  /**
99  * \brief Executes the algorithm and assigns each member of the population
100  * its level non-dominance (rank) and its individual contribution to the front
101  * it belongs to (share).
102  *
103  * \param [in,out] population The population to be ranked.
104  * \param [in,out] mu the number of individuals to select
105  */
106  template<typename PopulationType>
107  void operator()( PopulationType & population, std::size_t mu )
108  {
109  if(population.empty()) return;
110 
111  //perform a nondominated sort to assign the rank to every element
112  FastNonDominatedSort nonDomSort;
113  nonDomSort(population);
114 
115  typedef std::vector< view_reference<typename PopulationType::value_type > > View;
116 
117  unsigned int maxRank = 0;
118  std::map< unsigned int, View > fronts;
119 
120  for( unsigned int i = 0; i < population.size(); i++ ) {
121  maxRank = std::max( maxRank, static_cast<unsigned int>( population[i].rank() ) );
122  fronts[population[i].rank()].push_back( population[i] );
123  population[i].selected() = true;
124  }
125 
126  //deselect the highest rank fronts until we would end up with less or equal mu elements
127  unsigned int rank = maxRank;
128  std::size_t popSize = population.size();
129 
130  while(popSize-fronts[rank].size() >= mu){
131  //deselect all elements in this front
132  View & front = fronts[rank];
133  for(std::size_t i = 0; i != front.size(); ++i){
134  front[i].selected() = false;
135  }
136  popSize -= front.size();
137  --rank;
138  }
139  //now use the indicator to deselect the worst approximating elements of the last selected front
140  m_indicator.updateInternals(FitnessExtractor(),population);
141  View& front = fronts[rank];
142  for(; popSize >mu;--popSize) {
143  std::size_t lc = m_indicator.leastContributor(FitnessExtractor(),front);
144  front[lc].selected() = false;
145  front.erase( front.begin() + lc );
146  }
147  }
148 
149  /**
150  * \brief Stores/restores the serializer's state.
151  * \tparam Archive Type of the archive.
152  * \param [in,out] archive The archive to serialize to.
153  * \param [in] version number, currently unused.
154  */
155  template<typename Archive>
156  void serialize( Archive & archive, const unsigned int version )
157  {
158  archive & BOOST_SERIALIZATION_NVP( m_indicator );
159  }
160 
161  Indicator m_indicator; ///< Instance of the second level sorting criterion.
162 };
163 }
164 
165 #endif