Acceleration techniques for simulated annealing

Abstract

Combinatorial optimisation problems involve choosing the best solution from a finite set of mutually exclusive outcomes and are often deceptively difficult to solve. Simulated annealing is an heuristic method for finding 'good' solutions to optimisation problems. The technique is based on an analogy with a method in statistical mechanics designed to simulate the physical process of annealing. Decisions made when implementing the simulated annealing algorithm can affect both the algorithm efficiency (speed) and effectiveness. Since the time requirements of the simulated annealing algorithm can often be unacceptable, it is worth investigating various modifications to the basic simulated annealing algorithm in order to accelerate (i.e. 'speed up') its convergence to a good quality solution. Several techniques are investigated to accelerate the simulated annealing paradigm. These can be partitioned into two categories: those that are simple to implement and those that are more difficult to implement. Simple techniques include the selection of an appropriate annealing schedule, its subsequent parameter fine-tuning, and careful implementation of all problem specific coding requirements such as that represented by the incremental cost update procedure. Other techniques include the investigation of departures from 'pure' simulated annealing. Among these are: recording the best solution encountered in an annealing run, approximate exponentiation, approximate random number generation, and the implementation of a local search trigger. Techniques that are more arduous to implement include parallel simulated annealing, nested simulated annealing, and two stage simulated annealing. Most of these acceleration techniques are not mutually exclusive and several can often be used in combination to produce time savings of a magnitude greater than those available through the use of individual acceleration techniques. Dramatic time savings are generally unlikely, and although the simulated annealing algorithm can be made to perform more efficiently with a little care, it still remains slow when compared to tailored algorithms. Nevertheless, it possesses the ability to regularly produce very good solutions for some difficult combinatorial optimisation problems.