Coverage for moptipy / algorithms / so / simulated_annealing.py: 98%

1""" 

2The simulated annealing algorithm with configurable temperature schedule. 

3 

4A basic randomized local search (:mod:`~moptipy.algorithms.so.rls`) maintains 

5one interesting solution and derives one new solution from it using the 

6unary search operator (:class:`~moptipy.api.operators.Op1`). The new solution 

7replaces the current solution if it is not worse, i.e., better or equally 

8good. Simulated Annealing is similar to the :mod:`~moptipy.algorithms.so.rls`, 

9but it sometimes also accepts solutions that are worse than the current one. 

10It does so with a probability that becomes smaller the worse the new solution 

11is and also becomes smaller the smaller the current "temperature" is. 

12 

13Simulated Annealing applies a so-called temperature schedule (see 

14:mod:`~moptipy.algorithms.modules.temperature_schedule`), which basically is 

15function that relates the index of the algorithm iteration (i.e., the index 

16of the current objective function evaluation) to a temperature. It therefore 

17is a function accepting an integer value as input and returning a float 

18temperature. This function is usually monotonously decreasing over time, 

19meaning that the initial "temperature" is high and then becomes smaller. The 

20algorithm therefore is more likely to accept worse solutions at its beginning, 

21whereas it behaves basically like a :mod:`~moptipy.algorithms.so.rls` at the 

22end of its computational budget (if configured correctly). 

23 

24Simulated Annealing was independently developed by several researchers [1-4]. 

25The idea is inspired by Metropolis' approximation of how annealing can be 

26simulated [5]. 

27 

281. Scott Kirkpatrick, C. Daniel Gelatt, Jr., and Mario P. Vecchi. Optimization 

29 by Simulated Annealing. *Science Magazine.* 220(4598):671-680. 

30 May 13, 1983. doi: https://doi.org/10.1126/science.220.4598.671. 

31 https://www.researchgate.net/publication/6026283 

322. Vladimír Černý. Thermodynamical Approach to the Traveling Salesman Problem: 

33 An Efficient Simulation Algorithm. *Journal of Optimization Theory and 

34 Applications.* 45(1):41-51. January 1985. 

35 doi: https://doi.org/10.1007/BF00940812. 

36 http://mkweb.bcgsc.ca/papers/cerny-travelingsalesman.pdf. 

373. Dean Jacobs, Jan Prins, Peter Siegel, and Kenneth Wilson. Monte Carlo 

38 Techniques in Code Optimization. *ACM SIGMICRO Newsletter.* 13(4):143-148. 

39 December 1982. Also in Proceedings of the 15th Annual Workshop on 

40 Microprogramming (MICRO 15), October 5-7, 1982, Palo Alto, CA, USA, 

41 New York, NY, USA: ACM. doi: http://doi.org/10.1145/1014194.800944. 

424. Martin Pincus. Letter to the Editor - A Monte Carlo Method for the 

43 Approximate Solution of Certain Types of Constrained Optimization Problems. 

44 *Operations Research.* 18(6):1225-1228. November/December 1970. 

45 doi: https://doi.org/10.1287/opre.18.6.1225. 

465. Nicholas Metropolis, Arianna W. Rosenbluth, Marshall Nicholas Rosenbluth, 

47 Augusta H. Teller, Edward Teller. Equation of State Calculations by Fast 

48 Computing Machines. *The Journal of Chemical Physics*. 21(6):1087-1092. 

49 June 1953. doi: https://doi.org/10.1063/1.1699114. 

50 http://scienze-como.uninsubria.it/bressanini/montecarlo-history/mrt2.pdf. 

51""" 

52from math import exp 

53from typing import Callable, Final 

54 

55from numpy.random import Generator 

56from pycommons.types import type_error 

57 

58from moptipy.algorithms.modules.temperature_schedule import TemperatureSchedule 

59from moptipy.api.algorithm import Algorithm1 

60from moptipy.api.operators import Op0, Op1 

61from moptipy.api.process import Process 

62from moptipy.utils.logger import KeyValueLogSection 

63 

64 

65# start book 

66class SimulatedAnnealing(Algorithm1): 

67 """Simulated Annealing is an RLS sometimes accepting worsening moves.""" 

68 

69 def solve(self, process: Process) -> None: 

70 """ 

71 Apply the simulated annealing algorithm to an optimization problem. 

72 

73 :param process: the black-box process object 

74 """ 

75 # Create records for old and new point in the search space. 

76 best_x = process.create() # record for best-so-far solution 

77 new_x = process.create() # record for new solution 

78 # Obtain the random number generator. 

79 random: Final[Generator] = process.get_random() 

80 

81 # Put function references in variables to for faster calls. 

82 temperature: Final[Callable[[int], float]] = self.schedule.temperature 

83 r01: Final[Callable[[], float]] = random.random # random from [0, 1) 

84 evaluate: Final[Callable] = process.evaluate # the objective 

85 op1: Final[Callable] = self.op1.op1 # the unary operator 

86 should_terminate: Final[Callable] = process.should_terminate 

87 

88 # Start at a random point in the search space and evaluate it. 

89 self.op0.op0(random, best_x) # Create 1 solution randomly and 

90 best_f: int | float = evaluate(best_x) # evaluate it. 

91 tau: int = 0 # The iteration index, needs to be 0 at first cmp. 

92 

93 while not should_terminate(): # Until we need to quit... 

94 op1(random, new_x, best_x) # new_x = neighbor of best_x 

95 new_f: int | float = evaluate(new_x) 

96 if (new_f <= best_f) or ( # Accept if <= or if SA criterion 

97 r01() < exp((best_f - new_f) / temperature(tau))): 

98 best_f = new_f # Store its objective value. 

99 best_x, new_x = new_x, best_x # Swap best and new. 

100 tau += 1 # Step the iteration index. 

101# end book 

102 

103 def __init__(self, op0: Op0, op1: Op1, 

104 schedule: TemperatureSchedule) -> None: 

105 """ 

106 Create the simulated annealing algorithm. 

107 

108 :param op0: the nullary search operator 

109 :param op1: the unary search operator 

110 :param schedule: the temperature schedule to use 

111 """ 

112 super().__init__(f"sa_{schedule}", op0, op1) 

113 if not isinstance(schedule, TemperatureSchedule): 

114 raise type_error(schedule, "schedule", TemperatureSchedule) 

115 #: the temperature schedule 

116 self.schedule: Final[TemperatureSchedule] = schedule 

117 

118 def log_parameters_to(self, logger: KeyValueLogSection) -> None: 

119 """ 

120 Log all parameters of the simulated annealing algorithm. 

121 

122 :param logger: the logger for the parameters 

123 """ 

124 super().log_parameters_to(logger) 

125 with logger.scope("ts") as ts: 

126 self.schedule.log_parameters_to(ts) 

127 

128 def initialize(self) -> None: 

129 """Initialize the algorithm.""" 

130 super().initialize() 

131 self.schedule.initialize()