Dual Annealing is a global optimization algorithm.
As such, it is designed for objective functions that have a nonlinear response surface. It is a stochastic optimization algorithm, meaning that it makes use of randomness during the search process and each run of the search may find a different solution.
Dual Annealing is based on the Simulated Annealing optimization algorithm.
Simulated Annealing is a type of stochastic hill climbing where a candidate solution is modified in a random way and the modified solutions are accepted to replace the current candidate solution probabilistically. This means that it is possible for worse solutions to replace the current candidate solution. The probability of this type of replacement is high at the beginning of the search and decreases with each iteration, controlled by the “temperature” hyperparameter.
Dual annealing is an implementation of the classical simulated annealing (CSA) algorithm. It combines the annealing schedule (rate at which the temperature decreases over algorithm iterations) from “ fast simulated annealing ” (FSA) and the probabilistic acceptance of an alternate statistical procedure “ Tsallis statistics ” named for the author.
Experimental results find that this generalized simulated annealing algorithm appears to perform better than the classical or the fast versions of the algorithm to which it was compared. In addition to these modifications of simulated annealing, a local search algorithm can be applied to the solution found by the simulated annealing search.
This is desirable as global search algorithms are often good at locating the basin (area in the search space) for the optimal solution but are often poor at finding the most optimal solution in the basin. Whereas local search algorithms excel at finding the optima of a basin.
Pairing a local search with the simulated annealing procedure ensures the search gets the most out of the candidate solution that is located.