《模拟退火719》ppt课件

1、第三讲 模拟退火模型1 导 入 为了找出地球上最高的山，一群有志气的兔子们开场想方法。 方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道本人的使命是什么。但是，假设他过几年就杀死一部分海拔低的兔子，多产的兔子们本人就会找到珠穆朗玛峰。遗传算法 方案二：兔子们知道一个兔子的力量是微小的。于是，它们相互转告着，哪里的山曾经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻觅的战略。忌讳搜索法 方案三：兔子们用酒将本人灌醉了。它们随机地跳了很长时间。在这期间，它们能够走向高处，也能够踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝

2、最高方向跳去。 模拟退火法 算法的提出：模拟退火算法最早的思想由Metropolis等(1953)提出，1983年Kirkpatrick等将其运用于组合优化。算法的目的处理NP复杂性问题；抑制优化过程堕入部分极小；抑制初值依赖性。 在对固体物质进展模拟退火处置时，通常先将它加温熔化，使其中的粒子可自在运动，然后随着温度的逐渐下降，粒子也逐渐构成了低能态的晶格。假设在凝结点附近的温度下降速率足够慢，那么固体物质一定会构成最低能态的基态。 组合优化问题解空间中的每一点都代表一个具有不同目的函数值的解。所谓优化，就是在解空间中寻觅目的函数最小大解的过程。假设把目的函数看成能量函数，某一控制参数视为温

3、度T，解空间当作形状空间，那么寻觅基态的过程也就是求目的函数极小值的优化过程。模拟退火算法与模型物理退火过程：什么是退火？退火是指将固体加热到足够高的温度，使分子呈随机陈列形状，然后逐渐降温使之冷却，最后分子以低能形状陈列，固体到达某种稳定形状。 模拟退火算法与模型(C.)物理退火过程：加温过程加强粒子的热运动，消除系统原先能够存在的非均匀态；等温过程对于与环境换热而温度不变的封锁系统，系统形状的自发变化总是朝自在能减少的方向进展，当自在能到达最小时，系统到达平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体构造。 数学描画：假设用粒子的能量定义资料的形状，Met

4、ropolis 算法用一个简单的数学模型描画了退火过程。 假设资料在形状i 之下的能量为E(i) ，那么资料在温度T 时从形状i 进入形状j 就遵照如下规律：假设E(j)E(i) ，接受该形状被转移假设E(j) E(i) ，那么形状转换以如下的概率被接受 expE(i)- E(j)/KT其中，K是物理学中的波尔兹曼常数，T是资料温度数学描画：在某一个特定温度T下，进展了充分的转换之后，资料将到达热平衡。这时资料处于形状i的概率满足波尔兹曼分布：其中，x表示资料当前形状的随机变量，S表示形状空间集合SjKTjEKTiETeeiExEP)()()()(数学描画：其中，|S|表示形状空间集合中形状的

5、数量。这就阐明，一切形状在高温下具有一样的概率。SeeSjKTjEKTiET1lim)()(数学描画：而当温度下降时：上式阐明当温度降至很低时，资料会以很大约率进入最小能量形状。数学描画：从另外一个角度来看：在同一个温度T，选定两个能量E101数学描画：针对上述景象，Metropolis提出了著名的Metropolis准那么1953以概率接受新形状来模拟这一过程： 固体在恒定温度下到达热平衡的过程可以用Monte Carlo方法计算机随机模拟方法加以模拟，虽然该方法简单，但必需大量采样才干得到比较准确的结果，计算量很大。Metropolis准那么(1953)以概率接受新形状：假设在温度T，当前

6、形状i 新形状j 假设Ej=randrom0,1 s=sj; Until 抽样稳定准那么满足； 退温tk+1=update(tk)并令k=k+1； Until 算法终止准那么满足； 输出算法搜索结果。算法关键参数和操作的设定：从算法流程上看，模拟退火算法包括三函数两准那么，即形状产生函数、形状接受函数、温度更新函数、内循环终止准那么和外循环终止准那么，这些环节的设计将决议模拟退火算法的优化性能。此外，初温的选择对模拟退火算法性能也有很大影响。 形状产生函数：原那么：设计形状产生函数邻域函数的出发点应该是尽能够保证产生的候选解遍及全部的解空间。通常，形状产生函数由两部分组成，即产生候选解的方式和

7、候选解产生的概率分布方法：在当前形状的邻域构造内以一定概率方式均匀分布、正态分布、指数分布等产生形状接受函数：原那么：函数普通以概率的方式给出，不同接受函数的差别主要在于接受概率的方式不同。设计形状接受概率，应该遵照以下原那么：(1)在固定温度下，接受使目的函数下降的候选解的概率要大于使目的函数上升的候选解概率；(2)随温度的下降，接受使目的函数上升的解的概率要逐渐减小；(3)当温度趋于零时，只能接受目的函数下降的解。方法：形状接受函数的引入是模拟退火算法实现全局搜索的最关键的要素，模拟退火算法中通常采用min1,exp(-C/t)作为形状接受函数初始温度：初始温度、温度更新函数、内循环终止准

8、那么和外循环终止准那么通常被称为退火历程。原那么：经过实际分析可以得到初温的解析式，但处理实践问题时难以得到准确的参数；实践运用时往往要让初温充分大。实验阐明：初温越大，获得高质量解的机率越大，但破费较多的计算时间。方法：1)均匀抽样一组形状，以各形状目的值的方差为初温；2)随机产生一组形状，确定两两形状间的最大目的值差，根据差值，利用一定的函数确定初温，譬如 ，其中 为初始接受概率； 3)利用阅历公式。rptln/0rp温度更新函数：温度更新函数，即温度的下降方式，用于在外循环中修正温度值。常用的算法温度下降函数：1) ：越接近1温度下降越慢，且其大小可以不断变化；2 ：其中t0为起始温度，

9、K为算法温度下降的总次数。10 , 0 ,1kttkk0tKkKtk内循环终止准那么：常用的Metropolis抽样稳定准那么：1检验目的函数的均值能否稳定；2延续假设干步的目的值变化较小；3按一定的步数抽样。外循环终止准那么1设置终止温度的阈值； 2设置外循环迭代次数； 3算法搜索到的最优值延续假设干步坚持不变； 4概率分析方法。模拟退火算法的优缺陷：优点：质量高；初值鲁棒性强；简单、通用、易实现。缺陷由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。模拟退火算法的流程巡航问题：知敌方100 个目的的经度、纬度如表所示：模拟退火算法的实例巡航问题：知敌方100 个目的的经度、纬度如表所示：我方有一个基地，经度和纬度为70,40。假设我方飞机的速度为10