没有合适的资源?快使用搜索试试~ 我知道了~
一种有效的全局优化算法_模拟退火算法.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 45 浏览量
2022-07-11
09:47:27
上传
评论
收藏 217KB PDF 举报
温馨提示
试读
4页
一种有效的全局优化算法_模拟退火算法.pdf
资源推荐
资源详情
资源评论
收稿日期 : 2005 - 03 - 23
作者简介 :汪灵枝
(
1974—
)
,男 ,广西象州人 ,讲师 ,研究方向 :启发式算法 ;周优军
(
1974—
)
,男 ,广西全州人 ,讲师。
第 20卷第 2期
2005年 6月
柳 州 师 专 学 报
Journal of L iuzhou Teachers College
Vol. 20 No. 2
June 2005
一种有效的全局优化算法 ———模拟退火算法
汪灵枝 ,周优军
(
柳州师范高等专科学校 数学与计算机科学系 ,广西 柳州 , 545004
)
摘 要 :模拟退火算法是有效的全局优化算法 ,本文讨论了模拟退火算法发展过程及其理论依据 ,利用 MAT2
LAB语言编写程序并测试分析 ,认为算法本身可进一步改进 ,提出了算法改进思路和方法。
关键词 :模拟退火算法 ;全局优化 ;程序
中图分类号 : O224 文献标识码 : A 文章编号 : 1003 - 7020
(
2005
)
02 - 0120 - 04
1 引言
模拟退火
(
Simulated Annealing,简称 SA
)
算法是基于蒙
特卡罗
(
Monte Carlo
)
迭代求解法的一种启发式随机搜索算
法. 算法思想最早在 1953年由 N. Metropolis等人提出的 ,但
是把它用于组合优化和 VLSI设计却是在 1983年由 S. Kirk2
patrick等人和 V. Cerny分别提出来的. 算法将组合优化问题
和统计力学中的热平衡问题类比 ,另辟了组合优化问题的新
途径. 其出发点是物理学中的退火过程 ,即在对固体物质进
行退火处理时 ,通常是先将它加温 ,使其粒子可自由运动 ,然
后降温 ,粒子逐渐形成低能态的晶体 ,若在凝结点附近温度
下降得足够慢 ,则固体物质一定会形成最低能量的基态.
退火的概念最初是人们为了研究组合优化问题而提出
的 ,算法用于解决组合优化问题则是基于物理中固体物质的
退火过程与一般组合优化问题之间的相似性. 通过设定一初
温和初态 ,伴随温度的不断下降 ,结合概率突跳特性在解空
间中通过邻域函数进行随机搜索 ,最终得到全局最优. 模拟
退火算法是一种通用的优化算法 ,目前已在工程中得到了广
泛的应用 ,诸如 VLSI、生产调度、控制工程、机器学习、神经网
络、图象处理等领域.
2 算法基本原理和程序实现
2. 1 基本原理
模拟退火算法的基本思想是从一给定解开始 ,从邻域中
随机产生另一个解 ,接受 Metropolis准则允许目标函数在有
限范围内变坏 ,它由一控制参数 t决定 ,其作用类似于物理
过程中的温度 T,对于控制参数的每一取值 , 算法持续进行
“产生 —判断 —接受或舍弃 ”的迭代过程 ,对应着固体在某一
恒定温度下趋于热平衡的过程. 经过大量的解变换后 , 可以
求得给定控制参数 t值时优化问题的相对最优解. 然后减小
控制参数 t的值 ,重复执行上述迭代过程 ,当控制参数逐渐
减少并趋于 0时 ,系统亦越来越趋于平衡状态 ,最后系统状
态对应于优化问题的全局最优解 , 该过程也称为冷却过程.
由于固体退火必须缓慢降温 ,才能使得固体在每一个温度下
都达到热平衡 ,最终趋于平衡状态. 因此 ,控制参数 t经缓慢
衰减 ,才能确保模拟退火算法最终优化问题的整体最优解.
具体步骤如下
[1 ]
:
(
1
)
给定模型每一个参数变化范围 ,在这个范围内随机
选择一个初始模型 m
0
,并计算相应的目标函数值 E
(
m
0
)
.
(
2
)
对当前模型进行扰动产生一个新模型 m,计算相应
的目标函数值 E
(
m
)
,得到
△E = E
(
m
)
- E
(
m
0
)
.
(
1
)
(
3
)
若 △E < 0,则新模型 m 被接受;若 △E > 0,则新模型
m 按概率 P = exp
(
- △E /T
)
进行接受 , T为温度. 当模型被
接受时 ,置 m
0
=m , E
(
m
0
)
- E
(
m
)
.
(
4
)
在温度 T下 ,重复一定次数的扰动和接收过程 ,即重
复步骤
(
2
)
、
(
3
)
.
(
5
)
缓慢降低温度 T.
(
6
)
重复步骤
(
2
)
、
(
5
)
,直至收敛条件满足为止.
SA算法实质上分两次循环 ,随机扰动产生新模型并计
算目标函数
(
或称能量
)
的变化 ;决定新模型是否被接受. 由
于算法初温设计在高温条件 ,这使得 E增大的模型可能被接
受 ,因而能舍去局部极小值 ,通过缓慢地降低温度 ,算法最终
能收敛到全局最优点.
从上述步骤可看出模拟退火算法依据 Metropolis准则接
受新解 ,为此除了接受优化解外 ,还在一定限度内接受恶化
解 ,这正是 SA算法与局部搜索算法的本质区别所在. 开始时
候值大 ,可能接受较差的恶化解 ;随着 t的减小 ,则只能接受
好的恶化解;最后在 t值趋于零时 ,就不再接受恶化解了 ,从
而使得 SA能从局部最优的“陷阱 ”中跳出 ,最后得到全局最
021
资源评论
智慧安全方案
- 粉丝: 3615
- 资源: 59万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功