Simulated annealing with extended neighbourhood
Simulated annealing with extended neighbourhood
复制标题
DOI：
10.1080/00207169108804011
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
X. Yao
中科院分区：
文献类型：
--
作者：
X. Yao
模拟退火（SA）是一种强大的随机搜索方法，适用于范围广泛的问题，很少有先验知识。它可以为困难的组合优化问题产生非常高质量的解决方案。然而，SA所需的计算时间非常大。已经提出了各种方法来减少计算时间，但它们主要涉及SA'ol参数的仔细调整。本文首先分析了SA的邻域对SA性能的影响，并表明具有较大邻域的SA优于具有较小邻域的SA。给出了同时具有动态生成概率和动态接受概率的SA一般模型，并证明了其收敛性。SA的所有变体都可以在这样的推广下统一起来。最后，提出了一种扩展SA邻域的方法，该方法采用连续概率函数的离散逼近作为SA的生成函数，并给出了该方法的几个重要推论。
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'ol parameters. This paper first analyzes the impact of SA'neighbourhood on SA'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 genera...