模拟退火算法新.ppt
《模拟退火算法新.ppt》由会员分享,可在线阅读,更多相关《模拟退火算法新.ppt(50页珍藏版)》请在三一文库上搜索。
1、1,第五章 模拟退火,2,第五章 模拟退火,一.导言 二.退火过程和Bolzman方程 三.SA的算法构造及步骤 四.计算举例 五.SA的收敛性分析 六.SA的应用举例,3,模拟退火的产生(SA) 1953年 Metropolis提出原始的SA算法,未引 起反响 1982年 Kirkpatrick提出现代的SA算法,得到广泛的应用,一.导言(1),4,基本思想 模拟热力学当中的退火过程 退火过程: 物体: 高温 低温 高能状态 低能状态,一.导言(2),缓慢下降,5,淬火: 快速冷却,使金属处于高能状态,较硬易断 退火: 缓慢冷却,使金属处于低能状态,较为柔韧,一.导言(3),6,模拟退火在S
2、A中的应用 在SA中将目标函数作为能量函数 模拟: 初始高温 温度缓慢下降 终止在低温 这时能量函数达到极小,目标函数最小,一.导言(4),7,热力学中的退火过程 变温物体缓慢降温从而达到分子之间能量最 低的状态,二.退火过程和Bolzman方程(1),8,二.退火过程和Bolzman方程(2),9,Bolzman方程,二.退火过程和Bolzman方程(3),10,温度 对 的影响 当 很大时, ,各状态的概率几乎相等 SA开始做广域搜索,随着温度的下降 差别 扩大,二.退火过程和Bolzman方程(4),11,当 时, 与 的小差别带来 和 的巨大差别 例如: =90, =100,,二.退火
3、过程和Bolzman方程(5),12,当 =100时,二.退火过程和Bolzman方程(6),13,当 =1时 此时 结论: 时,以概率1趋于最小能量状态,二.退火过程和Bolzman方程(7),14,SA的模拟要求 初始温度足够高 降温过程足够慢 终止温度足够低,三.SA的算法构造及步骤(1),15,问题的描述及要素,三.SA的算法构造及步骤(2),16,SA的计算步骤 初始化,任选初始解, ,给定初始温度 ,终止温度 ,令迭代指标 。 注:选择 时,要足够高,使 随机产生一个邻域解, 计算目标值增量,三.SA的算法构造及步骤(3),17,若 转步 (j比i好无条件转移) ;否则产生 (j比
4、i好,有条件转移)。 注: 高时,广域搜索; 低时,局域搜索 若达到热平衡(内循环次数大于 )转步,否则转步。,三.SA的算法构造及步骤(4),18,降低 ,若 停止,否则转步。 注:降低 的方法有以下两种 流程框图见下页,三.SA的算法构造及步骤(5),19,20,问题的提出 单机极小化总流水时间的排序问题 四个工作: ,求 的最优顺序。,四.计算举例 (1),21,预备知识:按SPT准则,最优顺序为3-1-4-2,四.计算举例 (2),22,用SA求解这个问题 状态表达:顺序编码 邻域定义:两两换位定义为邻域移动 解: 设 降温过程定义为 初始解:i=1-4-2-3,四.计算举例 (3),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法
链接地址:https://www.31doc.com/p-2604732.html