模拟退火算法及其改进算法.ppt

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

2、运动又妨碍它准确落到最低态。采样时着重选取那些有重要贡献的状态则可较快达到较好的结果。,1.2 随机神经网络 BP神经网络和反馈神经网络都是使能量函数按梯度单调下降，如图 常常导致网络落入局部最小点而达不到全局最小点，这就意味着训练不收敛。,而随机网络即能赋予网络下山的能力，也能赋予网络上山的能力，特点如下： （1）在学习阶段，随机网络不像其它网络那样基于某种确定性算法（2）在运行阶段，随机网络不是按某种确定性的网络方程进行状态演变，神经元的净输入不能决定其状态是1还是0.,2.3 模拟退火算法的特点 2.3.1 模拟退火算法的优点 计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂

3、的非线性优化问题 2.3.2模拟退火算法的缺点 降温过程与解的质量的矛盾 2.4 模拟退火算法的改进 （1）设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。 （2） 设计高效的退火策略。,(3) 避免状态的迂回搜索。 (4) 采用并行搜索结构。 (5) 为避免陷入局部极小，改进对温度的控制方式 (6) 选择合适的初始状态。 (7) 设计合适的算法终止准则。 还可以通过以下方式进行改进 (1) 增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。 (2) 增加记忆功

4、能。为避免搜索过程中由于执行率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。,(3) 增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。 (4) 对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。 (5) 结合其他搜索机制的算法，如遗传算法、混沌搜索等。,3 模拟退火算法的应用,3.1改进模拟退火算法导弹研制投资决策研究中的应用 3.1.1 情况概述 导弹研制投资决策 是在综合考虑投资效果和风险的前提下 从众多的投资对象中选择一组合适的投资对象的过程。 投资总风险定义为

5、：,投资组合的总效益为：,：为第i个项目的总净现值,为0表示第i个项目未被选中，为1表示被选中,根据上述原则，决策目标函数为,资金约束为：,其中：,为投资额下限，,为投资额上限。,可得到投资风险组合优化决策模型如下：,3.1.2 模型建立 本模型的建立基于以下三个原则： （1）单位风险收益最大原则 通过计算组合投资的平均收益与组合风险比来判断组合方案的优劣 比值大的组合方案表其单位风险所获得的收益也大 （2）投资剩余资源最少原则 如果仅依据单位风险收益最大原则来决策就可能出现只有很少几个项目被选中的情况 这样会造成分配后的剩余资金过多 因此 在投资组合优化决策中 应在每笔单项投资可行的基础上

6、增加一个最低投资额度 的约束条件 以使剩余资金处于可以接受的水平,3.1.3 根据模拟退火算法的思想设计适合该模型的算法,步骤1 产生初始解,其中，,为可能解集合，,代表第,个单位是否获得,投资的状态,给出控制参数初值,Mapkob,链长度N以及停止参数K和,步骤2 判断初始解的可行性，若不可行，则进行快 速调整，否则转步骤3.,步骤3 产生新解并计算新解与当前解的目标函数值,之差,然后由接受准则计算,取,上服从均匀分布的随机数,若,接受新解，否则放弃新解。,步骤4 累计重排次数n，若,转步骤3，否则转,步骤5,步骤5 判断停止准则是否满足，若不满足,则令,转步骤3,否则停止算法输出当,前解。,由于模拟退火算法的随机性，终止解可能不是整个过程所遇到的解中最优的，即使是最优的，虽然可证明算法对整体最优解的渐进收敛性，但终止解的可接受性也不能不遭到怀疑，另外，当终止解在最优解的附近时，算法本身不能迅速逼近或达到它。,3.1.4实例分析,某型导弹改进项目的投资,为300万元，,为270万元。,现有10个研制单位申请投