Scheduling simulated annealing

Fig. 3.1. The cooling schedule during a simulated annealing run of 106 MC steps with goal curvature c0 = 10 in a box of unit edge length. The temperature program corresponds to a = 3. The adaptive changes in 6

Catoni, 0. (1998) Solving scheduling problems by simulated annealing. SIAM J Contr Optim, 36, 1539-1575. 

It is probably correct to say that successful application of simulated annealing requires a clever definition ofndghborhoods in the configuration space (i.e., specification of individual "moves") and a ju dous variation of the control parameter p. In the case of metric spaces we would like to have a rationale for choosing an appropriate step size and for specifying a priori an effective cooling schedule. 

Das, H., Cummings, P. T., and Levan, M. D. (1990), "Scheduling of Serial Multiproduct Batch Processes via Simulated Annealing," Computers Chemical Engineering, 14, 1351-1362. 

Ku, H.-M., and Karimi, I. A. (1991a), "An Evaluation of Simulated Annealing for Batch Process Scheduling," Industrial Engineering Chemistry Research, 30, 1, 163-169. 

The success and efficiency of simulated annealing depends on the choice of the annealing schedule [58], that is, the sequence of numerical values Ti > T2 > > T for the temperature. Note that multiplication of the temperature T by a factor s is formally equivalent to scaling the target E by 1/s. This applies to both the Monte Carlo as well as the molecular dynamics implementation of simulated annealing. This is immediately obvious upon inspection of the Metropolis Monte Carlo acceptance criterion (Eq. 10). For molecular dynamics this can be seen as follows. Let E be scaled by a factor 1/s while maintaining a constant temperature during the simulation. 

The advantage of the procedure as just described is that it allows one to experiment with different annealing schedules and perhaps develop some physical intuition for the process. On the other hand, it is possible to use a standard method of applying a simulated annealing schedule to an optimization problem, as discussed by O Mard [5]. 

H. Das, P.T. Cummings, M.D. Le Van, Scheduling of serial multiproduct batch processes via simulated annealing. Computers Chemical Engineering, 14 (1990) 1351. 

H. Ku, An evaluation of simulated annealing for batch process scheduling. Industrial Engineering Chemistry Research, 30 (1991) 163. 

T. Satoh, K. Nara, Maintenance scheduling by using simulated annealing method, IEEE Transactions on Power Systems, 6 (1991) 850. 

E. Peyrol, P. Floquet, L. Pibouleau, Scheduling and simulated annealing application to a simiconductor circuit fabrication plant. Computers Chemical Engineering, 17... 

M. Huang, F. Romero, A. Sangiovanii-Vincentelli. An efficient general cooling schedule for simulated annealing. In Proc. of Int l Conf. Computer Aided Design, 1986, pp. 281 -384. 

---