QuantLib: a free/open-source library for quantitative finance
fully annotated source code - version 1.34
Loading...
Searching...
No Matches
hybridsimulatedannealing.hpp
Go to the documentation of this file.
1/* -*- mode: c++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
3/*
4Copyright (C) 2015 Andres Hernandez
5
6This file is part of QuantLib, a free-software/open-source library
7for financial quantitative analysts and developers - http://quantlib.org/
8
9QuantLib is free software: you can redistribute it and/or modify it
10under the terms of the QuantLib license. You should have received a
11copy of the license along with this program; if not, please email
12<quantlib-dev@lists.sf.net>. The license is also available online at
13<http://quantlib.org/license.shtml>.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the license for more details.
18*/
19
20/*! \file hybridsimulatedannealing.hpp
21\brief Implementation based on:
22Very Fast Simulated Re-Annealing, Lester Ingber,
23Mathl. Comput. Modelling, 967-973, 1989
24*/
25
26#ifndef quantlib_optimization_hybridsimulatedannealing_hpp
27#define quantlib_optimization_hybridsimulatedannealing_hpp
28
33#include <utility>
34
35namespace QuantLib {
36
37 /*! Method is fairly straightforward:
38 1) Sampler provides a probability density (based on current value) for the parameters. Each
39 iteration a new draw is made from it to find a new point
40 2) Probability determines whether the new point, obtained from Sampler, is accepted or not
41 3) Temperature is a schedule T(k) for the iteration k, which affects the Sampler and Probability
42 4) Reannealing is a departure from the traditional Boltzmann Annealing method: it rescales
43 the iteration k independently for each dimension so as to improve convergence
44
45 The hybrid in the name is because one can provide it a local optimizer for use whenever any new
46 best point is found or at every accepted point, in which case is used is chose by the user.
47
48 Class Sampler must implement the following interface:
49 \code
50 void operator()(Array &newPoint, const Array &currentPoint, const Array &temp) const;
51 \endcode
52 Class Probability must implement the following interface:
53 \code
54 bool operator()(Real currentValue, Real newValue, const Array &temp) const;
55 \endcode
56 Class Temperature must implement the following interface:
57 \code
58 void operator()(Array &newTemp, const Array &currTemp, const Array &steps) const;
59 \endcode
60 Class Reannealing must implement the following interface:
61 \code
62 void operator()(Array & steps, const Array &currentPoint,
63 Real aCurrentValue, const Array & currTemp) const;
64 \endcode
65 */
66 template <class Sampler, class Probability, class Temperature, class Reannealing = ReannealingTrivial>
68 public:
73 };
78 };
79
80 HybridSimulatedAnnealing(const Sampler& sampler,
81 const Probability& probability,
82 Temperature temperature,
83 const Reannealing& reannealing = ReannealingTrivial(),
84 Real startTemperature = 200.0,
85 Real endTemperature = 0.01,
86 Size reAnnealSteps = 50,
87 ResetScheme resetScheme = ResetToBestPoint,
88 Size resetSteps = 150,
89 ext::shared_ptr<OptimizationMethod> localOptimizer =
90 ext::shared_ptr<OptimizationMethod>(),
91 LocalOptimizeScheme optimizeScheme = EveryBestPoint)
92 : sampler_(sampler), probability_(probability), temperature_(std::move(temperature)),
93 reannealing_(reannealing), startTemperature_(startTemperature),
94 endTemperature_(endTemperature),
95 reAnnealSteps_(reAnnealSteps == 0 ? QL_MAX_INTEGER : reAnnealSteps),
96 resetScheme_(resetScheme), resetSteps_(resetSteps == 0 ? QL_MAX_INTEGER : resetSteps),
97 localOptimizer_(localOptimizer),
98 optimizeScheme_(localOptimizer != nullptr ? optimizeScheme : NoLocalOptimize) {
99 if (!localOptimizer)
100 localOptimizer.reset(new LevenbergMarquardt);
101 }
102
103 EndCriteria::Type minimize(Problem& P, const EndCriteria& endCriteria) override;
104
105 private:
106 Sampler sampler_;
108 Temperature temperature_;
109 Reannealing reannealing_;
115 ext::shared_ptr<OptimizationMethod> localOptimizer_;
117 };
118
119 template <class Sampler, class Probability, class Temperature, class Reannealing>
122 P.reset();
123 reannealing_.setProblem(P);
124 Array x = P.currentValue();
125 Size n = x.size();
126 Size k = 1;
127 Size kStationary = 1;
128 Size kReAnneal = 1;
129 Size kReset = 1;
130 Size maxK = endCriteria.maxIterations();
131 Size maxKStationary = endCriteria.maxStationaryStateIterations();
132 bool temperatureBreached = false;
133 Array currentTemperature(n, startTemperature_);
134 Array annealStep(n, 1.0);
135 Array bestPoint(x);
136 Array currentPoint(x);
137 const Array& startingPoint(x);
138 Array newPoint(x);
139 Real bestValue = P.value(bestPoint);
140 Real currentValue = bestValue;
141 Real startingValue = bestValue; //to reset to starting point if desired
142 while (k <= maxK && kStationary <= maxKStationary && !temperatureBreached)
143 {
144 //Draw a new sample point
145 sampler_(newPoint, currentPoint, currentTemperature);
146 try{
147 //Evaluate new point
148 Real newValue = P.value(newPoint);
149
150 //Determine if new point is accepted
151 if (probability_(currentValue, newValue, currentTemperature)) {
152 if (optimizeScheme_ == EveryNewPoint) {
153 P.setCurrentValue(newPoint);
154 P.setFunctionValue(newValue);
155 localOptimizer_->minimize(P, endCriteria);
156 newPoint = P.currentValue();
157 newValue = P.functionValue();
158 }
159 currentPoint = newPoint;
160 currentValue = newValue;
161 }
162
163 //Check if we have a new best point
164 if (newValue < bestValue) {
165 if (optimizeScheme_ == EveryBestPoint) {
166 P.setCurrentValue(newPoint);
167 P.setFunctionValue(newValue);
168 localOptimizer_->minimize(P, endCriteria);
169 newPoint = P.currentValue();
170 newValue = P.functionValue();
171 }
172 kStationary = 0;
173 bestValue = newValue;
174 bestPoint = newPoint;
175 }
176 } catch(...){
177 //Do nothing, move on to new draw
178 }
179 //Increase steps
180 k++;
181 kStationary++;
182 for (Real& i : annealStep)
183 i++;
184
185 //Reanneal if necessary
186 if (kReAnneal == reAnnealSteps_) {
187 kReAnneal = 0;
188 reannealing_(annealStep, currentPoint, currentValue, currentTemperature);
189 }
190 kReAnneal++;
191
192 //Reset if necessary
193 if (kReset == resetSteps_) {
194 kReset = 0;
195 switch (resetScheme_) {
196 case NoResetScheme:
197 break;
198 case ResetToOrigin:
199 currentPoint = startingPoint;
200 currentValue = startingValue;
201 break;
202 case ResetToBestPoint:
203 currentPoint = bestPoint;
204 currentValue = bestValue;
205 break;
206 }
207 }
208 kReset++;
209
210 //Update the current temperature according to current step
211 temperature_(currentTemperature, currentTemperature, annealStep);
212
213 //Check if temperature condition is breached
214 for (Size i = 0; i < n; i++)
215 temperatureBreached = temperatureBreached && currentTemperature[i] < endTemperature_;
216 }
217
218 //Change end criteria type if appropriate
219 if (k > maxK)
221 else if (kStationary > maxKStationary)
223
224 //Set result to best point
225 P.setCurrentValue(bestPoint);
226 P.setFunctionValue(bestValue);
227 return ecType;
228 }
229
236}
237
238#endif
1-D array used in linear algebra.
Definition: array.hpp:52
Size size() const
dimension of the array
Definition: array.hpp:495
Criteria to end optimization process:
Definition: endcriteria.hpp:40
Size maxIterations() const
Size maxStationaryStateIterations() const
ext::shared_ptr< OptimizationMethod > localOptimizer_
HybridSimulatedAnnealing(const Sampler &sampler, const Probability &probability, Temperature temperature, const Reannealing &reannealing=ReannealingTrivial(), Real startTemperature=200.0, Real endTemperature=0.01, Size reAnnealSteps=50, ResetScheme resetScheme=ResetToBestPoint, Size resetSteps=150, ext::shared_ptr< OptimizationMethod > localOptimizer=ext::shared_ptr< OptimizationMethod >(), LocalOptimizeScheme optimizeScheme=EveryBestPoint)
EndCriteria::Type minimize(Problem &P, const EndCriteria &endCriteria) override
minimize the optimization problem P
Levenberg-Marquardt optimization method.
Abstract class for constrained optimization method.
Definition: method.hpp:36
Constrained optimization problem.
Definition: problem.hpp:42
const Array & currentValue() const
current value of the local minimum
Definition: problem.hpp:81
Real functionValue() const
value of cost function
Definition: problem.hpp:88
Real value(const Array &x)
call cost function computation and increment evaluation counter
Definition: problem.hpp:116
void setFunctionValue(Real functionValue)
Definition: problem.hpp:83
void setCurrentValue(const Array &currentValue)
Definition: problem.hpp:76
Abstract constraint class.
#define QL_MAX_INTEGER
Definition: qldefines.hpp:174
QL_REAL Real
real number
Definition: types.hpp:50
Real Probability
probability
Definition: types.hpp:82
std::size_t Size
size of a container
Definition: types.hpp:58
Functors for use on HybridSimulatedAnnealing.
Levenberg-Marquardt optimization method.
Definition: any.hpp:35
HybridSimulatedAnnealing< SamplerLogNormal, ProbabilityBoltzmannDownhill, TemperatureExponential, ReannealingTrivial > LogNormalSimulatedAnnealing
HybridSimulatedAnnealing< SamplerVeryFastAnnealing, ProbabilityBoltzmannDownhill, TemperatureVeryFastAnnealing, ReannealingFiniteDifferences > VeryFastSimulatedReAnnealing
HybridSimulatedAnnealing< SamplerVeryFastAnnealing, ProbabilityBoltzmannDownhill, TemperatureVeryFastAnnealing, ReannealingTrivial > VeryFastSimulatedAnnealing
HybridSimulatedAnnealing< SamplerGaussian, ProbabilityBoltzmannDownhill, TemperatureExponential, ReannealingFiniteDifferences > GaussianSimulatedReAnnealing
HybridSimulatedAnnealing< SamplerGaussian, ProbabilityBoltzmannDownhill, TemperatureExponential, ReannealingTrivial > GaussianSimulatedAnnealing
HybridSimulatedAnnealing< SamplerMirrorGaussian, ProbabilityBoltzmannDownhill, TemperatureExponential, ReannealingTrivial > MirrorGaussianSimulatedAnnealing
STL namespace.
Abstract optimization problem class.