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 s imulated annealing systems utilizing traditional homogeneous temperature sc hedules. While most previous work in this area has focused on ad hoc experi mentally derived constant starting temperatures for the low-temperature ann ealing phase, this investigation presents a method for generalized starting temperature determination for the aforementioned class of two-stage simula ted annealing systems. We have tested our method on three NP-hard optimizat ion 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 s olution quality. (C) 1999 Elsevier Science Ltd. All rights reserved.