A fast method for generalized starting temperature determination in homogeneous two-stage simulated annealing systems

We propose a method for determining the starting temperature in two-stage simulated annealing systems utilizing traditional homogeneous temperature schedules. While most previous work in this area has focused on ad hoc experimentally derived constant starting temperatures for the low-temperature annealing phase, this investigation presents a method for generalized starting temperature determination for the aforementioned class of two-stage simulated annealing systems. We have tested our method on three NP-hard optimization problems using both classic and adaptive homogeneous cooling schedules. The experimental results have been consistently very good - on average the running time is halved when using an adaptive cooling schedule and reduced by a third in the case of the classic schedule - with no average loss in solution quality. (C) 1999 Elsevier Science Ltd. All rights reserved.