Simulated annealing with extended neighbourhood

Research output: Journal PublicationsJournal Article (refereed)peer-review

49 Citations (Scopus)

Abstract

Simulated Annealing (SA) is a powerful stochastic search method applicable to a wide range of problems for which little prior knowledge is available. It can produce very high quality solutions for hard combinatorial optimization problems. However, the computation time required by SA is very large. Various methods have been proposed to reduce the computation time, but they mainly deal with the careful tuning of SA's control parameters. This paper first analyzes the impact of SA's neighbourhood on SA's performance and shows that SA with a larger neighbourhood is better than SA with a smaller one. The paper also gives a general model of SA, which has both dynamic generation probability and acceptance probability, and proves its convergence. All variants of SA can be unified under such a generalization. Finally, a method of extending SA's neighbourhood is proposed, which uses a discrete approximation to some continuous probability function as the generation function in SA, and several important corollaries of the general model are given. © 1991, Taylor & Francis Group, LLC. All rights reserved.
Original languageEnglish
Pages (from-to)169-189
Number of pages21
JournalInternational Journal of Computer Mathematics
Volume40
Issue number3-4
DOIs
Publication statusPublished - Jan 1991
Externally publishedYes

Keywords

  • algorithm analysis
  • combinatorial optimization
  • Simulated annealing
  • stochastic search

Fingerprint

Dive into the research topics of 'Simulated annealing with extended neighbourhood'. Together they form a unique fingerprint.

Cite this