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