模拟退火算法(完整版)ppt资料课件.ppt

1、模拟退火算法模拟退火算法是什么？是怎样提出来的？模拟退火算法是什么？是怎样提出来的？模拟退火算法模拟退火算法Simulated Annealing，SA是一种模拟物理退火的过程而设计的优化算法。是一种模拟物理退火的过程而设计的优化算法。它的根本思想最早在它的根本思想最早在1953年就被年就被Metropolis提出，提出，但直到但直到1983年年Kirkpatrick等人才设计出真正等人才设计出真正意义上的模拟退火算法并进行应用。意义上的模拟退火算法并进行应用。 模拟退火算法的根本思想是怎样的？模拟退火算法的根本思想是怎样的？模拟退火算法采用类似于物理退火的过程，模拟退火算法采用类似于物理退火

2、的过程，先在一个高温状态下相当于算法随机搜索，然后逐渐退火，先在一个高温状态下相当于算法随机搜索，然后逐渐退火，在每个温度下相当于算法的每一次状态转移徐徐冷却在每个温度下相当于算法的每一次状态转移徐徐冷却相当于算法局部搜索，最终到达物理基态相当于算法局部搜索，最终到达物理基态相当于算法找到最优解。相当于算法找到最优解。 简介简介l模拟退火算法的来源是根据复杂组合优化问题模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。与固体的退火过程之间的相似之处。l该算法在系统向着能量减小的趋势变化过程中，该算法在系统向着能量减小的趋势变化过程中，偶尔允许系统跳到能量较高的状态，以避开

3、局偶尔允许系统跳到能量较高的状态，以避开局部最小，最终稳定在全局最小。部最小，最终稳定在全局最小。简介简介lSAA属于随机模拟算法属于随机模拟算法l模拟统计物理学中物体加热后冷却这一退模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法，意图是防火过程而建立的随机优化算法，意图是防止陷入局部极小解，早期用于组合优化，止陷入局部极小解，早期用于组合优化，后来开展成一种通用的优化算法。后来开展成一种通用的优化算法。根本思想根本思想lSAA是是基于基于Mente Carlo迭代求解策略的一种迭代求解策略的一种随机寻优算法，其随机寻优算法，其出发点出发点是基于物理中固体物是基于物理中固体物质

4、的退火过程与一般组合优化问题之间的相似质的退火过程与一般组合优化问题之间的相似性。另一方面，性。另一方面，结合爬山法和随机行走。结合爬山法和随机行走。lSAA在某一初温下，伴随温度参数的不断下降，在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优。出并最终趋于全局最优。 模拟退火算法是一种通用的优化算法，目模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。前已在工程中得到了广泛应用。 根本思路根本思路l首先在高温下

5、进行搜索，此时各状态出现概率首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入相差不大，可以很快进入“热平衡状态，这热平衡状态，这时进行的是一种时进行的是一种“粗搜索，也就是大致找到粗搜索，也就是大致找到系统的低能区域；系统的低能区域；l随着温度的逐渐降低，各状态出现概率的差距随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。来越准确的找到网络能量函数的全局最小点。一、模拟退火算法概述一、模拟退火算法概述二、模拟退火算法的马氏链描述及收敛性二、模拟退火算法的马氏链描述及收敛

6、性三、模拟退火算法关键参数和操作设计三、模拟退火算法关键参数和操作设计四、模拟退火算法的改进及其并行性四、模拟退火算法的改进及其并行性五、模拟退火算法的实现及应用五、模拟退火算法的实现及应用固体退火过程固体退火过程Metropolis准那么准那么组合优化与物理退火的相似性组合优化与物理退火的相似性模拟退火算法的步骤模拟退火算法的步骤第一节第一节 模拟退火算法概述模拟退火算法概述 l算法的提出算法的提出l 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等等1953提出，提出，1983年年Kirkpatrick等将其应用于等将其应用于组合优化。组合优化。l Optimizat

7、ion by simulated annealing, IBM Research Reportl算法的目的算法的目的l 解决解决NP复杂性问题提供有效近似算法；复杂性问题提供有效近似算法；l 克服优化过程陷入局部极小；克服优化过程陷入局部极小；l 克服初值依赖性。克服初值依赖性。1、源于对固体退火过程的模拟；、源于对固体退火过程的模拟；2、采用、采用Metropolis接受准那么；接受准那么；3、用冷却进度表控制算法进程，使算法在多、用冷却进度表控制算法进程，使算法在多项式时间里给出一个近似解。项式时间里给出一个近似解。 固体退火过程的物理图像和统计性质是固体退火过程的物理图像和统计性质是SA

