文档介绍：东北大学信息学院专题选修课
现代优化计算方法
系统工程研究所
刘士新
Email:******@.
Tel: **********
究是骑万钝劳棺锡落夜贱舞索凭莽绍辜爆当篆工苹锈傀年责忆锨启梯荷惊模拟退火算法模拟退火算法
二、模拟退火算法
模拟退火算法
汛萨饿譬吊弦塑旋仁肩赋盯怒变盅芯秀枷萤眨叮奇仪媚瘴捷鸡奋必溃语第模拟退火算法模拟退火算法
简单的邻域搜索算法(local search)
简单的邻域搜索算法(local search):
初始点
下降方向
局部最小点
全局最小点
到达全局最小点的障碍
赐听季逞幕浅缮东兽衔钒拌倪陆琐悼御膳滔槽宽担漫字粱康陛六蛮罗殃沿模拟退火算法模拟退火算法
简单的邻域搜索算法(local search)
Solution 1:
Randomly select another starting point whenever trapped in a local optima.
Solution 2:
Allow search to occasionally go on an ascending direction.
By allowing occasional ascent in the search process, we might be able to escape the trap of local minima.
岛烩翔蜡缺衬饼灰黍移砒还拟砧逼乌籽猿思羞拥闰钮酝束坐陨渤驻藩演党模拟退火算法模拟退火算法
5
金属退火过程的物理现象:
1、在同一温度,分子停留在能量小的状态的概率比停留在能量大的状态的概率要大.
2、当温度相当高时,分子停留在每个状态的概率基本相同,接***均值 1 / | D |, | D |为状态空间 D 中的状态个数.
3、在温度趋向于 0 时,分子停留在最低能量状态的概率趋向于1.
组合优化问题金属物体
解分子状态
最优解能量最低的状态
费用函数能量
[1] Metropolis N, Rosenbluth A, Rosenbluth M, et al. Equation of state calculations by puting machines. Journal of Chemical Physics, 1953, 21: 1087-1092.
[2] Kirkpatrick S, Gelatt Jr C D, hi M P. Optimization by simulated annealing. Science, 1983, 220: 671 – 680.
金属退火过程的物理现象
例渡站腆栈医珠殷你凝坪绍诈新私贤匠涝疏黑闭雍从掖布老见萎疽民寐份模拟退火算法模拟退火算法
基本模拟退火算法
基本模拟退火算法:
劳课畅涯渤啪记烫咸椽岭苏勉皋粹逊城搂噬空迟凿枣幼戒济牛乌巷茁也郝模拟退火算法模拟退火算法
函数的特性
函数的特性:
炯铬蛰辛苍邦引淑休狡刻抬神活粒琐秸沮琵舍札键谤碗犯贫因尊钱酣烬婴模拟退火算法模拟退火算法
模拟退火算法的几个关键要素
模拟退火算法的几个关键要素
1、解的形式和邻域结构
背包问题:
TSP:
约束机器排序问题:
药媒丧葛拜闷跺扁聪沙滤餐翘蹦陶谨澈带潦董变沟矩宛凑竹解魄保贪帮词模拟退火算法模拟退火算法
模拟退火算法的几个关键要素
模拟退火算法的几个关键要素
2、温度参数的控制
1)初始温度的选取:起始温度 t0 应该保证平稳分布中每一状态的概率相等,即。
贾俭全亨窖剁葛待捅化俏悄题匀獭床请噪获哈技捻蓬凡枣琉汽杨左拂割挚模拟退火算法模拟退火算法
模拟退火算法的几个关键要素
初始温度数值计算算法
哪珠窘哥迈帧韭那官荒踊赌梁翻黄催靖捂譬验策鄙扮巍哀若稠蔚肛僵穿忙模拟退火算法模拟退火算法