Simulated Annealing (SA)

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

Simulated Annealing (SA).

This is the abstract class for all Simulated Annealing (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]

For its pytest based testing, please refer to this Python code.

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

Bras, P., 2024. Convergence of Langevin-simulated annealing algorithms with multiplicative noise. Mathematics of Computation, 93(348), pp.1761-1803.

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.

Lecchini-Visintini, A., Lygeros, J. and Maciejowski, J., 2007. Simulated annealing: Rigorous finite-time guarantees for optimization on continuous domains. Advances in Neural Information Processing Systems, 20.

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.

Granville, V., Krivánek, M. and Rasson, J.P., 1994. Simulated annealing: A proof of convergence. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(6), pp.652-656.

Bertsimas, D. and Tsitsiklis, J., 1993. Simulated annealing. Statistical Science, 8(1), pp.10-15.

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/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.

Hastings, W.K., 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), pp.97-109.

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.

SAs: