Compass Search
Compass Search#

class compass_search : public pagmo::not_population_based#
The Compass Search Solver (CS)
In the review paper by Kolda, Lewis, Torczon: ‘Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods’ published in the SIAM Journal Vol. 45, No. 3, pp. 385482 (2003), the following description of the compass search algorithm is given:
‘Davidon describes what is one of the earliest examples of a direct search method used on a digital computer to solve an optimization problem: Enrico Fermi and Nicholas Metropolis used one of the first digital computers, the Los Alamos Maniac, to determine which values of certain theoretical parameters (phase shifts) best fit experimental data (scattering cross sections). They varied one theoretical parameter at a time by steps of the same magnitude, and when no such increase or decrease in any one parameter further improved the fit to the experimental data, they halved the step size and repeated the process until the steps were deemed sufficiently small. Their simple procedure was slow but sure, and several of us used it on the Avidac computer at the Argonne National Laboratory for adjusting six theoretical parameters to fit the pionproton scattering data we had gathered using the University of Chicago synchrocyclotron. While this basic algorithm undoubtedly predates Fermi and Metropolis, it has remained a standard in the scientific computing community for exactly the reason observed by Davidon: it is slow but sure’.
See also
Kolda, Lewis, Torczon: ‘Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods’ published in the SIAM Journal Vol. 45, No. 3, pp. 385482 (2003)
Note
This algorithm does not work for multiobjective problems, nor for stochastic problems.
Note
The search range is defined relative to the boxbounds. Hence, unbounded problems will produce an error.
Note
Compass search is a fully deterministic algorithms and will produce identical results if its evolve method is called from two identical populations.
Public Types

typedef std::tuple<unsigned long long, double, vector_double::size_type, double, double> log_line_type#
Single entry of the log (feval, best fitness, n. constraints violated, violation norm, range)

typedef std::vector<log_line_type> log_type#
The log.
Public Functions

compass_search(unsigned max_fevals = 1, double start_range = .1, double stop_range = .01, double reduction_coeff = .5)#
Constructor.
Constructs compass_search
 Parameters
max_fevals – maximum number of fitness evaluations
start_range – start range
stop_range – stop range
reduction_coeff – range reduction coefficient
 Throws
std::invalid_argument – if
start_range
is not in (0,1]std::invalid_argument – if
stop_range
is not in (start_range,1]std::invalid_argument – if
reduction_coeff
is not in (0,1)

population evolve(population) const#
Algorithm evolve method (juice implementation of the algorithm)
Evolves the population up to when the search range becomes smaller than the defined stop_range
 Parameters
pop – population to be evolved
 Throws
std::invalid_argument – if the problem is multiobjective or stochastic
std::invalid_argument – if the population is empty
 Returns
evolved population

