A Two-Stage Simulated Annealing Methodology

Authors:Varanelli, James, Department of Computer ScienceUniversity of Virginia Cohoon, James, Department of Computer ScienceUniversity of Virginia

We propose a two-stage simulated annealing method. While most previous work has focused on ad hoc experimentally-derived constant starting temperatures for the low temperature annealing phase, this paper instead presents a more formal method for generalized starting temperature determination in two-stage simulated annealing systems. We have tested our method on three NP-hard optimization problems using both classic and logarithmic cooling schedules. The experimental results have been consistently very good-on average the running time is halved when using a logarithmic cooling schedule and reduced by a third in the case of the classic schedule-with no loss in solution quality. We also present results for an alternative stop criterion used with the classic schedule that further reduces the two-stage running time by an additional five to ten percent in our problem suite.
Note: Abstract extracted from PDF text

All rights reserved (no additional license for public reuse)
Source Citation:

Varanelli, James, and James Cohoon. "A Two-Stage Simulated Annealing Methodology." University of Virginia Dept. of Computer Science Tech Report (1994).

University of Virginia, Department of Computer Science
Published Date: