模拟退火算法

模拟退火算法摘要：模拟退火算法是一种新的随机搜索方法，它来源于固体退火原理，基于MetropoliS接受准则，与以往的近似算法相比，具有以一定的概率接受恶化解，引进算法控制参数，隐含并行性等特点；模拟退火算法应用范围很广，其应用需要满足三方面的要求，具有描述简单、使用灵活、运行效率高和较少受初始条件约束等优点，然而收敛速度慢，执行时间长，特别适合并行计算。关键词：模拟退火算法来源；基本思想；特点；一般要求；优缺点1.引子在科学与工程计算中，经常发生的一个问题是在Rn中或者是在一个有界区域上求某个非线性函数f(x)的极小点。在f(x)可导时，一个最基本的算法就是最速下降法。这一方法从某一选定的初值开始，利用如下公式进行迭代，即此处表示函数梯度，是一个与迭代步数有关的参数，它的适当选取，保证每步迭代均使函数值下降。除此之外，还存在多种寻求函数极小的算法。然而以速降法为代表的传统算法具有共同的缺点，它们都不保证求得全局极小，只能保证收敛到一个由初值决定的局部极小点。而模拟退火算法的出现很好地解决了这个问题。2.SA算法的起源模拟退火算法来源于固体退火原理，其核心思想与热力学的原理极为类似，尤其相似于液体流动和结晶以及金属冷却和退火的方式。高温下，液体的大量分子彼此之间进行着相对自由移动。如果该液体慢慢地冷却，热能可动性就会消失。大量原子常常能够自行排列成行，形成一个纯净的晶体，该晶体在各个方向上都被完全有序地排列在几百万倍于单个原子的距离之内。因此，这一过程的本质在于缓慢地冷却，以争取足够的时间，让大量原子在丧失可动性之前进行重新分布，这是确保到低能量状态所必需的条件。简单而言，物理退火过程由以下三部分组成：1)加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。熔解过程与系统的熵增过程相联系，系统能量也随温度的升高而增大。2)等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。3)冷却过程。其目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。模拟退火算法与物理退火过程的相似关系模拟退火物理退火解粒子状态最优解能量最低态设定初温溶解过程Metropolis采样过程等温过程控制参数的下降冷却目标函数能量3.SA算法的基本思想3.1 Metropolis准则固体在恒定温度下达到热平衡的过程可以用Morte Carlo算法方法加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。鉴于物理系统倾向于能量较低的状态，而热运动又防碍它准确落到最低态。采样时着重选取那些有重要贡献的状态则可较快达到较好的结果。因此，MetropoliS等在1953年提出了重要的采样法，即以概率接受新状念。其具体描述如下。先给定以粒子相对位置表征的初始状态作为固体的当前状态，该状态的能量为，然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新的状态，新状态的能量是，如果，则接受新状态为当前状态；否则，考虑到热运动的影响，该新状态是否“接受”要依据粒子处于该状态的几率来判断。如果新状态可以接受，那么就以取代成为当前状态，重复以上新状态的产生过程。在大量迁移(固体状态的变换称为迁移)后，系统趋于能量较低的平衡状态。通过对上述物理现象的模拟，可以得到函数优化的MetropoliS接受准则。3.2 SA算法的思想由初始解i和控制参数初值t开始，对当前解重复 产生新解 计算目标函数差 接受或舍弃的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。3.3 SA算法的特点SA算法与其它搜索方法相比，具有如下的特点：1）以一定的概率接受恶化解；模拟退火算法(SA)在搜索策略上与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模拟退火算法在迭代过程中不仅接受佳目标函数变“好”的试探点，而且还能以一定的概率接受使目标函数值变“差”的试探点，迭代中出现的状态是随机产生的，并不强求后一状态一定优于前一状态，接受概率随着温度的下降而逐渐增大。传统的方法很容易限于局部最优解而停滞不前，很多传统的优化算法往往是确定性的，从一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往可能使得搜索永远达不到最优点，因而限制了算法的应用范围。模拟退火算法(SA)以一种概率的方式来进行搜索，增加了搜索过程的灵活性。2）引进算法控制参数；引进类似于退火温度的算法控制参数，它将优化过程分成各个阶段，并决定各个阶段下随机状态的取舍标准，接受函数由Metropolis算法给出一个简单的数学模型。模拟退火算法的两个重要步骤是：一是在每个控制参数下，出前迭代点出发，产生邻近的随机状态，由控制参数确定的接受准则决定此新状念的取舍，并由此形成一定长度的随机Markov链；二是缓慢降低控制参数，提高接收准则，直至控制参数趋于零，状态链稳定于优化问题的最优状态，提高模拟退火算法全局最优解的可靠性。3）使用对象函数值进行搜索；传统搜索算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其它一些辅助信息才能确定搜索方向，当这些信息不存在时，算法就失效了。而模拟退火算法仅使用由目标函数变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需其它的辅助信息。需要着重指出的是：模拟退火算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定，对适应度函数唯一的要求是对于输入可计算出加以比较的正的输出。这个特性对很多无法或很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用模拟退火算法就比较方便。4）隐含并行性；并行算法是60年代发展起来的，其发展速度相当快。有些专家甚至认为目前提高计算机系统性能的唯一方法是“选择大量的并行”。从目前情况看，并行算法的设计主要采用两种方法：一是对现有的串行算法加工改造，使之成为好的并行算法；二是结合所用并行计算机的结构特点，直接设计新的并行算法。将模拟退火算法改造为并行算法还是比较容易的。目前常见的有以下几种并行策略：操作并行策略，试演并行策略，区域分裂策略和混乱松弛策略等。这几种并行算法在不同程度上对解的质量，收敛速度上较模拟退火算法优，由此可预见，模拟退火算法隐含并行性，它是优于其它求解过程的关键所在。另外模拟退火算法的隐含并行性还有助于处理非线性问题。5）搜索复杂区域。模拟退火算法最善于搜索复杂地区，从中找出期望值高的区域，在求解简单问题上效率并不高。4.SA算法的基本步骤1) 随机产生一个初始解x0，令xbest x0并计算目标函数值E(x0);2) 设置初始温度T(0)=T0，迭代次数i = 1;3) Do while T(i) Tmin 1) for j = 1k 2) 对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算 新的目标函数值E(xnew) ，并计算目标函数值的增量E = E(xnew) - E(xbest) 。 3) 如果E 0，则xbest = xnew； 4) 如果E 0，则p = exp(- E /T(i); 1) 如果c = random0,1 p， xbest = xnew; 否则xbest = xbest。 5) End for4) i = i 1；5) End Do6) 输出当前最优点，计算结束。5.SA算法的应用范围与一般要求SA算法是近年来备受重视的一类软计算方法，能解决传统的非线性规划方法难于解决的某些问题，在VLSI、生成调度、控制工程、机器学习、神经网络、图像处理、函数优化等许多领域得到广泛的研究。 SA算法的应用需满足如下三个方面的要求：1）对问题的简明形式的描述即数学模型，由解空间、目标函数和初始解三部分构成；a解空间为问题的所有可能(可行或不可行)解的集合，它限定了初始解选取和新解产生时的范围，对无约束优化问题，解空间就是所有可行解的集合，而在许多组合优化问题中，解除了满足目标函数最优外，还必须满足一组约束。因此，在解集中可能包含一些不可行解。b目标函数是对问题的优化目标的数学描述，通常表述为若干优化目标的一个和式，目标函数的选取必须正确体现问题的整体优化要求。一般来说，目标函数不一定就是问题的优化目标函数值，但对应关系很明显。此外，目标函数应当易于计算这将有利于在优化过程中简化目标函数差的计算，便于提高算法效率。c初始解是算法开始迭代的起点。初始解的选取应使得算法导出较好的最终解，但大量试验结果表明，模拟退火算法是一种“健壮”的算法，即算法的最终解对于仞始解的依赖性不大。2）新解的产生和接受机制；a出一个产生装置从当前解出发在解空间中产生一个新解，便于下面的计算和接受，通常选择由当前解经过简单的变换即可产生新解的方法，如对构成解的全部或部分元素进行置换、互换或反演等，新解的产生方法决定了当前解的邻域结构。b计算与新解伴随的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。c判断新解是否被接受。判断的依据是Metropolis准则。此外，在有约束的组合优化问题中，该接受准则还应加上对新解的可行性判定。d新解被确定接受时，用新解代替当前解，同时修正目标函数值。此时，当前解实现了一次迭代。可在此基础上丌始下一轮试验。当新解被判定为舍弃时，则在原当前解基础上继续下一轮试验。3）冷却进度表。所谓的冷却进度表是一组控制算法进程的参数用以逼近模拟退火算法的渐进收敛性态，使算法在有限时限执行过程后返回一个近似最优解。冷却进度表包括控制参数的初值、及其衰减函数、对应的Markov链的长度和停止准则。它是影响模拟退火算法试验性能的重要因素，其合理选取是算法应用的关键。6.SA算法的优缺点与同类方法相比，SA算