Extra Utilities¶
SimulatedAnnealing¶
Included in src/util/SimulatedAnnealing.hh
is a general purpose algorithm for globally minimizing a D dimensional continuous
function that contains many local minima. Effectively this is a hybrid between the
Nelder-Mead downhill simplex method
and simulated annealing as
described in section 10.9 of Numerical Recipes in 'C'
but reimplemented in a
less confusing way for C++.
Usage¶
The SimulatedAnnealing
class is templated to the dimensionality of function
to be minimized. The constructor
SimulatedAnnealing(Minimizable *func)
takes a single argument that is an object implementing the pure virtual Minimizable
class.
Minimizable
only requires that the object implement the call operator as follows
virtual double operator()(double *args);
where the result is the value of the function evaluated at function(args[0],…,args[D]).
After creating the SimulatedAnnealing
object, set the initial simplex using
void SetSimplexPoint(size_t pt, std::vector<double> &point)
where pt
specifies the index of the point you are setting [0, D], i.e. D+1 required points,
and the simplex is copied from the D length vector point
.
Once the initial D+1 simplex points are specified, call the Anneal
method to actually minimize
void Anneal(double temp0, size_t nAnneal, size_t nEval, double alpha)
where temp0
is the initial temperature and alpha
controls the temperature according to the
annealing schedule T = temp0
* (1 - cycle
/ nAnneal
) ^ alpha
. The annealing is run at nAnneal
different temperatures ( cycle
) where each cycle
tests nEval
new points.
Once the algorithm has finished GetBestPoint
will return the tested point with the lowest function
value in the last Anneal
cycle
void GetBestPoint(std::vector<double> &point)
where the best point will be copied into the D length vector point
.
Example¶
As a concrete example, to minimize f(x,y) = x^A+y^B with A=B=2, first implement the Minimizable
function
class Func : public Minimizable {
public:
double A,B;
Func(double _A, double _B) : A(_A), B(_B) { };
virtual double operator()(double *params) {
return pow(params[0],A) + pow(params[1],B);
}
}
Then the code to minimize would look something like this
Func func(2.0,2.0); //A = B = 2.0
SimulatedAnnealing<2> anneal(func);
vector<double> point(2), seed(2);
seed[0] = seed[1] = -1.0;
anneal.SetSimplexPoint(0,seed); // Point0 -> (-1,-1)
seed[0] = 1.0;
anneal.SetSimplexPoint(1,seed); // Point1 -> (1,-1)
seed[1] = 1.0;
anneal.SetSimplexPoint(2,seed); // Point2 -> (1,1)
anneal.Anneal(10,150,50,4.0); // Minimize
anneal.GetBestPoint(point);
cout << point[0] << ',' << point[1] << endl;