Adaptive Simulated Annealing Technique

To understand how the Adaptive Simulated Annealing algorithm works, it helps to visualize the problems presented by such complex systems as a geographical terrain. For example, consider a mountain range, with two “parameters,” such as along the North-South and East-West directions. We want to find the lowest valley in this terrain. The ASA algorithm approaches this problem similar to using a ball that can bounce over mountains from valley to valley. We start at a high “temperature,” where the temperature is an ASA parameter that mimics the effect of a fast moving particle in a hot object like a hot molten metal; the ball is permitted to make very high bounces and is able to bounce over any mountain to access any valley, given enough bounces. As the temperature is made relatively colder, the ball cannot bounce so high, and it can settle, becoming trapped in relatively smaller ranges of valleys.

We imagine that our mountain range is aptly described by a “cost function” (the ObjectiveandPenalty parameter in Isight). We define probability distributions of the two directional parameters, called generating distributions, because they generate possible valleys or states we are to explore. We define another distribution, called the acceptance distribution, which depends on the difference of cost functions of the present generated valley we are to explore and the last saved lowest valley. The acceptance distribution decides probabilistically whether to stay in a new lower valley or to bounce out of it. All the generating and acceptance distributions depend on temperatures.

In a D-dimensional parameter space with parameters $p^i$ having ranges $[A_i,B_i]$, about the $k$’th last saved point (e.g., a local optima),$p_k^i$, a new point is generated using a distribution defined by the product of distributions for each parameter,$g^i(y^i,T_i)$, in terms of random variables $y^i$ in $[-1,1]$, where $p_k+1^i=p_k^i+y^i(B_i-A_i)$, and “temperatures” $T_i,g^i(y^i;T_i)=1/\left[2\left(\left|y^i\right|+T_i\right)(1+1/T_i)\right]$.

The cost functions, $C(p_k+1)-C\left(p_k\right)$, are compared using a uniform random generator, $U$ in $(0,1)$, in a “Boltzmann” test: If $\exp [-\left(C(p_k+1)-C\left(p_k\right)\right)/T_{\cos t}]>U$, where $T_{\cos t}$ is the “temperature” used for this test, the new point is accepted as the new saved point for the next iteration. Otherwise, the last saved point is retained.

The annealing schedule for each parameter temperature, $T_i$, from a starting temperature $T_{i}0$, is as follows:

$T_i\left(k_i\right)=T_{0i}\exp (-c_i{k}_i^{1/D})$.

The annealing schedule for the cost temperature is developed similarly to the parameter temperatures. However, the index for reannealing the cost function, $k_{\cos t}$, is determined by the number of accepted points, instead of the number of generated points as used for the parameters.

$T_{\cos t}\left(k_{\cos t}\right)=T_{0\cos t}\exp (-c_{\cos t}{k}_{\cos t}^{1/D})$.

As determined by the technique options selected, the parameter “temperatures” may be periodically adaptively reannealed or increased relative to their previous values, using their relative first derivatives with respect to the cost function, to guide the search “fairly” among the parameters.

As determined by the technique options selected, the reannealing of the cost temperature resets the scale of the annealing of the cost acceptance criteria using the new $T_{0\cos t}$ value. The new $T_{0\cos t}$ value is taken to be the minimum of the current initial cost temperature and the maximum of the absolute values of the best and last cost functions and their difference. The new $k_{\cos t}$ is calculated taking $T_{\cos t}$T_cost as the maximum of the current value and the absolute value of the difference between the last and best saved minima of the cost function, constrained not to exceed the current initial cost temperature. This procedure resets the scale of the annealing of the cost temperature within the scale of the current best or last saved minimum.