# Simulated Annealing with Exploratory Sensing for Global Optimization
## 2 Simulated Annealing and Sensing Memory
### Simulated Annealing Algorithm  
Annealing theory is based on condensed matter physics, where particles in a physical system control the behaviors of the annealing process [2]. Simulated annealing implements the Metropolis algorithm to emulate metal annealing in metallurgy, where heating and controlled cooling reshape the metal particles. Controlling the metal temperature carefully by increasing it to higher values and decreasing it arranges the particles to minimize the system energy. The standard SA algorithm is a successful randomized local search algorithm for finding minima or near minima solutions of optimization problems [60]. It is a particularly valuable tool for solving high dimensionality problems [61]. Although the SA method can find solutions for extensive range problems, its main drawback is the high computational time [60]. Let \(s\) be the current state and alternative states in its neighborhood \(N(s)\). One state \(s^{\prime}\in N(s)\) is selected, and the difference between the current state cost and the selected state energy is computed as \(D=f(s^{\prime})-f(s)\). _Metropolis criterion_ is used to choose \(s^{\prime}\) as the current state in two cases:  
* If \(D<=0\), means the new state has a smaller or equal cost, then \(s^{\prime}\) is chosen as the current state as down-hills is always accepted. * If \(D>0\), and the probability of accepting \(s^{\prime}\) is larger than a random value \(R_{nd}\) such that \(e^{-D/T}>R_{nd}\) then \(s^{\prime}\) is chosen as the current state where \(T\) is a control parameter known as _Temperature_. This parameter is gradually decreased during the search process, making the algorithm greedier as the probability of accepting uphill moves decreases over time. Moreover, \(R_{nd}\) is a randomly generated number, where \(0<R_{nd}<1\). Accepting uphill moves is important for the algorithm to avoid being stuck in local minima. In the last case where \(D>0\) and the probability is lower than the random value \(e^{-d/T}<=R_{nd}\), no moves are accepted, and the current state \(s\) continues to be the current solution. When starting with a large cooling parameter, large deterioration can be accepted. Then, as the temperature decreases, only small deterioration are accepted until the temperature approaches zero when no deterioration is accepted. Therefore, adequate temperature scheduling is essential to optimize the search. SA can be implemented to find the closest possible optimal value within a finite time where the cooling schedule can be specified by four components [60]:  
* Initial value of temperature. * A function to decrease temperature value gradually. * A final temperature value. * The length of each homogeneous Markov chains. A Markov chain is a sequence of trials where the trial outcome's probability only depends on the previous trial outcome. It is classified as homogeneous when the transition probabilities do not depend on the trial number [62]. The success of SA depends on how good the choice of its parameters. For instance, the algorithm can be stuck in a local minimum when choosing small initial temperatures since the exploration process must be carried during the first stages. On the other hand, a significant temperature could cause the convergence to be very slow. The same effect can be obtained when applying an inappropriate cooling schedule. Also, adjusting the neighborhood range for SA is essential in continuous optimization problems [63]. All inputs should not have the same step sizes, but these steps should be selected according to their effects on the objective function [64]. The authors in [65] proposed a method to identify the step size during the annealing process, which begins at significant steps and gradually decreases them. The initial temperature can also be chosen within the standard deviation of the mean cost of several moves [66]. When finite Markov chains are used to model SA mathematically, the temperature is reduced once for each Markov chain.