8、A的的物理背景；物理背景；Metropolis接受准那么使算法跳离局部接受准那么使算法跳离局部最优最优 “险井；而冷却进度表的合理选择是算法应险井；而冷却进度表的合理选择是算法应用的前提。用的前提。 l算法的根底算法的根底 l固体退火过程固体退火过程l 什么是退火：什么是退火：l 退火是指将固体加热到足够高的温度，使分退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体到达某种稳定最后分子以低能状态排列，固体到达某种稳定状态。状态。 固体退火是将固体加热至融化，再徐固体退火是将固体加热至融化，再徐徐冷

9、却使之凝固成规整晶体的热力学过程，徐冷却使之凝固成规整晶体的热力学过程，属于热力学与统计物理研究的范畴。属于热力学与统计物理研究的范畴。由以下三局部组成：由以下三局部组成：加温过程加温过程等温过程等温过程冷却过程冷却过程固体在恒定温度下到固体在恒定温度下到达热平衡的过程！达热平衡的过程！ l固体退火过程固体退火过程l 加温过程加温过程增强粒子的热运动，使其偏离增强粒子的热运动，使其偏离平衡位置，目的是消除系统原先可能存在的非平衡位置，目的是消除系统原先可能存在的非均匀态；均匀态；l 等温过程等温过程退火过程中要让温度慢慢降低，退火过程中要让温度慢慢降低，在每一个温度下要到达热平衡状态，对于与环

10、在每一个温度下要到达热平衡状态，对于与环境换热而温度不变的封闭系统满足自由能较少境换热而温度不变的封闭系统满足自由能较少定律，系统状态的自发变化总是朝自由能减少定律，系统状态的自发变化总是朝自由能减少的方向进行，当自由能到达最小时，系统到达的方向进行，当自由能到达最小时，系统到达平衡态；平衡态；l 冷却过程冷却过程使粒子热运动减弱并渐趋有序，使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。系统能量逐渐下降，从而得到低能的晶体结构。当液体凝固为固体的晶态时退火过程完成。当液体凝固为固体的晶态时退火过程完成。 l数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态

