SMS-EMOA.h
Go to the documentation of this file.
1/*!
2 *
3 *
4 * \brief Implements the SMS-EMOA.
5 *
6 * See Nicola Beume, Boris Naujoks, and Michael Emmerich.
7 * SMS-EMOA: Multiobjective selection based on dominated hypervolume.
8 * European Journal of Operational Research, 181(3):1653-1669, 2007.
9 *
10 *
11 *
12 * \author T.Voss
13 * \date 2010
14 *
15 *
16 * \par Copyright 1995-2017 Shark Development Team
17 *
18 * <BR><HR>
19 * This file is part of Shark.
20 * <https://shark-ml.github.io/Shark/>
21 *
22 * Shark is free software: you can redistribute it and/or modify
23 * it under the terms of the GNU Lesser General Public License as published
24 * by the Free Software Foundation, either version 3 of the License, or
25 * (at your option) any later version.
26 *
27 * Shark is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU Lesser General Public License for more details.
31 *
32 * You should have received a copy of the GNU Lesser General Public License
33 * along with Shark. If not, see <http://www.gnu.org/licenses/>.
34 *
35 */
36#ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_SMS_EMOA_H
37#define SHARK_ALGORITHMS_DIRECT_SEARCH_SMS_EMOA_H
38
39// MOO specific stuff
40#include <shark/Algorithms/DirectSearch/Individual.h>
41#include <shark/Algorithms/DirectSearch/Operators/Indicators/HypervolumeIndicator.h>
42#include <shark/Algorithms/DirectSearch/Operators/Selection/TournamentSelection.h>
43#include <shark/Algorithms/DirectSearch/Operators/Selection/IndicatorBasedSelection.h>
44#include <shark/Algorithms/DirectSearch/Operators/Recombination/SimulatedBinaryCrossover.h>
45#include <shark/Algorithms/DirectSearch/Operators/Mutation/PolynomialMutation.h>
46#include <shark/Algorithms/DirectSearch/Operators/Evaluation/PenalizingEvaluator.h>
47
48#include <shark/Algorithms/AbstractMultiObjectiveOptimizer.h>
49
50namespace shark {
51
52/// \brief Implements the SMS-EMOA.
53///
54/// Please see the following paper for further reference:
55/// - Beume, Naujoks, Emmerich.
56/// SMS-EMOA: Multiobjective selection based on dominated hypervolume.
57/// European Journal of Operational Research.
58/// \ingroup multidirect
59class SMSEMOA : public AbstractMultiObjectiveOptimizer<RealVector >{
60public:
61 SMSEMOA(random::rng_type& rng = random::globalRng):mpe_rng(&rng) {
62 m_mu = 100;
63 m_mutator.m_nm = 20.0;
64 m_crossover.m_nc = 20.0;
65 m_crossoverProbability = 0.9;
66 this->m_features |= AbstractMultiObjectiveOptimizer<RealVector >::CAN_SOLVE_CONSTRAINED;
67 }
68
69 std::string name() const {
70 return "SMSEMOA";
71 }
72
73 /// \brief Returns the probability that crossover is applied.
74 double crossoverProbability()const{
75 return m_crossoverProbability;
76 }
77
78 double nm()const{
79 return m_mutator.m_nm;
80 }
81
82 double nc()const{
83 return m_crossover.m_nc;
84 }
85
86 unsigned int mu()const{
87 return m_mu;
88 }
89
90 unsigned int& mu(){
91 return m_mu;
92 }
93
94 std::size_t numInitPoints() const{
95 return m_mu;
96 }
97
98 HypervolumeIndicator& indicator(){
99 return m_selection.indicator();
100 }
101 HypervolumeIndicator const& indicator()const{
102 return m_selection.indicator();
103 }
104
105 void read( InArchive & archive ){
106 archive & BOOST_SERIALIZATION_NVP( m_parents );
107 archive & BOOST_SERIALIZATION_NVP( m_mu );
108 archive & BOOST_SERIALIZATION_NVP( m_best );
109
110 archive & BOOST_SERIALIZATION_NVP( m_selection );
111 archive & BOOST_SERIALIZATION_NVP( m_crossover );
112 archive & BOOST_SERIALIZATION_NVP( m_mutator );
113 archive & BOOST_SERIALIZATION_NVP( m_crossoverProbability );
114 }
115 void write( OutArchive & archive ) const{
116 archive & BOOST_SERIALIZATION_NVP( m_parents );
117 archive & BOOST_SERIALIZATION_NVP( m_mu );
118 archive & BOOST_SERIALIZATION_NVP( m_best );
119
120 archive & BOOST_SERIALIZATION_NVP( m_selection );
121 archive & BOOST_SERIALIZATION_NVP( m_crossover );
122 archive & BOOST_SERIALIZATION_NVP( m_mutator );
123 archive & BOOST_SERIALIZATION_NVP( m_crossoverProbability );
124 }
125
126 using AbstractMultiObjectiveOptimizer<RealVector >::init;
127 /**
128 * \brief Initializes the algorithm for the supplied objective function.
129 *
130 * \param [in] function The objective function.
131 * \param [in] initialSearchPoints A set of intiial search points.
132 */
133 void init(
134 ObjectiveFunctionType const& function,
135 std::vector<SearchPointType> const& initialSearchPoints
136 ){
137 checkFeatures(function);
138 std::vector<RealVector> values(initialSearchPoints.size());
139 for(std::size_t i = 0; i != initialSearchPoints.size(); ++i){
140 SHARK_RUNTIME_CHECK(function.isFeasible(initialSearchPoints[i]),"Starting point(s) not feasible");
141 values[i] = function.eval(initialSearchPoints[i]);
142 }
143
144 std::size_t dim = function.numberOfVariables();
145 RealVector lowerBounds(dim, -1E20);
146 RealVector upperBounds(dim, 1E20);
147 if (function.hasConstraintHandler() && function.getConstraintHandler().isBoxConstrained()) {
148 typedef BoxConstraintHandler<SearchPointType> ConstraintHandler;
149 ConstraintHandler const& handler = static_cast<ConstraintHandler const&>(function.getConstraintHandler());
150
151 lowerBounds = handler.lower();
152 upperBounds = handler.upper();
153 } else{
154 SHARK_RUNTIME_CHECK(
155 function.hasConstraintHandler() && !function.getConstraintHandler().isBoxConstrained(),
156 "Algorithm does only allow box constraints"
157 );
158 }
159 doInit(initialSearchPoints,values,lowerBounds, upperBounds,mu(),nm(),nc(),crossoverProbability());
160 }
161
162 /**
163 * \brief Executes one iteration of the algorithm.
164 *
165 * \param [in] function The function to iterate upon.
166 */
167 void step( ObjectiveFunctionType const& function ) {
168 std::vector<IndividualType> offspring = generateOffspring();
169 PenalizingEvaluator penalizingEvaluator;
170 penalizingEvaluator( function, offspring.begin(), offspring.end() );
171 updatePopulation(offspring);
172 }
173protected:
174 /// \brief The individual type of the SMS-EMOA.
175 typedef shark::Individual<RealVector,RealVector> IndividualType;
176
177 void doInit(
178 std::vector<SearchPointType> const& initialSearchPoints,
179 std::vector<ResultType> const& functionValues,
180 RealVector const& lowerBounds,
181 RealVector const& upperBounds,
182 std::size_t mu,
183 double nm,
184 double nc,
185 double crossover_prob
186 ){
187 SIZE_CHECK(initialSearchPoints.size() > 0);
188 m_mu = mu;
189 m_mutator.m_nm = nm;
190 m_crossover.m_nc = nc;
191 m_crossoverProbability = crossover_prob;
192 m_best.resize( mu );
193 m_parents.resize( mu );
194 //if the number of supplied points is smaller than mu, fill everything in
195 std::size_t numPoints = 0;
196 if(initialSearchPoints.size()<=mu){
197 numPoints = initialSearchPoints.size();
198 for(std::size_t i = 0; i != numPoints; ++i){
199 m_parents[i].searchPoint() = initialSearchPoints[i];
200 m_parents[i].penalizedFitness() = functionValues[i];
201 m_parents[i].unpenalizedFitness() = functionValues[i];
202 }
203 }
204 //copy points randomly
205 for(std::size_t i = numPoints; i != mu; ++i){
206 std::size_t index = random::discrete(*mpe_rng, std::size_t(0),initialSearchPoints.size()-1);
207 m_parents[i].searchPoint() = initialSearchPoints[index];
208 m_parents[i].penalizedFitness() = functionValues[index];
209 m_parents[i].unpenalizedFitness() = functionValues[index];
210 }
211 //create initial mu best points
212 for(std::size_t i = 0; i != mu; ++i){
213 m_best[i].point = m_parents[i].searchPoint();
214 m_best[i].value = m_parents[i].unpenalizedFitness();
215 }
216 m_selection( m_parents, mu );
217
218 m_crossover.init(lowerBounds,upperBounds);
219 m_mutator.init(lowerBounds,upperBounds);
220 }
221
222 std::vector<IndividualType> generateOffspring()const{
223 std::vector<IndividualType> offspring(1);
224 offspring[0] = createOffspring(m_parents.begin(),m_parents.begin()+mu());
225 return offspring;
226 }
227
228 void updatePopulation( std::vector<IndividualType> const& offspring) {
229 m_parents.push_back(offspring[0]);
230 m_selection( m_parents, mu());
231
232 //if the individual got selected, insert it into the parent population
233 if(m_parents.back().selected()){
234 for(std::size_t i = 0; i != mu(); ++i){
235 if(!m_parents[i].selected()){
236 m_best[i].point = m_parents[mu()].searchPoint();
237 m_best[i].value = m_parents[mu()].unpenalizedFitness();
238 m_parents[i] = m_parents.back();
239 break;
240 }
241 }
242 }
243 m_parents.pop_back();
244 }
245
246 std::vector<IndividualType> m_parents; ///< Population of size \f$\mu + 1\f$.
247private:
248
249 IndividualType createOffspring(
250 std::vector<IndividualType>::const_iterator begin,
251 std::vector<IndividualType>::const_iterator end
252 )const{
253 TournamentSelection< IndividualType::RankOrdering > selection;
254
255 IndividualType mate1( *selection(*mpe_rng, begin, end ) );
256 IndividualType mate2( *selection(*mpe_rng, begin, end) );
257
258 if( random::coinToss(*mpe_rng, m_crossoverProbability ) ) {
259 m_crossover(*mpe_rng, mate1, mate2 );
260 }
261
262 if( random::coinToss(*mpe_rng,0.5) ) {
263 m_mutator(*mpe_rng, mate1 );
264 return mate1;
265 } else {
266 m_mutator(*mpe_rng, mate2 );
267 return mate2;
268 }
269 }
270
271 unsigned int m_mu; ///< Size of parent generation
272
273 IndicatorBasedSelection<HypervolumeIndicator> m_selection; ///< Selection operator relying on the (contributing) hypervolume indicator.
274 SimulatedBinaryCrossover< RealVector > m_crossover; ///< Crossover operator.
275 PolynomialMutator m_mutator; ///< Mutation operator.
276
277 double m_crossoverProbability; ///< Crossover probability.
278 random::rng_type* mpe_rng;
279};
280}
281
282
283#endif