Simulated Annealing (Corana’s version)#

class simulated_annealing : public pagmo::not_population_based#

Simulated Annealing, Corana’s version with adaptive neighbourhood.

../../../_images/Hill_Climbing_with_Simulated_Annealing.gif

This version of the simulated annealing algorithm is, essentially, an iterative random search procedure with adaptive moves along the coordinate directions. It permits uphill moves under the control of metropolis criterion, in the hope to avoid the first local minima encountered.

The implementation provided here allows to obtain a reannealing procedure via subsequent calls to the pagmo::simulated_annealing::evolve() method.

See also

Corana, A., Marchesi, M., Martini, C., & Ridella, S. (1987). Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm Corrigenda for this article is available here. ACM Transactions on Mathematical Software (TOMS), 13(3), 262-280.

See also

https://people.sc.fsu.edu/~inavon/5420a/corana.pdf

Note

When selecting the starting and final temperature values it helps to think about the temperature as the deterioration in the objective function value that still has a 37% chance of being accepted.

Note

At each call of the evolve method the number of fitness evaluations will be n_T_adj * n_range_adj * bin_size times the problem dimension

Warning

The algorithm is not suitable for multi-objective problems, nor for constrained or stochastic optimization

Public Types

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

Single entry of the log (fevals, best, current, avg_range, temperature)

typedef std::vector<log_line_type> log_type#

The log.

Public Functions

simulated_annealing(double Ts = 10., double Tf = .1, unsigned n_T_adj = 10u, unsigned n_range_adj = 1u, unsigned bin_size = 20u, double start_range = 1., unsigned seed = pagmo::random_device::next())#

Constructor.

Constructs simulated_annealing

Parameters

  • Ts – starting temperature

  • Tf – final temperature

  • n_T_adj – number of temperature adjustments in the annealing schedule

  • n_range_adj – number of adjustments of the search range performed at a constant temperature

  • bin_size – number of mutations that are used to compute the acceptance rate

  • start_range – starting range for mutating the decision vector

  • seed – seed used by the internal random number generator

Throws

  • std::invalid_argument – if Ts or Tf are not finite and positive, start_range is not in (0,1], n_T_adj or n_range_adj are not strictly positive

  • std::invalid_argument – if Tf > Ts

population evolve(population) const#

Algorithm evolve method.

Parameters

pop – population to be evolved

Throws

  • std::invalid_argument – if the problem is multi-objective, constrained or stochastic

  • std::invalid_argument – if the population size is < 1u

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

  • >=1: will print and log one line at minimum every level fitness evaluations.

Example (verbosity 5000): 

Fevals:          Best:       Current:    Mean range:   Temperature:
 ...
 45035      0.0700823       0.135928     0.00116657      0.0199526
 50035      0.0215442      0.0261641    0.000770297           0.01
 55035     0.00551839      0.0124842    0.000559839     0.00501187
 60035     0.00284761     0.00703856    0.000314098     0.00251189
 65035     0.00264808      0.0114764    0.000314642     0.00125893
 70035      0.0011007     0.00293813    0.000167859    0.000630957
 75035    0.000435798     0.00184352    0.000126954    0.000316228
 80035    0.000287984    0.000825294    8.91823e-05    0.000158489
 85035     9.5885e-05    0.000330647    6.49981e-05    7.94328e-05
 90035     4.7986e-05    0.000148512    4.24692e-05    3.98107e-05
 95035    2.43633e-05    2.43633e-05    2.90025e-05    1.99526e-05

Fevals is the number of function evaluation used, Best is the best fitness function found, Current is the last fitness sampled, Mean range is the Mean search range across the decision vector components, Temperature is the current temperature.

Parameters

level – verbosity level

inline unsigned get_verbosity() const#

Gets the verbosity level.

Returns

the verbosity level

void set_seed(unsigned)#

Sets the seed.

Parameters

seed – the seed controlling the algorithm stochastic behaviour

inline unsigned get_seed() const#

Gets the seed.

Returns

the seed controlling the algorithm stochastic behaviour

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 simulated_annealing::log_line_type containing: Fevals, Best, Current, Mean range Temperature as described in simulated_annealing::set_verbosity

Returns

an std::vector of simulated_annealing::log_line_type containing the logged values Gen, Fevals, Best, Improvement, Mutations

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.