第八章 启发式算法.ppt

第八章_启发式算法第八章启发式算法
组合优化模型与算法设计
Model binatorial
Optimization and Design of Algorithm
1
第八章启发式算法
本章介绍的启发式算法也称智能算法、现代优化
算法,自20世纪80年代初以来已得到深入研究和广泛
应用,主要包括模拟退火算法、神经网络算法、遗传
算法、蚁群优化算法等等.
它们的共性是基于客观世界中的一些自然现象,
通过与组合优化求解进行类比,找出它们的一些共
性,建立相应的算法.
仿生学
这些算法的目标是希望求解 NP 难问题的全局最优
解,有一定的普适性,可用于解决大量的实际应用问
题.
生命科学与工程科学的相互交叉、相互渗透、相互
促进是近代科学技术发展的显著特点之一.
2
第八章启发式算法
§1 模拟退火算法
§2 神经网络算法
§3 遗传算法
3
第八章启发式算法
§1 模拟退火算法
模拟退火(Simulated Annealing,简记 SA)算法
是一种通用的随机搜索算法.
模拟退火算法最初的思想由 Metropolis 在1953年
提出,它来源于固体的退火过程,Kirkpatrick 在1983
年成功将其应用在组合优化问题中.
目的是降低硬度,改善切削加工性;消除残余应
力,稳定尺寸,减少变形与裂纹倾向;细化晶粒,调
整组织,消除组织缺陷.
金属物体在加热至一定的温度后,它的所有分子
在状态空间 D 中自由运动,系统能量增大. 随着温度
的下降,这些分子逐渐停留在不同的状态,系统能量
逐渐下降,最后在常温时达到基态,分子重新以一定
的结构排列,系统能量下降至最小值. 这种由高温向
低温逐渐降温的过程称为退火.
4
§1 模拟退火算法
一、原理与步骤
进一步研究表明,在同一温度分子停留在能量小
的状态的概率比停留在能量大的状态的概率大.
由统计力学的研究表明,在温度 T ,分子停留在
状态 r 满足 Boltzmann 概率分布
其中,E(r) 表示状态 r 的能量,kB > 0 为 B –常数,
表示分子能量的一个随机变量. Z(T) 为概率分布的标
准化因子
Metropolis 准则:如果,则接受新状态,否则
按概率接受新状态.
其中;T = T(t)为一随时间 t 增加
而下降的参数,它相当于退火过程中的温度.
对固体在恒定温度下达到热平衡过程的模拟
在温度趋向于零时,分子停留在最低能量状态的
概率趋向于 1 .
温度下降过快,会如何?
5
第八章启发式算法
金属物体
组合优化问题
状态
能量最低的状态
最优解
能量
费用函数
解
模拟退火算法的基本原理:
称为 Metropolis 过程
1、给定温度 t 及点 x0 ,计算函数值 f(x0) ;
2、随机产生扰动,得到新点 x1=x0+ ,计算 f(x1)
及;
3、若,则接受新点,作为下一次模拟的出发点;
4、若,则计算新点接受概率, ,
产生[0,1] 区间上均匀分布的伪随机数 r , 若
则接受新点作为下一次模拟的出发点;否则放弃新
点,仍取原来的点作为下一次模拟的出发点.
按照一定的退火方案逐渐降低温度,重复 M- 过
程,构成了模拟退火算法.
6
§1 模拟退火算法
令控制参数 t 担当固体退火过程中温度的角色,
对于 t 的每一取值,算法采用 Metropolis 过程,持续
进行“产生新解——判断——接受/ 舍弃”的迭代过
程而达到该“温度”下的“平衡点”,随着参数 t 徐徐“降
温”并趋向于零时,最终求得组合优化问题的相对全局
最优解.
简单的模拟退火算法的步骤:
Step 1 任选一初始解 xi0;xi = xi0; k = 0; t0 = tmax .
初始温度
Step 2 若在该温度达到内循环停止条件,则到 Step 3;
否则,从邻域 N(xi) 中随机选取一 xj , 计算
;若,则xi = xj , 否则
若时,则 xi = xj ; 重
复 Step 2 .
Step 3 tk+1 = d(tk); k = k+1; 若满足停止条件,终止计
算;否则,回到 Step 2 .
温度下降规则
(衰减函数)
在(0,1)之间均匀分布的伪随机数
7
第八章启发式算法
在上述的 SA 算法中,包含一个内循环和一个外
循环. 内循环是 Step 2,它表明在同一个温度 tk 时,
在一些状态随机搜索. 外循环主要包括 Step 3 .
温度下降规则;
迭代步数增加;
停止条件.
SA 算法的每一次迭代都体现集中和扩散两个策略
的平衡. 对遇到的下一个迭代解,如果这个解更好,
则采用集中策略,选择这个解为新解. 不然