Source code for fresh_solutions.kernel.cooling

"""Temperature schedules shared by the kernel's annealing solvers.

The geometric schedule needs two constants tuned per problem. The adaptive
Aarts--Van Laarhoven (1985) schedule sets the initial temperature from the average uphill
move and decreases it from the spread of the objectives at the current temperature.
"""

from __future__ import annotations

import math
import statistics
from collections.abc import Sequence
from dataclasses import dataclass, field


[docs] @dataclass(frozen=True) class AdaptiveCooling: """The Aarts and Van Laarhoven (1985) polynomial-time cooling rule. Parameters ---------- initial_acceptance : float, optional The acceptance ratio the initial temperature targets, in ``(0, 1)``. Defaults to 0.9. delta : float, optional The distance from stationarity the decrement allows; it must be positive. Defaults to 0.1. """ initial_acceptance: float = 0.9 delta: float = 0.1 def __post_init__(self) -> None: """Reject parameters the cooling rule is undefined for.""" if not 0.0 < self.initial_acceptance < 1.0: raise ValueError("initial_acceptance must be in (0, 1)") if self.delta <= 0.0: raise ValueError("delta must be positive")
[docs] def initial_temperature(self, increases: Sequence[float]) -> float: """Return the initial temperature for a sample of uphill move costs. ``c_0 = mean(positive dE) / ln(1 / chi_0)``, so a move that raises the objective by the observed average is accepted with probability ``chi_0`` at ``c_0``. Parameters ---------- increases : sequence of float The objective changes of the sampled moves. Only positive changes are used. Returns ------- float The initial temperature, or ``0.0`` when no sampled move was uphill. """ uphill = [change for change in increases if change > 0.0] if not uphill: return 0.0 return (sum(uphill) / len(uphill)) / math.log(1.0 / self.initial_acceptance)
[docs] def cool(self, temperature: float, spread: float) -> float: """Return the next temperature from the current one and its objective spread. ``c_{k+1} = c_k / (1 + c_k ln(1 + delta) / (3 sigma_k))``. A non-positive spread leaves the temperature unchanged, because the rule is undefined there. Parameters ---------- temperature : float The current temperature. spread : float The population standard deviation of the objectives at the current temperature. Returns ------- float The next temperature. """ if spread <= 0.0: return temperature return temperature / (1.0 + temperature * math.log1p(self.delta) / (3.0 * spread))
[docs] @dataclass class TemperatureSchedule: """Advance the temperature: geometric, or the adaptive Aarts--Van Laarhoven rule. The schedule owns the temperature the solver reads each iteration. In adaptive mode the first ``window`` iterations form a random walk that estimates the initial temperature, and each following group of ``window`` iterations recomputes it from the spread of the objectives seen. In geometric mode the temperature is multiplied by ``cooling``. Parameters ---------- initial : float The starting temperature, used as-is in geometric mode. cooling : float The geometric factor, used only in geometric mode. adaptive : bool Whether to use the adaptive rule. window : int The number of iterations per temperature in adaptive mode. rule : AdaptiveCooling The adaptive rule's parameters. Attributes ---------- temperature : float The temperature the next iteration should read. """ initial: float cooling: float adaptive: bool window: int rule: AdaptiveCooling = field(default_factory=AdaptiveCooling) temperature: float = field(init=False, default=0.0) _increases: list[float] = field(init=False, default_factory=list) _samples: list[float] = field(init=False, default_factory=list) _warmed: bool = field(init=False, default=False) def __post_init__(self) -> None: """Set the starting temperature and whether a warm-up is still due.""" if self.window < 1: raise ValueError("window must be positive") self.temperature = math.inf if self.adaptive else self.initial self._warmed = not self.adaptive
[docs] def observe(self, increase: float, objective: float) -> None: """Record one iteration, then advance the temperature. Parameters ---------- increase : float The objective change the move proposed (positive for a worse objective). objective : float The objective of the current configuration after the move. """ if not self.adaptive: self.temperature *= self.cooling return if not self._warmed: self._increases.append(increase) if len(self._increases) >= self.window: self.temperature = self.rule.initial_temperature(self._increases) self._increases.clear() self._warmed = True return self._samples.append(objective) if len(self._samples) >= self.window: self.temperature = self.rule.cool(self.temperature, statistics.pstdev(self._samples)) self._samples.clear()
[docs] @staticmethod def effective_window(iterations: int, window: int) -> int: """Return the adaptive window for an iteration budget. The warm-up and at least one cooling step both need a window of iterations, so the window is capped at half the budget. Parameters ---------- iterations : int The iteration budget. window : int The requested window. Returns ------- int The window to use, at least one. """ return max(1, min(window, max(1, iterations // 2)))