SteadyStateMOCMA.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief SteadyStateMOCMA.h
5  *
6  * \author T.Voss
7  * \date 2010
8  *
9  *
10  * \par Copyright 1995-2015 Shark Development Team
11  *
12  * <BR><HR>
13  * This file is part of Shark.
14  * <http://image.diku.dk/shark/>
15  *
16  * Shark is free software: you can redistribute it and/or modify
17  * it under the terms of the GNU Lesser General Public License as published
18  * by the Free Software Foundation, either version 3 of the License, or
19  * (at your option) any later version.
20  *
21  * Shark is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24  * GNU Lesser General Public License for more details.
25  *
26  * You should have received a copy of the GNU Lesser General Public License
27  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
28  *
29  */
30 #ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_STEADYSTATEMOCMA
31 #define SHARK_ALGORITHMS_DIRECT_SEARCH_STEADYSTATEMOCMA
32 
33 // MOO specific stuff
40 
42 #include <boost/foreach.hpp>
43 
44 namespace shark {
45 
46 /**
47  * \brief Implements the \f$(\mu+1)\f$-MO-CMA-ES.
48  *
49  * Please see the following papers for further reference:
50  * - Igel, Suttorp and Hansen. Steady-state Selection and Efficient Covariance Matrix Update in the Multi-Objective CMA-ES.
51  * - Voß, Hansen and Igel. Improved Step Size Adaptation for the MO-CMA-ES.
52  */
53 template<typename Indicator=HypervolumeIndicator>
55 public:
59  };
60 private:
61 
63  std::vector< Individual > m_pop; ///< Population of size \f$\mu+1\f$.
64  std::size_t m_mu; ///< Size of parent population
65 
66  shark::PenalizingEvaluator m_evaluator; ///< Evaluation operator.
67  IndicatorBasedSelection<Indicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
68 
69  NotionOfSuccess m_notionOfSuccess; ///< Flag for deciding whether the improved step-size adaptation shall be used.
70  double m_individualSuccessThreshold;
71  double m_initialSigma;
72 public:
73 
75  m_individualSuccessThreshold = 0.44;
76  initialSigma() = 1.0;
77  constrainedPenaltyFactor() = 1E-6;
78  mu() = 100;
81  }
82 
83  /**
84  * \brief Returns the name of the algorithm.
85  */
86  std::string name() const {
87  return "SteadyStateMOCMA";
88  }
89 
90  std::size_t mu()const{
91  return m_mu;
92  }
93  std::size_t& mu(){
94  return m_mu;
95  }
96 
97  double initialSigma()const{
98  return m_initialSigma;
99  }
100  double& initialSigma(){
101  return m_initialSigma;
102  }
103 
104  /// \brief Returns the penalty factor for an individual that is outside the feasible area.
105  ///
106  /// The value is multiplied with the distance to the nearest feasible point.
108  return m_evaluator.m_penaltyFactor;
109  }
110 
111  /// \brief Returns a reference to the penalty factor for an individual that is outside the feasible area.
112  ///
113  /// The value is multiplied with the distance to the nearest feasible point.
115  return m_evaluator.m_penaltyFactor;
116  }
117 
119  return m_notionOfSuccess;
120  }
122  return m_notionOfSuccess;
123  }
124  /**
125  * \brief Stores/loads the algorithm's state.
126  * \tparam Archive The type of the archive.
127  * \param [in,out] archive The archive to use for loading/storing.
128  * \param [in] version Currently unused.
129  */
130  template<typename Archive>
131  void serialize(Archive &archive, const unsigned int version) {
132  archive & BOOST_SERIALIZATION_NVP(m_pop);
133  archive & BOOST_SERIALIZATION_NVP(m_mu);
134  archive & BOOST_SERIALIZATION_NVP(m_best);
135 
136  archive & BOOST_SERIALIZATION_NVP(m_evaluator);
137  archive & BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
138  archive & BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
139  archive & BOOST_SERIALIZATION_NVP(m_initialSigma);
140  }
141 
143  /**
144  * \brief Initializes the algorithm for the supplied objective function.
145  *
146  * \param [in] function The objective function.
147  * \param [in] startingPoints A set of intiial search points.
148  */
149  void init(
150  ObjectiveFunctionType& function,
151  std::vector<SearchPointType> const& startingPoints
152  ){
153  checkFeatures(function);
154  function.init();
155 
156  m_pop.resize(mu());
157  m_best.resize(mu());
158  std::size_t noVariables = function.numberOfVariables();
159 
160  for(std::size_t i = 0; i != mu(); ++i){
161  m_pop[i] = Individual(noVariables,m_individualSuccessThreshold,m_initialSigma);
162  m_pop[i].searchPoint()=function.proposeStartingPoint();
163  m_evaluator(function, m_pop[i]);
164  m_best[i].point = m_pop[i].searchPoint();
165  m_best[i].value = m_pop[i].unpenalizedFitness();
166  }
167  m_selection(m_pop,m_mu);
168  m_pop.push_back(Individual(noVariables,m_individualSuccessThreshold,m_initialSigma));
170  }
171 
172  /**
173  * \brief Executes one iteration of the algorithm.
174  *
175  * \param [in] function The function to iterate upon.
176  */
177  void step( ObjectiveFunctionType const& function ) {
178  //find the last element with rank 1
179  std::size_t maxIdx = 0;
180  for (; maxIdx < m_pop.size(); maxIdx++) {
181  if (m_pop[maxIdx].rank() != 1)
182  break;
183  }
184  //sample a random parent with rank 1
185  Individual& parent = m_pop[Rng::discrete(0, std::max<std::size_t>(0, maxIdx-1))];
186  //sample offspring from this parent
187  Individual& offspring = m_pop[mu()];
188  offspring = parent;
189  offspring.mutate();
190  m_evaluator(function, offspring);
191 
192  m_selection(m_pop,m_mu);
193  if (m_notionOfSuccess == IndividualBased && offspring.selected()) {
194  offspring.updateAsOffspring();
196  }
197  else if (m_notionOfSuccess == PopulationBased && offspring.selected() && offspring.rank() <= parent.rank() ) {
198  offspring.updateAsOffspring();
200  }else{
202  }
203 
204  if(offspring.selected()){
205  //exchange the selected and nonselected elements
206  for(std::size_t i = 0; i != mu(); ++i){
207  if(!m_pop[i].selected()){
208  noalias(m_best[i].point) = m_pop[mu()].searchPoint();
209  m_best[i].value = m_pop[mu()].unpenalizedFitness();
210  swap(m_pop[i] , m_pop[mu()]);
211  }
212  }
213  //now push rank 1 elements to the front
215  }
216  }
217 protected:
218  /// \brief sorts all individuals with rank one to the front
220  std::size_t start = 0;
221  std::size_t end = mu()-1;
222  while(start != end){
223  if(m_pop[start].rank() == 1){
224  ++start;
225  }else if(m_pop[end].rank() != 1){
226  --end;
227  }else{
228  swap(m_pop[start],m_pop[end]);
229  swap(m_best[start],m_best[end]);
230  }
231  }
232  }
233 };
234 
238 
239 }
240 
241 #endif