Simulated Annealing
Simulated AnnealingThe algorithm is a general probabilistic algorithm that is used to find the optimal solution to a proposition in a large search space.
principle
Applying the theory of thermodynamics to statistics, imagine each point in the search space as a molecule in the air; the energy of a molecule is its own kinetic energy; and each point in the search space, like an air molecule, carries "energy" to indicate the degree of suitability of the point for the proposition.
The algorithm starts with an arbitrary point in the search space: at each step, a "neighbor" is selected and then the probability of reaching the "neighbor" from the current position is calculated.
Basic Elements
State Space and State Generation Function
1) The search space is also called the state space, which consists of the set of encoded feasible solutions.
2) The state generation function (neighborhood function) should ensure that the generated candidate solutions are distributed throughout the entire solution space as much as possible. It usually consists of two parts, namely the method of generating candidate solutions and the probability distribution of candidate solutions.
3) Candidate solutions are generally obtained by randomly sampling the solution space according to a certain probability density function.
4) Probability distribution can be uniform distribution, normal distribution, exponential distribution, etc.
State transition probability
1) State transition probability refers to the probability of transition from one state to another.
2) The common understanding is the probability of accepting a new solution as the current solution.
3) It is related to the current temperature parameter T and decreases as the temperature drops.
4) The Metropolis criterion is generally adopted.
Inner loop termination criteria
1) Check whether the mean of the objective function is stable.
2) The target value changes little over several consecutive steps.
3) Sampling according to a certain number of steps.
Outer loop termination criteria
1) Set the termination temperature threshold.
2) Set the number of outer loop iterations.
3) The optimal value searched by the algorithm remains unchanged for several consecutive steps.
4) Check whether the system entropy is stable.
Key Steps
New state generation function → New state acceptance function → Sampling stability criterion → Cooling function → Annealing end criterion
Advantages of Simulated Annealing
The simulated annealing algorithm can find the approximate optimal solution to the problem quickly. Under the premise of proper parameter setting, the simulated annealing algorithm has a high search efficiency.