## 6 Local Search Algorithms
### Simulated Annealing  
Simulated annealing is a powerful meta-heuristic optimization algorithm that draws inspiration from the annealing process used in metallurgy. In metallurgy, annealing involves heating a material to a high temperature and gradually cooling it down, thereby enhancing its properties. Similarly, simulated annealing utilizes this concept by iteratively exploring solution spaces to find optimal solutions. By mimicking the atom rearrangement in the cooling process, simulated annealing aims to converge toward a more orderly and improved state for the given problem.  
Simulated annealing operates on a similar principle. The algorithm initiates the best solution constructed by the BACA to the problem and proceeds iteratively to enhance it. By introducing small modifications to the solution, the algorithm continuously refines its quality. Even if these alterations lead to a potentially worse solution, simulated annealing accepts them with a decreasing probability as the algorithm advances. This unique characteristic enables the algorithm to overcome local minima and thoroughly explore the solution space, promoting the discovery of more optimal solutions.  
The following are the steps involved in simulated annealing:  
Initialize with a solution from BACA  
Repeat the following steps until a stopping criterion is met:Make small changes to the solution.
* Calculate the change in the objective function.
* Accept the change with a probability that depends on the change in the objective function and the temperature.
* Decrease the temperature.  
Algorithm 3 illustrates the simulated annealing algorithm with the BACA as pseudo-code.  
```
Input :best solution from BACA Output :the best solution obtained during the iterations
1 SA parameters:
2// BACA solution
3// initial temperature
4// cooling rate
5// stopping criterion
6// neighbor solution generation
7// fitness function
8 Initialization:
9// BACA solution
10// initial temperature
11// cooling rate
12 whiletemperature greater than thresholddo
13 generate a new neighbor solution by making a small change to current solution
14 evaluate the cost(fitness) of the current and new solution
15 ifcostNew \(<\) costCurrentthen
16 update current solution with new solution
17 ifcostNew \(<\) costBestSolutionthen
18 update best solution with new solution
19 update the current temperature by multiplying it with the cooling rate
20 return the best solution obtained during the iteration
```  
**Algorithm 3**Binary Ant Colony Algorithm with Simulated Annealing  
The acceptance probability uses an exponential function of the coverage difference and temperature. When the temperature is high early on, worse solutions have a decent chance of being accepted. As it decreases over iterations, worse solutions are less likely to be accepted. This allows thorough exploration early on, moving toward exploitation as the number of iterations increases. The temperature schedule and initial value require tuning for good performance. Temperature governs the likelihood of accepting worse solutions during the algorithm's progression. At the outset, the temperature is set high, favoring the acceptance of inferior solutions. As the algorithm advances, the temperature gradually decreases, leading to a reduced probability of accepting worse solutions.  
The stopping criterion in simulated annealing can be defined by a fixed number of iterations, a specific level of convergence, or a particular value of the objective function. Once the stopping criterion is satisfied, the algorithm concludes, returning the best solution discovered.