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#: The minimal temperature (about 1.262177448353619e-29) is used to 

65#: prevent the algorithm from crashing because the temperature reaches 

66#: zero. 

67MIN_TEMPERATURE: Final[float] = float.fromhex("0x1.0000000000000p-96") 

68 

69 

70# start book 

71class SimulatedAnnealing(Algorithm1): 

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

73 

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

75 """ 

76 Apply the simulated annealing algorithm to an optimization problem. 

77 

78 :param process: the black-box process object 

79 """ 

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

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

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

83 # Obtain the random number generator. 

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

85 

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

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

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

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

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

91 should_terminate: Final[Callable] = process.should_terminate 

92 

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

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

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

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

97 

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

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

100 new_f: int | float = evaluate(new_x) 

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

102 r01() < exp((best_f - new_f) / max( 

103 MIN_TEMPERATURE, temperature(tau)))): 

104 best_f = new_f # Store its objective value. 

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

106 tau += 1 # Step the iteration index. 

107# end book 

108 

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

110 schedule: TemperatureSchedule) -> None: 

111 """ 

112 Create the simulated annealing algorithm. 

113 

114 :param op0: the nullary search operator 

115 :param op1: the unary search operator 

116 :param schedule: the temperature schedule to use 

117 """ 

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

119 if not isinstance(schedule, TemperatureSchedule): 

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

121 #: the temperature schedule 

122 self.schedule: Final[TemperatureSchedule] = schedule 

123 

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

125 """ 

126 Log all parameters of the simulated annealing algorithm. 

127 

128 :param logger: the logger for the parameters 

129 """ 

130 super().log_parameters_to(logger) 

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

132 self.schedule.log_parameters_to(ts) 

133 

134 def initialize(self) -> None: 

135 """Initialize the algorithm.""" 

136 super().initialize() 

137 self.schedule.initialize()