We choose a standard simulated annealing approach for continuous global optimization problems to compute approximations of global optima. Since there are already good implementations of several codes in the public domain, we choose the code of Goffe, Ferrier and Rogers [11] as a starting point for our own implementation. After preliminary testing, we found that their code outperformed the code of Ingber [12] when applied to the facility dispersion problem above. However, we have not tried to fine tune every possible parameter in the implementation of Ingber. Doing this may result in significant performance gains.
It turned out that after the implementation of the objective function some changes in the parameters were necessary in order to have a program that produces good results. We list here only the most important parameters, for details about the implementation we refer to [10, 11].
We set the starting temperature of the simulated annealing algorithm to
T := 5.0. If N denotes the total number of facilities in the problem, the
temperature is reduced after 5 N steps according to
. The maximum number of function evaluations
is set to 100 N. The algorithm stops when the maximum number of function
evaluations is achieved or when the changes in the best known function values
during the last four temperature reductions and the differences between the
function values in the last step are less than
.
Note that, due to the peculiar chosen parameters, at most 20 temperature
reductions take place. Since the temperature is reduced by a fixed amount, the
algorithm used is in fact a specific form of simulated quenching, not simulated
annealing. However, after experimenting with different annealing schemes, we
never found that the algorithm got stuck in a nonglobal minimum, even with such
a strict annealing schedule.
As it can be seen, the stopping criterion based on function values is not a particular strict one. This is the case because there is no necessity for high accuracy in Phase I. The algorithm of the second phase will converge to the minimum approached by the simulated annealing algorithm much faster than a stochastic method.