Title :
Optimal simulated annealing schedules for larger problems
Author :
Benfold, William ; Hallam, Jonathan ; Pr?¼gel-Bennett, Adam
Author_Institution :
Sch. of Electron. & Comput. Sci., Southampton Univ., UK
Abstract :
We present a method for optimizing parameters for a search algorithm (we choose simulated annealing as a specific example) on a finite search space. The search is described as a Markov process, giving the average cost on a specific problem as a function of the search parameters. A minimization is then performed over the parameter space to provide an optimal parameter set. We demonstrate this technique on a toy problem; we then use a ´barrier tree´ model to reduce 20-variable Max-SAT problems from over a million search points to more manageable 30-40 states. The annealing schedules produced do not perform as well as predicted, but there is some evidence that a single schedule optimized over a problem set may produce better results.
Keywords :
Markov processes; computability; minimisation; search problems; simulated annealing; Markov process; Max-SAT problem; barrier tree; finite search space; optimal parameter set; optimal simulated annealing schedule; parameter space minimization; search algorithm; toy problem; Computational modeling; Cost function; Intelligent systems; Markov processes; Optimal scheduling; Predictive models; Processor scheduling; Scheduling algorithm; Simulated annealing; Speech;
Conference_Titel :
Evolutionary Computation, 2005. The 2005 IEEE Congress on
Print_ISBN :
0-7803-9363-5
DOI :
10.1109/CEC.2005.1554816