- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
模拟退火算法
1982年Kirkpatrick将固体退火过程应用于组合优化问
题的求解,提出一种有效的近似算法,称为模拟退
火算法。
模拟退火算法从初始解i = i 开始,在当前
0
解i的邻域S 中按照Metropolis准则有哪些信誉好的足球投注网站新解
i
j 以取代当前解i。这个过程不断进行下去,
直到达到目标函数最优。
固体退火过程
退火是固体由高温下粒子排列的无序的液态冷却而凝
固成粒子排列有序的固体晶态的过程。
退火是系统的熵不断减小,能量趋于最小值的过程。
它遵循热力学中的自由能减少定律:
F E Ts
其中F、E和S分别表示自由能、能量和熵。
系统从非平衡态自发变化到平衡态,都是能量和熵竞
争的结果,温度决定二者孰重。
Metropolis接受准则
设i是一个状态,j是由i可得到的一个新状态。它们的
能量分别为E 和E 。
i j
若E <E ,则状态j 可以取代状态i。
j i
否则固体处于状态i和状态j 的几率为
其中k是Boltzmann常数,T为绝对温度,r <1。
设 是(0, 1)中的随机数,若r > ,则状态j 可以取代
状态i。
模拟退火算法的框架
k = 0; i = i ; t = t ; //初始化
0 0
while (不满足停止准则) {
Gen(S ); //产生i的邻域S ,|S |=L
i i i k
for (j ∈S ) //用Metropolis准则对S 中的
i i
if (f(i) f(j)) i = j; //每个状态j检测是否可替代i
else if (exp((f(i) – f(j))/ t) random(0, 1)) i = j;
k = k + 1; t = t ; // 降温;进入下一轮迭代
k
}
算法的性能
算法可以渐进地收敛于整体最优解。
Metropolis准则给算法引入了随机性,使算法进程方
向呈现跳跃性,从而可能避开局部最优,但不能完
全避开局部收敛。
最终解不依赖于初始解。
温度t和|S |(即L )决定算法的收敛速度。
i k
算法的复杂性为O(kLP(n)) ,其中k为迭代次数,
L=max{|S |},P(n)是问题规模n的多项式函数。求高
i
质量的近似解的耗费也较高。
模拟退火算法的应用
应用模拟退火算法的工作如下:
(1)确定解问题、能量函数和初始解:解空间是所有
可行解的集合;能量函数是优化目标的数学描述;
初始解是开始计算的起点。
(2)新解的产生和接受准则:从当前解产生新解;用
Metropolis准则判断新解是否可替代当前解;然后用
新解/当前解进行下一轮实验。
(3)冷却进度表及其它参数:L 由新解来确定,冷却
k
温度t 用冷却进度表或衰减函数给出。
k
用模拟退火算法解TSP
解空间为所有的排列,初始解为1, 2,…, n 。
能量函数f为发、该排列的周游路线长度。即
n
f(d d …d ) = min{∑d d + d d }
i1 i2 in ik ik+1 in i1
k=1
产生
您可能关注的文档
最近下载
- 一种蚕丝面膜制备工艺.pdf VIP
- 基坑工程技术标准DG TJ08-61-2018上海(1).pdf
- 2024必威体育官网网址观知识竞赛试题及一套完整答案.docx
- GB-T50353-2013建筑工程建筑面积计算规范.ppt
- 《DB21T2355-2014-建设项目环境监理技术规范》.pdf
- 节约型机关创建自评报告.docx VIP
- 火电厂设备检修项及定额导则(A).doc VIP
- 板式换热器面积计算.xls VIP
- 译林版小学英语四年级上册知识点和同步练习(全).pdf VIP
- Unit 11 Lesson 1 Living in a Community 课件-高中英语北师大版(2019)选择性必修第四册.pptx
文档评论(0)