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. 385-482 (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 pion-proton 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. 385-482 (2003)

Note

This algorithm does not work for multi-objective problems, nor for stochastic problems.

Note

The search range is defined relative to the box-bounds. 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 multi-objective 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:          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.10352e-05
    139        95.4515              0              0    3.05176e-05
    143        95.4502              0              0    3.05176e-05
    151        95.4502              0              0    1.52588e-05
    159        95.4502              0              0    7.62939e-06
Exit condition -- range: 7.62939e-06 <= 1e-05

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 search

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 user-defined algorithm (UDA).

Returns

a string containing the algorithm name

std::string get_extra_info() const

Extra info.

One of the optional methods of any user-defined 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 an std::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 an std::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.