智能优化理论-第14章模拟退火算法

第14章模拟退火算法模拟退火算法的提出固体退火过程的统计力学原理模拟退火算法的数学描述模拟退火算法的实现要素多目标模拟退火算法求解旅行商问题复习思考题contents目录模拟退火算法的提出01模拟退火算法是一种物理中固体物质的退火过程与一般组合优化问题之间的相似性而提出的算法。模拟退火算法具有全局收敛性、隐含并行性及广泛的适应性，能处理不同类型的优化设计变量，不需要任何辅助信息。模拟退火算法是一种具有全局优化能力的通用优化算法，广泛用于生产调度、控制工程、机器学习、神经网络等领域。模拟退火算法可用于求解不同的非线性问题，对不可微甚至不连续的函数优化，它以较大概率求得全局解。模拟退火算法的提出固体退火过程的统计力学原理02物理退火过程01模拟退火算法的基本思想源于对固体退火降温过程的模拟。02物理系统的退火是先将固体加热至熔化状态，再徐徐冷却使之凝固成规整晶体的热力学过程。金属（高温）退火（液体结晶）过程可分为烈下3个过程。03

物理退火过程高温过程在加温过程中，粒子热运动加剧且能量在提高，当温度足够高时，金属熔解为液体，粒子可以自由运动和重新排列。降温过程随着温度下降，粒子能量减少，运动减慢。结晶过程粒子最终进入平衡状态，固化为具有最小能量的晶体。物理退火过程固体退火过程可以视为一个热力学系统，是热力学与统计物理的研究对象。固体在加热过程中，随着温度的逐渐升高，固体粒子的热运动不断增强，能量在提高，于是粒子偏离平衡位置越来越大。当温度升至熔解温度后，固体熔解为液体，粒子排列从较有序的结晶态转变为无序的液态，这个过程称为熔解。输入标题02010403物理退火过程熔解过程系统能量随温度升高而增大。为了使系统在每一温度下都达到平衡态，最终达到固体的基态，退火过程必须徐徐进行，这样才能保证系统能量随温度降低而趋于最小值。当温度降至结晶温度后，粒子运动变为围绕晶体格子的微小振动，由液态凝固成晶态，这一过程称为退火。冷却时，随着温度徐徐降低，液体粒子的热运动逐渐减弱而趋于有序。用蒙特卡洛方法模拟固体在恒定温度下达到热平衡的过程时，必须大量采样才能得到比较精确的结果，会产生非常大的计算量。物理系统倾向于能量较低的状态，而热运动又妨碍它准确落入最低状态，如果采样时着重提取那些有重要贡献的状态，则可以较快地得到较好的结果。1953年，Metropolis等提出重要性采样法，其产生固体的状态序列的方法如下：先给定粒子相对位置表征的初始状态i，作为固体的当前状态，该状态的能量为Ei；Metropolis准则然后使随机选取的某个粒子的位移随机地产生微小变化，并得到一个新状态j，它的能量为Ej；如果Ej<Ei，则该新状态就作为重要状态，否则考虑到热运动的影响，根据固体处于该状态的概率来判断它是否是重要状态。固体处于状态i和状态j的概率的比值等于相应的Bolzmann因子的比值，即P(t)为在温度t下粒子处于内能Ei的概率分布函数；KB为Bolzmann常数；被称为配分函数。P(t)是一个小于1的数，用随机数发生器产生一个[0，1]区间上的随机数A，若P(t)<A，则新状态j作为重要状态，就以j取代i成为当前状态，否则仍然以i作为当前状态；Metropolis准则Metropolis准则010203重复上述新状态的产生过程，在大量迁移后，系统趋向能量较低的平衡状态，固体状态的概率分布趋于Gibbs正则分布。高温下可接受与当前状态的能量差较大的新状态作为重要状态，而在低温下只能接受与当前状态的能量差较小的新状态作为重要状态，当温度趋于零时，接受Ej>Ei的新状态j的概率为零。上述接受新状态的准则称为Metropolis接受准则，相应的算法称为Metropolis算法，这种算法的计算量显著减小。通过对上述物理现象的模拟，即可以得到函数优化的Metropolis接受准则。设S表示解空间，表示解空间到实数域的映射，t为模拟退火过程中的温度控制参数。假定L(S，f)存在邻域以及相应解的产生机制，f(i)和f(j)分别为解i和解j的目标函数值。由解i过渡到解j的接受概率采用以下Metropolis准则确定Metropolis准则模拟退火算法的数学描述03模拟退火算法的数学描述组合优化最小代价问题的求解过程，利用局部搜索从一个给定的初始解出发，随机生成新的解，如果这一代解的代价小于当前解的代价，则用它取代当前解。02不断地随机生成新解，重复上述步骤，直至求得最小代价值。组合优化问题与金属退火过程类比情况如表12.1所示。03在退火过程中，金属加热到熔解后会使其所有分子在状态空间S中自由运动。随着温度徐徐下降，这些分子会逐渐停留在不同的状态。01010203根据统计力学原理，早在1953年Metropolis就提出一个数学模型，用以描述在温度T下粒子从具有能量E(i)的当前状态i进入具有能量E(j)的新状态j的原则。若E(j)≤E(i)，则状态转换被接受；若E(j)>E(i)，则状态转换以如下概率被接受：其中，为转移概率；K为Boltzmann常数；T为材料的温度。模拟退火算法的数学描述在一个特定的环境下，如果进行足够多次的转换，将能达到热平衡。此时，材料处于状态i的概率服从Boltzmann分布。当高温时，则有：这一结果表明在高温下所有状态具有相同的概率。模拟退火算法的数学描述当温度下降，退火过程在每一温度下热力学系统达到平衡的过程，系统状态的自发变化总是朝着自由能减少的方向进行，当系统自由能达到最小值时，系统达到平衡态。时，则有：可见，当温度降至很低时，材料倾向进入具有最小能量状态。模拟退火算法的数学描述当温度相当高时每个状态分布的概率基本相同，接近平均值为状态空间中状态的总数。随着温度下降并降至很低时，系统进入最小能量状态。当温度趋于0时，分子停留在最低能量状态的概率趋向1。在同一温度，分子停留在能量最小状态的概率比停留在能量最大状态的概率要大。模拟退火算法的数学描述模拟退火算法的实现要素04从一个任意被选择的初始解出发探测整个空间，并且通过扰动产生一个新解，按照Metropolis准则判断是否接受新解，并降低控制温度。模拟退火算法的执行策略由如下步骤构成Simulatedannealing()模拟退火算法的流程的伪代码实现过程模拟退火算法的实现流程Initialize(i0,t0,l0);模拟退火算法的实现流程03do循环{01k=0;02i=iopt;模拟退火算法的实现流程123for(L=1;L<=l0;L++){Generate(i,j);Metropolis(j,i);模拟退火算法的实现流程模拟退火算法的实现流程010203Update(lk,tk,k);}whileStop-criterion()k=k+1;在上述算法中，i0，t0，l0分别表示初始状态的解、控制参数（相当于温度t）以及解产生次数的初始值。下标k表示迭代次数，lk表示第k轮迭代中解产生的次数。函数Initialize(i0,t0,l0)表示初始化，Generate(i,j)表示从解i产生一个新的解j，Metropolis(j,i)表示解的接受准则，Update(lk,tk,k)表示更新lk，tk，k的值，Stop-criterion0表示算法的终止准则。模拟退火算法的实现流程模拟退火算法的实现流程在实际应用中，SA必须在有限时间内实现，因此需要下述条件。010203起始温度。控制温度下降的函数。决定在每个温度下状态转移（迁移）参数的准则。模拟退火算法的实现流程模拟退火算法的实现流程终止SA的准则。终止温度。用模拟退火算法解决优化问题包括三部分内容：一是对优化问题的描述，在解空间上对所有可能解定义代价函数；二是确定从一个解到另一个解的扰动和转移机制；三是确定冷却过程。冷却进度表是一组控制算法进程的参数，用来逼近模拟退火算法的渐进收敛性态，使算法在有限时限执行过程后返回一个近似最优解。冷却进度表包括控制参数的初值及其衰减函数、每个温度值对应的迭代次数和终止准则。控制参数的初值t0是影响模拟退火算法全局搜索性能的重要因素之一，其值高，则搜索到全局最优解的可能性大，但相应的计算代价高；反之，则计算代价降低，但是得到全局最优解的可能性减小。冷却进度表冷却进度表在实际应用中，t0般需要根据试验结果进行多次调整，通常t0的取值较大。Markov链是一个尝试序列，其中某次尝试的结果仅由前一尝试的结果所决定，因而具有记忆遗忘功能。Markov链的长度lk表示Metropolis算法在第k次迭代时产生的新解的数目。Markov链长度的选取原则是：在控制参数t的衰减函数己选定的前提下，对Markov链长度的选取，应该满足在控制参数的每一个取值上解的概率分布都趋于平稳分布。由于新解被接受的概率随tk的递减而减小，故接受固定数量的新解需要产生的新解数随之增多。当tk→0时，lk→为限定lk的值，以免在tk值较小时产生过长的Markov链。常用的lk的确定方法为固定长度lk=l和由接受和拒绝的比例来控制迭代步数。在控制参数的每一取值上趋于平稳分布需要产生的新解数，可由恢复平稳分布至少应接受的新解数（某些固定数）来确定。冷却进度表为避免算法进程产生过长的链，应使温度缓缓降低，即控制参数的衰减量以小为益。控制参数的衰减量较小时，算法进程迭代次数可能增多，因而可以期望算法进程中被接受的新解增多，可以访问更多的邻域，搜索更大范围的解空间，返回更高质量的最终解，同时计算时间也会增多。试验表明，只要衰减函数选取恰当，就能在不影响计算时间合理性的前提下，较大幅度地提高最终解的质量。冷却进度表多目标模拟退火算法05传统的模拟退火算法只针对单个优化目标进行求解，而在多目标问题中，各个目标可能是相互冲突的或者相互独立的，不能直接比较解的优劣。近年来也有一些研究成果结合了多目标优化问题的特性，设计了多目标模拟退火算法来解决问题。多目标模拟退火(Multi-objectiveSimulatedAnnealing，MOSA)算法的研究始于1985年，早期的工作还包括Ulungu等和Serafini等设计的一个完整的MOSA，并将其应用于多目标组合优化问题。010203多目标模拟退火算法由于物体退火与多目标优化问题之间的本质联系，模拟退火算法适合扩展并应用于多目标优化问题的求解。多目标模拟退火算法的出现为多目标优化问题的求解开辟了一条新的途径，在多目标优化算法中也己表现出良好的性能和前景。已有很多多目标模拟退火算法相关的研究，多目标模拟退火算法的基本流程描述如下多目标模拟退火算法对算法的相关参数进行初始化，如初始温度、迭代次数等。步骤1步骤2步骤3随机产生初始解i，计算其所有目标函数值f(i)并将其加入Pareto解集中。给定一种随机扰动，产生i的邻域解j，计算其所有目标函数值f(j)。030201多目标模拟退火算法比较新产生的邻域解j与Pareto解集中的每个解，更新Pareto解集。步骤4如果新邻域解j进入Pareto解集，则用解j替代解i，转到步骤8。步骤5按某种方法计算接受概率。步骤6多目标模拟退火算法步骤7如果新解j未进入Pareto解集，则根据接受概率决定是否接受新解。如果新解j被接受，则令其为新的当前解i；如果新解j未被接受，则保留当前解i。每隔一定迭代次数，从Pareto解集中随机选择一个解，作为初始解，重新搜索。采取某种降温策略，执行一次降温。步骤8步骤9多目标模拟退火算法多目标模拟退火算法01步骤10:重复步骤3～步骤9，直到达到最低温度，输出结果，算法结束。02多目标模拟退火算法受到广泛重视，并在很多工程领域得到迅速