How Simulated Annealing Finds High‑Quality Solutions: A Step‑by‑Step Guide

1 Algorithm Steps

1.1 Initialization

Regarding the initial temperature, a larger initial temperature increases the probability of obtaining high‑quality solutions but requires more computation time. Higher temperature allows acceptance of worse solutions (larger search space) and slows the cooling rate (reducing convergence speed).

Common methods for setting the initial solution include:

(1) Sample a set of solutions from a probability distribution and use the variance of their objective values as the initial temperature (e.g., normal distribution).

(2) Randomly generate a set of states, determine the maximum objective difference between any two states, and compute the initial temperature using a predefined function.

(3) Use an empirical formula.

1.2 Generating a New Solution

To simplify subsequent calculations and acceptance decisions, and to reduce algorithm runtime, a new solution is usually generated by applying a simple transformation to the current solution, such as swapping or permuting all or part of its elements. The transformation method determines the neighborhood structure of the new solution, which influences the choice of cooling schedule.

1.3 Computing the Objective Function Difference

Since the objective‑function difference is caused only by the transformed part, it is best computed incrementally. Empirical evidence shows that incremental calculation is the fastest method for most applications.

1.4 Determining Whether the New Solution Is Accepted

The acceptance decision follows an acceptance criterion, most commonly the Metropolis criterion.

1.5 Replacing the Current Solution When the New One Is Accepted

If the new solution is accepted, it replaces the current solution by applying the same transformation to the current solution and updating the objective value, completing one iteration. The next iteration then begins. If the new solution is rejected, the current solution remains unchanged for the next trial.

1.6 Temperature Update and Next Iteration

2 Pseudocode