Simulated Annealing: Parameter Selection and Optimization Strategies
Simulated annealing is a powerful probabilistic technique used to find the global optimum of a complex function. To apply this method to a specific problem, a developer must carefully define several core parameters. Because no single configuration works for every scenario, the effectiveness of the algorithm depends heavily on how these components are tuned to the specific problem landscape.
The primary parameters required for implementation include the state space (all possible solutions), the energy function E() (the goal or cost function), the candidate generator neighbour() (the method for finding adjacent states), the acceptance probability function P(), and the annealing schedule temperature(), which includes the initial temperature (init_temp).
ไม่มีภาพประกอบ
Key Facts
- No Universal Settings: There is no general way to find the best parameters for all problems; they must be adjusted empirically.
- Graph Diameter: The candidate generator must ensure a short path from the initial state to the global optimum.
- Deterministic Updates: Threshold accepting can speed up optimization without sacrificing final quality.
- Energy Heuristics: Candidate generators are most effective when they prioritize moves to states with similar energy levels.
- Barrier Avoidance: Using diverse move types (e.g., segment-flips vs. pair-swaps) helps the algorithm escape deep local minima.
Designing the Candidate Generator
Simulated annealing can be viewed as a random walk on a search graph where vertices represent states and edges represent candidate moves. A critical requirement for the neighbour() function is that the diameter of this search graph—the longest shortest path between any two nodes—must be small enough to allow the algorithm to reach the global optimum efficiently.
Efficient Candidate Generation
As the algorithm progresses, the current state typically reaches a much lower energy than a random state. Therefore, the generator should be skewed toward candidate moves where the destination state's energy is similar to the current state. This heuristic avoids wasting iterations on extremely poor moves, which are far more common than extremely good ones.
For example, in the Traveling Salesman Problem (TSP), swapping two consecutive cities in a low-energy tour usually has a modest effect on total length. In contrast, swapping two arbitrary cities is more likely to increase the length significantly. Consequently, a consecutive-swap generator often outperforms an arbitrary-swap generator, despite the latter potentially offering a shorter path to the optimum.
Avoiding Energy Barriers
A major challenge in optimization is the presence of deep local minima—states that have much lower energy than all their neighbors, creating "closed catchment basins." These basins can trap the algorithm for a long time, with the escape time often being exponential relative to the energy difference between the basin bottom and the surrounding states.
To mitigate this, developers can implement diverse move types. In the TSP, two tours might be nearly equal in length but separated by a high-energy barrier if only pair-swaps are used. However, if the generator includes segment-flips (reversing the order of a set of consecutive cities), these two states may reside in the same basin, allowing the algorithm to move between them more easily.
Transition and Acceptance Probabilities
The transition probability is the likelihood that the algorithm moves from state s to state s'. This is influenced by the current temperature, the order in which candidates are generated, and the acceptance probability function P().
The Metropolis-Hastings Influence
A common acceptance function, defined by Kirkpatrick et al., sets the probability to 1 if the new state has lower energy (e' < e), and exp(-(e'-e)/T) otherwise. While this is based on physical systems and the Metropolis-Hastings algorithm, it is often used even when the candidate generator is not symmetric or probabilistic. In such cases, the algorithm's behavior may not actually mirror thermodynamic equilibrium, though this function remains a standard in many implementations.
Threshold Accepting
Research by Moscato, Fontanari, Dueck, and Scheuer suggests that deterministic updates—known as threshold accepting—can accelerate optimization. They argue that the stochastic nature of Metropolis updating is less important than the "smoothening" of the cost function landscape at high temperatures. Later research in 2001 confirmed that deterministic update strategies are optimal for a large class of random walk algorithms on cost landscapes.
ไม่มีภาพประกอบ
The Cooling Schedule
The cooling rate determines how the temperature decreases over time. Ideally, the rate should be slow enough for the system to remain near thermodynamic equilibrium. However, the relaxation time—the time required to restore equilibrium after a temperature change—varies based on the energy function's topography and the candidate generator.
Because these factors are often "black box" functions, the ideal cooling rate must be adjusted empirically. To solve this, adaptive simulated annealing algorithms link the cooling schedule to actual search progress. Some advanced approaches, such as Thermodynamic Simulated Annealing, automatically adjust the temperature based on the energy difference between states according to thermodynamic laws.
| Parameter | Role | Optimization Goal |
|---|---|---|
| Energy Function E() | Defines the goal/cost | Accurately represent the problem objective |
| Candidate Generator | Proposes new states | Small graph diameter; avoid deep basins |
| Acceptance Function P() | Decides if a move is accepted | Balance exploration vs. exploitation |
| Cooling Schedule | Controls temperature decay | Allow sufficient relaxation time |
Frequently Asked Questions
Why is there no universal set of parameters for simulated annealing?
The effectiveness of the algorithm depends on the specific "topography" of the energy function and the structure of the state space, which vary from one problem to another. Therefore, parameters must be tuned empirically for each unique case.
What is the difference between Metropolis updating and threshold accepting?
Metropolis updating uses a probabilistic rule to decide whether to accept a worse state, whereas threshold accepting uses a deterministic update. Threshold accepting can often speed up the process without reducing the quality of the final solution.
How does the candidate generator affect the search for the global optimum?
The generator defines the edges of the search graph. If the generator is too restrictive, the graph diameter becomes too large, or the algorithm may get trapped in deep local minima (catchment basins) that it cannot escape.
What is relaxation time in the context of cooling schedules?
Relaxation time is the duration the algorithm must wait for the probability distribution of the current state to return to equilibrium after the temperature has been lowered.
Why prioritize candidates with similar energy levels?
Since the current state is likely already at a low energy level, moves to states with similar energy are more likely to be accepted and lead to further improvements, whereas moves to very high-energy states are usually rejected.