ExtremalOptimization

for functions of continuous variables.

Build Status

This package implements the basic mechanism of Extremal Optimization (τ-EO) as described in Boettcher, Stefan; Percus, Allon G. (2001-06-04). "Optimization with Extremal Dynamics". Physical Review Letters.

The only twist w.r.t. classical EO is an affine invariant update equation for the worst performing solutions,

where X₁, X₂, X₃ are chosen random inside the pool of candidate solutions, this update mechanism allows EO to work on continuous spaces, and be invariant w.r.t. affine transformations of X and monotonous tranformations of the cost function.

API:

function optimize(
    f,
    s,
    N;
    reps_per_particle = 100,
    β = 1.0,
    τ = 1.2,
    atol = 0.0,
    rtol = sqrt(eps(1.0)),
    f_atol = 0.0,
    f_rtol = sqrt(eps(1.0)),
    verbose = false,
    rng = Random.GLOBAL_RNG,
    callback = state -> nothing,
)
  • f : cost function to minimize, whose argument is either a scalar or a vector, must returns a scalar value.
  • s : function whose input is the particle number and output is a random initial point to be ranked by f.
  • N : number of particles to use, choose a number greater than d+4 where d is the number of dimensions.
  • reps_per_particle : maximum number of iterations per particle.

Usage example:

using ExtremalOptimization
rosenbrock2d(x) = (x[1]-1)^2+(x[2]-x[1]^2)^2
initpoint(i) = randn(2)
optimize(rosenbrock2d, initpoint, 50)

output

(x = [1.000000001, 1.000000004], fx = 4.0e-18, f_nevals = 2726)

as expected the algorithm has found the optimum at (1, 1), up to the specified tolerance.