MOCMA.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Implements the generational Multi-objective Covariance Matrix Adapation ES.
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_MOCMA
33 #define SHARK_ALGORITHMS_DIRECT_SEARCH_MOCMA
34 
35 // MOO specific stuff
42 
43 
45 
46 #include <boost/foreach.hpp>
47 
48 namespace shark {
49 
50 /**
51  * \brief Implements the generational MO-CMA-ES.
52  *
53  * Please see the following papers for further reference:
54  * - Igel, Suttorp and Hansen. Steady-state Selection and Efficient Covariance Matrix Update in the Multi-Objective CMA-ES.
55  * - Voß, Hansen and Igel. Improved Step Size Adaptation for the MO-CMA-ES.
56  */
57 template<typename Indicator=HypervolumeIndicator>
59 public:
63  };
64 public:
65 
66  IndicatorBasedMOCMA(DefaultRngType& rng= Rng::globalRng):mpe_rng(&rng) {
67  m_individualSuccessThreshold = 0.44;
68  initialSigma() = 1.0;
69  mu() = 100;
72  }
73 
74  /**
75  * \brief Returns the name of the algorithm.
76  */
77  std::string name() const {
78  return "MOCMA";
79  }
80 
81  std::size_t mu()const{
82  return m_mu;
83  }
84  std::size_t& mu(){
85  return m_mu;
86  }
87 
88  double initialSigma()const{
89  return m_initialSigma;
90  }
91  double& initialSigma(){
92  return m_initialSigma;
93  }
94 
96  return m_notionOfSuccess;
97  }
99  return m_notionOfSuccess;
100  }
101  void read( InArchive & archive ){
102  archive >> BOOST_SERIALIZATION_NVP(m_parents);
103  archive >> BOOST_SERIALIZATION_NVP(m_mu);
104  archive >> BOOST_SERIALIZATION_NVP(m_best);
105 
106  archive >> BOOST_SERIALIZATION_NVP(m_selection);
107  archive >> BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
108  archive >> BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
109  archive >> BOOST_SERIALIZATION_NVP(m_initialSigma);
110  }
111  void write( OutArchive & archive ) const{
112  archive << BOOST_SERIALIZATION_NVP(m_parents);
113  archive << BOOST_SERIALIZATION_NVP(m_mu);
114  archive << BOOST_SERIALIZATION_NVP(m_best);
115 
116  archive << BOOST_SERIALIZATION_NVP(m_selection);
117  archive << BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
118  archive << BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
119  archive << BOOST_SERIALIZATION_NVP(m_initialSigma);
120  }
121 
122  void init( ObjectiveFunctionType& function){
123  checkFeatures(function);
124  if(!function.canProposeStartingPoint())
125  throw SHARKEXCEPTION( "Objective function does not propose a starting point");
126  std::vector<RealVector> points(mu());
127  for(std::size_t i = 0; i != mu(); ++i){
128  points[i] = function.proposeStartingPoint();
129  }
130  init(function,points);
131  }
132  /**
133  * \brief Initializes the algorithm for the supplied objective function.
134  *
135  * \param [in] function The objective function.
136  * \param [in] initialSearchPoints A set of intiial search points.
137  */
138  void init(
139  ObjectiveFunctionType& function,
140  std::vector<SearchPointType> const& initialSearchPoints
141  ){
142  checkFeatures(function);
143  std::vector<RealVector> values(initialSearchPoints.size());
144  for(std::size_t i = 0; i != initialSearchPoints.size(); ++i){
145  if(!function.isFeasible(initialSearchPoints[i]))
146  throw SHARKEXCEPTION("[MOCMA::init] starting point(s) not feasible");
147  values[i] = function.eval(initialSearchPoints[i]);
148  }
149  this->doInit(initialSearchPoints,values,mu(),initialSigma() );
150  }
151 
152  /**
153  * \brief Executes one iteration of the algorithm.
154  *
155  * \param [in] function The function to iterate upon.
156  */
157  void step( ObjectiveFunctionType const& function ) {
158  std::vector<IndividualType> offspring = generateOffspring();
159  PenalizingEvaluator penalizingEvaluator;
160  penalizingEvaluator( function, offspring.begin(), offspring.end() );
161  updatePopulation(offspring);
162  }
163 protected:
164  /// \brief The individual type of the SteadyState-MOCMA.
166 
167  void doInit(
168  std::vector<SearchPointType> const& initialSearchPoints,
169  std::vector<ResultType> const& functionValues,
170  std::size_t mu,
171  double initialSigma
172  ){
173  SIZE_CHECK(initialSearchPoints.size() > 0);
174  m_mu = mu;
175  m_initialSigma = initialSigma;
176 
177  m_best.resize( mu );
178  m_parents.resize( mu );
179  std::size_t noVariables = initialSearchPoints[0].size();
180 
181  //if the number of supplied points is smaller than mu, fill everything in
182  std::size_t numPoints = 0;
183  if(initialSearchPoints.size()<=mu){
184  numPoints = initialSearchPoints.size();
185  for(std::size_t i = 0; i != numPoints; ++i){
186  m_parents[i] = IndividualType(noVariables,m_individualSuccessThreshold,m_initialSigma);
187  m_parents[i].searchPoint() = initialSearchPoints[i];
188  m_parents[i].penalizedFitness() = functionValues[i];
189  m_parents[i].unpenalizedFitness() = functionValues[i];
190  }
191  }
192  //copy points randomly
193  for(std::size_t i = numPoints; i != mu; ++i){
194  std::size_t index = discrete(*mpe_rng,0,initialSearchPoints.size()-1);
195  m_parents[i] = IndividualType(noVariables,m_individualSuccessThreshold,m_initialSigma);
196  m_parents[i].searchPoint() = initialSearchPoints[index];
197  m_parents[i].penalizedFitness() = functionValues[index];
198  m_parents[i].unpenalizedFitness() = functionValues[index];
199  }
200  //create initial mu best points
201  for(std::size_t i = 0; i != mu; ++i){
202  m_best[i].point = m_parents[i].searchPoint();
203  m_best[i].value = m_parents[i].unpenalizedFitness();
204  }
205  }
206 
207  std::vector<IndividualType> generateOffspring()const{
208  std::vector<IndividualType> offspring(mu());
209  for(std::size_t i = 0; i != mu(); ++i){
210  std::size_t parentId = i;
211  offspring[i] = m_parents[parentId];
212  offspring[i].mutate(*mpe_rng);
213  offspring[i].parent() = parentId;
214  }
215  return offspring;
216  }
217 
218  void updatePopulation( std::vector<IndividualType> const& offspringVec) {
219  m_parents.insert(m_parents.end(),offspringVec.begin(),offspringVec.end());
220  m_selection( m_parents, mu());
221 
222  //determine from the selection which parent-offspring pair has been successful
223  for (std::size_t i = 0; i < mu(); i++) {
225  //new update: an offspring is successful if it is selected
226  if ( m_notionOfSuccess == PopulationBased && m_parents[mu()+i].selected()) {
227  m_parents[mu()+i].updateAsOffspring();
228  offspringSuccess = CMAChromosome::Successful;
229  }
230  //old update: an offspring is successfull if it is better than its parent
231  else if ( m_notionOfSuccess == IndividualBased && m_parents[mu()+i].selected() && m_parents[mu()+i].rank() <= m_parents[i].rank()) {
232  m_parents[mu()+i].updateAsOffspring();
233  offspringSuccess = CMAChromosome::Successful;
234  }
235  if(m_parents[i].selected())
236  m_parents[i].updateAsParent(offspringSuccess);
237  }
238 
239  //partition the selected individuals to the front and remove the unselected ones
240  std::partition(m_parents.begin(), m_parents.end(),IndividualType::IsSelected);
241  m_parents.erase(m_parents.begin()+mu(),m_parents.end());
242 
243  //update solution set
244  for (std::size_t i = 0; i < mu(); i++) {
245  noalias(m_best[i].point) = m_parents[i].searchPoint();
246  m_best[i].value = m_parents[i].unpenalizedFitness();
247  }
248  }
249 
250  std::vector<IndividualType> m_parents; ///< Population of size \f$\mu + 1\f$.
251 
252 private:
253  std::size_t m_mu; ///< Size of parent population
254 
255  IndicatorBasedSelection<Indicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
256 
257  NotionOfSuccess m_notionOfSuccess; ///< Flag for deciding whether the improved step-size adaptation shall be used.
258  double m_individualSuccessThreshold;
259  double m_initialSigma;
260  DefaultRngType* mpe_rng;
261 };
262 
266 
267 }
268 
269 #endif