模拟退火719课件

1/16/202411导入为了找出地球上最高的山，一群有志气的兔子们开始想方法。方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一局部海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。遗传算法方案二：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。禁忌搜索法

组合优化问题解空间中的每一点都代表一个具有不同目标函数值的解。所谓优化，就是在解空间中寻找目标函数最小〔大〕解的过程。假设把目标函数看成能量函数，某一控制参数视为温度T，解空间当作形态空间，那么寻找基态的过程也就是求目标函数极小值的优化过程。数学描述：在某一个特定温度T下，进行了充分的转换之后，材料将到达热平衡。这时材料处于状态i的概率满足波尔兹曼分布：其中，x表示材料当前状态的随机变量，S表示状态空间集合数学描述：其中，|S|表示状态空间集合中状态的数量。这就说明，所有状态在高温下具有相同的概率。数学描述：而当温度下降时：上式说明当温度降至很低时，材料会以很大概率进入最小能量状态。数学描述：从另外一个角度来看：在同一个温度T，选定两个能量E1<E2，有：在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。>0<1数学描述：针对上述现象，Metropolis提出了著名的Metropolis准那么〔1953〕——以概率接受新状态——来模拟这一过程：固体在恒定温度下到达热平衡的过程可以用MonteCarlo方法〔计算机随机模拟方法〕加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。Metropolis准那么(1953)—以概率接受新状态：假设在温度T，当前状态i→新状态j假设Ej<Ei，那么接受j为当前状态；否那么，假设概率p=exp[-(Ej-Ei)/KT]大于[0,1)区间的随机数，那么仍接受状态j为当前状态；假设不成立，那么保存状态i为当前状态。p=exp[-(Ej-Ei)/KT]：在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量状态产生函数：原那么：设计状态产生函数〔邻域函数〕的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两局部组成，即产生候选解的方式和候选解产生的概率分布方法：在当前状态的邻域结构内以一定概率方式〔均匀分布、正态分布、指数分布等〕产生温度更新函数：温度更新函数，即温度的下降方式，用于在外循环中修改温度值。常用的算法温度下降函数：1)：α越接近1温度下降越慢，且其大小可以不断变化；2〕：其中t0为起始温度，K为算法温度下降的总次数。内循环终止准那么：常用的Metropolis抽样稳定准那么：〔1〕检验目标函数的均值是否稳定；〔2〕连续假设干步的目标值变化较小；〔3〕按一定的步数抽样。外循环终止准那么〔1〕设置终止温度的阈值；〔2〕设置外循环迭代次数；〔3〕算法搜索到的最优值连续假设干步保持不变；〔4〕概率分析方法。巡航问题：敌方100个目标的经度、纬度如表所示：巡航问题：敌方100个目标的经度、纬度如表所示：我方有一个基地，经度和纬度为〔70,40〕。假设我方飞机的速度为1000公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的