智能优化算法模拟退火算法ppt课件

智能优化算法与应用 1 自我介绍 刘敏 电气学院自动化系副教授2007 2012年美国加州大学博士 博士后2000 2007年北京大学本科 硕士研究方向 计算机视觉 图像处理联系方式liu min 2 参考教材 王耀南 智能信息处理技术 高等教育出版社 2003年8月第1版 王凌 智能优化算法及其应用 清华大学出版社 施普林格出版社 2004 3 模拟退火算法及其应用SimulatedAnnealing SA 4 导言 模拟退火算法 SimulatedAnnealing SA 是一种通用的优化算法 目前 已在 生产调度 控制工程 计算机视觉 神经网络 图像处理等工程领域中得到了广泛应用 1953年 Metropolis等提出SA思想 1983年 Kirkpatrick等将其用于组合优化 目的在于 为具有NP复杂性的问题提供有效的近似求解算法 克服优化过程陷入局部极小 克服初值依赖性 5 尼古拉 梅特罗波利斯 尼古拉 梅特罗波利斯 NicholasConstantineMetropolis 1915年6月11日生于美国芝加哥 1936年他在芝加哥大学取得学士学位 1941年取得实验物理学博士学位 之后留校在冶金学实验室 MetallurgicalLaboratory 工作 其间他在1942年曾参与哥伦比亚大学的原子弹计划 1943年他进入洛斯阿拉莫斯实验室 参加著名的 曼哈顿计划 与 原子弹之父 费米 EnricoFermi 和泰勒 EdwardTeller 一起工作 其任务是为高温 高压 高密度下的物质建立状态方程 从此他的研究工作从物理学转入了数学领域 在曼哈顿计划中他是课题组组长 6 7 组合优化 组合优化 作为应用数学中最年轻而又至关重要的领域之一 整合了组合数学 线性规划以及算法理论的方法和技巧 由于它在解决从远程通讯到超大规模集成电路 从产品运销到航班机组排班等领域内困难问题方面的成功 这一领域在过去的十年里取得了巨大的 超乎寻常的发展 8 计算机视觉 ComputerVision计算机视觉是一门研究如何使机器 看 的科学 更进一步的说 就是是指用摄影机和电脑代替人眼对目标进行识别 跟踪和测量等 并进一步做图形处理 用电脑处理成为更适合人眼观察或传送给仪器检测的图像 9 计算机视觉 制造业 检验识别 文档分析 医疗诊断 军事 智能电网等领域中各种智能系统中不可分割的一部分 美国把对计算机视觉的研究列为对经济和科学有广泛影响的科学和工程中的重大基本问题 即所谓的重大挑战 grandchallenge 为计算机和机器人开发具有与人类水平相当的视觉能力 10 人脸识别 在FBI 人脸识别终于要真正发挥在电影中一样的作用了 作为国家的指纹数据库的更新的一部分 美国联邦调查局已经开始推出了面部识别 识别罪犯 反恐 而这些高富帅们的手笔也不是一般的大 1billion 11 机器视觉 其他应用 湖南大学电气院指纹打卡美国加州大学实验室红膜识别计算机视觉又叫做机器视觉 扫地机器人http ipd pps tv play 373X1J html 12 爬山算法 HillClimbing 介绍模拟退火前 先介绍爬山算法 爬山算法是一种简单的贪心搜索算法 该算法每次从当前解的临近解空间中选择一个最优解作为当前解 直到达到一个局部最优解 爬山算法实现很简单 其主要缺点是会陷入局部最优解 而不一定能搜索到全局最优解 如图1所示 假设C点为当前解 爬山算法搜索到A点这个局部最优解就会停止搜索 因为在A点无论向那个方向小幅度移动都不能得到更优的解 13 爬山算法 14 模拟退火 SA SimulatedAnnealing 思想 爬山法是完完全全的贪心法 每次都鼠目寸光的选择一个当前最优解 因此只能搜索到局部的最优值 模拟退火其实也是一种贪心算法 但是其搜索过程引入了随机因素 模拟退火算法以一定的概率接受一个比当前解要差的解 因此有可能会跳出这个局部的最优解 达到全局的最优解 以图1为例 模拟退火算法在搜索到局部最优解A后 会以一定的概率接受到E的移动 也许经过几次这样的不是局部最优的移动后会到达D点 于是就跳出了局部最大值A 15 模拟退火算法思想 模拟退火算法描述 若J Y i 1 J Y i 即移动后得到更优解 则总是接受该移动若J Y i 1 J Y i 即移动后的解比当前解要差 则以一定的概率接受移动 而且这个概率随着时间推移逐渐降低 逐渐降低才能趋向稳定 这里的 一定的概率 的计算参考了金属冶炼的退火过程 这也是模拟退火算法名称的由来 16 TSP问题 作为模拟退火算法应用 讨论货郎担问题 TravellingSalesmanProblem 简记为TSP 设有n个城市 用数码1 n代表 城市i和城市j之间的距离为d i j i j 1 n TSP问题是要找遍访每个域市恰好一次的一条回路 且其路径总长度为最短 旅行商问题属于所谓的NP完全问题 精确的解决TSP只能通过穷举所有的路径组合 其时间复杂度是O N 使用模拟退火算法可以比较快的求出TSP的一条近似最优路径 17 NP问题 P问题 可以在以多项式表达的时间内求出确切解的问题 也就是说它的计算复杂度是一个多项式 我们通常用的O n O logn O n 2 等等类似的都是这类问题 O n for i 0 i 100 i O n 2 for i 0 i 100 i for j 0 j 100 j 18 非确定性问题 什么是非确定性问题呢 有些计算问题是确定性的 比如加减乘除之类 你只要按照公式推导 按部就班一步步来 就可以得到结果 但是 有些问题是无法按部就班直接地计算出来 比如 找大质数的问题 有没有一个公式 你一套公式 就可以一步步推算出来 下一个质数应该是多少呢 这样的公式是没有的 19 NP问题 NP问题 英文是non deterministicpolynomial 是多项式时间可以验证的问题 最初是在非确定图灵机上 如果一个问题存在一个解 那么就先猜它 一定可以在多项式时间内猜到这个解 关键是就是不判定这个问题到底有没有解 p NP目前还没有被证实 也就是还不知道P和NP的关系 但是可以确定的是P属于NP 20 模拟退火算法及其应用 SA算法是基于MonteCarlo迭代求解策略的一种随机寻优算法 其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性 21 MonteCarlo蒙特卡洛 欧洲地中海之滨 法国的东南方 有一个世界上版图最小的国家摩纳哥公国 世人称之为 赌博之国 袖珍之国 邮票小国 22 蒙特卡洛模拟 蒙特卡洛模拟为方便的解决困难而复杂的实际问题开启了一扇大门 估计蒙特卡罗模拟最著名的早期使用是诺贝尔奖物理学家EnricoFermi 原子弹之父 在1930年的应用 那时他用一种随机方法来计算刚发现的中子的性质 23 蒙特卡罗 有关MonteCarlo方法历史背景的最精确描述来自JunLiu的专著 他指出一批物理学家在二战期间为估算薛定谔方程的本征值而发明了一种基于统计抽样的数值计算法 其最初想法归功于Ulam 后来Ulam的同事Metropolis将该方法命名为MonteCarlo 1950年代Metropolis和几名统计物理学同事发表了一篇经典论文 提出了MarkovChainMonteCarlo MCMC 算法 而MCMC法后来是Bayesian统计学能够不断前进的主要动力 24 蒙特卡罗 蒙特卡罗模拟是曼哈顿计划所用到的模拟的核心部分 在20世纪50年代蒙特卡罗模拟就用在LosAlamos国家实验室发展氢弹的早期工作中 并流行于物理学和运筹学研究领域 兰德公司和美国空军是这个时期主要的两个负责资助和传播蒙特卡罗方法的组织 今天蒙特卡罗模拟也被广泛应用于不同的领域 包括工程 物理学 研发 商业和金融 25 退火 中文名称 退火英文名称 annealing将金属加热到一定温度 保持足够时间 然后以适宜速度冷却 通常是缓慢冷却 有时是控制冷却 的一种金属热处理工艺 1 26 什么是退火退火淬火 物理退火过程 27 退火的作用 1 降低硬度 改善切削加工性 2 消除残余应力 稳定尺寸 减少变形与裂纹倾向 3 细化晶粒 调整组织 消除组织缺陷 4 均匀材料组织和成分 改善材料性能或为以后热处理做组织准备 在生产中 退火工艺应用很广泛 根据工件要求退火的目的不同 退火的工艺规范有多种 常用的有完全退火 球化退火 和去应力退火等 28 模拟退火算法的基本思想 启发注意到一个自然规则 物质总是趋于最低的能态 水总是向低处流 电子总是向最低能级的轨道排布 最低能态是最稳定的状态 物质会 自动 地趋向的最低能态 29 模拟退火算法的设计与原理猜想 物质自动趋向的最低能态与函数最小值之间有相似性 我们能不能设计一种算法求函数最小值 就像物质 自动 地趋向最低能态 降温图像 离散函数图像 相似性 最小值 最低能态 30 物理模型 固体退火 退火俗称固体降温先把固体加热至足够高温 使固体中所有粒子处于无序的状态 最高的熵值 然后将温度缓慢下降 粒子渐渐有序 熵值下降 这样只要温度上升得足够高 冷却过程足够慢 则所有粒子最终会处于最低能态 最低的熵值 最低能态 时间 温度 31 模拟退火算法的设计与原理类比 根据Metropolis准则 粒子在温度T时趋于热平衡的概率为其中E为温度T时的内能 E为其改变量 k为Boltzmann常数 可以设计算法 将系统熵值类比为函数值F 来模拟这个退火过程 32 Metropolis准则 1953 以概率接受新状态p exp Ej Ei kBT 在高温下 可接受与当前状态能量差较大的新状态 在低温下 只接受与当前状态能量差较小的新状态 33 2 3模拟退火算法及其应用 物理退火过程由以下三部分组成 加温过程增强粒子热运动 使其偏离平衡位置 当温度足够高时 固体熔解为液体 消除系统可能存在的非均匀态 使随后进行的冷却过程以某一平衡态为起点 等温过程对于与周围环境交换热量而温度不变的封闭系统 系统状态的自发变化总朝自由能减少的方向进行 当自由能达到最小时 系统达到平衡态 冷却过程使粒子的热运动减弱并渐趋有序 系统能量逐渐下降 从而得到低能的晶体结构 34 2 3模拟退火算法及其应用 为了模拟固体在恒定温度下达到热平衡的过程 可采用MonteCarlo方法 该方法简单 但必须大量采样才能得到较精确结果 计算量很大 考虑到物理系统倾向于能量较低的状态 而热运动又妨碍它准确落到最低态的图像 采样时着重取那些有重要贡献的状态则可较快达到较好的结果 1953年 Metropolis等据此提出了重要性采样法 也称为Metropolis准则 即以概率接受新状态 35 2 3模拟退火算法及其应用 Metropolis准则 在温度t 由当前状态i产生新状态j 两者的能量分别为Ci和Cj 若Cj Ci 则接受新状态j为当前状态 否则 若概率pr exp Cj Ci kt 大于 0 1 区间内的随机数 仍接受新状态j为当前状态 若不成立 则保留状态i为当前状态 其中 k为Boltzmann常数 36 2 3模拟退火算法及其应用 SA算法的基本思路 由某一较高初温开始 利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索 伴随温度的不断下降重复抽样过程 最终得到问题的全局最优解 37 模拟退火算法的实现思想 SA算法的计算过程可视为重复递减控制参数值 温度 并进行Metropolis算法的迭代过程 一次Metropolis算法是指 对于控制参数t的每一取值 算法在Markov链长度内持续进行 产生新解 判断 接受 舍弃 的迭代过程 对应着固体在某一恒定温度下趋于热平衡的过程 算法终止时的当前解即为所得近似最优解 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程 38 马尔科夫过程 一类随机过程 它的原始模型马尔可夫链 由俄国数学家A A 马尔可夫于1907年提出 该过程具有如下特性 在已知目前状态 现在 的条件下 它未来的演变 将来 不依赖于它以往的演变 过去 例如森林中动物头数的变化构成 马尔可夫过程 在现实世界中 有很多过程都是马尔可夫过程 如液体中微粒所作的布朗运动 传染病受感染的人数 车站的候车人数等 都可视为马尔可夫过程 关于该过程的研究 1931年A H 柯尔莫哥洛夫在 概率论的解析方法 一文中首先将微分方程等分析的方法用于这类过程 奠定了马尔可夫过程的理论基础 39 MarkovProcess 马尔科夫过程 MarKovProcess 是一个典型的随机过程 设X t 是一随机过程 当过程在时刻t0所处的状态为已知时 时刻t t t0 所处的状态与过程在t0时刻之前的状态无关 这个特性成为无后效性 无后效的随机过程称为马尔科夫过程 马尔科夫过程中的时同和状态既可以是连续的 又可以是离散的 我们称时间离散 状态离散的马尔科夫过程为马尔科夫链 马尔科夫链中 各个时刻的状态的转变由一个状态转移的概率矩阵控制 40 2 3模拟退火算法及其应用 例 考虑一元函数求最大值的优化问题 41 2 2模拟退火算法及其应用 SA在局部极小解处有机会跳出 并最终趋于全局最优的根本原因 算法通过概率判断来接受新状态 理论上 初温充分高 降温足够慢 每一温度下抽样足够长 最终温度趋于零时 算法以概率1收敛到全局最优解 由于SA的某些收敛条件无法严格实现 或即使某些收敛条件可以实现 但常因为实际应用的效果不理想而不被采用 迄今为止 SA的参数选择依然是一个难题 通常只能依据一定的启发式准则或大量的实验加以选取 42 二 退火过程和Bolzman方程 2 43 Bolzman方程 二 退火过程和Bolzman方程 3 44 温度对的影响当很大时 各状态的概率几乎相等SA开始做广域搜索 随着温度的下降差别扩大 二 退火过程和Bolzman方程 4 45 当时 与的小差别带来和的巨大差别例如 90 100 二 退火过程和Bolzman方程 5 46 当 100时 二 退火过程和Bolzman方程 6 47 当 1时此时结论 时 以概率1趋于最小能量状态 二 退火过程和Bolzman方程 7 48 2 3模拟退火算法及其应用 步骤1 确定编码方式和能量函数 目标函数 最常用的编码方案 实数编码 以实数来表示求解状态 s 1 8函数优化问题中 能量函数由待优化函数变换而成 若目标函数为最大化问题 C s f s 若目标函数为最小化问题 C s f s 49 2 3模拟退火算法及其应用 步骤2 确定初温实验表明 初温t0越大 获得高质量解的几率越大 但计算时间增加 初温的确定应折衷考虑优化质量和效率 常用方法包括 均匀抽样一组状态 以各状态目标值的方差为初温 随机产生一组状态 确定两两状态间的最大目标值差 max 计算初温 t0 max lnpr初始接受概率pr理论上接近于1 初温也可选为某个较大的常数 50 2 3模拟退火算法及其应用 步骤3 确定初始状态 初始解 理论上 初始状态可以随机取 但为了提高优化效率 可采用启发式算法快速得到一个解 并以此为SA的初始状态 51 2 3模拟退火算法及其应用 步骤4 状态产生函数 新解产生函数 设计的出发点是尽可能保证产生的候选解遍布全部解空间 最常用的状态产生函数 snew sold 为扰动幅度参数 为随机扰动变量 随机扰动可服从柯西分布 高斯分布 均匀分布 52 柯西分布 a为尺度参数高斯分布 为方差 均值为0均匀分布 53 2 3模拟退火算法及其应用 以原点为中心的柯西和高斯分布函数曲线 54 2 3模拟退火算法及其应用 步骤5 状态接受函数该函数的引入是SA算法实现全局搜索的最关键因素 一般以概率方式给出 最常用的状态接受函数 min 1 exp C sj C si tk random 0 1 设计状态接受概率 应该遵循以下原则 固定温度下 接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率 随温度下降 接受使目标函数值上升解的概率要逐渐减小当温度趋于零时 只能接受目标函数值下降的解 55 2 3模拟退火算法及其应用 步骤6 内循环终止准则或称Metropolis抽样稳定准则常用的抽样稳定准则包括 检验目标函数的均值是否稳定 连续若干步的目标值变化较小 按一定的步数抽样 56 2 3模拟退火算法及其应用 步骤7 退温函数温度的下降方式 用于在外循环中修改温度值 目前 最常用的温度更新函数 指数退温函数 tk 1 tk 为退温速率 0 l 且 大小可以不断变化 57 2 3模拟退火算法及其应用 步骤8 外循环终止准则即算法终止准则 用于决定算法何时结束 设置温度终值te是一种简单的方法 SA算法的收敛性理论中要求te趋于零 这显然不实际 通常的做法包括 设置终止温度的阈值 设置外循环迭代次数 算法搜索到的最优值连续若干步保持不变 检验系统熵是否稳定 58 2 2模拟退火算法及其应用 从算法流程上看 SA算法包括三函数两准则 即 新 状态产生函数 新 状态接受函数温度更新函数 退温函数 内循环终止准则 抽样稳定准则 外循环终止准则 退火结束准则 这些环节的设计决定SA的优化性能 初温的选择对SA算法性能也有很大影响 初温 温度更新函数 内循环终止准则和外循环终止准则通常被称为退火历程 59 模拟退火算法流程图 60 SA的模拟要求初始温度足够高降温过程足够慢终止温度足够低 三 SA的算法构造及步骤 1 61 问题的描述及要素 三 SA的算法构造及步骤 2 62 SA的计算步骤初始化 任选初始解 给定初始温度 终止温度 令迭代指标 注 选择时 要足够高 使随机产生一个邻域解 计算目标值增量 三 SA的算法构造及步骤 3 63 若转步 j比i好无条件转移 否则产生 j比i好 有条件转移 注 高时 广域搜索 低时 局域搜索若达到热平衡 内循环次数大于 转步 否则转步 三 SA的算法构造及步骤 4 64 降低 若停止 否则转步 注 降低的方法有以下两种流程框图见下页 三 SA的算法构造及步骤 5 65 66 问题的提出单机极小化总流水时间的排序问题四个工作 求的最优顺序 四 计算举例 1 67 预备知识 按SPT准则 最优顺序为3 1 4 2 四 计算举例 2 68 用SA求解这个问题状态表达 顺序编码邻域定义 两两换位定义为邻域移动解 设降温过程定义为初始解 i 1 4 2 3 四 计算举例 3 69 注释 无条件转移 为有条件转移 在 中 虽然目标值变坏 但搜索范围变大 是随机产生的 四 计算举例 4 70 注释 有条件转移 为无条件转移 在 中 停在4 3 1 2状态 目标值仍为109 四 计算举例 5 71 注释 无条件转移 在 中 停在3 1 4 2状态 目标值仍为92 SA没有历史最优 不会终止在最优解 故算法一定要保持历史最优 四 计算举例 6 72 2 4TSP问题的求解 模拟退火算法编码最常用策略 路径编码直接采用城市在路径中的位置来构造用于优化的状态 例 九城市TSP问题 路径 5 4 1 7 9 8 6 2 3路径编码 541798623 73 2 4TSP问题的求解 状态产生函数对于基于路径编码的SA状态产生函数操作 可设计为 互换操作逆序操作插入操作例 状态为 541798623 两随机位置为2 6互换操作结果 581794623 逆序操作结果 589714623 插入操作结果 584179623 74 1 10周 三 7 8节 南校区 天马 综313 多媒体 自带电脑 人数 94 1 10周 五 5 6节 南校区 天马 综112 多媒体 自带电脑 人数 94 75