Coverage for moptipy / algorithms / modules / temperature_schedule.py: 84%
122 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2A temperature schedule as needed by Simulated Annealing.
4The Simulated Annealing algorithm implemented in
5:mod:`~moptipy.algorithms.so.simulated_annealing` performs a local search that
6always accepts a non-worsening move, i.e., a solution which is not worse than
7the currently maintained one. However, it will also *sometimes* accept one
8that is worse. The probability of doing so depends on how much worse that
9solution is and on the current *temperature* of the algorithm. The higher the
10temperature, the higher the acceptance probability. The temperature changes
11over time according to the
12:class:`~moptipy.algorithms.modules.temperature_schedule.TemperatureSchedule`.
14The temperature schedule receives an iteration index `tau` as input and
15returns the current temperature via :meth:`~moptipy.algorithms.modules.\
16temperature_schedule.TemperatureSchedule.temperature`. Notice that `tau` is
17zero-based for simplicity reason, meanings that the first objective function
18evaluation is at index `0`.
19"""
21from math import e, isfinite, log
22from typing import Final
24from pycommons.math.int_math import try_int
25from pycommons.strings.enforce import enforce_non_empty_str_without_ws
26from pycommons.types import check_int_range, type_error
28from moptipy.api.component import Component
29from moptipy.api.objective import Objective, check_objective
30from moptipy.utils.logger import KeyValueLogSection
31from moptipy.utils.strings import num_to_str_for_name
34# start schedule
35class TemperatureSchedule(Component):
36 """The base class for temperature schedules."""
38 def __init__(self, t0: float) -> None:
39 # end schedule
40 """
41 Initialize the temperature schedule.
43 :param t0: the starting temperature, must be > 0
44 """
45 super().__init__()
46 if not isinstance(t0, float):
47 raise type_error(t0, "t0", float)
48 if (not isfinite(t0)) or (t0 <= 0.0):
49 raise ValueError(f"t0 must be >0, cannot be {t0}.")
50# start schedule
51 #: the starting temperature
52 self.t0: Final[float] = t0
54 def temperature(self, tau: int) -> float:
55 """
56 Compute the temperature at iteration `tau`.
58 :param tau: the iteration index, starting with `0` at the first
59 comparison of two solutions, at which point the starting
60 temperature :attr:`~TemperatureSchedule.t0` should be returned
61 :returns: the temperature
62 """
63# end schedule
65 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
66 """
67 Log all parameters of this temperature schedule as key-value pairs.
69 :param logger: the logger for the parameters
71 >>> from moptipy.utils.logger import InMemoryLogger
72 >>> with InMemoryLogger() as l:
73 ... with l.key_values("C") as kv:
74 ... TemperatureSchedule(0.1).log_parameters_to(kv)
75 ... text = l.get_log()
76 >>> text[1]
77 'name: TemperatureSchedule'
78 >>> text[3]
79 'T0: 0.1'
80 >>> len(text)
81 6
82 """
83 super().log_parameters_to(logger)
84 logger.key_value("T0", self.t0)
87# start exponential
88class ExponentialSchedule(TemperatureSchedule):
89 """
90 The exponential temperature schedule.
92 The current temperature is computed as `t0 * (1 - epsilon) ** tau`.
94 >>> ex = ExponentialSchedule(10.0, 0.05)
95 >>> print(f"{ex.t0} - {ex.epsilon}")
96 10.0 - 0.05
97 >>> ex.temperature(0)
98 10.0
99 >>> ex.temperature(1)
100 9.5
101 >>> ex.temperature(2)
102 9.025
103 >>> ex.temperature(1_000_000_000_000_000_000)
104 0.0
105 """
107 def __init__(self, t0: float, epsilon: float) -> None:
108 """
109 Initialize the exponential temperature schedule.
111 :param t0: the starting temperature, must be > 0
112 :param epsilon: the epsilon parameter of the schedule, in (0, 1)
113 """
114 super().__init__(t0)
115# end exponential
116 if not isinstance(epsilon, float):
117 raise type_error(epsilon, "epsilon", float)
118 if (not isfinite(epsilon)) or (not (0.0 < epsilon < 1.0)):
119 raise ValueError(
120 f"epsilon cannot be {epsilon}, must be in (0,1).")
121# start exponential
122 #: the epsilon parameter of the exponential schedule
123 self.epsilon: Final[float] = epsilon
124 #: the value used as basis for the exponent
125 self.__one_minus_epsilon: Final[float] = 1.0 - epsilon
126# end exponential
127 if not (0.0 < self.__one_minus_epsilon < 1.0):
128 raise ValueError(
129 f"epsilon cannot be {epsilon}, because 1-epsilon must be in "
130 f"(0, 1) but is {self.__one_minus_epsilon}.")
131# start exponential
133 def temperature(self, tau: int) -> float:
134 """
135 Compute the temperature at iteration `tau`.
137 :param tau: the iteration index, starting with `0` at the first
138 comparison of two solutions, at which point the starting
139 temperature :attr:`~TemperatureSchedule.t0` should be returned
140 :returns: the temperature
142 >>> s = ExponentialSchedule(100.0, 0.5)
143 >>> s.temperature(0)
144 100.0
145 >>> s.temperature(1)
146 50.0
147 >>> s.temperature(10)
148 0.09765625
149 """
150 return self.t0 * (self.__one_minus_epsilon ** tau)
151# end exponential
153 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
154 """
155 Log all parameters of the exponential temperature schedule.
157 :param logger: the logger for the parameters
159 >>> from moptipy.utils.logger import InMemoryLogger
160 >>> with InMemoryLogger() as l:
161 ... with l.key_values("C") as kv:
162 ... ExponentialSchedule(0.2, 0.6).log_parameters_to(kv)
163 ... text = l.get_log()
164 >>> text[1]
165 'name: exp0d2_0d6'
166 >>> text[3]
167 'T0: 0.2'
168 >>> text[5]
169 'e: 0.6'
170 >>> len(text)
171 8
172 """
173 super().log_parameters_to(logger)
174 logger.key_value("e", self.epsilon)
176 def __str__(self) -> str:
177 """
178 Get the string representation of the exponential temperature schedule.
180 :returns: the name of this schedule
182 >>> ExponentialSchedule(100.5, 0.3)
183 exp100d5_0d3
184 """
185 return (f"exp{num_to_str_for_name(self.t0)}_"
186 f"{num_to_str_for_name(self.epsilon)}")
189# start logarithmic
190class LogarithmicSchedule(TemperatureSchedule):
191 """
192 The logarithmic temperature schedule.
194 The temperature is computed as `t0 / log(e + (tau * epsilon))`.
196 >>> lg = LogarithmicSchedule(10.0, 0.1)
197 >>> print(f"{lg.t0} - {lg.epsilon}")
198 10.0 - 0.1
199 >>> lg.temperature(0)
200 10.0
201 >>> lg.temperature(1)
202 9.651322627630812
203 >>> lg.temperature(1_000_000_000_000_000_000_000_000_000_000_000_000_000)
204 0.11428802155348732
205 """
207 def __init__(self, t0: float, epsilon: float) -> None:
208 """
209 Initialize the logarithmic temperature schedule.
211 :param t0: the starting temperature, must be > 0
212 :param epsilon: the epsilon parameter of the schedule, is > 0
213 """
214 super().__init__(t0)
215# end logarithmic
216 if not isinstance(epsilon, float):
217 raise type_error(epsilon, "epsilon", float)
218 if (not isfinite(epsilon)) or (epsilon <= 0.0):
219 raise ValueError(
220 f"epsilon cannot be {epsilon}, must be > 0.")
221# start logarithmic
222 #: the epsilon parameter of the logarithmic schedule
223 self.epsilon: Final[float] = epsilon
225 def temperature(self, tau: int) -> float:
226 """
227 Compute the temperature at iteration `tau`.
229 :param tau: the iteration index, starting with `0` at the first
230 comparison of two solutions, at which point the starting
231 temperature :attr:`~TemperatureSchedule.t0` should be returned
232 :returns: the temperature
234 >>> s = LogarithmicSchedule(100.0, 0.5)
235 >>> s.temperature(0)
236 100.0
237 >>> s.temperature(1)
238 85.55435113150568
239 >>> s.temperature(10)
240 48.93345190925178
241 """
242 return self.t0 / log(e + (tau * self.epsilon))
243# end logarithmic
245 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
246 """
247 Log all parameters of the logarithmic temperature schedule.
249 :param logger: the logger for the parameters
251 >>> from moptipy.utils.logger import InMemoryLogger
252 >>> with InMemoryLogger() as l:
253 ... with l.key_values("C") as kv:
254 ... LogarithmicSchedule(0.2, 0.6).log_parameters_to(kv)
255 ... text = l.get_log()
256 >>> text[1]
257 'name: ln0d2_0d6'
258 >>> text[3]
259 'T0: 0.2'
260 >>> text[5]
261 'e: 0.6'
262 >>> len(text)
263 8
264 """
265 super().log_parameters_to(logger)
266 logger.key_value("e", self.epsilon)
268 def __str__(self) -> str:
269 """
270 Get the string representation of the logarithmic temperature schedule.
272 :returns: the name of this schedule
274 >>> LogarithmicSchedule(100.5, 0.3)
275 ln100d5_0d3
276 """
277 return (f"ln{num_to_str_for_name(self.t0)}_"
278 f"{num_to_str_for_name(self.epsilon)}")
281class ExponentialScheduleBasedOnBounds(ExponentialSchedule):
282 """
283 An exponential schedule configured based on the objective's range.
285 This exponential schedule takes an objective function as parameter.
286 It uses the lower and the upper bound of this function, `LB` and `UB`,
287 to select a start and end temperature based on the provided fractions.
288 Here, we set `W = lb_sum_weight * LB + ub_sum_weight * UB`.
289 If we set `lb_sum_weight = -1` and `ub_sum_weight = 1`, then `W` will be
290 the range of the objective function.
291 If we set `lb_sum_weight = 1` and `ub_sum_weight = 0`, then we base the
292 temperature setup entirely on the lower bound.
293 If we set `lb_sum_weight = 0` and `ub_sum_weight = 1`, then we base the
294 temperature setup entirely on the upper bound.
295 Roughly, the start temperature will be `W * start_range_frac` and
296 the end temperature, to be reached after `n_steps` FEs, will be
297 `W * end_range_frac`.
298 Since sometimes the upper and lower bound may be excessivly large, we
299 can provide limits for `W` in form of `min_bound_sum` and `max_bound_sum`.
300 This will then override any other computation.
301 Notice that it is expected that `tau == 0` when the temperature function
302 is first called. It is expected that `tau == n_range - 1` when it is
303 called for the last time.
305 >>> from moptipy.examples.bitstrings.onemax import OneMax
306 >>> es = ExponentialScheduleBasedOnBounds(
307 ... OneMax(10), -1, 1, 0.01, 0.0001, 10**8)
308 >>> es.temperature(0)
309 0.1
310 >>> es.temperature(1)
311 0.09999999539482989
312 >>> es.temperature(10**8 - 1)
313 0.0010000000029841878
314 >>> es.temperature(10**8)
315 0.0009999999569324865
317 >>> es = ExponentialScheduleBasedOnBounds(
318 ... OneMax(10), -1, 1, 0.01, 0.0001, 10**8, max_bound_sum=5)
319 >>> es.temperature(0)
320 0.05
321 >>> es.temperature(1)
322 0.04999999769741494
323 >>> es.temperature(10**8 - 1)
324 0.0005000000014920939
325 >>> es.temperature(10**8)
326 0.0004999999784662432
328 >>> try:
329 ... ExponentialScheduleBasedOnBounds(1, 0.01, 0.0001, 10**8)
330 ... except TypeError as te:
331 ... print(te)
332 objective function should be an instance of moptipy.api.objective.\
333Objective but is int, namely 1.
335 >>> try:
336 ... ExponentialScheduleBasedOnBounds(
337 ... OneMax(10), -1, 1, -1.0, 0.0001, 10**8)
338 ... except ValueError as ve:
339 ... print(ve)
340 Invalid bound sum factors [-1.0, 0.0001].
342 >>> try:
343 ... ExponentialScheduleBasedOnBounds(
344 ... OneMax(10), -1, 1, 0.9, 0.0001, 1)
345 ... except ValueError as ve:
346 ... print(ve)
347 n_steps=1 is invalid, must be in 2..1000000000000000.
348 """
350 def __init__(self, f: Objective,
351 lb_sum_weight: int | float = -1,
352 ub_sum_weight: int | float = 1,
353 start_factor: float = 1e-3,
354 end_factor: float = 1e-7,
355 n_steps: int = 1_000_000,
356 min_bound_sum: int | float = 1e-20,
357 max_bound_sum: int | float = 1e20) -> None:
358 """
359 Initialize the range-based exponential schedule.
361 :param f: the objective function whose range we will use
362 :param lb_sum_weight: the weight of the lower bound in the bound sum
363 :param ub_sum_weight: the weight of the upper bound in the bound sum
364 :parma start_factor: the factor multiplied with the bound sum to get
365 the starting temperature
366 :parm end_factor: the factor multiplied with the bound sum to get
367 the end temperature
368 :param n_steps: the number of steps until the end range should be
369 reached
370 :param min_bound_sum: a lower limit for the weighted sum of the bounds
371 :param max_bound_sum: an upper limit for the weighted sum of the bounds
372 """
373 f = check_objective(f)
374 if not isinstance(lb_sum_weight, int | float):
375 raise type_error(lb_sum_weight, "lb_sum_weight", (int, float))
376 if not isinstance(ub_sum_weight, int | float):
377 raise type_error(ub_sum_weight, "ub_sum_weight", (int, float))
378 if not isinstance(start_factor, float):
379 raise type_error(start_factor, "start_factor", float)
380 if not isinstance(end_factor, float):
381 raise type_error(end_factor, "end_factor", float)
382 if not isinstance(min_bound_sum, int | float):
383 raise type_error(min_bound_sum, "min_bound_sum", (int, float))
384 if not isinstance(max_bound_sum, int | float):
385 raise type_error(max_bound_sum, "max_bound_sum", (int, float))
387 if not (isfinite(min_bound_sum) and isfinite(max_bound_sum) and (
388 0 < min_bound_sum < max_bound_sum)):
389 raise ValueError(f"Invalid bound sum limits [{min_bound_sum}"
390 f", {max_bound_sum}].")
391 if not (isfinite(start_factor) and isfinite(end_factor) and (
392 0.0 < end_factor < start_factor < 1e50)):
393 raise ValueError(f"Invalid bound sum factors [{start_factor}"
394 f", {end_factor}].")
395 if not (isfinite(lb_sum_weight) and isfinite(ub_sum_weight)):
396 raise ValueError(f"Invalid bound sum weights [{lb_sum_weight}"
397 f", {ub_sum_weight}].")
398 #: the number of steps that we will perform until reaching the end
399 #: range fraction temperature
400 self.__n_steps: Final[int] = check_int_range(
401 n_steps, "n_steps", 2, 1_000_000_000_000_000)
403 lb_sum_weight = try_int(lb_sum_weight)
404 #: the sum weight for the lower bound
405 self.__lb_sum_weight: Final[int | float] = lb_sum_weight
406 ub_sum_weight = try_int(ub_sum_weight)
407 #: the sum weight for the upper bound
408 self.__ub_sum_weight: Final[int | float] = ub_sum_weight
409 #: the start temperature bound sum factor
410 self.__start_factor: Final[float] = start_factor
411 #: the end temperature bound sum factor
412 self.__end_factor: Final[float] = end_factor
413 min_bound_sum = try_int(min_bound_sum)
414 #: the minimum value for the bound sum
415 self.__min_bound_sum: Final[int | float] = min_bound_sum
416 max_bound_sum = try_int(max_bound_sum)
417 #: the maximum value for the bound sum
418 self.__max_bound_sum: Final[int | float] = max_bound_sum
420 #: the name of the objective function used
421 self.__used_objective: Final[str] = enforce_non_empty_str_without_ws(
422 str(f))
423 flb: Final[float | int] = f.lower_bound()
424 fub: Final[float | int] = f.upper_bound()
425 if flb > fub:
426 raise ValueError(
427 f"Objective function lower bound {flb} > upper bound {fub}?")
429 #: the lower bound of the objective value
430 self.__f_lower_bound: Final[int | float] = flb
431 #: the upper bound for the objective value
432 self.__f_upper_bound: Final[int | float] = fub
434 bound_sum: Final[float | int] = try_int(max(min_bound_sum, min(
435 max_bound_sum,
436 (flb * lb_sum_weight if lb_sum_weight != 0 else 0) + (
437 fub * ub_sum_weight if ub_sum_weight != 0 else 0))))
438 if not (isfinite(bound_sum) and (
439 min_bound_sum <= bound_sum <= max_bound_sum)):
440 raise ValueError(
441 f"Invalid bound sum {bound_sum} resulting from bounds [{flb}"
442 f", {fub}] and weights {lb_sum_weight}, {ub_sum_weight}.")
443 #: the bound sum
444 self.__f_bound_sum: Final[int | float] = bound_sum
446 t0: Final[float] = start_factor * bound_sum
447 te: Final[float] = end_factor * bound_sum
448 if not (isfinite(t0) and isfinite(te) and (0 < te < t0 < 1e100)):
449 raise ValueError(
450 f"Invalid setup {start_factor}, {end_factor}, "
451 f"{bound_sum} leading to temperatures {t0}, {te}.")
452 #: the end temperature
453 self.__te: Final[float] = te
455 epsilon: Final[float] = 1 - (te / t0) ** (1 / (n_steps - 1))
456 if not (isfinite(epsilon) and (0 < epsilon < 1) and (
457 0 < (1 - epsilon) < 1)):
458 raise ValueError(
459 f"Invalid computed epsilon {epsilon} resulting from setup "
460 f"{start_factor}, {end_factor}, {bound_sum} leading "
461 f"to temperatures {t0}, {te}.")
462 super().__init__(t0, epsilon)
464 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
465 """
466 Log all parameters of the configured exponential temperature schedule.
468 :param logger: the logger for the parameters
470 >>> from moptipy.utils.logger import InMemoryLogger
471 >>> from moptipy.examples.bitstrings.onemax import OneMax
472 >>> with InMemoryLogger() as l:
473 ... with l.key_values("C") as kv:
474 ... ExponentialScheduleBasedOnBounds(
475 ... OneMax(10), -1, 1, 0.01, 0.0001).log_parameters_to(kv)
476 ... text = l.get_log()
477 >>> text[1]
478 'name: expRm1_1_0d01_0d0001_1em20_1e20'
479 >>> text[3]
480 'T0: 0.1'
481 >>> text[5]
482 'e: 4.6051641873212645e-6'
483 >>> text[7]
484 'nSteps: 1000000'
485 >>> text[8]
486 'lbSumWeight: -1'
487 >>> text[9]
488 'ubSumWeight: 1'
489 >>> len(text)
490 25
491 """
492 super().log_parameters_to(logger)
493 logger.key_value("nSteps", self.__n_steps)
494 logger.key_value("lbSumWeight", self.__lb_sum_weight)
495 logger.key_value("ubSumWeight", self.__ub_sum_weight)
496 logger.key_value("startFactor", self.__start_factor)
497 logger.key_value("endFactor", self.__end_factor)
498 logger.key_value("minBoundSum", self.__min_bound_sum)
499 logger.key_value("maxBoundSum", self.__max_bound_sum)
500 logger.key_value("f", self.__used_objective)
501 logger.key_value("fLB", self.__f_lower_bound)
502 logger.key_value("fUB", self.__f_upper_bound)
503 logger.key_value("boundSum", self.__f_bound_sum)
504 logger.key_value("Tend", self.__te)
506 def __str__(self) -> str:
507 """
508 Get the string representation of the configured exponential schedule.
510 :returns: the name of this schedule
512 >>> from moptipy.examples.bitstrings.onemax import OneMax
513 >>> ExponentialScheduleBasedOnBounds(OneMax(10), -1, 1, 0.01, 0.0001)
514 expRm1_1_0d01_0d0001_1em20_1e20
515 """
516 return "expR" + "_".join(map(num_to_str_for_name, (
517 self.__lb_sum_weight, self.__ub_sum_weight, self.__start_factor,
518 self.__end_factor, self.__min_bound_sum, self.__max_bound_sum)))