A stepwise-overlapped parallel simulated annealing algorithm

✍ Scribed by Youngtak Kim; Myunghwan Kim

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 937 KB
• Volume: 10
• Category: Article
• ISSN: 0167-9260
• DOI: 10.1016/s0167-9260(05)80034-3

✦ Synopsis

This paper proposes a parallel annealing algorithm, called stepwise-overlapped annealing, that can be efficiently implemented to a multiprocessor system with a large number of processors such as hypercube computers. It is an improved aigorithm of the systolic annealing that was ,proposed by Aarts et al. [8]. We introduce modifications for correcting the temperature decrement strategy and also enhance the communication pattern. Instead of the temperature decrement at each subchain, it calculates the temperature decrement at the start of each Markov chain with the standard deviation of a complete Markov chain previously processed.

It is based on an annealing schedule of polynomial time complexity. Experimental results show high efficiencies even when a large number of processors are used. The merit of this parallel annealing algorithm is a simple communication pattern and thus less communication overhead. This parallel annealing algorithm can also effectively replace the high temperature region of the application-dependent parallel simulated annealing algorithms.