i made a super tiny package which could be useful to people attempting to optimize functions which have many multiple local minima and/or jumps, this algorithm finds solutions via a non-greedy policy, it does not improve on the best solutions, it improves the worst solutions in a rejection-free approach, this package is still in the process of being registered, let me know if you have suggestions or if you find it useful in your work
for functions of continuous variables.
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.
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
N: number of particles to use, choose a number greater than
dis the number of dimensions.
reps_per_particle: maximum number of iterations per particle.
using ExtremalOptimization rosenbrock2d(x) = (x-1)^2+(x-x^2)^2 initpoint(i) = randn(2) optimize(rosenbrock2d, initpoint, 50)
(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.