模拟退火算法第一节.ppt

模拟退火 simulatedannealing 算法是局部搜索算法的扩展 它源于对固体退火过程的模拟 采用Metropolis接受准则 并用一组称为冷却进度表的参数控制算法进程 使算法在多项式时间里给出一个近似最优解 模拟退火算法最早的思想由Metropolis在1953年提出 Kirkpatrick在1983年成功地应用在组合最优化问题中 第2章模拟退火算法 一固体退火过程 退火是一种物理过程 固体退火是先将固体加热至熔化 再徐徐冷却使之凝固成规整晶体的热力学过程 退火过程中 系统在每一温度下达到平衡态 系统状态的分布满足一定的概率分布 即在温度T 系统达到平衡态后 分子停留在状态r满足波兹曼 Boltzmann 概率分布 2 1模拟退火算法及模型 其中 E r 为状态r的能量 kB 0为波兹曼常数 为分子能量的一个随机变量 称为波兹曼因子 Z T 为概率分布的标准化因子 先研究由 2 1 确定的函数随T变化的趋势 选定两个能量E1 E2 在同一个温度T 有 D为状态空间 在同一个温度 2 2 表示分子停留在能量小状态的概率比停留在能量大状态的概率要大 当温度相当高时 2 1 的概率分布使得每个状态的概率基本相同 接近平均值1 D D 为状态空间D 中状态的个数 此时 具有最低能量状态的波兹曼概率接近并超出平均值1 D 当rmin是D中具有最低能量的状态时 得 由 所以 关于温度T是单调下降的 又有 其中 D0是具有最低能量的状态集合 因此得到 当T趋向于0时 当温度趋向于0时 2 1 决定的概率渐近 由此可以得到 在温度趋向于0时 分子停留在最低能量状态的概率趋向1 综合上面的讨论 分子在最低能量状态的概率变化趋势由图 a 表示 对于非能量最小的状态 由 2 2 和分子在能量最小状态的概率是单调减小的事实 在温度较高时 分子在 使 2 1 决定的概率在 0 t 是单调升的 再由 2 4 可知 当温度趋于0时 2 1 定义的概率趋于0 概率变化曲线见图 b 从上面的讨论得到 在温度很低时 能量越低的状态的概率值越高 在极限状况 只有能量最低的点概率不为 即有 1 系统在T平衡时 系统状态的概率分布趋于 2 1 式 例2 1简化概率分布 2 1 为 其中q t 为标准化因子 设共有四个能量点x 1 2 3 4 率分布变化 二 Metropolis准则 固体在恒定温度下达到热平衡的过程可以进行模拟 1953年 Metropolis等提出重要性采样法 他们用下述方法产生固体的状态序列 先给定以粒子相对位置表征的初始状态i 作为固体的当前状态 该状态的能量是Ei 然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化 得到一个新状态j 新状态的能量是Ej 如EjEi 则考虑热运动的影响 该新状态是否重要状态 要依据固体处于该状态的几率来 判断 由 2 1 知 固体处于i和j的概率的比值等于相应Boltzmann因子的比值 即 r是一个小于1的数 用随机数发生器产生一个 0 1 区间的随机数 若r 则新状态j作为重要状态 否则舍去 若新状态j是重要状态 就以j取代i成为当前状态 否则仍以i为当前状态 再重复以上新状态产生过程 在大量固体状态的变换后 系统趋于能量较低的平衡状态 固体状态的概率分布趋于 2 1 式的Boltzmann概率分布 由 式可知 高温下可接受与当前状态能差较大的新状态为重要状态 而在低温下只能接受与当前状态能差较小的新状态为重要状态 这与不同温度下热运动的影响完全一致 在温度趋与零时 就不能接受任一Ej Ei的新状态j了 上述接受新状态的准则称为Metropolis准则 相应的算法称为Metropolis算法 这种算法的计算量显著减少 三 模拟退火算法 对固体退火过程的研究给人们以新的启示 1982年 Kirkpatrick等首先意识到固体退火过程与组合优化问题之间存在的类似性 Metropolis等对固体在恒定温度下达到热平衡的模拟也给他们以启迪 应该把Metropolis准则引入到过程中来 最终他们得到一种对Metropolis算法进行迭代的组合优化算法 这种算法模拟固体退火过程 称之为模拟退火算法 我们可以将组合优化问题同金属物体退火进行类比 组合优化问题 金属物体 假设算法用以解决如下组合优化问题 解 费用 目标 函数 最优解 状态 能量 能量最低的状态 模拟退火算法 Step1任选一个初始解x0 xi x0 k 0 Step2若在该温度达到内循环条件 则到step3 Step3tk 1 d tk k k 1 若满足停止条件 终 t0 tmax 初始温度 否则 从邻域N xi 中随机选一xj 计算 fij f xj f xi 若 fij 0 则xi xj 否则若exp fij tk random 0 1 时 则xi xj 重复step2 止计算 否则 回到step2 产生一个0与1之间的一个随机数 1 随算法进程递减其值的控制参数t担当固体退火过程中的温度T的角色 2 对t的每一取值 算法持续进行 产生新解 判断 接受 舍弃 的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程 也就是执行了一次Metropolis算法 模拟退火算法从某个初始解出发 经过大量解的变换后 可以求得给定控制参数值时组合优化问题的相对最优解 然后减小t的值 重复执行Metropolis算法 就可以在t趋于零时 最终求得整体最优解 3 由于退火必须 徐徐 降温 t也必须缓慢衰减 才能确保模拟退火算法最终趋于组合优化问题的整体最优解集 4 模拟退火算法依据Metropolis准则接受新解 因此除接受优化解外 还在一个限定范围内接受恶化解 这正是模拟退火算法与局部搜索算法的本质区别所在 开始时t值大 可能接受较差的恶化解 随着t的减小 只能接受较好的恶化解 最后在t值趋于零时 就不再接受任何恶化解了 这就使算法既可以从局部最优的陷阱中跳出 更有可能求得组合优化问题的整体最优解 又不失简单性和通用性 因此对大多数组合优化问题而言 模拟退火算法要优于局部搜索算法 模拟退火算法的数学模型可以描述为 在给定邻域结构后 模拟退火过程是从一个状态到另一个状态不断地随机游动 我们可用马尔可夫链描述这一过程 当温度t为一确定值时 两个状态的转移概率定义为 Gij t 称为从i到j的产生概率 Gij t 表示在状态i时 j状态被选取的概率 比较容易理解的是j是i的邻居 如果在邻域中等概率选取 则j被 选中的概率为 Aij t 称为接受概率 Aij t 表示在状态i产生j后 接受j的概率 如在模拟退火算法中接受的概率是 2 5 2 6 2 7 为模拟退火算法的主要模型 模拟退火算法主要可以分为两类 第一类为齐次算法 在 2 5 中对每一个固定的t 计算对应的马尔可夫链变化 直至达到一个稳定状态 然后再使温度下降 第二类是非齐次算法 由一个马尔可夫链组成 要求在两个相邻的转移中 温度t是下