Detailed Analysis of Uphill Moves in Temperature Parallel Simulated Annealing and Enhancement of Exchange Probabilities
Yang Jun
School of Information Science,
Japan Advanced Institute of Science and Technology,
1-1 Asahidai, Tatsunokuchi, Ishikawa 923-1292, Japan
Satoshi Mizuta
Faculty of Science and Technology,
Hirosaki University,
3 Bunkyo-cho, Hirosaki-city, Aomori 036-8561, Japan
Abstract
This paper demonstrates that the probability of the occurrence of uphill moves in temperature parallel simulated annealing is so small that the effects of parallelization might be lost when the number of processing nodes is small. A modification in the probability of solution exchange between the processes is one tactic to recover the parallelization effects. This method is evaluated by a traveling salesman problem with 33 cities in China. The results of the experiments show that, although it violates the detailed balance condition, the modification can improve the quality of the solutions.
