Parallel Optimizer library

Jun 15, 2013, tags: c++

I have been working on a project over the last year where I have to evaluate a large set of parameters in a potentially high-dimensional space. Because of this, I implemented a particle-swarm optimizer. The algorithm searches for the X that minimizes f(X) with the goal of converging to a solution as fast as possible given an arbitrary energy-landscape. Exhaustive search is simply infeasible in this high-dimensional search-space.

Later I added multithreading capabilities to the code for faster convergence because the evaluation of many f(X) is very easy to run in parallel.

Eventually I realized that the library might actually stand on its own so I cleaned it up and wrote some documentation and put the library on github.

The Rosenbrock-example uses the Parallel-Optimizer-Library to quickly find a minimum value for the Rosenbrock test-function. The source-code of the example explains the major parts in setting up the search:

#include "Optimizer/Optimizer.h"
#include "Optimizer/ParticleSwarmOptimization.h"

// For this example, we would like to minimize the Rosenbrock function.
// A class Rosenbrock is created to contain the details of our problem.
// The Rosenbrock class inherits PAO::OptimizationWorker which adds 
// the parallel processing capabilities.

class Rosenbrock : public PAO::OptimizationWorker
{
public:
    // In the constructor we use setParameterBounds to describe the
    // parameter-space we would like to search:
    Rosenbrock() {
        PAO::ParameterBounds b;
        for (int i=0; i<Dimensions; ++i)
        b.registerParameter(-L/2, L/2);

        setParameterBounds(b);
    }

    // PAO::OptimizationWorker requires the fitnessFunction method
    // to be implemented. This function should implement our f(X) 
    // and return the value of said function.
    double fitnessFunction (PAO::Parameters &X) {
        double sum=0;
        for (int i=0; i<Dimensions-1; ++i)
            sum += 100*pow( X[i+1] - X[i]*X[i], 2) + pow(X[i]-1, 2);

        return sum;
    }

    private:
    // Other than implementing fitnessFunction and supplying
    // parameter-bounds as seen above, there are no other requirements.

    const int Dimensions=3; // Dimensions of search-space
    const double L=100; // Length of dimension searched
};


int main()
{
    // Ask the system for number of supported threads
    int numWorkers = std::thread::hardware_concurrency();   

    // The optimizer takes a vector of OptimizationWorker*'s as argument
    // where each worker runs in parallell during optimization.
    // Here we create that vector:
    std::vector<PAO::OptimizationWorker*> workers;
    for (int i=0; i<numWorkers; ++i) {
        Rosenbrock *w = new Rosenbrock;
        workers.push_back( (PAO::OptimizationWorker*) w );      
    }

    // Here we specify some parameters for the particle swarm
    // optimization algorithm.
    PAO::PSOParameters psoparams;
    psoparams.swarms = 3;
    psoparams.particleCount = 1000;
    psoparams.generations = 100;
    psoparams.variant = PAO::NeighborhoodBest;

    // When instantiating a ParticleSwarmOptimzer, we supply 
    // a vector of OptimizationWorkers and the algorithm's parameters.
    PAO::ParticleSwarmOptimizer PSO( workers, psoparams );

    // Set a callback for when a new minimum value is found
    // printNewMinimum(...) is a small function that prints the new value
    PSO.setCallbackNewMinimum(printNewMinimum);

    // Now all that remains is to start the optimization.
    double y = PSO.optimize();  

    std::cout << "Best value found is "<<y<<std::endl;

    for (int i=0; i<numWorkers; ++i)
        delete workers[i];

    return 0;
}

For a quick demonstration, clone and build the library and run the Rosenbrock example with

git clone git://github.com/PureW/Parallel-Optimizer-Library.git
cd Parallel-Optimizer-Library
./waf configure
./waf build_release
./build/release/rosenbrock