SIMULATED ANNEALING ALGORITHM - TECHNICAL IMPROVEMENTS

We present an overview of the main problem-independent sequential and parallel amelioration techniques of the Stimulated Annealing algorithm . We begin by briefly exposing the theoretical framework encompassing the standard markovian model, the notion of cycle and the optimal temp erature schedules Theory of cycles yields explicit relationships betwe en the geometry Of the energy landscape and the expected behavior of t ile algorithm. It lends to the design of efficient temperature schedul es, as well as to improvements of the algorithm behavior by distorting the cost function. Next, we present a survey of parallelization techn iques, focussing on problem-independent synchronous strategies. They p rovide flexible and general tools, allowing operational research pract itioners to rake advantage of the computational power of parallel arch itectures. We conclude with an application. It concerns the search for Hamiltonian paths in cubic graphs. It brings to the fore the efficien cy of the cost function distortions technique, when used in combinatio n with Parallel Simulated Annealing. (C) Elsevier, Paris.