Simulated Annealing: Complete Guide — Principles, Examples, and Python Implementation

Summary

Simulated annealing is an optimization metaheuristic inspired by the physical annealing process in metallurgy. Unlike greedy algorithms that systematically descend toward the best neighbor, simulated annealing sometimes accepts worse solutions with a probability controlled by a decreasing temperature parameter. This mechanism allows it to escape local minima and asymptotically converge to the global optimum. In this guide, we will explore the mathematical foundations, the physical intuition, a complete Python implementation on the Traveling Salesman Problem (TSP), as well as best practices for hyperparameter tuning.

Mathematical Principles

Simulated annealing solves an optimization problem of finding a solution $s^*$ that minimizes a cost function $E(s)$ defined on a search space $S$. The algorithm proceeds through successive iterations starting from an initial solution $s_0$.

Step 1: Generating a Neighbor Solution

At each iteration $k$, a candidate solution $s’$ is generated in the neighborhood of the current solution $s_k$. The neighborhood $N(s_k)$ is a set of “nearby” solutions to $s_k$, defined according to the problem structure:

• For the TSP (Traveling Salesman Problem), swap two cities in the tour.
• For a continuous function, add Gaussian noise to each coordinate.
• For a combinatorial problem, reverse or permute two elements.

Step 2: Metropolis Acceptance Criterion

The energy variation $\Delta E = E(s’) – E(s_k)$ is computed. The acceptance criterion is the heart of the algorithm:

1. If $\Delta E < 0$: the candidate solution is better — it is accepted systematically ($s_{k+1} = s’$).
2. If $\Delta E \geq 0$: the candidate solution is worse — it is accepted with probability:

$$P(\text{accept}) = \exp\left(-\frac{\Delta E}{T_k}\right)$$

where $T_k$ is the current temperature. This probability is compared to a random number $r \sim U(0, 1)$: if $r < P$, the solution is accepted despite the deterioration.

This criterion, called the Boltzmann distribution, guarantees that:
– At high temperature, worse solutions are frequently accepted (strong exploration).
– At low temperature, worse solutions are rarely accepted (strong exploitation).
– At zero temperature, only improving moves are accepted (classical descent).

Step 3: Temperature Schedule (Cooling Schedule)

The temperature decreases according to a cooling schedule. The most common scheme is geometric cooling:

$$T_{k+1} = \alpha \cdot T_k$$

