Simulated Annealing (SA)

class pypop7.optimizers.sa.sa.SA(problem, options)[source]

Simulated Annealing (SA).

This is the abstract class for all SA classes. Please use any of its instantiated subclasses to optimize the black-box problem at hand.

Note

“Typical advantages of SA algorithms are their very mild memory requirements and the small computational effort per iteration.”—[Bouttier&Gavra, 2019, JMLR]

“The SA algorithm can also be viewed as a local search algorithm in which there are occasional upward moves that lead to a cost increase. One hopes that such upward moves will help escape from local minima.”—[Bertsimas&Tsitsiklis, 1993, Statistical Science]

Parameters:

  • problem (dict) –

    problem arguments with the following common settings (keys):

    • ’fitness_function’ - objective function to be minimized (func),

    • ’ndim_problem’ - number of dimensionality (int),

    • ’upper_boundary’ - upper boundary of search range (array_like),

    • ’lower_boundary’ - lower boundary of search range (array_like).

  • options (dict) –

    optimizer options with the following common settings (keys):

    • ’max_function_evaluations’ - maximum of function evaluations (int, default: np.Inf),

    • ’max_runtime’ - maximal runtime to be allowed (float, default: np.Inf),

    • ’seed_rng’ - seed for random number generation needed to be explicitly set (int);

    and with the following particular settings (keys):

    • ’temperature’ - annealing temperature (float),

    • ’x’ - initial (starting) point (array_like).

temperature

annealing temperature.

Type:

float

x

initial (starting) point.

Type:

array_like

References

Bouttier, C. and Gavra, I., 2019. Convergence rate of a simulated annealing algorithm with noisy observations. Journal of Machine Learning Research, 20(1), pp.127-171. https://www.jmlr.org/papers/v20/16-588.html

Siarry, P., Berthiau, G., Durdin, F. and Haussy, J., 1997. Enhanced simulated annealing for globally minimizing functions of many-continuous variables. ACM Transactions on Mathematical Software, 23(2), pp.209-228. https://dl.acm.org/doi/abs/10.1145/264029.264043

Bertsimas, D. and Tsitsiklis, J., 1993. Simulated annealing. Statistical Science, 8(1), pp.10-15. https://tinyurl.com/yknunnpt

Corana, A., Marchesi, M., Martini, C. and Ridella, S., 1987. Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm. ACM Transactions on Mathematical Software, 13(3), pp.262-280. https://dl.acm.org/doi/abs/10.1145/29380.29864 https://dl.acm.org/doi/10.1145/66888.356281

Szu, H.H. and Hartley, R.L., 1987. Nonconvex optimization by fast simulated annealing. Proceedings of the IEEE, 75(11), pp.1538-1540.

Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P., 1983. Optimization by simulated annealing. Science, 220(4598), pp.671-680. https://science.sciencemag.org/content/220/4598/671

Hastings, W.K., 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), pp.97-109. https://academic.oup.com/biomet/article/57/1/97/284580

Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E., 1953. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6), pp.1087-1092. https://aip.scitation.org/doi/abs/10.1063/1.1699114

SAs: