On the Design of an Adaptive Simulated Annealing Algorithm

In Proceedings of the International Conference on Principles and Practice of Constraint Programming First Workshop on Autonomous Search. AAAI Press, .



In this paper, we demonstrate the ease in which an adaptive simulated annealing algorithm can be designed. Specifically, we use the adaptive annealing schedule known as the modified Lam schedule to apply simulated annealing to the weighted tardiness scheduling problem with sequence-dependent setups. The modified Lam annealing schedule adjusts the temperature to track the theoretical optimal rate of accepted moves. Employing the modified Lam schedule allows us to avoid the often tedious tuning of the annealing schedule; as the algorithm tunes itself for each instance during problem solving. Our results show that an adaptive simulated annealer can be competitive when compared to highly tuned, hand crafted algorithms. Specifically, we compare our results to a state-of-the-art genetic algorithm for weighted tardiness scheduling with sequence-dependent setups. Our study serves as an illustration of the ease with which a parameter-free simulated annealer can be designed and implemented.