where $\alpha \in ]0, 1[$ is the cooling rate, typically $\alpha \in [0.80, 0.99]$.

Other schemes exist:
– Linear cooling: $T_{k+1} = T_k – \delta$
– Logarithmic cooling (theoretically optimal): $T_k = \frac{c}{\log(k + 1)}$
– Adaptive annealing: dynamic adjustment based on the observed acceptance rate

Step 4: Convergence

Under logarithmically slow cooling and a connected neighborhood space, simulated annealing asymptotically converges to the global optimum with probability 1. In practice, the algorithm is stopped after a maximum number of iterations or when the temperature reaches a minimum threshold.

Generic Python Implementation

import random
import math

def simulated_annealing(cost_func, neighbor_func, initial_sol,
                         initial_temp=1000.0, cooling_rate=0.995,
                         min_temp=1e-10, max_iter=100000, random_state=None):
    """
    Generic implementation of simulated annealing.

    Args:
        cost_func: function to minimize E(s) -> float
        neighbor_func: function generating a neighbor N(s) -> s'
        initial_sol: starting solution
        initial_temp: initial temperature T_0
        cooling_rate: cooling factor alpha
        min_temp: minimum stopping temperature
        max_iter: maximum number of iterations
        random_state: random seed for reproducibility

    Returns:
        best_sol: best solution found
        best_cost: associated cost
        history: cost history at each iteration
    """
    if random_state is not None:
        random.seed(random_state)

    current_sol = initial_sol
    current_cost = cost_func(current_sol)

    best_sol = current_sol
    best_cost = current_cost

    history = [current_cost]
    temp = initial_temp

    for i in range(max_iter):
        # Generate a neighbor
        neighbor = neighbor_func(current_sol)
        neighbor_cost = cost_func(neighbor)

        # Energy variation
        delta_e = neighbor_cost - current_cost

        # Metropolis criterion
        if delta_e < 0:
            # Improvement: always accept
            current_sol = neighbor
            current_cost = neighbor_cost
        else:
            # Deterioration: probabilistic acceptance
            acceptance_prob = math.exp(-delta_e / temp) if temp > 0 else 0.0
            if random.random() < acceptance_prob:
                current_sol = neighbor
                current_cost = neighbor_cost

        # Update the best
        if current_cost < best_cost:
            best_sol = current_sol
            best_cost = current_cost

        history.append(best_cost)

        # Cooling
        temp *= cooling_rate

        # Stopping condition
        if temp < min_temp:
            break

    return best_sol, best_cost, history

Physical Intuition: The Annealing of a Metal

The analogy with metallurgy is both elegant and deeply instructive. When a metallurgist heats an alloy to a very high temperature, the atoms acquire considerable kinetic energy and move freely, without any particular order. The disordered structure corresponds to a high-energy state.

By slowly cooling the metal (a process called annealing), the atoms progressively lose energy and reorganize into an ordered crystalline configuration — the minimum energy state, the most stable. This final structure corresponds to the global optimum of our objective function.

Conversely, if the metal is cooled too quickly (quenching), the atoms do not have time to reorganize properly and remain frozen in a disordered configuration. The resulting structure is locally stable but globally suboptimal — the equivalent of a local minimum in optimization.

In the algorithmic context, simulated annealing optimization works exactly according to this principle:

• The high temperature at the start allows broad exploration of the search space, sometimes accepting worse solutions to escape local valleys. It is as if the atoms had enough energy to cross energy barriers.
• The decreasing temperature progressively reduces this freedom of exploration, concentrating the search in promising regions.
• The final temperature approaches zero: the algorithm behaves like a local gradient descent, refining the solution in the reached attraction basin.

This physical metaphor explains why the cooling rate is so critical: too fast cooling (too small α) leads to premature convergence toward a local minimum, while too slow cooling (α close to 1) guarantees better solution quality at the cost of considerably increased computation time.

Complete Python Implementation: The Traveling Salesman Problem

The TSP is the classic testbed for optimization methods. Given a set of cities and the distances between them, the goal is to find the minimum-length tour visiting each city exactly once and returning to the starting point.

Data and Utility Functions

import math
import random

# Generate random cities
def generate_cities(n_cities, seed=42, width=100, height=100):
    """Generates n_cities random positions."""
    rng = random.Random(seed)
    cities = [(rng.uniform(0, width), rng.uniform(0, height)) for _ in range(n_cities)]
    return cities

# Calculate Euclidean distance between two cities
def distance(city_a, city_b):
    return math.sqrt((city_a[0] - city_b[0])**2 + (city_a[1] - city_b[1])**2)

# Calculate total tour length
def tour_length(tour, cities):
    total = 0.0
    for i in range(len(tour)):
        total += distance(cities[tour[i]], cities[tour[(i + 1) % len(tour)]])
    return total

# Generate a neighbor by swapping two positions
def swap_neighbor(tour):
    """Swaps two random positions in the tour."""
    new_tour = tour[:]
    i, j = random.sample(range(len(new_tour)), 2)
    new_tour[i], new_tour[j] = new_tour[j], new_tour[i]
    return new_tour

Running Simulated Annealing on the TSP

# Configuration
n_cities = 30
cities = generate_cities(n_cities, seed=42)

# Initial solution: random order
random.seed(42)
initial_tour = list(range(n_cities))
random.shuffle(initial_tour)

# Run simulated annealing optimization
best_tour, best_length, history = simulated_annealing(
    cost_func=lambda t: tour_length(t, cities),
    neighbor_func=swap_neighbor,
    initial_sol=initial_tour,
    initial_temp=1000.0,
    cooling_rate=0.998,
    min_temp=0.01,
    max_iter=500000,
    random_state=42
)

print(f"Best length found: {best_length:.2f}")
print(f"Iterations performed: {len(history) - 1}")

Trajectory Visualization with matplotlib

import matplotlib.pyplot as plt

# Plot cities and best tour
fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# Plot 1: the final tour
ax1 = axes[0]
for i in range(len(best_tour)):
    a = cities[best_tour[i]]
    b = cities[best_tour[(i + 1) % len(best_tour)]]
    ax1.plot([a[0], b[0]], [a[1], b[1]], 'b-', linewidth=1.5, alpha=0.8)
ax1.scatter( for c in cities],  for c in cities], c='red', s=50, zorder=5)
for i, (x, y) in enumerate(cities):
    ax1.annotate(str(i), (x, y), fontsize=9, ha='center', va='bottom')
ax1.set_title(f'Best tour (length = {best_length:.2f})')
ax1.set_xlabel('x')
ax1.set_ylabel('y')
ax1.grid(True, alpha=0.3)

# Plot 2: convergence
ax2 = axes[1]
ax2.plot(history, color='darkgreen', linewidth=1.5)
ax2.set_title('Simulated Annealing Convergence')
ax2.set_xlabel('Iteration')
ax2.set_ylabel('Tour length')
ax2.set_yscale('log')
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

Impact of the Cooling Schedule

The choice of cooling rate α is the most influential parameter. Let’s compare three configurations on the same 30-city TSP:

