模拟退火模型

《模拟退火模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、模拟退火模型主讲人：泰山教育小石老师模型背景什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。泰山教育版权所有淘宝ID:liuxingma123模型背景物理退火过程加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结

2、构。泰山教育版权所有淘宝ID:liuxingma123模型背景热力学中的退火现象指物体逐渐降温时发生的物理现象：温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温时，可达到最低能量状态；但如果快速降温，会导致不是最低能态的非晶形。大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。泰山教育版权所有淘宝ID:liuxingma123模拟退火算法思想模仿自然界退火现象而得，利用了物理

3、中固体物质的退火过程与一般优化问题的相似性从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量泰山教育版权所有淘宝ID:liuxingma123算法简介设热力学系统Sn中有个状态(有限个,离散的),状态iET的能量为,在温度下，经一段时间达到热平衡，ik这时处于状态i的概率为：−EPT()=CexpiikkTk则有如下关系：EP↓→↑TP↓→

4、↓iiki如何确定C?k泰山教育版权所有淘宝ID:liuxingma123算法简介Bolzman方程−EexpiTkPTik()=n−E∑expiTi=1k可见：Ei↑⇒PTik()↓∗Tkk↓⇒PTi∗()→1,i代表Ei最小的那一个nTk下的平均能量：ET(k)=∑EPTiik⋅()i=1Tk↓⇒→EEi∗泰山教育版权所有淘宝ID:liuxingma123背景温度TPT对()的影响kikEi当T很大时，→0kTkPTik()≈1各状态的概率几乎相等n随着温度的下降PTik()差别扩大Ei

5、当T很小趋于0时，→∞kTk当T→01时，以概率趋于最小能量状态k泰山教育版权所有淘宝ID:liuxingma123算法简介模拟退火算法的模拟要求1初始温度足够高2降温过程足够慢3终止温度足够低泰山教育版权所有淘宝ID:liuxingma123算法简介模拟退火算法的计算步骤①初始化,任选初始解,,iS∈给定初始温度T0，终止温度T,令迭代指标kTT=0,=。fk0E注：选择T时，要足够高，使i→00Tk②随机产生一个邻域解，jNiNi∈(),(()表示i的邻域)计算目标值增量∆=ffjfi()−()泰山教育版权所有

6、淘宝ID:liuxingma123算法简介③若∆U(0,1,)若exp−∆f,Tk则令ij=(j比i好，有条件转移)。注：T高时，广域搜索；T低时，局域搜索kk④若达到热平衡(内循环次数大于nT(k))转步⑤，否则转步②。泰山教育版权所有淘宝ID:liuxingma123算法简介⑤kk=+1降低Tk，若TTkf<停止，否则转步②。注：降低Tk的方法有以下两种1.较好的方法TTrkk+1=⋅其中r∈−(0.950.99)。优点：简单易行2.TT

7、T=−∆kk+112泰山教育版权所有淘宝ID:liuxingma123模拟退火算法对TSP问题的求解旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complet或NPC）和NP难

8、题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。泰山教育版权所有淘宝ID:liuxingma123模拟退火算法对TSP问题的求解城市X坐标Y坐标城市X坐标Y坐标10.66830.253660.22930.761020.61950.263470.51710.941430.40000