《现代优化技术-靳志宏》算法收敛性.ppt

现代优化技术 第13讲 算法收敛性浅析 一 模拟退火算法的基本思想 启发注意到一个自然规则 物质总是趋于最低的能态 水总是向低处流 电子总是向最低能级的轨道排布 最低能态是最稳定的状态 物质会 自动 地趋向的最低能态 模拟退火算法 起源 物理退火原理 模拟退火算法与物理退火过程的相似关系 模拟退火算法 Metropolis准则 Metropolis准则假设在状态xold时 系统受到某种扰动而使其状态变为xnew 与此相对应 系统的能量也从E xold 变成E xnew 系统由状态xold变为状态xnew的接受概率p 模拟退火算法 流程 随机产生一个初始解x0 令xbest x0 并计算目标函数值E x0 设置初始温度T 0 To DowhileT Tmin 降温过程forj 1 k 等温过程对当前最优解xbest按照某一邻域函数 产生一新的解xnew 计算新的目标函数值E xnew 并计算目标函数值的增量 E E xnew E xbest 如果 E 0 则xbest xnew 如果 E 0 则p exp E T i 如果c random 0 1 p xbest xnew 否则xbest xbest Endfor按照温度控制策略更新T EndDo输出当前最优点 计算结束 模拟退火算法 要素 1 状态空间与状态产生函数 邻域函数 搜索空间也称为状态空间 它由经过编码的可行解的集合所组成 状态产生函数 邻域函数 应尽可能保证产生的候选解能遍布全部解空间 通常由两部分组成 即产生候选解的方式和候选解产生的概率分布 候选解一般按照某一概率分布对解空间进行随机采样来获得 概率分布可以是均匀分布 正态分布 指数分布等等 模拟退火算法 要素 2 状态转移概率 接受概率 p状态转移概率是指从一个状态xold 一个可行解 向另一个状态xnew 另一个可行解 的转移概率 通俗的理解是接受一个新解为当前解的概率 它与当前的温度参数T有关 随温度下降而减小 一般采用Metropolis准则 模拟退火算法 要素 3 冷却进度表T t 冷却进度表是指从某一高温状态To向低温状态冷却时的降温管理表 假设时刻t的温度用T t 来表示 则经典模拟退火算法的降温方式为 而快速模拟退火算法的降温方式为 这两种方式都能够使得模拟退火算法收敛于全局最小点 模拟退火算法 要素 4 初始温度T0实验表明 初温越大 获得高质量解的几率越大 但花费的计算时间将增加 因此 初温的确定应折衷考虑优化质量和优化效率 常用方法包括 1 均匀抽样一组状态 以各状态目标值的方差为初温 2 随机产生一组状态 确定两两状态间的最大目标值差 max 然后依据差值 利用一定的函数确定初温 比如 t0 max pr 其中pr为初始接受概率 3 利用经验公式给出 模拟退火算法 要素 5 内循环终止准则或称Metropolis抽样稳定准则 用于决定在各温度下产生候选解的数目 常用的抽样稳定准则包括 1 检验目标函数的均值是否稳定 2 连续若干步的目标值变化较小 3 按一定的步数抽样 模拟退火算法 要素 6 外循环终止准则即算法终止准则 常用的包括 1 设置终止温度的阈值 2 设置外循环迭代次数 3 算法搜索到的最优值连续若干步保持不变 4 检验系统熵是否稳定 模拟退火算法的改进 也可通过增加某些环节而实现对模拟退火算法的改进 主要的改进方式包括 1 增加升温或重升温过程 在算法进程的适当时机 将温度适当提高 从而可激活各状态的接受概率 以调整搜索进程中的当前状态 避免算法在局部极小解处停滞不前 2 增加记忆功能 为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解 可通过增加存储环节 将 BestSoFar 的状态记忆下来 3 增加补充搜索过程 即在退火过程结束后 以搜索到的最优解为初始状态 再次执行模拟退火过程或局部性搜索 4 对每一当前状态 采用多次搜索策略 以概率接受区域内的最优状态 而非标准SA的单次比较方式 5 结合其他搜索机制的算法 如遗传算法 混沌搜索等 6 上述各方法的综合应用 15 1随机过程的概念 随机过程被认为是概率论的 动力学 部分 即它的研究对象是随时间演变的随机现象 它是从多维随机变量向一族 无限多个 随机变量的推广 给定一随机试验 其样本空间 将样本空间中的每一元作如下对应 便得到一系列结果 17 例1 抛掷一枚硬币的试验 样本空间是 现定义 18 19 20 例5 考虑抛掷一颗骰子的试验 22 随机过程的分类 随机过程可根据参数集T和任一时刻的状态分为四类 参数集T可分为离散集和连续集两种情况 任一时刻的状态分别为离散型随机变量和连续型随机变量两种 连续参数连续型的随机过程 如例2 例3连续参数离散型的随机过程 如例1 例4离散参数离散型的随机过程 如例5离散参数连续型的随机过程 如下例 马尔科夫Markov链 引例假定某大学有1万学生 每人每月用1支牙膏 并且只使用 中华 牙膏与 黑妹 牙膏两者之一 根据本月 12月 调查 有3000人使用黑妹牙膏 7000人使用中华牙膏 又据调查 使用黑妹牙膏的3000人中 有60 的人下月将继续使用黑妹牙膏 40 的人将改用中华牙膏 使用中华牙膏的7000人中 有70 的人下月将继续使用中华牙膏 30 的人将改用黑妹牙膏 据此 可以得到如表所示的统计表 状态和状态转移状态是指客观事物可能出现或存在的状况 如企业的产品在市场上可能畅销 也可能滞销 状态转移是指客观事物由一种状态到另一种状态的变化 客观事物的状态不是固定不变的 它可能处于这种状态 也可能处于那种状态 往往条件变化 状态也会发生变化 如某种产品在市场上本来是滞销的 但是由于销售渠道变化了 或者消费心理发生了变化等 它便可能变为畅销产品 转移概率与转移概率矩阵假定某大学有1万学生 每人每月用1支牙膏 并且只使用 中华 牙膏与 黑妹 牙膏两者之一 根据本月 12月 调查 有3000人使用黑妹牙膏 7000人使用中华牙膏 又据调查 使用黑妹牙膏的3000人中 有60 的人下月将继续使用黑妹牙膏 40 的人将改用中华牙膏 使用中华牙膏的7000人中 有70 的人下月将继续使用中华牙膏 30 的人将改用黑妹牙膏 据此 可以得到如表所示的统计表 上表中的4个概率就称为状态的转移概率 而这四个转移概率组成的矩阵B 称为转移概率矩阵 可以看出 转移概率矩阵的一个特点是其各行元素之和为 2转移概率矩阵及柯尔莫哥洛夫定理 例1某计算机机房的一台计算机经常出故障 研究者每隔15min观察一次计算机的运行状态 收集了24h的数据 共作97次观察 用1表示正常状态 用0表示不正常状态 所得的数据序列如下 1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111 近邻探索过程 全局最优解 局部最优解2 局部最优解1 邻域 目标函数値 模拟退火算法的数学模型可以描述为 在给定邻域结构后 模拟退火过程是从一个状态到另一个状态不断地随机游动 我们可以用马尔科夫链描述这一过程 对给定的温度t 两个状态的转移概率定义为 称为从i到j的产生概率 generationprobability 表示在状态i时 j状态被选取的概率 比较容易理解的是j为i的邻居 如果在邻域中等概率选取 则j被选中的概率为 称为接受概率 acceptanceprobability 表示产生状态j后 j状态被接受的概率 在模拟退火算法中常见的是 由上面三组公式可以看出 一步转移概率只同状态i转移到状态j有关 同第几次迭代无关 因此 马氏链是时齐的 正是这个原因 将这一类算法取名为时齐算法 下面 介绍几个概率论中常用概念 辅助同学们理解算法收敛性的讨论过程 若存在n 使得 则称状态i可达状态j 记成若状态i和状态j满足且 则称状态i和状态j相通 记成 有如下定理 定理 若且则有 定义从i到达j的首达时刻的随机变量为 其概率定义为 迟早到达概率定义为 定理 的充分必要条件是 定理 状态j是常返的 则以概率1系统无穷次返回状态j 状态j是非常返的 则以概率1 系统只有限次返回状态j 记表示自状态i出发 系统通过j状态至少m次的概率 记表示状态i出发通过j状态至少m次的时间 于是 有 进而 所以 常返的含义 常返中的一种特殊情况为正常返 定义 当时为正常返 当时为零常返 常返定理表明常返是以概率1无穷次返回同一状态 上式表明有些常返状态的平均返回次数是有限的 而有些是无限的 当马氏链的离散状态均为常返且平均返回次数有限 就称该马氏链是正常返的 在模拟退火的理论中 经常用到的一个概念是不可约 不可约中用到的一个概念是闭集 一个集合C是闭集的定义为 有 这表示集合C是一个封闭的集合 i不可达到j 对任意n成立 除整个状态空间外 没有别的闭集的马氏链成为不可约的马氏链 定理1 不可约 有限状态且时齐的马氏链是正常返的 定理2 非周期 不可约且时齐的马氏链是正常返的充分必要条件 存在唯一平稳分布 满足 模拟退火算法的时齐算法 当具有以下条件成立时 则可以认为该模拟退火算法收敛全局最优解 1 在每一个给定的温度t 给出算法一步转移概率的一些限定条件 使得定理2成立 由此得到平稳分布概率 2 给出平稳分布应该满足的条件 使得当温度渐进达到0度时 平稳分布的极限存在 即要求 3 进一步要求平稳分布的极限具有全局最优性条件 其中是最优状态集合 探索空间 searchspace 与实行可能域 feasiblesolutionfield 1 探索空间 实行可能域 目标函数值探索评价基准 近邻例一台机器的交货期最小迟延排序问题 工件的集合 1 2 3 4 可行解的集合从 1 2 3 4 中構成4 种可能的排序 目标函数一台机器的交货期最小迟延排序问题 目标函数交货期迟延的合計 最小化 可行解 順列 1234所对应的目标函数 J1 6 近邻一台机器的交货期最小迟延排序问题 近邻两个相邻工件交換后得到的排序 可行解1234的近邻 1243 1324 2134 一台机器的交货期最小迟延排序问题近邻图 1234 1243 点与解一一对应 6 6 7 7 5 4 3 5 7 7 10 8 7 8 6 6 8 5 5 4 6 10 目标函数值 2134 1324 探索空间 searchspace 与实行可能域 feasiblesolutionfield 2 探索空间 目标函数值 objectivefunctionvalue 惩罚函数值 penaltyfunctionvalue 实行可能域 探索空间 实行可能域 探索评价基准 带有时间窗约束的VRP问题 邻域交换不能随意进行 因为需要满足客户时间窗的硬性要求 处理办法有两种 1 不排斥不可行解 用惩罚函数进行处理 通常为在目标函数设置一个惩罚项 如果突破时间窗则使目标函数为一个正无穷大的值 该种做法的实质是扩大了解空间 使近邻搜索空间具有完备性 同时又不影响搜索结果 但会影响搜索路径 有好有坏 这样的改造会使邻域内选择解的概率满足上述定理的假设条件 充分满足随机性 会提高算法的各方面性能 因此是推荐方法 2 排斥不可行解 直接忽略 不能满足上述定理的条件 影响算法收敛性 解空间的搜索 解 离散随机状态 随机状态的跳转 满意解 最终状态 SA接受准则 GA算子 状态转移概率矩阵 目标函数的导向性 稳态概率最大似然值对应状态 考试题型 选择 20 判断 20 简答 60 简答内容 1 对于概念 技术细节的描述 原理的阐述 2 编码设计 3 编写算法伪代码 4 算法的时间复杂度计算 5 收敛性简要分析 下次课 1 数学模型 算法设计以及程序设计的关系 难点 约束条件的算法处理 模式定理与积木块假设 算法迭代中不可行解的处理办法 2 算法程序实现的实例详解 适应度函数编写的难点 复杂模型的程序推进核心 时间残值矩阵 Q A