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;