模拟退火算法 第三节ppt课件

2 3实现的技术问题 冷却进度表 模拟退火算法的渐近收敛性意味着 对多数组合优化问题来说 算法的执行过程只有进行无限多次变换后 才能返回一个整体最优解 因而作为最优化算法 模拟退火算法的执行过程不能囿于多项式时间 它是一种指数时间算法 因而无法应用于实际 按理论要求 齐次算法要在每一个温度迭代无穷步以达到平稳分布 而非齐次算法要求温度下降的迭代次数是指数次 从应用的角度来看 在可接受的时间里得到满意的解就可以了 因此本节介绍的技术问题无法保证模拟退火算法得到全局最优解 应用这些技术的模拟退火算法还是一种启发式算法 一 冷却进度表的一般概念 定义 一个冷却进度表应当规定下述参数 控制参数t的初值t0 即初始温度的选取 控制参数t的衰减函数 即温度下降的规则 马氏链的长度Lk 即每一温度马氏链的迭代长度 控制参数t的终值tf 即停止准则 二 冷却进度表的选取原则 任一有效的冷却进度表都必须妥善解决两个问题 一是算法的收敛性问题 已经证明模拟退火算法在一定条件下的渐近收敛性 但这并不意味着任一冷却进度表都能确保算法收敛 不合理的冷却进度表会使算法在某些解间 振荡 而不能收敛于某一近似解 这个问题可以通过tk Lk以及停止准则的合理选取加以解决 二是模拟退火算法的实验性能问题 算法的实验性能一般用两个指标 平均情况下最终解的质量和CPU时间 来衡量 模拟退火算法最终解的 质量与相应CPU时间呈反向关系 很难两全其美 实验性能问题的妥善解决只有一种方法 折衷 即在合理的CPU时间里尽量提高最终解的质量 这种抉择涉及冷却进度表所有参数的合理选取 冷却进度表可以根据经验法则 基于折衷原则 或理论分析 基于准平衡概念 选取 经验法则从合理的CPU时间出发 探索提高最终解质量的途径 简单直观而有赖丰富的实践 理论分析由最终解的质量入手 寻求缩减CPU时间的方法 精细透彻却难免繁琐的推证 只有综合两者的优势才能构造出高效的冷却进度表 1 控制参数初值t0的选取 起始温度t0应保证平稳分布中每一状态的概率相等 应让初始接受率 由Metropolis准则 可推知t0值很大 例如取 0 0 9 则在 fij 100时 t0 949 下面给出数值计算估计t0的方法 数值计算估计方法的基本思想是给出一个值 0 0接近1 如 0 0 9 0 8等 对给定的初始温度t0用以下的算法 初始温度数值计算算法 Step1给定一个常量T 初始温度t0 0 R0 0 k 1 Step2在该温度迭代L步 L为一个给定的常数 分 Step3当 Rk 0 时 停止计算 否则 当Rk 1和 通过数值计算 可以估计出温度t0 别记录模拟退火算法中接受和被拒绝的个数 计算接受的状态数同迭代步数L的比率Rk Rk 0时 则k k 1 t0 t0 T 返回step2 当Rk 1和Rk 0时 则k k 1 t0 t0 T 返回step2 当Rk 1 0且Rk 0时 则k k 1 t0 t0 T 2 T T 2 返回step2 当Rk 1 0且Rk 0时 则k k 1 t0 t0 T 2 返回step2 K充分大的数 其中 实际计算中 可以选K 10 20 100 等实验值 对一些问题 有时可以简单地估计 如对TSP的 估计 则可用 1替代 但有的时候 会出现 比较难估计 此时 通常采用统计的方法估计费用函数的上下限 假设 f i i D 是一个大样本空间 且服从正态分布 即 f i i D 的密度函数为 从状态空间D中随机选n个独立样本 Xi i 1 n 样本均值统计量为 样本方差统计量为 则估计 的值为 Aarts等人也提出了一个计算t0的方法 他们的做法是 假定对控制参数的某个确定值t产生一个m次变换的序列 并设m1和m2分别是其中目 则接受率 可用下式近似 只要将 设定为初始接受率 0 就能求出相应的t0值 增大变换的平均增量 2 齐次算法的温度下降方法 为避免算法进程产生过长的马氏链 控制参数tk的衰减量以小为宜 我们可猜想在控制参数小衰减量的情况下 两个相继值tk和tk 1上的平稳分布是相互逼近的 因此 如果在值tk上已经达到准平衡 则可以期望在tk值衰减为tk 1值后 可能只需进行少量的变换就足以恢复tk 1值上的准平衡 这样就可以选取较短长度的马氏链来缩减CPU时间 控制参数小衰减量还可能导致算法进程迭代次数的增加 因而可以期望算法进程接受更多的变换 访问更多的邻域 搜索更大范围的解空间 返回更高质的最终解 当然也花费更多的CPU时间 实验结果表明 只要衰减函数选得恰当 就能在不影响CPU时间合理性的前提下 较大幅度地提高最终解的质量 此外 如上所述 在控制参数小衰减量的情况中 可以选取短马氏链缩减CPU时间 齐次算法的理论要求温度下降到零 整个系统以概率 收敛到全局最优解 无论直观理解还是理论要求 温度总是下降的 因此 一个非常直观的下降方法是 1 tk 1 tk k 0 1 2 其中0 1 是一个接近1的常数 越接近1温度下降得越慢 这个衰减函数被许多研究者采用 他们选用的 值是0 5 0 99 这种方法简单易行 很受应用人员的欢迎 它的每一步以相同的比率下降 其中t0为初始温度 L为算法温度下降的总次数 这一下降方法的优点是易于操作 而且可以简单的控制温度下降的总步数 它的每一步下降长度相等 只适用于以迭代次数为停止准则的冷却进度表 3 齐次算法每一温度的迭代长度规则 即马氏链长度Lk的选取 Lk值给定算法进程在第k个马氏链中进行的变换数 有限序列 Lk 则规定了算法进程搜索的解范围 由于多数组合优化问题的解空间规模随问题规模n呈指数型增大 为使算法最终解的质量有所保证 理应建立Lk与n间的某种关系 指数型的关系显然是不切合实际的 因而Lk通常取为问题规模n的一个多项式函数 固定长度 在每一温度 迭代相同的步数 步数的选取同 问题的大小有关 通常采用与邻域大小直接相关 的规则 如TSP中的2 opt 邻域大小是 n是城市数 在同一温度 可取 由接受和拒绝的比率来控制迭代步数 当温度很高时 每一个状态被接受的频率基本相同 而且几乎所有的状态都被接受 此时 在同一温度应使迭代的步数尽量小 当温度渐渐变低时 越来越多的状态被拒绝 如果在此温度的 迭代太少 则可能造成过早地陷入局部最优状态 比较直观和有效的方法是随着温度的下降 将同一温度的迭代步长增加 实现的一种方法是给定一个充分大的步长上限U和一个接受次数指标R 当接受次数等于R时 在此温度不再迭代而使温度下降 否则 一直迭代到上限步数 实现的第二种方法是给定一个接受比率指标R 迭代步长上限U和下限L 每一温度至少迭代L步且记录同一温度迭代的总次数和被接受的次数 当迭代超过L步时 若接受次数同总次数的比率不小于R时 在这一温度不再迭代而开始温度下降 否则 一直迭代到上限步数 同样可以用拒绝次数为指标类似上面的讨论得到一些控制迭代步数的规则 概率控制法 略 4 算法的终止原则 即控制参数终值tf的选取 中已经提及 即总的温度下 模拟退火算法从初始温度开始 通过在每一温度的迭代和温度的下降 最后达到终止原则而停止 尽管有些原则有一定理论的指导 终止原则大多是直观的 下面分类讨论 零度法 即tf充分小 模拟退火算法的最终温度为零 因而最为简单的原则是 给定一个比较小的正数 当温度tk 时 算法停止 表示已经达到最低温度 循环总数控制法 这一简单原则在齐次算法的温度下降方法 降次数为一定值L 当温度迭代次数达到L时 停止运算 这一原则可分为两类 一类是整个算法的总迭代步数为一固定数 它表示各温度时马氏链迭代数 内循环 的总和为一个给定的数 这样很容易计算算法的复杂性 但需要合理分配内循环的长度和温度下降的次数 另一类是内循环的次数由迭代长度规则的 和 决定 温度下降次数 外循环 为一个定值 这样的控制法对估计算法的复杂性有一定的困难 基于不改进规则的控制法 以算法进程所得到的某些近似解为衡量标准 判断算法当前解的质量是否持续得到明显提高 从而确定是否终止算法 Kirkpatrick等人选取的停止准则是 在若干个 取s个如s 1 s 2等 相继的马氏链中解无任何变化 含优化或恶化 就终止算法 或在一个温度和给定的迭代次数内没有改进当前的局部最优解 则停止算法 模拟退火的一个基本思想是跳出局部最优解 直观的结论是在较高的温度没能跳出局部最优解 则在低的温度跳 出局部最优解的可能也比较小 由此产生上面的停止原则 接受概率控制法 给定一个指标 f 0是一个比较小的数 除当前局部最优解以外 其他状态的接受概率都小于 f时 停止运算 实现 和 时 记录当前局部最优解 给定一个固定的迭代次数 当在规定的次数里没有离开局部最优解或每一次计算的接受概率都小于 f 则在这个温度停止计算 邻域法 若采用产生概率 和接受概率 且设f0和f1分别为一个邻域内的局部最优和次最优值 当满足 时 其中N为邻域的大小 从局部最优到次优的接受概率满足 而从局部最优到其他费用更高 的状态的接受概率更小 直观的想法是邻域中每次至少有一个状态被接受 但当满足 时 除局部最优解以外状态的接受概率都小于邻域总点平均数 此时可以认为从局部最优解转移到其他状态的可能性很小 因此停止