Shark machine learning library
About Shark
News!
Contribute
Credits and copyright
Downloads
Getting Started
Installation
Using the docs
Documentation
Tutorials
Quick references
Class list
Global functions
FAQ
Showroom
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
File Members
include
shark
Algorithms
DirectSearch
CMA.h
Go to the documentation of this file.
1
//===========================================================================
2
/*!
3
*
4
*
5
* \brief Implements the most recent version of the non-elitist CMA-ES.
6
*
7
* Hansen, N. The CMA Evolution Startegy: A Tutorial, June 28, 2011
8
* and the eqation numbers refer to this publication (retrieved April 2014).
9
*
10
*
11
* \author Thomas Voss and Christian Igel
12
* \date April 2014
13
*
14
* \par Copyright 1995-2015 Shark Development Team
15
*
16
* <BR><HR>
17
* This file is part of Shark.
18
* <http://image.diku.dk/shark/>
19
*
20
* Shark is free software: you can redistribute it and/or modify
21
* it under the terms of the GNU Lesser General Public License as published
22
* by the Free Software Foundation, either version 3 of the License, or
23
* (at your option) any later version.
24
*
25
* Shark is distributed in the hope that it will be useful,
26
* but WITHOUT ANY WARRANTY; without even the implied warranty of
27
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28
* GNU Lesser General Public License for more details.
29
*
30
* You should have received a copy of the GNU Lesser General Public License
31
* along with Shark. If not, see <http://www.gnu.org/licenses/>.
32
*
33
*/
34
//===========================================================================
35
36
37
#ifndef SHARK_ALGORITHMS_DIRECT_SEARCH_CMA_H
38
#define SHARK_ALGORITHMS_DIRECT_SEARCH_CMA_H
39
40
#include <
shark/Core/DLLSupport.h
>
41
#include <
shark/Algorithms/AbstractSingleObjectiveOptimizer.h
>
42
#include <
shark/Statistics/Distributions/MultiVariateNormalDistribution.h
>
43
#include <
shark/Algorithms/DirectSearch/Individual.h
>
44
45
46
namespace
shark
{
47
/**
48
* \brief Implements the CMA-ES.
49
*
50
* The algorithm is described in
51
*
52
* Hansen, N., S. Kern (2004). Evaluating the CMA Evolution Strategy
53
* on Multimodal Test Functions. In Proceedings of the Eighth
54
* International Conference on Parallel Problem Solving from Nature
55
* (PPSN VIII), pp. 282-291, LNCS, Springer-Verlag
56
*/
57
class
CMA
:
public
AbstractSingleObjectiveOptimizer
<RealVector >
58
{
59
public
:
60
/**
61
* \brief Models the recombination type.
62
*/
63
enum
RecombinationType
{
64
EQUAL
= 0,
65
LINEAR
= 1,
66
SUPERLINEAR
= 2
67
};
68
69
/**
70
* \brief Default c'tor.
71
*/
72
SHARK_EXPORT_SYMBOL
CMA
();
73
74
/// \brief From INameable: return the class name.
75
std::string
name
()
const
76
{
return
"CMA-ES"
; }
77
78
/**
79
* \brief Calculates the center of gravity of the given population \f$ \in \mathbb{R}^d\f$.
80
*
81
*
82
*/
83
template
<
typename
Container,
typename
Extractor>
84
RealVector
weightedSum
(
const
Container & container,
const
RealVector &
weights
,
const
Extractor & e ) {
85
86
RealVector result(
m_numberOfVariables
, 0. );
87
88
for
( std::size_t j = 0; j < container.size(); j++ )
89
result +=
weights
( j ) * e( container[j] );
90
91
return
( result );
92
}
93
94
/**
95
* \brief Calculates lambda for the supplied dimensionality n.
96
*/
97
SHARK_EXPORT_SYMBOL
static
std::size_t
suggestLambda
( std::size_t dimension ) ;
98
99
/**
100
* \brief Calculates mu for the supplied lambda and the recombination strategy.
101
*/
102
SHARK_EXPORT_SYMBOL
static
std::size_t
suggestMu
( std::size_t
lambda
,
RecombinationType
recomb =
SUPERLINEAR
) ;
103
104
void
read
(
InArchive
& archive );
105
void
write
(
OutArchive
& archive )
const
;
106
107
using
AbstractSingleObjectiveOptimizer<RealVector >::init
;
108
/**
109
* \brief Initializes the algorithm for the supplied objective function.
110
*/
111
SHARK_EXPORT_SYMBOL
void
init
(
ObjectiveFunctionType
&
function
,
SearchPointType
const
& p);
112
113
/**
114
* \brief Initializes the algorithm for the supplied objective function.
115
*/
116
SHARK_EXPORT_SYMBOL
void
init
(
117
ObjectiveFunctionType
&
function
,
118
SearchPointType
const
& initialSearchPoint,
119
std::size_t lambda,
120
std::size_t
mu
,
121
double
initialSigma,
122
const
boost::optional< RealMatrix > & initialCovarianceMatrix = boost::optional< RealMatrix >()
123
);
124
125
/**
126
* \brief Executes one iteration of the algorithm.
127
*/
128
SHARK_EXPORT_SYMBOL
void
step
(
ObjectiveFunctionType
const
&
function
);
129
130
/** \brief Accesses the current step size. */
131
double
sigma
()
const
{
132
return
m_sigma
;
133
}
134
135
/** \brief Accesses the current step size. */
136
void
setSigma
(
double
sigma
) {
137
m_sigma
=
sigma
;
138
}
139
140
141
/** \brief Accesses the current population mean. */
142
RealVector
const
&
mean
()
const
{
143
return
m_mean
;
144
}
145
146
/** \brief Accesses the current weighting vector. */
147
RealVector
const
&
weights
()
const
{
148
return
m_weights
;
149
}
150
151
/** \brief Accesses the evolution path for the covariance matrix update. */
152
RealVector
const
&
evolutionPath
()
const
{
153
return
m_evolutionPathC
;
154
}
155
156
/** \brief Accesses the evolution path for the step size update. */
157
RealVector
const
&
evolutionPathSigma
()
const
{
158
return
m_evolutionPathSigma
;
159
}
160
161
/** \brief Accesses the covariance matrix of the normal distribution used for generating offspring individuals. */
162
RealMatrix
const
&
covarianceMatrix
()
const
{
163
return
m_mutationDistribution
.
covarianceMatrix
();
164
}
165
166
/**
167
* \brief Accesses the recombination type.
168
*/
169
RecombinationType
recombinationType
()
const
{
170
return
m_recombinationType
;
171
}
172
173
/**
174
* \brief Returns a mutable reference to the recombination type.
175
*/
176
RecombinationType
&
recombinationType
() {
177
return
m_recombinationType
;
178
}
179
180
/**
181
* \brief Returns a const reference tothe lower bound on sigma times smalles eigenvalue.
182
*/
183
const
double
&
lowerBound
()
const
{
184
return
m_lowerBound
;
185
}
186
187
/**
188
* \brief Returns a mutable reference to the lower bound on sigma times smalles eigenvalue.
189
*/
190
double
&
lowerBound
() {
191
return
m_lowerBound
;
192
}
193
194
/**
195
* \brief Returns the size of the parent population \f$\mu\f$.
196
*/
197
std::size_t
mu
()
const
{
198
return
m_mu
;
199
}
200
201
/**
202
* \brief Returns a mutabl rference to the size of the parent population \f$\mu\f$.
203
*/
204
std::size_t&
mu
(){
205
return
m_mu
;
206
}
207
208
/**
209
* \brief Returns a immutable reference to the size of the offspring population \f$\mu\f$.
210
*/
211
std::size_t
lambda
()
const
{
212
return
m_lambda
;
213
}
214
215
/**
216
* \brief Returns a mutable reference to the size of the offspring population \f$\mu\f$.
217
*/
218
std::size_t &
lambda
(){
219
return
m_lambda
;
220
}
221
222
/**
223
* \brief Returns eigenvectors of covariance matrix (not considering step size)
224
*/
225
RealMatrix
const
&
eigenVectors
()
const
{
226
return
m_mutationDistribution
.
eigenVectors
();
227
}
228
229
/**
230
* \brief Returns a eigenvectors of covariance matrix (not considering step size)
231
*/
232
RealVector
const
&
eigenValues
()
const
{
233
return
m_mutationDistribution
.
eigenValues
();
234
}
235
236
/**
237
* \brief Returns condition of covariance matrix
238
*/
239
double
condition
()
const
{
240
RealVector
const
&
eigenValues
=
m_mutationDistribution
.
eigenValues
();
241
return
max
(eigenValues)/
min
(eigenValues);
242
}
243
244
245
protected
:
246
/**
247
* \brief Updates the strategy parameters based on the supplied offspring population.
248
*/
249
SHARK_EXPORT_SYMBOL
void
updateStrategyParameters
(
const
std::vector<
Individual<RealVector, double, RealVector>
> & offspring ) ;
250
251
std::size_t
m_numberOfVariables
;
///< Stores the dimensionality of the search space.
252
std::size_t
m_mu
;
///< The size of the parent population.
253
std::size_t
m_lambda
;
///< The size of the offspring population, needs to be larger than mu.
254
255
RecombinationType
m_recombinationType
;
///< Stores the recombination type.
256
257
double
m_sigma
;
258
double
m_cC
;
259
double
m_c1
;
260
double
m_cMu
;
261
double
m_cSigma
;
262
double
m_dSigma
;
263
double
m_muEff
;
264
265
double
m_lowerBound
;
266
267
RealVector
m_mean
;
268
RealVector
m_weights
;
269
270
RealVector
m_evolutionPathC
;
271
RealVector
m_evolutionPathSigma
;
272
273
std::size_t
m_counter
;
///< counter for generations
274
275
MultiVariateNormalDistribution
m_mutationDistribution
;
276
};
277
}
278
279
#endif