美赛数模智能算法之模拟退火算法

,美赛数模智能算法之模拟退火算法主讲人：老教练,前言,为了找出地球上最高的山，一群有志气的兔子们开始想办法。,前言(C.),方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。遗传算法,前言(C.),方案二：兔子们朝着比现在高的地方跳去，它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实，它们这种做法只是自己心理上认为找到了最高的山，并不能保证局部最优值就是全局最优值。局部搜索法,前言(C.),方案三：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。禁忌搜索法,前言(C.),方案四：兔子们用酒将自己灌醉了。它们随机地跳了很长时间。在这期间，它们可能走向高处，也可能踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝最高方向跳去。模拟退火法,前言(C.),模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。,前言(C.),算法的提出：模拟退火算法最早的思想由Metropolis等(1953)提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。,前言(C.),在对固体物质进行模拟退火处理时，通常先将它加温熔化，使其中的粒子可自由运动，然后随着温度的逐渐下降，粒子也逐渐形成了低能态的晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能态的基态。,前言(C.e),组合优化问题解空间中的每一点都代表一个具有不同目标函数值的解。所谓优化，就是在解空间中寻找目标函数最小（大）解的过程。若把目标函数看成能量函数，某一控制参数视为温度T，解空间当作形态空间，那么寻找基态的过程也就是求目标函数极小值的优化过程。,模拟退火算法与模型,物理退火过程：什么是退火？退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,模拟退火算法与模型(C.),物理退火过程：加温过程增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,模拟退火算法与模型(C.),数学描述：如果用粒子的能量定义材料的状态，Metropolis算法用一个简单的数学模型描述了退火过程。假设材料在状态i之下的能量为E(i)，那么材料在温度T时从状态i进入状态j就遵循如下规律：如果E(j)E(i)，接受该状态被转移如果E(j)E(i)，则状态转换以如下的概率被接受expE(i)-E(j)/KT其中，K是物理学中的波尔兹曼常数，T是材料温度,模拟退火算法与模型(C.),数学描述：在某一个特定温度T下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态i的概率满足波尔兹曼分布：其中，x表示材料当前状态的随机变量，S表示状态空间集合,数学描述：显然：其中，|S|表示状态空间集合中状态的数量。这就表明，所有状态在高温下具有相同的概率。,模拟退火算法与模型(C.),数学描述：而当温度下降时：上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。,模拟退火算法与模型(C.),数学描述：从另外一个角度来看：在同一个温度T，选定两个能量E10,1,数学描述：针对上述现象，Metropolis提出了著名的Metropolis准则（1953）以概率接受新状态来模拟这一过程：固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。,模拟退火算法与模型(C.),Metropolis准则(1953)以概率接受新状态：若在温度T，当前状态i新状态j若Ej=randrom0,1s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。,模拟退火算法与模型(C.e),算法关键参数和操作的设定：从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定模拟退火算法的优化性能。此外，初温的选择对模拟退火算法性能也有很大影响。,算法关键参数和操作的设定,状态产生函数：原则：设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布方法：在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生,算法关键参数和操作的设定(C.),状态接受函数：原则：函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。方法：状态接受函数的引入是模拟退火算法实现全局搜索的最关键的因素，模拟退火算法中通常采用min1,exp(-C/t)作为状态接受函数,算法关键参数和操作的设定(C.),初始温度：初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程。原则：通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；实际应用时往往要让初温充分大。实验表明：初温越大，获得高质量解的机率越大，但花费较多的计算时间。方法：1)均匀抽样一组状态，以各状态目标值的方差为初温；2)随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温，譬如，其中为初始接受概率；3)利用经验公式。,算法关键参数和操作的设定(C.),温度更新函数：温度更新函数，即温度的下降方式，用于在外循环中修改温度值。常用的算法温度下降函数：1)：越接近1温度下降越慢，且其大小可以不断变化；2）：其中t0为起始温度，K为算法温度下降的总次数。,算法关键参数和操作的设定(C.),内循环终止准则：常用的Metropolis抽样稳定准则：（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。外循环终止准则（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。,算法关键参数和操作的设定(C.),模拟退火算法的优缺点：优点：质量高；初值鲁棒性强；简单、通用、易实现。缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。,算法关键参数和操作的设定(C.e),模拟退火算法的流程,改进的可行方案：设计合适的状态产生函数；设计高效的退火历程；避免状态的迂回搜索；采用并行搜索结构；避免陷入局部极小，改进对温度的控制方式；选择合适的初始状态；设计合适的算法终止准则。,模拟退火算法的改进,改进的方式：增加升温或重升温过程，避免陷入局部极小；增加记忆功能（记忆“Bestsofar”状态）；增加补充搜索过程（以最优结果为初始解）；对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；结合其它搜索机制的算法；上述各方法的综合。,模拟退火算法的改进(C.e),巡航问题：已知敌方100个目标的经度、纬度如表所示：,模拟退火算法的实例,巡航问题：已知敌方100个目标的经度、纬度如表所示：我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为1000公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在