Class diff_evo (o2scl)

O2scl : Class List

template<class func_t = multi_funct, class vec_t = boost::numeric::ublas::vector<double>, class init_funct_t = mm_funct>
class diff_evo : public o2scl::mmin_base<multi_funct, multi_funct, boost::numeric::ublas::vector<double>>

Multidimensional minimization by the differential evolution method.

This class minimizes a function using differential evolution. This method is a genetic algorithm and as such works well for non continuous problems, since it does not require the gradient of the function to be minimized.

The method starts by initializing a the population of points in the parameter space. The user can specify a function which creates the initial population using set_init_function() . Alternatively, by default this class chooses random points near the initial point with a default step size of 0.01 in every direction. The step size can be changed using set_step() .

After the initial population is created the algorithm will repeat until a solution is found or the maximum number of iterations is reached.

The maximum total number of function calls is ntrial plus one times the population size, which defaults to 10 times the number of dimensions.

Based on [Storn97].

If the population converges prematurely, then diff_evo::f and pop_size should be increased.

Idea for Future:

AWS, 7/25/19, The code stops early if nconv generations go by without a better fit, but we could also consider some code which terminates early if the minimum is found to within a particular tolerance.

Idea for Future:

This class probably has a simple parallelization like o2scl::anneal_para ?

Note

The constructor sets o2scl::mmin_base::ntrial to 1000 .

Subclassed by o2scl::diff_evo_adapt< func_t, vec_t, init_funct_t >

Public Types

typedef boost::numeric::ublas::vector<double> ubvector

Public Functions

inline diff_evo()

inline virtual ~diff_evo()

inline virtual void set_init_function(init_funct_t &function)

Set the function that is used to select the initial population.

The init function is called in the beginning to fill the population with random individuals, so it is best to make this cover the part of the parameter space you are interested in. The method will find solutions outside this parameter space, but choosing a good init function will help finding solutions faster.

Note that this function stores a pointer to the user-specified function so care must be taken to ensure the pointer is still valid when the minimization is run.

inline virtual int mmin(size_t nvar, vec_t &x0, double &fmin, func_t &func)

Calculate the minimum fmin of func w.r.t the array x of size nvar.

Initialize all agents x with random positions in the search-space. Until a termination criterion is met (e.g. number of iterations performed, or adequate fitness reached), repeat the following: For each agent x in the population do: Pick three agents a, b, and c from the population at random, they must be distinct from each other as well as from agent x Pick a random index {1, …, n}, where the highest possible value n is the dimensionality of the problem to be optimized. Compute the agent’s potentially new position y = [y1, …, yn] by iterating over each i {1, …, n} as follows: Pick ri~U(0,1) uniformly from the open range (0,1) If (i=R) or (ri<CR) let yi = ai + F(bi - ci), otherwise let yi = xi If (f(y) < f(x)) then replace the agent in the population with the improved candidate solution, that is, set x = y in the population.

Pick the agent from the population that has the lowest fmin and return it as the best found candidate solution.

inline virtual void print_iter(size_t nvar, double fmin, int iter, vec_t &best_fit, size_t pop_size_loc)

Print out iteration information.

template<class vec2_t>
inline int set_step(size_t nv, vec2_t &stepv)

Set the step sizes for the default initialization.

Public Members

size_t pop_size

Population size (default 0)

Should be at least 4. Typically between \( 5 d \) and \( 10 d \) where \( d \) is the dimensionality of the problem.

If this is 0 (the default), then \( 10 d \) is used.

size_t nconv

The number of generations without a better fit before we assume that the algorithm has converged (default 25)

double f

Differential weight (default 0.75)

A parameter which controls the amplification of the differential variation. Usually between 0 and 2.

double cr

Crossover probability (default 0.8)

Usually between 0 and 1.

Protected Functions

inline virtual int initialize_population(size_t nvar, vec_t &x0, size_t pop_size_loc)

Initialize a population of random agents.

inline virtual std::vector<int> pick_unique_agents(int nr, size_t x, size_t pop_size_loc)

Pick number of unique agent id’s.

Unique from x and each other

Uses the Fisher-Yates algorithm.

Idea for Future:

AWS, 7/25/19: GSL may have a better Fisher-Yates implementation we should use here. Or is it in the o2scl::permutation class?

Protected Attributes

vec_t population

Vector containing the population.

A long vector with all agents after each other

ubvector fmins

Vector that keeps track of the function values.

init_funct_t *rand_init_funct

Function that is used to produce random init variables.

This function is used to fill the population with random agents

rng gr

Random number generator.

std::vector<double> step

Step size for initialization.

Private Functions

diff_evo(const diff_evo<func_t, vec_t, init_funct_t>&)

diff_evo<func_t, vec_t, init_funct_t> &operator=(const diff_evo<func_t, vec_t, init_funct_t>&)