模拟退火算法的原理及算法在优化问题上的应用

模拟退火算法是近年来在国内外都比较受关注的算法。它的思想最早在1953年由Metropolis提出，在1983年被Kirkpatrick等人成功引入组合优化领域。由于它具有很强的实用性和极佳的性能表现，迅速引起了很多专家学者的兴趣，不断对其进行研究。 本文阐述了模拟退火算法的原理，并从文献角度回顾了近年来较为成功并被广泛采用的对模拟退火算法进行的一些改进，对模拟退火是一种有益的补充。模拟退火算法主要应用在各种优化问题上，函数优化是其中非常重要的一个方面。本文举了两个函数优化的例子，观察应用模拟退火解决这两个问题的表现，并针对实际得到的结果对模拟退火算法的冷却进度表、有限终止性、可行性以及效果和效率进行了进一步的讨论。 NP问题是一个比较麻烦的问题，其解的规模随问题规模的增大而成指数级增长，对于一般的方法而言，当问题规模过大时，就失去了可行性。模拟退火作为一种随机算法，它的特点非常适于求解NP问题，比如著名的旅行商问题(Traveling Salesman Problem)。我们首先介绍了目前比较常用于解决此问题的蚁群算法和分支限界法的原理，然后用模拟退火算法来实现对TSP问题的求解，并将结果与遗传算法的结果进行比较，发现模拟退火算法的表现是令人称道的。由于算法的随机性，最好能结合有记忆的模拟退火算法，让我们得到更好的解。 同时，我们还对基于单位风险收益最大化原则的贷款优化组合决策模型进行了讨论，并将改进的模拟退火算法应用于其上。实际的结果表明，模拟退火算法在解决这类问题上有着优异的表现，而且，针对具体的问题，对模拟退火算法进行适当的改进也是完全有必要的。 另外，我们还将模拟退火算法应用到一个板式家具下料的工业优化问题上，通过对算法的改进，我们发现算法的表现也值得我们称道。