Multidimensional minimization by the differential evolution method. More...
#include <diff_evo.h>
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. Based on Storn97.
If the population converges prematurely, then diff_evo::f and pop_size should be increased.
Definition at line 76 of file diff_evo.h.
Public Types | |
typedef boost::numeric::ublas::vector< double > | ubvector |
Public Member Functions | |
virtual void | set_init_function (init_funct_t &function) |
Set the function that is used to select the initial population. More... | |
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 . More... | |
virtual void | print_iter (size_t nvar, double fmin, int iter, vec_t &best_fit) |
Print out iteration information. More... | |
template<class vec2_t > | |
int | set_step (size_t nv, vec2_t &stepv) |
Set the step sizes for the default initialization. | |
![]() | |
mmin_base (const mmin_base< multi_funct, multi_funct, boost::numeric::ublas::vector< double > > &mb) | |
Copy constructor. | |
int | set_verbose_stream (std::ostream &out, std::istream &in) |
Set streams for verbose I/O. More... | |
virtual int | mmin (size_t nvar, boost::numeric::ublas::vector< double > &x, double &fmin, multi_funct &func)=0 |
Calculate the minimum min of func w.r.t. the array x of size nvar . | |
virtual int | mmin_de (size_t nvar, boost::numeric::ublas::vector< double > &x, double &fmin, multi_funct &func, multi_funct &dfunc) |
Calculate the minimum min of func w.r.t. the array x of size nvar with gradient dfunc . | |
int | print_iter (size_t nv, vec2_t &x, double y, int iter, double value, double limit, std::string comment) |
Print out iteration information. More... | |
const char * | type () |
Return string denoting type ("mmin_base") | |
mmin_base< multi_funct, multi_funct, boost::numeric::ublas::vector< double > > & | operator= (const mmin_base< multi_funct, multi_funct, boost::numeric::ublas::vector< double > > &mb) |
Copy constructor from operator=. | |
Public Attributes | |
size_t | pop_size |
Population size (default 0) More... | |
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) More... | |
double | cr |
Crossover probability (default 0.8) More... | |
![]() | |
int | verbose |
Output control. | |
int | ntrial |
Maximum number of iterations. | |
double | tol_rel |
Function value tolerance. | |
double | tol_abs |
The independent variable tolerance. | |
int | last_ntrial |
The number of iterations for in the most recent minimization. | |
bool | err_nonconv |
If true, call the error handler if the routine does not "converge". | |
Protected Member Functions | |
virtual int | initialize_population (size_t nvar, vec_t &x0) |
Initialize a population of random agents. | |
virtual std::vector< int > | pick_unique_agents (int nr, size_t x) |
Pick number of unique agent id's. More... | |
Protected Attributes | |
vec_t | population |
Vector containing the population. More... | |
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. More... | |
rng_gsl | gr |
Random number generator. | |
std::vector< double > | step |
Step size for initialization. | |
![]() | |
std::ostream * | outs |
Stream for verbose output. | |
std::istream * | ins |
Stream for verbose input. | |
Private Member 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 > &) |
|
inlinevirtual |
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.
Definition at line 165 of file diff_evo.h.
|
inlineprotectedvirtual |
Unique from x and each other
Uses the Fisher-Yates algorithm.
Definition at line 384 of file diff_evo.h.
|
inlinevirtual |
Definition at line 292 of file diff_evo.h.
|
inlinevirtual |
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.
Definition at line 139 of file diff_evo.h.
double o2scl::diff_evo< func_t, vec_t, init_funct_t >::cr |
Usually between 0 and 1.
Definition at line 109 of file diff_evo.h.
double o2scl::diff_evo< func_t, vec_t, init_funct_t >::f |
A parameter which controls the amplification of the differential variation. Usually between 0 and 2.
Definition at line 103 of file diff_evo.h.
size_t o2scl::diff_evo< func_t, vec_t, init_funct_t >::pop_size |
Should be at least 4. Typically between and
where
is the dimensionality of the problem.
If this is 0 (the default), then it is set by mmin to be equal to .
Definition at line 91 of file diff_evo.h.
|
protected |
A long vector with all agents after each other
Definition at line 333 of file diff_evo.h.
|
protected |
This function is used to fill the population with random agents
Definition at line 342 of file diff_evo.h.
Documentation generated with Doxygen. Provided under the
GNU Free Documentation License (see License Information).