Computing the initial temperature of simulated annealing

被引:114
作者
Ben-Ameur, W [1 ]
机构
[1] Inst Natl Telecommun, SAMOVAR, CNRS, INT,GET, F-91011 Evry, France
关键词
simulated annealing; initial temperature; acceptance ratio;
D O I
10.1023/B:COAP.0000044187.23143.bd
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 [运筹学与控制论]; 12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];
摘要
The classical version of simulated annealing is based on a cooling schedule. Generally, the initial temperature is set such that the acceptance ratio of bad moves is equal to a certain value chi(0). In this paper, we first propose a simple algorithm to compute a temperature which is compatible with a given acceptance ratio. Then, we study the properties of the acceptance probability. It is shown that this function is convex for low temperatures and concave for high temperatures. We also provide a lower bound for the number of plateaux of a simulated annealing based on a geometric cooling schedule. Finally, many numerical experiments are reported.
引用
收藏
页码:369 / 385
页数:17
相关论文
共 16 条
[1]
Aarts E., 1997, LOCAL SEARCH COMBINA, P91, DOI DOI 10.1038/S41598-021-83315-9
[2]
THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM [J].
BONOMI, E ;
LUTTON, JL .
SIAM REVIEW, 1984, 26 (04) :551-568
[4]
Simulated annealing: Searching for an optimal temperature schedule [J].
Cohn, H ;
Fielding, M .
SIAM JOURNAL ON OPTIMIZATION, 1999, 9 (03) :779-802
[5]
GROVER L, 1986, P IEEE ICCAD 86 SANT
[6]
COOLING SCHEDULES FOR OPTIMAL ANNEALING [J].
HAJEK, B .
MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (02) :311-329
[7]
OPTIMIZATION BY SIMULATED ANNEALING - AN EXPERIMENTAL EVALUATION .1. GRAPH PARTITIONING [J].
JOHNSON, DS ;
ARAGON, CR ;
MCGEOCH, LA ;
SCHEVON, C .
OPERATIONS RESEARCH, 1989, 37 (06) :865-892
[8]
OPTIMIZATION BY SIMULATED ANNEALING - AN EXPERIMENTAL EVALUATION .2. GRAPH-COLORING AND NUMBER PARTITIONING [J].
JOHNSON, DS ;
ARAGON, CR ;
MCGEOCH, LA ;
SCHEVON, C .
OPERATIONS RESEARCH, 1991, 39 (03) :378-406
[9]
Johnson DS., 1997, Local search in combinatorial optimization, P215, DOI DOI 10.1108/01445150910987763
[10]
OPTIMIZATION BY SIMULATED ANNEALING [J].
KIRKPATRICK, S ;
GELATT, CD ;
VECCHI, MP .
SCIENCE, 1983, 220 (4598) :671-680