模拟退火算法简介与实例

模拟退火算法简介与实例 2010-07-10 12:30:55| 分类： algorithms | 标签： |字号大中小 订阅 摘要 模拟退火算法是 S. Kirkpatrick, C. D. Gelatt 和 M. P. Vecchi 在 1983 年所发明。是一种典型的概率模拟算法（ Monte Carlo 算法），其基本想想与冶金上的退火有相似之处，在一个相当大的空间内搜索最优解，而每次只搜索与自己临近的状态。此算法被证明以接近概率 1 接近最优解。其中有较好的物理思想，是模拟类算法中的典范。模拟退火算法由于要计算相临状态，这与 Ising 模拟的计算模拟有相似之处，因此本文也将对 Ising 做一个介绍。本文介绍算法的基本思想并做一个例子求解 TSP 问题（旅行商问题），重在介绍算法思想，具体算法的优化与改进不是本文涵盖范围。 1. Ising 模型 Ising 模型描述的是物体的铁磁性质，在铁和镍这类金属中，当温度低于居里温度时，原子的自旋自发地倾向某个方向，而产生宏观磁矩。温度高于居里温度时,自旋的取向非常紊乱,因而不产生净磁矩。当温度从大于或小于两边趋于居里温度时，金属的比热容趋于无限大。这是物质在铁磁性状态和非铁磁性状态之间的相变。伊辛模型就是模拟铁磁性物质的结构，解释这类相变现象的一种粗略的模型。它的优点在于，用统计物理方法，对二维情形求得了数学上严格的解。这就使得铁磁性物质相变的大致特征，获得了理论上的描述。 1.1 模型描述 这个模型所研究的系统是由 N 个阵点排列成 n 维周期性点阵，这里 n=2。点阵的几何构形可以是立方的或六角形的,每个阵点上都赋予一个取值+1 或-1 的自旋变量 i,如果 i+1,即第 N 个阵点的自旋向上；如i-1 ，即第个 N 阵点的自旋向下并且认为只是最近邻的自旋之间有相互作用。点阵的位形用一组自旋变量（这里 i2）来确定，如下图所示 图 1，模型图示 图 2，最近临磁子 1.2 模型计算 1)两个相临磁子趋向平行能量最低，即两个磁子的自旋方向非平行与平行。能量相差 E。 2)每个磁子的磁矩为 m,总的磁矩为每个磁子的磁矩和。 3)总的能量为每对相临磁子能量和。 4)随机选择晶格内的磁子，与和它相临的磁子比较，如果翻转后能量降低则接受翻转，如果能量升高则以概率 接受翻转， 为波尔兹曼常数。 5）模型选择周期性边界条件，即模型的左边界与右边界相联，上边界与下边界相联。 1.3 模拟结果 图 3 较低温度运行一段时间后 图 4 较低温度运行更长一段时间后 图 5 较高温度运行一段时间后 在较低的温度下运行一段时间后可以发现有相同磁矩块聚集的情况，即出现磁畴。具体比热计算与相变点计算本文不做进一步讨论。 2. 模拟退火算法 模拟退火算法的关键是与 Ising 模型的计算一样，要找到系统中的“ 能量”与“能量差”，并且使最优的解处在能量最小的地方，用概率法模拟能量的变化过程。下面双 TSP（旅行商问题）来说明这种方法，旅行商问题描述的是一个旅行商要在 N 之间游走来贩卖货物，而路费的成本与距离成正比，因此他想在 N 个城市之间找到仅一条最短路径，即能去所有城市一次且仅一次，最后回到出发点。这个简单的问题被证明为 NP 问题，对于 N 个城市的问题计算量为 O(N!),对于 N=40 时的计算量就已是目前全世界最强的计算机都难以解决。因此必须寻找其它的可行的算法。模拟退火算法就是其中一种。 2.1 计算步骤本算法对于 TSP 问题的计算方法如下，我们随机选择一种路径，称为一种配置。记这种配置为： 计算这种配置下的路径总长度 图 6 退火前的配置 我们随机选择其中的两个城市 I,j ,把之间的城市反转，之后把这个配置改变为： 计算此种配置下的路径总长度 是 的一个近临配置，如果 则我们就真的把原配置更新为新配置，如果 ,这种情况下并不直接拒绝这种新的配置，而是以概率 ,T 为算法中设定的温度，如果这种步骤不断进行下去，将使得总的路径长度趋于变小，但是如果 T 的值较大则路径长度不易达到最小，因 为较长的路径不易在模拟中被拒绝。但是随着模拟过程的进行，如果 T 的值不断减小，则能使路径不断减小，并且使较大的路径增长变化不易被接受。因此在模拟过程中要确定合适的温度变化速度，也就是退火速度。如果城市较多，则要减小温度变化的速度，这与冶炼中较大块的金属降温速度较慢一致。 图 7，经过两次模拟运算后的结果 在运算之前的路径的总长度为 36580.3，两次模拟之后的结果分别为 6025.71 和 5925.48 ，这个是模拟退火算法的特点，每次运算都有随机性，找到的不一定是最优解，但是与是优解的配置相差不多。 3. 模拟退火应用 模拟退火算法是随机模拟算法(Monte Carlo 算法)中十分重要的一种，此算法在求解最优解的过程中不易被最局部最优解束缚，因为在计算过程中对于较长的路径如果温度合适也能跳到长路径上去。此算法的主要对于系统的维度并不敏感，并且对于有多个，甚至成百上千的系统优化目标也不会显著增大计算量（相对于原问题中的指数级的运算量，此算法的计算果可近似看成是线性的），并且可以对于具体的问题和对于解的需求，可以调解系统中温度的变化速度，在解的精度和计算速度之间寻找一个权衡。 (注：本文关于 Ising 模型和模拟退火算法的源代码放在以下网址上，,仅供参考) /self.aspx/share/ising.rar/self.aspx/share/anneal.rar1. 参考文献1维基百科 simulated annealing 词条/wiki/Simulated_annealing2Application of