Cooling Schemes

In the context of optimization algorithms—most notably Simulated Annealing—a Cooling Scheme (or cooling schedule) is a mathematical strategy that dictates how the “temperature” parameter decreases over time.

Why Cooling Schemes are Important

The temperature in an optimization process controls the balance between exploration and exploitation:

Exploration (High Temperature): Early in the process, high temperatures allow the algorithm to accept worse s olutions with a higher probability. This prevents the search from getting stuck in local optima and helps explore the broader search space.
Exploitation (Low Temperature): As the temperature decreases, the algorithm becomes more selective, eventually only accepting moves that improve the result. This allows the search to converge on a global optimum.

Choosing the right cooling scheme is critical because:

Convergence Speed: If the temperature drops too quickly (quenched), the algorithm may converge prematurely to a sub-optimal local minimum.
Solution Quality: If the temperature drops too slowly, the algorithm may take an impractical amount of time to reach a solution.
Problem Adaptability: Different problem domains may require different cooling behaviors—such as linear, exponential, or adaptive adjustments—to find the best results efficiently.

Linear Cooling

The LinearCooling scheme reduces the temperature by a constant value in each step. It is one of the simplest cooling schedules and provides a predictable, steady decrease in exploration.

Mathematics

The temperature at iteration \(i\) is calculated as:

\[T_i = \max(T_{initial} - i \cdot \text{step}, 0)\]

Where:

\(T_{initial}\) is the starting temperature.
\(\text{step}\) is the constant reduction value.

Usage Example

from altbacken.external.temperature import LinearCooling

# Start at 100, decrease by 1 each iteration
cooling = LinearCooling(initial_temperature=100.0, step=1.0)

Exponential Cooling

The ExponentialCooling scheme reduces the temperature by a fixed percentage (the cooling rate) at each step. This results in a fast initial drop that slows down as the temperature approaches zero.

Mathematics

The temperature \(T\) at iteration \(i\) is calculated as:

\[T_i = T_{initial} \cdot \alpha^i\]

where:

\(T_{initial}\) is the starting temperature.
\(\alpha\) is the cooling rate (\(0 < \alpha < 1\)).
\(i\) is the current iteration.

Example Usage

from altbacken.external.temperature import ExponentialCooling

# Start at 100, reduce by 5% each iteration (cooling rate of 0.95)
cooling = ExponentialCooling(initial_temperature=100.0, cooling_rate=0.95)

Logarithmic Cooling

The LogarithmicCooling scheme provides a cooling schedule based on a logarithmic function. It is characterized by an extremely slow decrease in temperature, making it suitable for problems that require extensive fine-tuning and where computation time is less critical than finding the global optimum.

Mathematics

The temperature \(T\) at iteration \(i\) is calculated as:

\[T_i = \frac{T_{initial}}{\ln(i + \text{shift})}\]

where:

\(T_{initial}\) is the starting temperature.
\(\text{shift}\) is a factor added to the denominator (must be \(> 1\)) to avoid division by zero and regulate the initial cooling rate.
\(i\) is the current iteration.

Example Usage

from altbacken.external.temperature import LogarithmicCooling

# Initialize logarithmic cooling with a standard shift
cooling = LogarithmicCooling(initial_temperature=100.0, shift=1.1)

Cosine Annealing

The CosineCooling scheme (often referred to as Cosine Annealing) adjusts the temperature according to a half-period of a cosine curve. It starts at the initial temperature and gradually decreases to zero over a fixed number of iterations.

Mathematics

The temperature \(T\) at iteration \(i\) is calculated as:

\[T_i = \frac{1}{2} T_{initial} \left( 1 + \cos\left( \frac{i \cdot \pi}{i_{max}} \right) \right)\]

where: * \(T_{initial}\) is the starting temperature. * \(i\) is the current iteration. * \(i_{max}\) is the maximum number of iterations.

If the current iteration exceeds \(i_{max}\), the temperature remains at 0.0.

Example Usage

from altbacken.external.temperature import CosineCooling

# Initialize cooling that reaches 0 after 1000 iterations
cooling = CosineCooling(initial_temperature=100.0, max_iterations=1000)

# The cooling object can then be passed to the annealing process

Adaptive Cooling

The AdaptiveCooling scheme adjusts the temperature dynamically based on the search progress. Unlike static schedules, it can “re-heat” the system if improvements are found, allowing for further exploration of promising areas, while cooling down when the search stagnates.

Mathematics

The temperature \(T\) at iteration \(i\) is calculated based on the previous temperature \(T_{i-1}\) and whether the last move resulted in an improvement:

\[\begin{split}T_i = \begin{cases} T_{initial} & \text{if } i = 0 \\ T_{i-1} \cdot \text{heating} & \text{if improvement was found} \\ T_{i-1} \cdot \text{cooling} & \text{otherwise} \end{cases}\end{split}\]

where: * \(\text{cooling}\) is a factor in \((0, 1)\) to decrease temperature. * \(\text{heating}\) is a factor \(> 1\) to increase temperature.

Example Usage

from altbacken.external.temperature import AdaptiveCooling

# Initialize with a 10% decrease on failure and a 5% increase on improvement
cooling = AdaptiveCooling(initial_temperature=100.0, cooling=0.9, heating=1.05)

Predefined Temperature

The PredefinedTemperature scheme allows you to provide an explicit sequence of temperature values. This is particularly useful when you have a specific cooling schedule from literature or when you need to reproduce a specific experimental setup exactly.

Behavior

The scheme iterates through the provided sequence:

For iteration \(i\), the temperature is \(T_{i}\) from the sequence.
If the number of iterations exceeds the length of the sequence, the temperature remains at 0.0.

Example Usage

from altbacken.external.temperature import PredefinedTemperature

# Define a custom sequence of temperatures
custom_temps = [100.0, 50.0, 25.0, 10.0, 5.0, 1.0]
cooling = PredefinedTemperature(custom_temps)