flowchart TD
A[Start] --> B[Initialize Solution]
B --> C[Set Initial Temperature]
C --> D[Begin Optimization Loop]
D --> E[Select Neighbor]
E --> G[Accept New Solution?]
G -->|Yes| H[Update Current Solution]
H --> I[Reduce Temperature]
I --> J{Check Termination Criteria}
J -->|No| D
J -->|Yes| K[End]
G -->|No| I
3 Simulated Annealing Workflow
Simulated Annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space. It is often used when the search space is discontinuous and steep valleys and peaks complicate the path to the global maximum or minimum. The algorithm is inspired by the process of annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heating process causes the atoms to become disordered and then the slow cooling process attempts to bring the system to a more ordered state.
3.1 Algorithm Workflow
The workflow for the Simulated Annealing algorithm is typically as follows:
- Initialization:
- Start with an initial solution (often generated at random).
- Set an initial temperature that is high enough to allow for exploration of the entire search space.
- Define the cooling schedule, which is the process of lowering the temperature gradually as the algorithm proceeds.
- Iterative Optimization:
- Select a neighbor: At each step of the algorithm, generate a “neighboring” solution. This is typically a small random variation of the current solution.
- Calculate the change in energy (cost difference): Determine the difference in the objective function values between the current solution and the generated neighbor.
- Decide to accept the new solution: This decision is made using the Metropolis criterion:
- If the new solution improves the objective function (i.e., it has lower energy in minimization problems), it is always accepted.
- If the new solution does not improve the objective function, it may still be accepted with a probability that depends on the difference in the objective function values and the current temperature. The probability is calculated using the formula \(P = e^{-\Delta e/t}\) where \(\Delta e\) is the change in energy, and \(T\) is the current temperature.
- Cooling:
- Reduce the temperature according to the cooling schedule. This reduction in temperature reduces the probability of accepting worse solutions, thus allowing the algorithm to focus more on exploitation rather than exploration as it converges.
- Termination:
- Repeat the iterative process of exploring neighboring solutions and adjusting temperatures until a stopping criterion is met, such as reaching a minimum temperature, a maximum number of iterations, or a satisfactory solution stability.
Figure 3.1 shows the workflow of simulated annealing.