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-2017 Shark Development Team
13 *
14 * <BR><HR>
15 * This file is part of Shark.
16 * <http://shark-ml.org/>
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
36#include <shark/Algorithms/DirectSearch/Operators/Indicators/HypervolumeIndicator.h>
37#include <shark/Algorithms/DirectSearch/Operators/Indicators/AdditiveEpsilonIndicator.h>
38#include <shark/Algorithms/DirectSearch/Operators/Selection/IndicatorBasedSelection.h>
39#include <shark/Algorithms/DirectSearch/Operators/Evaluation/PenalizingEvaluator.h>
40#include <shark/Algorithms/DirectSearch/CMA/CMAIndividual.h>
41
42
43#include <shark/Algorithms/AbstractMultiObjectiveOptimizer.h>
44
45namespace shark {
46
47/// \brief Implements the generational 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/// \ingroup multidirect
53template<typename Indicator=HypervolumeIndicator>
54class IndicatorBasedMOCMA : public AbstractMultiObjectiveOptimizer<RealVector >{
55public:
60public:
61
62 IndicatorBasedMOCMA(random::rng_type& rng= random::globalRng):mpe_rng(&rng) {
63 m_individualSuccessThreshold = 0.44;
64 initialSigma() = 1.0;
65 mu() = 100;
66 notionOfSuccess() = PopulationBased;
67 this->m_features |= AbstractMultiObjectiveOptimizer<RealVector >::CAN_SOLVE_CONSTRAINED;
68 }
69
70 /**
71 * \brief Returns the name of the algorithm.
72 */
73 std::string name() const {
74 return "MOCMA";
75 }
76
77 std::size_t mu()const{
78 return m_mu;
79 }
80 std::size_t& mu(){
81 return m_mu;
82 }
83
84 /// \brief The number of points used for initialization of the algorithm.
85 std::size_t numInitPoints() const{
86 return m_mu;
87 }
88
89 double initialSigma()const{
90 return m_initialSigma;
91 }
92 double& initialSigma(){
93 return m_initialSigma;
94 }
95
96 NotionOfSuccess notionOfSuccess()const{
97 return m_notionOfSuccess;
98 }
99 NotionOfSuccess& notionOfSuccess(){
100 return m_notionOfSuccess;
101 }
102 void read( InArchive & archive ){
103 archive >> BOOST_SERIALIZATION_NVP(m_parents);
104 archive >> BOOST_SERIALIZATION_NVP(m_mu);
105 archive >> BOOST_SERIALIZATION_NVP(m_best);
106
107 archive >> BOOST_SERIALIZATION_NVP(m_selection);
108 archive >> BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
109 archive >> BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
110 archive >> BOOST_SERIALIZATION_NVP(m_initialSigma);
111 }
112 void write( OutArchive & archive ) const{
113 archive << BOOST_SERIALIZATION_NVP(m_parents);
114 archive << BOOST_SERIALIZATION_NVP(m_mu);
115 archive << BOOST_SERIALIZATION_NVP(m_best);
116
117 archive << BOOST_SERIALIZATION_NVP(m_selection);
118 archive << BOOST_SERIALIZATION_NVP(m_notionOfSuccess);
119 archive << BOOST_SERIALIZATION_NVP(m_individualSuccessThreshold);
120 archive << BOOST_SERIALIZATION_NVP(m_initialSigma);
121 }
122
123 using AbstractMultiObjectiveOptimizer<RealVector >::init;
124 /**
125 * \brief Initializes the algorithm for the supplied objective function.
126 *
127 * \param [in] function The objective function.
128 * \param [in] initialSearchPoints A set of intiial search points.
129 */
130 void init(
131 ObjectiveFunctionType const& function,
132 std::vector<SearchPointType> const& initialSearchPoints
133 ){
134 checkFeatures(function);
135 std::vector<RealVector> values(initialSearchPoints.size());
136 for(std::size_t i = 0; i != initialSearchPoints.size(); ++i){
137 SHARK_RUNTIME_CHECK(function.isFeasible(initialSearchPoints[i]),"Starting point(s) not feasible");
138 values[i] = function.eval(initialSearchPoints[i]);
139 }
140 this->doInit(initialSearchPoints,values,mu(),initialSigma() );
141 }
142
143 /**
144 * \brief Executes one iteration of the algorithm.
145 *
146 * \param [in] function The function to iterate upon.
147 */
148 void step( ObjectiveFunctionType const& function ) {
149 std::vector<IndividualType> offspring = generateOffspring();
150 PenalizingEvaluator penalizingEvaluator;
151 penalizingEvaluator( function, offspring.begin(), offspring.end() );
152 updatePopulation(offspring);
153 }
154
155 Indicator& indicator(){
156 return m_selection.indicator();
157 }
158 Indicator const& indicator()const{
159 return m_selection.indicator();
160 }
161protected:
162 /// \brief The individual type of the SteadyState-MOCMA.
163 typedef CMAIndividual<RealVector> IndividualType;
164
165 void doInit(
166 std::vector<SearchPointType> const& initialSearchPoints,
167 std::vector<ResultType> const& functionValues,
168 std::size_t mu,
169 double initialSigma
170 ){
171 SIZE_CHECK(initialSearchPoints.size() > 0);
172 m_mu = mu;
173 m_initialSigma = initialSigma;
174
175 m_best.resize( mu );
176 m_parents.resize( mu );
177 std::size_t noVariables = initialSearchPoints[0].size();
178
179 //if the number of supplied points is smaller than mu, fill everything in
180 std::size_t numPoints = 0;
181 if(initialSearchPoints.size()<=mu){
182 numPoints = initialSearchPoints.size();
183 for(std::size_t i = 0; i != numPoints; ++i){
184 m_parents[i] = IndividualType(noVariables,m_individualSuccessThreshold,m_initialSigma);
185 m_parents[i].searchPoint() = initialSearchPoints[i];
186 m_parents[i].penalizedFitness() = functionValues[i];
187 m_parents[i].unpenalizedFitness() = functionValues[i];
188 }
189 }
190 //copy points randomly
191 for(std::size_t i = numPoints; i != mu; ++i){
192 std::size_t index = random::discrete(*mpe_rng,std::size_t(0),initialSearchPoints.size()-1);
193 m_parents[i] = IndividualType(noVariables,m_individualSuccessThreshold,m_initialSigma);
194 m_parents[i].searchPoint() = initialSearchPoints[index];
195 m_parents[i].penalizedFitness() = functionValues[index];
196 m_parents[i].unpenalizedFitness() = functionValues[index];
197 }
198 //create initial mu best points
199 for(std::size_t i = 0; i != mu; ++i){
200 m_best[i].point = m_parents[i].searchPoint();
201 m_best[i].value = m_parents[i].unpenalizedFitness();
202 }
203
204 indicator().init(functionValues.front().size(),mu,*mpe_rng);
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++) {
224 CMAChromosome::IndividualSuccess offspringSuccess = CMAChromosome::Unsuccessful;
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 const& ind){return ind.selected();});
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
252private:
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 random::rng_type* mpe_rng;
261};
262
263typedef IndicatorBasedMOCMA< HypervolumeIndicator > MOCMA;
264typedef IndicatorBasedMOCMA< AdditiveEpsilonIndicator > EpsilonMOCMA;
265
266}
267
268#endif