How Simulated Annealing Beats Hill Climbing for Solving the Traveling Salesman Problem

Hill Climbing Overview

Hill climbing is a simple greedy search that repeatedly moves to the best neighboring solution until a local optimum is reached, but it cannot escape that local optimum.

Simulated Annealing Concept

Simulated annealing (SA) extends greedy search by occasionally accepting worse solutions with a probability that decreases as the temperature drops, allowing the algorithm to jump out of local optima and potentially reach the global optimum.

The acceptance rule is:

If J(Y(i+1)) >= J(Y(i)) (the new state is better), always accept.

If J(Y(i+1)) < J(Y(i)), accept with probability exp(dE/(kT)), where dE = J(Y(i+1)) - J(Y(i)) and k is a constant.

The probability formula originates from the physical annealing process: P(dE) = exp(dE/(kT)), where higher temperature yields higher chance of accepting an energy‑increasing move.

Pseudocode

/*
 * J(y): evaluation function value at state y
 * Y(i): current state
 * Y(i+1): new state
 * r: cooling rate (0 < r < 1)
 * T: system temperature (initially high)
 * T_min: lower temperature bound
 */
while (T > T_min) {
    dE = J(Y(i+1)) - J(Y(i));
    if (dE >= 0) {
        // better solution, always accept
        Y(i+1) = Y(i);
    } else {
        if (exp(dE / T) > random(0, 1)) {
            // accept worse move with probability exp(dE/T)
            Y(i+1) = Y(i);
        }
    }
    T = r * T; // cooling step
    i++;
}

Applying SA to the Traveling Salesman Problem (TSP)

The TSP asks for the shortest possible tour that visits each of N cities exactly once and returns to the start. Exact solutions require factorial time, so SA provides a fast approximation.

SA for TSP proceeds as:

Generate a new tour P(i+1) and compute its length L(P(i+1)).

If L(P(i+1)) < L(P(i)), accept the new tour; otherwise accept it with the SA probability, then lower the temperature.

Repeat until a stopping condition (e.g., temperature below T_min) is met.

Common ways to create a new tour include:

Swap two randomly chosen cities.

Reverse the order of cities between two randomly chosen positions.

Select three cities m, n, k and move the segment between m and n to follow k.

Algorithm Evaluation

Simulated annealing is a stochastic algorithm; it does not guarantee a global optimum but often finds a high‑quality near‑optimal solution quickly. Proper parameter tuning (initial temperature, cooling rate r, and stopping criteria) can make SA more efficient than exhaustive search for large instances.