11、r满足满足Boltzmann概率分布概率分布 温度低时能量低的微观状态概率大，温度趋于零时，温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。固体几乎处于概率最大能量最小的基态。DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)(子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随 l数学表述数学表述 在在同一个温度同一个温度T，选定两个能量，选定两个能量E1E2，有，有 在同一个温度，分子停留在能量小的状态的概在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态

12、的概率要大。率比停留在能量大的状态的概率要大。TkEETkETZEEPEEPBB12121exp1exp)(10l数学表述数学表述l 假设假设|D|为状态空间为状态空间D中状态中状态的个数，的个数，D0是具有最低能量的是具有最低能量的状态集合：状态集合：l (1) 当温度很高时，每个状态当温度很高时，每个状态概率根本相同，接近平均值概率根本相同，接近平均值1/|D|；l (2) 状态空间存在超过两个不状态空间存在超过两个不同能量时，具有最低能量状态的同能量时，具有最低能量状态的概率超出平均值概率超出平均值1/|D| ；l (3) 当温度趋于当温度趋于0时，分子停时，分子停留在最低能量状态的概率

13、趋于留在最低能量状态的概率趋于1。能量最低状态能量最低状态非能量最低状态非能量最低状态 lMetropolis准那么准那么1953以概率接受新状以概率接受新状态态l 固体在恒定温度下到达热平衡的过程可以用固体在恒定温度下到达热平衡的过程可以用Monte Carlo方法计算机随机模拟方法加以方法计算机随机模拟方法加以模拟，虽然该方法简单，但必须大量采样才能模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。得到比较精确的结果，计算量很大。lMonte Carlo模拟退火过程模拟退火过程l蒙特卡罗蒙特卡罗(Monte Carlo)方法，或称计算机方法，或称计算机随机模拟方法，是

14、一种基于随机模拟方法，是一种基于“随机数的计随机数的计算方法。这一方法源于美国在第一次世界算方法。这一方法源于美国在第一次世界大战中研制原子弹的大战中研制原子弹的“曼哈顿方案。该方曼哈顿方案。该方案的主持人之一、数学家冯案的主持人之一、数学家冯诺伊曼用著名诺伊曼用著名世界的赌城世界的赌城摩纳哥的摩纳哥的Monte Carlo来命来命名这种方法，为它蒙上了一层神秘色彩。名这种方法，为它蒙上了一层神秘色彩。lMonte Carlo方法方法lMonte Carlo方法的根本思想很早以前就被方法的根本思想很早以前就被人们所发现和利用。人们所发现和利用。l早在早在17世纪，人们就知道用事件发生的世纪，人

15、们就知道用事件发生的“频频率来决定事件的率来决定事件的“概率。概率。lBuffon试验：试验：19世纪人们用投针试验的方世纪人们用投针试验的方法来求解圆周率法来求解圆周率。l本世纪本世纪40年代电子计算机的出现，特别是年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样学方法在计算机上大量、快速地模拟这样的试验成为可能。的试验成为可能。lMonte Carlo方法方法l用民意测验来作一个不严格的比喻。民意用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，测验的人不是征询每一个登记选民的意

16、见，而是通过对选民进行小规模的抽样调查来而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其根本思想是一样的。确定可能的优胜者。其根本思想是一样的。l它需要一个良好的随机数源。这种方法往它需要一个良好的随机数源。这种方法往往包含一些误差，但是随着随机抽取样本往包含一些误差，但是随着随机抽取样本数量的增加，结果也会越来越精确。数量的增加，结果也会越来越精确。 lMetropolis准那么准那么1953以概率接受新状以概率接受新状态态l 假设在温度假设在温度T，当前状态，当前状态i 新状态新状态jl 假设假设Ej=randrom0,1 s=sj;l Until 抽样稳定准那么满足；抽样稳定准那

17、么满足；l 退温退温tk+1=update(tk)并令并令k=k+1；l Until 算法终止准那么满足；算法终止准那么满足； l 输出算法搜索结果。输出算法搜索结果。 l影响优化结果的主要因素影响优化结果的主要因素l 给定初温给定初温t=t0，随机产生初始状态，随机产生初始状态s=s0，令，令k=0；l Repeatl Repeatl 产生新状态产生新状态sj=Genete(s)；l if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;l Until 抽样稳定准那么满足；抽样稳定准那么满足；l 退温退温tk+1=update(tk)并令并令k=k+1；l U

18、ntil 算法终止准那么满足；算法终止准那么满足； l 输出算法搜索结果。输出算法搜索结果。三函数两准那么三函数两准那么初始温度初始温度三函数两准那三函数两准那么么状态产生函数状态产生函数状态接受函数状态接受函数退温函数退温函数抽样稳定准那抽样稳定准那么么退火结束准那退火结束准那么么SAA流程流程确定确定初温初温随机给定随机给定初始解初始解收敛准收敛准则则满足满足否？否？输出结果输出结果Y抽样稳定准则抽样稳定准则满足否？满足否？由当前由当前状态产生状态产生新状态新状态接受函数接受函数成立否？成立否？替换当前状态替换当前状态YYNNN退温退温保持当前状态不变保持当前状态不变 关键环节关键环节1

19、1 初温、初始解初温、初始解2 2 状态产生函数状态产生函数3 3 状态接受函数状态接受函数4 4 退温函数退温函数5 5 抽样稳定准那么抽样稳定准那么6 6 收敛准那么收敛准那么SAA特点特点l可以保证全局最优可以保证全局最优l特别适合组合优化问题特别适合组合优化问题l可以随机选择初始解可以随机选择初始解l对问题本身没有特别要求，不会因为问题对问题本身没有特别要求，不会因为问题实例的改变影响性能实例的改变影响性能l简单易行，通用性好简单易行，通用性好马氏链描述马氏链描述收敛性收敛性时齐算法收敛性时齐算法收敛性非时齐算法收敛性非时齐算法收敛性渐近性态渐近性态第二节第二节 SAA的马氏链描述及收

20、敛性的马氏链描述及收敛性 模拟退火算法模拟退火算法(SAA)是将物理退火过程与是将物理退火过程与组合优化相结合的一种随机迭代寻优算法。组合优化相结合的一种随机迭代寻优算法。数学模型描述为数学模型描述为 由某一较高初始温度开始，在给定的由某一较高初始温度开始，在给定的邻域结构中，模拟退火过程，利用概率特邻域结构中，模拟退火过程，利用概率特性与抽样策略在解空间中随机搜索，随着性与抽样策略在解空间中随机搜索，随着温度不断下降重复抽样，用来优化问题的温度不断下降重复抽样，用来优化问题的解。解。引言引言设设 为所有状态构成的解空间，为所有状态构成的解空间，,21ss)(kX为为k时刻状态变量的取值。时刻

21、状态变量的取值。随机序列随机序列 称为称为马氏链马氏链,若若,)(21kkXZn满足满足)(|)()(inXjnXPnpij11简简记记记忆遗忘功能记忆遗忘功能)1(|)()1(,)1(,)0(|)(10inXjnXPinXiXiXjnXP 一步转移概率一步转移概率)(|)()(inXjnXPnpij11n步转移概率步转移概率)(|)()(iXjnXPpnij0有限状态马氏链有限状态马氏链假设解空间有限。假设解空间有限。时齐马氏链时齐马氏链)()(,1npnpZnijij模拟退火算法模拟退火算法(SAA)的搜索进程：的搜索进程： 算法从某一个初始状态开始后，每一步算法从某一个初始状态开始后，每

22、一步状态转移均是在当前状态的邻域中随机产生状态转移均是在当前状态的邻域中随机产生新状态，然后以一定概率进行接受的。新状态，然后以一定概率进行接受的。 接受概率仅依赖于新状态和当前状态，接受概率仅依赖于新状态和当前状态，并由温度加以控制。因此，并由温度加以控制。因此，SAA对应一个马对应一个马氏链。氏链。假设固定每一温度，算法均假设固定每一温度，算法均计算马氏链的变化直至平稳计算马氏链的变化直至平稳分布，然后下降温度。分布，然后下降温度。时齐算法时齐算法非时齐算法非时齐算法假设无需各温度下算法均到假设无需各温度下算法均到达平稳分布，但温度需按照达平稳分布，但温度需按照一定的速率下降。或称非平一定

23、的速率下降。或称非平稳马氏链算法。稳马氏链算法。SAA根底理论根底理论 iNkkiiijijijiijtpijandNjijandNjtagtpji)(10)()(,/ )(exp, 1min,tCCaijji 通通常常令令马氏链模型马氏链模型 iNjiijijigigNjNjigjigg),()(, 0),(/ ),(,SAA要实现全局收敛必须满足以下条件：要实现全局收敛必须满足以下条件：状态可达性状态可达性初值鲁棒性初值鲁棒性极限分布存在性极限分布存在性收敛到最优解收敛到最优解温度不变，温度不变，M链极限分布存链极限分布存在在温度渐近温度渐近0，M链极限分布存在链极限分布存在对应马氏链的状

24、态图是强连通的对应马氏链的状态图是强连通的对算法的最终结果不依赖于初值对算法的最终结果不依赖于初值定义定义1状态状态i可达状态可达状态j:00)(|)()(iXjnXPpnijji 定义定义2平稳分布平稳分布:称称 为马氏链的平稳分布为马氏链的平稳分布,若一步转移概率满足等式若一步转移概率满足等式,Zjvj01iijijpvv时齐算法的收敛性时齐算法的收敛性 时齐模拟退火算法的收敛性时齐模拟退火算法的收敛性结论结论：结论结论1 时齐模拟退火算法对应的有限状态马时齐模拟退火算法对应的有限状态马氏链存在平稳分布。氏链存在平稳分布。结论结论2 当温度趋于当温度趋于0时，马氏链以概率时，马氏链以概率1

25、收敛收敛到最优状态集，而收敛到非最优状态的概率到最优状态集，而收敛到非最优状态的概率为为0。实现途径：实现途径：通过各温度下各状态序列无限长通过各温度下各状态序列无限长得以实现！得以实现！非时齐算法的收敛性非时齐算法的收敛性收敛定理收敛定理 对退温函数加以严格控制，可使得对退温函数加以严格控制，可使得SA算法以概率算法以概率1收敛到全局最优解。收敛到全局最优解。 可设计退温函数为可设计退温函数为, 1, 0,)ln( kmktk m2其中其中 ，则当，则当 时，时，SA算法算法以概率以概率1收敛到全局最优解。收敛到全局最优解。rL 算法渐近性能的逼近算法渐近性能的逼近 收敛可以保证，但是时间性

26、能不好收敛可以保证，但是时间性能不好 收敛速度有待研究收敛速度有待研究第三节第三节 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计三函数两准那三函数两准那么么状态产生函数状态产生函数状态接受函数状态接受函数退温函数退温函数抽样稳定准那抽样稳定准那么么退火结束准那退火结束准那么么从算法流程看，从算法流程看，SA算法包括三函数两准那么算法包括三函数两准那么初温初温1 状态产生函数邻域函数状态产生函数邻域函数设计的出发点：设计的出发点：尽可能保证产生的候选解遍布全部解空间。尽可能保证产生的候选解遍布全部解空间。产生候选解的方式产生候选解的方式候选解产生的概率分布候选解产生的概率分布

27、两局部两局部l前者决定由当前解产生候选解的方式，后者决前者决定由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概定在当前解产生的候选解中选择不同状态的概率。率。l候选解的产生方式由问题的性质决定，通常在候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生，当前状态的邻域结构内以一定概率方式产生，l而邻域函数和概率方式可以多样化设计，其中而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、正态分布、指数分概率分布可以是均匀分布、正态分布、指数分布、柯西分布等。布、柯西分布等。2 状态接受函数状态接受函数目的：目的：尽可能接受优化解尽可能

28、接受优化解 tC /exp, 1min 状态接受函数一般以概率的方式给状态接受函数一般以概率的方式给出，不同接受函数的差异主要在于接受出，不同接受函数的差异主要在于接受概率的形式不同。概率的形式不同。固定温度下，接受使目标函数值下降的候选解固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率。的概率要大于使目标函数值上升的候选解的概率。随温度的下降，接受使目标函数值上升的解的随温度的下降，接受使目标函数值上升的解的概率要逐渐减小。概率要逐渐减小。当温度趋于零时，只能接受目标函数值下降的解。当温度趋于零时，只能接受目标函数值下降的解。设计状态接受概率，应遵循的原那么

29、：设计状态接受概率，应遵循的原那么：3 初温初温0t实验说明：初温值只要选择充分大，获得高实验说明：初温值只要选择充分大，获得高质量解的概率就大！但花费计算时间增加。质量解的概率就大！但花费计算时间增加。初温的选择要足够高。初温的选择要足够高。初温确实定应折衷考虑优化质量和优化效率。初温确实定应折衷考虑优化质量和优化效率。均匀抽样一组状态，选各状态目标值的方差均匀抽样一组状态，选各状态目标值的方差利用经验公式利用经验公式8 . 0ln0 ppft )(min)(max0jfjfKKtsjsj 充分大充分大随机产生一组状态，确定两随机产生一组状态，确定两两状态间的最大目标值差，两状态间的最大目标

30、值差，然后依据差值，利用一定的然后依据差值，利用一定的函数确定初温。例如，函数确定初温。例如，初始温度初始温度温度更新函数温度更新函数内循环终止准那内循环终止准那么么外循环终止准那外循环终止准那么么退火历程退火历程(annealing schedule)4 温度更新函数温度更新函数衰减量衰减量“以小为宜以小为宜实验说明降温速度越慢，获得高质量解的几率实验说明降温速度越慢，获得高质量解的几率越大，但花费的计算时间将同时增加。越大，但花费的计算时间将同时增加。温度高时下降的慢些，温度低时下降的快些。温度高时下降的慢些，温度低时下降的快些。即温度的下降方式，用于在外循环中修改温度值。即温度的下降方式

31、，用于在外循环中修改温度值。Nahar及及Skiscim等人把等人把 划分成划分成K个个小区间，温度更新函数为小区间，温度更新函数为,00 tKktKkKtk, 2 , 1,0 101 kkttKirkpatrick首先提出首先提出被被Johnson,Bonomi及及Lutton采用采用95. 0 取取0.5至至0.99之间之间 5 内循环终止准那么内循环终止准那么检验目标函数值的均值是否稳定检验目标函数值的均值是否稳定连续假设干步目标函数值的变化较小连续假设干步目标函数值的变化较小按一定的步数抽样按一定的步数抽样链长链长kLMetropolis抽样稳定准那么抽样稳定准那么用于决定在各温度下产

32、生候选解的数目。用于决定在各温度下产生候选解的数目。时齐算法时齐算法常用常用Metropolis抽样稳定准那么包括：抽样稳定准那么包括：非时齐非时齐SAA：每个温度下只产生一个或少量候选解。每个温度下只产生一个或少量候选解。l具体应与问题规模成比例。具体应与问题规模成比例。l实验说明高温时迭代次数越多越好，低温实验说明高温时迭代次数越多越好，低温时迭代次数可以适当减少。时迭代次数可以适当减少。6 外循环终止准那么外循环终止准那么理论上理论上要求温度终值趋于零要求温度终值趋于零设置终止温度的阀值设置终止温度的阀值设置外循环迭代次数设置外循环迭代次数(6-50)算法搜索到的最优值连续假设干步保持不

33、变算法搜索到的最优值连续假设干步保持不变optoptrfffe *算法终止准那么算法终止准那么用于决定算法何时结束。用于决定算法何时结束。通常的做法包括：通常的做法包括：检验系统熵是否稳定检验系统熵是否稳定三个参数三个参数 、 和和 值均有显著影响。值均有显著影响。kL0t总结总结过大的过大的 值、值、 值和值和 值均能导致过长的值均能导致过长的CPU时间。因而在最终解的质量有待较大时间。因而在最终解的质量有待较大 值和值和 值予以保证的前提下，选取较小值予以保证的前提下，选取较小的的 值可以抑制值可以抑制CPU时间上升的态势。时间上升的态势。0tkL0tkL模拟退火算法根本要素和设定方法模拟

34、退火算法根本要素和设定方法l模拟退火算法是一种通用的随机搜索算法，它模拟退火算法是一种通用的随机搜索算法，它可用于解决众多的优化问题，并已经广泛的应可用于解决众多的优化问题，并已经广泛的应用于其他领域。如用于其他领域。如VLSL设计、图像识别等。当设计、图像识别等。当待解决的问题复杂性较高，而且规模较大时，待解决的问题复杂性较高，而且规模较大时，在对问题的领域知识甚少的情况下，采用模拟在对问题的领域知识甚少的情况下，采用模拟退火算法最适宜。因为模拟退火算法不像其他退火算法最适宜。因为模拟退火算法不像其他确定型启发式算法那样，需要依赖于问题的领确定型启发式算法那样，需要依赖于问题的领域知识来提高

35、算法的性能。域知识来提高算法的性能。l但是，从另一方面来说，有关待解决问题的一但是，从另一方面来说，有关待解决问题的一些知识后，模拟退火算法却无法充分利用它们，些知识后，模拟退火算法却无法充分利用它们，这使得模拟退火算法的优点就成了缺点。如何这使得模拟退火算法的优点就成了缺点。如何把传统的启发式搜索方法和模拟退火随机搜索把传统的启发式搜索方法和模拟退火随机搜索算法结合起来，这是一个有待研究的十分有意算法结合起来，这是一个有待研究的十分有意义的课题。义的课题。l模拟退火算法在求解规模较大的实际问题时，往模拟退火算法在求解规模较大的实际问题时，往往存在以下缺点：往存在以下缺点：l1收敛速度比较慢。

36、收敛速度比较慢。l2尽管理论上只要计算时间足够长，模拟退尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率火法就可以保证以概率1收敛于全局最优点。但收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。化效果不甚理想。l 3在每一温度下很难判定是否到达了平衡状在每一温度下很难判定是否到达了平衡状态。态。l为此，人们对模拟退火算法提出了各种各样的为此，人们对模

37、拟退火算法提出了各种各样的改进，其中包括并行模拟退火算法、快速模拟改进，其中包括并行模拟退火算法、快速模拟退火算法退火算法Cauchy机和对模拟退火算法中各机和对模拟退火算法中各个函数和参数的重新设计等。个函数和参数的重新设计等。SA算法直接简单模拟固体退火。算法直接简单模拟固体退火。特点：特点：思路清晰、原理简单、使用灵活、应用广泛思路清晰、原理简单、使用灵活、应用广泛同时，由于其直接性和简单化，也存在缺乏同时，由于其直接性和简单化，也存在缺乏与弊病，使其应用及性能受到一定影响。与弊病，使其应用及性能受到一定影响。第四节第四节 模拟退火算法的改进及并行性模拟退火算法的改进及并行性不同不同p值

38、对值对CHN144实例测得实例测得 值值0tp0t950.19904900.800.600.700.100.9908494033622459801pftln0 l模拟退火算法的优点模拟退火算法的优点l 质量高；质量高；l 初值鲁棒性强；初值鲁棒性强；l 简单、通用、易实现。简单、通用、易实现。l模拟退火算法的缺点模拟退火算法的缺点l 由于要求较高的初始温度、较慢的降温速由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够屡次率、较低的终止温度，以及各温度下足够屡次的抽样，因此优化过程较长。的抽样，因此优化过程较长。l改进的可行方案改进的可行方案l 1设计适宜的状态产生函数；

39、设计适宜的状态产生函数；l 2设计高效的退火历程；设计高效的退火历程；l 3防止状态的迂回搜索；防止状态的迂回搜索；l 4采用并行搜索结构；采用并行搜索结构；l 5防止陷入局部极小，改进对温度的控制防止陷入局部极小，改进对温度的控制方式；方式；l 6选择适宜的初始状态；选择适宜的初始状态；l 7设计适宜的算法终止准那么。设计适宜的算法终止准那么。 l改进的方式：增加某些新的环节改进的方式：增加某些新的环节l 1增加升温或重升温过程，防止陷入局部增加升温或重升温过程，防止陷入局部极小；极小；l 2增加记忆功能记忆增加记忆功能记忆“Best so far状状态；态；l 3增加补充搜索过程以最优结果

40、为初始增加补充搜索过程以最优结果为初始解；解；l 4对每一当前状态，采用屡次搜索策略，对每一当前状态，采用屡次搜索策略，以概率接受区域内的最优状态；以概率接受区域内的最优状态；l 5结合其它搜索机制的算法；结合其它搜索机制的算法；l 6上述各方法的综合。上述各方法的综合。 l改进的思路改进的思路l 1记录记录“Best so far状态，并即时更状态，并即时更新；新；l 2设置双阈值，使得在尽量保持最优性的设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连前提下减少计算量，即在各温度下当前状态连续续 m1 步保持不变那么认为步保持不变那么认为Metropolis抽样稳定

41、，抽样稳定，假设连续假设连续 m2 次退温过程中所得最优解不变那次退温过程中所得最优解不变那么认为算法收敛。么认为算法收敛。l改进的退火过程改进的退火过程l 1给定初温给定初温t0，随机产生初始状态，随机产生初始状态s，令初，令初始最优解始最优解s*=s，当前状态为，当前状态为s(0)=s，i=p=0；l 2令令t=ti，以，以t，s*和和s(i)调用改进的抽样过程，调用改进的抽样过程，返回其所得最优解返回其所得最优解s*和当前状态和当前状态s(k)，令当前，令当前状态状态s(i)=s(k)；l 3判断判断C(s*)m2? 假设是，那么转第假设是，那么转第(6)步；否那步；否那么，返回第么，返

42、回第(2)步；步；l 6以最优解以最优解s*作为最终解输出，停止算法。作为最终解输出，停止算法。l改进的抽样过程改进的抽样过程l 1令令k=0时的初始当前状态为时的初始当前状态为s(0)=s(i)，q=0；l 2由状态由状态s通过状态产生函数产生新状态通过状态产生函数产生新状态s，计算增量计算增量C=C(s)-C(s)；l 3假设假设CC(s)? 假设是，那么令假设是，那么令s*=s，q=0；否那么，令；否那么，令q=q+1。假设。假设C0，那么以，那么以概率概率exp(-C/t)接受接受s作为下一当前状态；作为下一当前状态；l 4令令k=k+1，判断，判断qm1? 假设是，那么转假设是，那么

43、转第第(5)步；否那么，返回第步；否那么，返回第(2)步；步；l 5将当前最优解将当前最优解s*和当前状态和当前状态s(k)返回返回改进退火过程。改进退火过程。TINA lTime-invariant noise algorithml状态产生函数中扰动强度不随时间改变，而是和能量大小相关，能量大的扰动大，能量小的扰动小，能量为零，扰动也为零，算法停止。MTRSAl单调升温(Monotonic temperature rising) SAl在算法退火后期，温度很低且陷入局部极小解的时，算法很难跳出。因此，可以适当重新提高温度，促使算法跳出。SAMGl记忆指导SA(Simulated Anneal

44、ing with Memmory Guidance ,简记为SAMG)l增加一个记忆装置，存储算法计算过程产生的最好的解，以这个解为最终解。自适应SAl自适应自适应SA算法算法, l根据邻域搜索进展的反响信息根据邻域搜索进展的反响信息, 自适应确定温度自适应确定温度变化和邻域搜索强度变化和邻域搜索强度l特点：特点：l1) 退火过程中温度参数变化符合幅值递减的下退火过程中温度参数变化符合幅值递减的下降总趋势降总趋势, 但不排除局部升温的可能但不排除局部升温的可能, 以保证寻以保证寻求到适宜的温度序列求到适宜的温度序列, 防止陷入局部最优防止陷入局部最优;l2) 算法的终止条件依据退火温度和邻域搜

