CONVERGENCE OF SIMULATED ANNEALING WITH FEEDBACK TEMPERATURE SCHEDULES

It is well known that the standard simulated annealing optimization me thod converges in distribution to the minimum of the cost function if the probability alpha for accepting an increase in costs goes to 0. al pha is controlled by the ''temperature'' parameter, which in the stand ard setup is a fixed sequence of values converging slowly to 0. We stu dy a more general model in which the temperature may depend on the sta te of the search process. This allows us to adapt the temperature to t he landscape of the cost function. The temperature may temporarily ris e such that the process can leave a local optimum more easily. We give weak conditions on the temperature schedules such that the process of solutions finally concentrates near the optimal solutions. We also br iefly sketch computational results for the job shop scheduling problem .