# Comparison of different cooling rates
for alpha in [0.90, 0.95, 0.995]:
    random.seed(42)
    init = list(range(n_cities))
    random.shuffle(init)

    _, cost, hist = simulated_annealing(
        cost_func=lambda t: tour_length(t, cities),
        neighbor_func=swap_neighbor,
        initial_sol=init,
        initial_temp=1000.0,
        cooling_rate=alpha,
        min_temp=0.01,
        max_iter=500000,
        random_state=42
    )
    print(f"alpha = {alpha:.3f} -> length = {cost:.2f}, iterations = {len(hist)-1}")

Typical results:
– α = 0.90 (fast cooling): convergence in ~100 iterations, but degraded solution — the algorithm is trapped in a local minimum.
– α = 0.95 (moderate): ~300 iterations, intermediate result — good speed/quality tradeoff.
– α = 0.995 (slow): ~1000+ iterations, solution closest to optimum — thorough space exploration.

This illustration shows the fundamental tradeoff between computation time and solution quality, inherent to all metaheuristics.

Hyperparameters: Tuning Guide

The performance of simulated annealing optimization depends strongly on five key hyperparameters:

Practical Method for Calibrating $T_0$

A good practice is to calibrate the initial temperature to achieve an initial acceptance rate of approximately 80%:

def calibrate_initial_temp(cost_func, neighbor_func, sol, n_samples=100, target_rate=0.8):
    """Estimates T_0 to achieve a target acceptance rate."""
    import math
    random.seed(42)
    deltas = []
    for _ in range(n_samples):
        neighbor = neighbor_func(sol)
        delta_e = cost_func(neighbor) - cost_func(sol)
        if delta_e > 0:
            deltas.append(delta_e)

    if not deltas:
        return 1000.0

    avg_delta = sum(deltas) / len(deltas)
    # P(accept) = exp(-delta/T) = target_rate
    # => T = -delta / ln(target_rate)
    t0 = -avg_delta / math.log(target_rate)
    return max(t0, 1.0)

This automatic approach avoids manual trial-and-error and adapts $T_0$ to the natural scale of the objective function.

Advantages and Limitations of Simulated Annealing

Advantages

1. Conceptual and implementation simplicity — a few lines of code suffice, without a complex population structure.
2. Escape from local minima — the Metropolis criterion allows crossing energy barriers.
3. Applicable to any problem — as long as you can define a cost function and a neighborhood, the algorithm applies. No need for derivatives or continuity.
4. Theoretical convergence guarantee — under logarithmic cooling, asymptotic convergence to the global optimum.
5. Minimal memory — only one current solution is stored, unlike genetic algorithms that maintain an entire population.
6. Easy to parallelize — multiple independent annealing runs can be executed from different initial solutions.

Limitations

1. Slow convergence — the asymptotic guarantee requires logarithmic cooling, impractical in real-world use.
2. Hyperparameter sensitivity — a poor choice of $T_0$ or $\alpha$ severely degrades performance.
3. No progressive learning — unlike genetic algorithms or PSO, simulated annealing does not capitalize on accumulated experience.
4. Inferior performance on certain problems — specific methods (linear programs, exact solvers) vastly outperform simulated annealing on problems where they apply.
5. Difficult neighborhood definition — for complex problems, designing a good neighborhood is an art in itself.

4 Concrete Use Cases

1. Industrial Scheduling (Job Shop Scheduling)

In a production workshop, the goal is to sequence a set of tasks on multiple machines while minimizing the makespan (total production time). Simulated annealing explores the space of task permutations, temporarily accepting longer schedules to discover globally better configurations. Industrial companies like Airbus and Bosch have successfully used this approach to optimize their assembly lines.

Neighborhood: reverse two consecutive tasks in the sequence. Cost function: total duration of the simulated schedule.

2. Circuit Board Component Placement (VLSI Placement)

Placing cells on an electronic chip must minimize total interconnection length while respecting density and non-overlap constraints. Simulated annealing is historically one of the first algorithms to have been successfully applied to this problem (Timberwolf tool, 1980s).

Neighborhood: randomly move a cell or swap two cells. Cost function: sum of estimated connection lengths (HPWL model).

3. Clustering and Image Segmentation

In computer vision, simulated annealing can be used to optimize the assignment of pixels to clusters, minimizing an energy combining fidelity to cluster centers and spatial regularity (penalizing dissimilar neighborhoods, as in a Potts model).

Neighborhood: reassign a pixel to a different cluster. Cost function: total model energy (data term + regularization term).

4. Financial Portfolio Optimization

Constructing an optimal portfolio under constraints (budget, diversity, maximum risk) is a difficult mixed-integer quadratic problem. Simulated annealing explores the space of discrete allocations, seeking the best return/risk tradeoff.

Neighborhood: slightly modify the weight of one asset (increase one, decrease another). Cost function: negative risk-adjusted Sharpe ratio.

See Also

• Mastering Maximal Arrangements in Python: Complete Guide and Tips for Developers
• Mastering Zebra Circles in Python: Complete Guide for Programming Enthusiasts