45、索进算法的终止条件依据退火温度和邻域搜索进展状态设计展状态设计;l3) 每一温度下算法的迭代次数随温度下降而递每一温度下算法的迭代次数随温度下降而递增增, 邻域搜索强度依其对目标函数的奉献动态分邻域搜索强度依其对目标函数的奉献动态分配配;l4) 温度变化、邻域搜索和终止条件的控制机制温度变化、邻域搜索和终止条件的控制机制由算法过程自动触发。由算法过程自动触发。1、操作并行性操作并行性：各个环节同时处理；：各个环节同时处理；2、进程并行性进程并行性：同时多个算法运行；：同时多个算法运行；3、空间并行性空间并行性：解空间分解分别处理，最终组：解空间分解分别处理，最终组合。合。全过程并行性全过程并行

46、性子进程并行性子进程并行性第五节第五节 算法的实现与应用算法的实现与应用引言引言SAA应用的一般形式：应用的一般形式： 从选定的初始解开始，在借助于控制参从选定的初始解开始，在借助于控制参数数t递减时产生的一系列递减时产生的一系列Markov链中，利用链中，利用一个新解产生装置和接受准那么，重复进行一个新解产生装置和接受准那么，重复进行包括包括“产生新解产生新解-计算目标函数差计算目标函数差-判断判断是否接受新解是否接受新解-接受接受(或舍弃或舍弃)新解这四新解这四个任务的实验，不断对当前解迭代，从而到个任务的实验，不断对当前解迭代，从而到达使目标函数最优的执行过程。达使目标函数最优的执行过程