inline void set_verbosity(unsigned level)#
Sets the algorithm verbosity.
Sets the verbosity level of the screen output and of the log returned by get_log().
level
can be:0: no verbosity
>0: will print and log one line each objective function improvement, or range reduction
Example (verbosity > 0u):
Fevals, is the number of fitness evaluations made, Best is the best fitness Violated and Viol.Norm are the number of constraints violated and the L2 norm of the violation (accounting for the tolerances returned by problem::get_c_tol, and Range is the range used at that point of the searchFevals: Best: Violated: Viol. Norm: Range: 4 110.785 1 2.40583 0.5 12 110.785 1 2.40583 0.25 20 110.785 1 2.40583 0.125 22 91.0454 1 1.01855 0.125 25 96.2795 1 0.229446 0.125 33 96.2795 1 0.229446 0.0625 41 96.2795 1 0.229446 0.03125 .. ....... . ........ 0.03125 111 95.4617 1 0.00117433 0.000244141 115 95.4515 0 0 0.000244141 123 95.4515 0 0 0.00012207 131 95.4515 0 0 6.10352e05 139 95.4515 0 0 3.05176e05 143 95.4502 0 0 3.05176e05 151 95.4502 0 0 1.52588e05 159 95.4502 0 0 7.62939e06 Exit condition  range: 7.62939e06 <= 1e05
 Parameters
level – verbosity level

inline unsigned get_verbosity() const#
Gets the verbosity level.
 Returns
the verbosity level

inline double get_max_fevals() const#
Gets the maximum number of iterations allowed.
 Returns
the maximum number of iterations allowed

inline double get_stop_range() const#
Gets the stop_range.
 Returns
the stop range

inline double get_start_range() const#
Get the start range.
 Returns
the start range

inline double get_reduction_coeff() const#
Get the reduction_coeff.
 Returns
the reduction coefficient

inline std::string get_name() const#
Algorithm name.
One of the optional methods of any userdefined algorithm (UDA).
 Returns
a string containing the algorithm name

std::string get_extra_info() const#
Extra info.
One of the optional methods of any userdefined algorithm (UDA).
 Returns
a string containing extra info on the algorithm

inline const log_type &get_log() const#
Get log.
A log containing relevant quantities monitoring the last call to evolve. Each element of the returned
std::vector
is a compass_search::log_line_type containing: Fevals, Best, Violated and Viol.Norm, Range as described in compass_search::set_verbosity Returns
an
std::vector
of compass_search::log_line_type containing the logged values Fevals, Best, Range

void set_random_sr_seed(unsigned)#
Set the seed for the
"random"
selection/replacement policies. Parameters
seed – the value that will be used to seed the random number generator used by the
"random"
selection/replacement policies.

void set_selection(const std::string&)#
Set the individual selection policy.
This method will set the policy that is used to select the individual that will be optimised when calling the
evolve()
method of the algorithm.The input string must be one of
"best"
,"worst"
and"random"
:"best"
will select the best individual in the population,"worst"
will select the worst individual in the population,"random"
will randomly choose one individual in the population.
set_random_sr_seed() can be used to seed the random number generator used by the
"random"
policy.Instead of a selection policy, a specific individual in the population can be selected via set_selection(population::size_type).
 Parameters
select – the selection policy.
 Throws
std::invalid_argument – if
select
is not one of"best"
,"worst"
or"random"
.

inline void set_selection(population::size_type n)#
Set the individual selection index.
This method will set the index of the individual that is selected for optimisation in the
evolve()
method of the algorithm. Parameters
n – the index in the population of the individual to be selected for optimisation.

boost::any get_selection() const#
Get the individual selection policy or index.
This method will return a
boost::any
containing either the individual selection policy (as anstd::string
) or the individual selection index (as a population::size_type). The selection policy or index is set via set_selection(const std::string &) and set_selection(population::size_type). Returns
the individual selection policy or index.

void set_replacement(const std::string&)#
Set the individual replacement policy.
This method will set the policy that is used in the
evolve()
method of the algorithm to select the individual that will be replaced by the optimised individual.The input string must be one of
"best"
,"worst"
and"random"
:"best"
will select the best individual in the population,"worst"
will select the worst individual in the population,"random"
will randomly choose one individual in the population.
set_random_sr_seed() can be used to seed the random number generator used by the
"random"
policy.Instead of a replacement policy, a specific individual in the population can be selected via set_replacement(population::size_type).
 Parameters
replace – the replacement policy.
 Throws
std::invalid_argument – if
replace
is not one of"best"
,"worst"
or"random"
.

inline void set_replacement(population::size_type n)#
Set the individual replacement index.
This method will set the index of the individual that is replaced after the optimisation in the
evolve()
method of the algorithm. Parameters
n – the index in the population of the individual to be replaced after the optimisation.

boost::any get_replacement() const#
Get the individual replacement policy or index.
This method will return a
boost::any
containing either the individual replacement policy (as anstd::string
) or the individual replacement index (as a population::size_type). The replacement policy or index is set via set_replacement(const std::string &) and set_replacement(population::size_type). Returns
the individual replacement policy or index.

typedef std::tuple<unsigned long long, double, vector_double::size_type, double, double> log_line_type#