模拟退火算法及其改进算法课件

1、1.模拟退火算法起源1.1 模拟退火算法起源于物理退火1.1.1 物理退火过程： a.加温过程b.保温过程c.冷却过程T0降温温度升高原子动能增加跳离原来位置的概率增加原子动能减小跳离原来位置的概率减小继续降温原子位置排列将趋于能量低的状态最后稳定 根据这一物理过程，1953年Metropolis提出重要性采样法，即以概率接受新状态。 称为Metropolis准则。 该准则指出：固体在恒定温度下达到热平衡的过程可以用MorteCarol算法方法加以模 拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。鉴于物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低态。采样

2、时着重选取那些有重要贡献的状态则可较快达到较好的结果。1.2 随机神经网络 BP神经网络和反馈神经网络都是使能量函数按梯度单调下降，如图 常常导致网络落入局部最小点而达不到全局最小点，这就意味着训练不收敛。 而随机网络即能赋予网络下山的能力，也能赋予网络上山的能力，特点如下：（1）在学习阶段，随机网络不像其它网络那样基于某种确定性算法（2）在运行阶段，随机网络不是按某种确定性的网络方程进行状态演变，神经元的净输入不能决定其状态是1还是0. 2.模拟退火算法2.1 模拟退火算法的原理模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大

3、，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为P=e-E/(kT)其中: E为温度T时的内能 E为能量的改变量 k为Boltzmann常数 用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法 。2.2 模拟退火算法的步骤(3) 避免状态的迂回搜索。(4) 采用并行搜索结构。(5) 为避免陷入局部极小，改进对温度的控制方式(6) 选择合适的初始状态。(7) 设计合适的算法终止准则。还可以通过以下方式进行改进 (1) 增加升温或重升温

4、过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。(2) 增加记忆功能。为避免搜索过程中由于执行率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。(3) 增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4) 对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5) 结合其他搜索机制的算法，如遗传算法、混沌搜索等。3 模拟退火算法的应用3.1改进模拟退火算法导弹研制投资决策研究中的应用 3

5、.1.1 情况概述 导弹研制投资决策 是在综合考虑投资效果和风险的前提下 从众多的投资对象中选择一组合适的投资对象的过程。 投资总风险定义为：取上服从均匀分布的随机数若接受新解，否则放弃新解。步骤4 累计重排次数n，若转步骤3，否则转步骤5 步骤5 判断停止准则是否满足，若不满足,则令转步骤3,否则停止算法输出当前解。由于模拟退火算法的随机性，终止解可能不是整个过程所遇到的解中最优的，即使是最优的，虽然可证明算法对整体最优解的渐进收敛性，但终止解的可接受性也不能不遭到怀疑，另外，当终止解在最优解的附近时，算法本身不能迅速逼近或达到它。3.1.4实例分析某型导弹改进项目的投资为300万元，为270万元。现有10个研制单位申请投资，有关信息如表1表2所示。现在要求确