47、。SAA实现实现l通用框架通用框架l确定问题编码方案确定问题编码方案l设计初始温度、终止温度和温度下降策略设计初始温度、终止温度和温度下降策略退温函数退温函数l设计能量函数设计能量函数l设定稳定准那么设定稳定准那么l设计产生新解的方式状态产生函数设计产生新解的方式状态产生函数l设计设计Metropolis接受准那么状态接受函接受准那么状态接受函数数l生成初始状态生成初始状态1、数学模型、数学模型对问题的简明描述。对问题的简明描述。解空间解空间目标函数目标函数初始解初始解所有所有可能解可能解的集合，它限定了初的集合，它限定了初始解选取和新解产生的范围始解选取和新解产生的范围对问题的优化目标的数学

48、描述，对问题的优化目标的数学描述，易计算，对应关系明确易计算，对应关系明确算法开始迭代的起点，它的选取算法开始迭代的起点，它的选取使算法能导出较好的最终解使算法能导出较好的最终解2、新解的产生和接受机制、新解的产生和接受机制产生新解产生新解由产生装置从当前解的解空间中产生。由产生装置从当前解的解空间中产生。计算目标函数值之差计算目标函数值之差最快的方法是按增量计算。最快的方法是按增量计算。判断新解是否被接受判断新解是否被接受准那么准那么Metropolis.)/exp(,001ftffp新解代替当前解新解代替当前解代替变换局部，修正目标函数值。代替变换局部，修正目标函数值。3、温度更新函数、温

49、度更新函数关键参数：初温、温度降低函数、马氏关键参数：初温、温度降低函数、马氏链长度、停止准那么。链长度、停止准那么。SAA求解求解TSPl关键问题关键问题l如何由旧的解产生新的解如何由旧的解产生新的解l方式很多方式很多l相邻两位置对换相邻两位置对换变动最小变动最小l任意两位置对换任意两位置对换l单点位置移动单点位置移动l子排列位置移动子排列位置移动l子排列反序子排列反序l子排列位置移动且反序子排列位置移动且反序变动最大变动最大l理论已经证明上述所有方式都收敛理论已经证明上述所有方式都收敛l实际验证收敛性能差异很大实际验证收敛性能差异很大1、组合优化问题的求解、组合优化问题的求解数学模型数学模

50、型 一个商人欲到一个商人欲到 个城市推销商品，每两个城市推销商品，每两个城市个城市 和和 之间的距离为之间的距离为 ，如何选择，如何选择一条道路使得商人每个城市走一遍后回到起一条道路使得商人每个城市走一遍后回到起点且所走路经最短。点且所走路经最短。ijdjin 解空间解空间),(),( | ),(的循环排列为nSnn212121目标函数目标函数niniidf1211),(初始解初始解),(n21选为选为新解的产生新解的产生1、互换操作、互换操作(SWAP)随机交换两个不同城市的位置。随机交换两个不同城市的位置。2、逆序操作、逆序操作(INV)两个不同随机位置的城市逆序。两个不同随机位置的城市逆