模拟退火算法ppt课件_第1页
模拟退火算法ppt课件_第2页
模拟退火算法ppt课件_第3页
模拟退火算法ppt课件_第4页
模拟退火算法ppt课件_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

模拟退火算法 SimulatedAnnealing 1 引子2 SA算法的起源3 SA算法的基本思想4 SA算法的步骤5 SA算法应用范围与一般要求6 SA算法的优缺点 1 引子 在科学与工程计算中 经常发生的一个问题是在Rn中或者是在一个有界区域上求某个非线性函数f x 的极小点 在f x 可导时 一个最基本的算法就是最速下降法 这一方法从某一选定的初值开始 利用如下公式进行迭代 即 然而以速降法为代表的传统算法具有共同的缺点 它们都不保证求得全局极小 只能保证收敛到一个由初值决定的局部极小点 每次都鼠目寸光的选择一个当前最优解 因此只能搜索到局部的最优值 模拟退火其实也是一种贪心算法 但是它的搜索过程引入了随机因素 模拟退火算法以一定的概率来接受一个比当前解要差的解 因此有可能会跳出这个局部的最优解 达到全局的最优解 2 SA算法的起源 SA算法起源于对固体退火过程的模拟 简单而言 在固体退火时 先将固体加热使其温度充分高 再让其徐徐冷却 其物理退火过程由以下三部分组成 加温过程 等温过程 冷却过程 SA算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术 模拟退火算法与物理退火过程的相似关系 3 SA算法的基本思想 在搜索最优解的过程中 SA算法除了可以接受优化解外 还基于随机接受准则 Metropolis准则 有限度地接受恶化解 并且接受恶化解的概率慢慢趋向于0 这使得算法有可能从局部最优中跳出 尽可能找到全局最优解 并保证了算法的收敛 SA的思想最早是由Metropolis等在1953年提出的 Metropolis等提出了重要性采样法 即以概率接受新状态 SA算法的思想为 由初始解i和控制参数初值t开始 对当前解重复产生新解 计算目标函数差 接受或舍弃的迭代 并逐步衰减t值 算法终止时的当前解即为所得近似最优解 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程 SA算法与其它搜索方法相比 具有如下的特点 以一定的概率接受恶化解 引进算法控制参数 使用对象函数值进行搜索 隐含并行性 搜索复杂区域 4 SA算法的基本步骤 1 随机产生一个初始解x0 令xbest x0并计算目标函数值E x0 2 设置初始温度T 0 To 迭代次数i 1 3 DowhileT i Tmin1 forj 1 k2 对当前最优解xbest按照某一邻域函数 产生一新的解xnew 计算新的目标函数值E xnew 并计算目标函数值的增量 E E xnew E xbest 3 如果 E 0 则xbest xnew 4 如果 E 0 则p exp E T i 1 如果c random 0 1 p xbest xnew 否则xbest xbest 5 Endfor4 i i 1 5 EndDo6 输出当前最优点 计算结束 流程图 5 SA算法应用范围与一般要求 SA算法是近年来备受重视的一类软计算方法 能解决传统的非线性规划方法难于解决的某些问题 在VLSI 生成调度 控制工程 机器学习 神经网络 图像处理 函数优化等许多领域得到广泛的研究 SA算法的应用需满足如下三个方面的要求 1 对问题的简明形式的描述即数学模型 由解空间 目标函数和初始解三部分构成 2 新解的产生和接受机制 3 冷却进度表 冷却进度表是指从某一高温状态T0向低温状态冷却时的降温管理表 假设时刻t的温度用T t 来表示 则经典模拟退火算法的降温方式为 而快速模拟退火算法的降温方式为 这两种方式都能够使得模拟退火算法收敛于全局最小点 5 SA算法应用范围与一般要求 5 SA算法应用范围与一般要求 初始温度T0的设定 实验表明 初温越大 获得高质量解的几率越大 但花费的计算时间将增加 因此 初温的确定应折衷考虑优化质量和优化效率 常用方法包括 1 均匀抽样一组状态 以各状态目标值的方差为初温 2 随机产生一组状态 确定两两状态间的最大目标值差 max 然后依据差值 利用一定的函数确定初温 比如 t0 max pr 其中pr为初始接受概率 3 利用经验公式给出 5 SA算法应用范围与一般要求 算法终止准则 常用的包括 1 设置终止温度的阈值 2 设置外循环迭代次数 3 算法搜索到的最优值连续若干步保持不变 4 检验系统熵是否稳定 6 SA算法的优缺点 与同类方法相比 SA算法具有以下优缺点 优点 高效 灵活 通用 初值鲁棒性强 适用于并行处理 可用于求解复杂

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论