△E= E(m1) -E(m0)
△E≤0? Yes No
m0= m 1
新模型按 Metropolis准则接受
缓慢降低温度
满足收敛条件为止
传统模拟退火流程图
Metropolis接受准则：
• ⊿E<0，新模型无条件被接受—接受能量值较 小状态 • 否则，
E r exp( ) kbT
• 产生随机数ξ ∈[0，1] • 若r>ξ ，新模型被接受，否则被舍 弃。 —接受能量值较大状态，从而在模拟退
3－9
3－10
T k T0 Exp ck1/ N


100
温 度 初 始 温 度 ： 100 迭 代 次 数 ： 100 参 数 个 数 N: 2
90
80
70
60
50
衰 减 率 系 数 递 增 方 向 0.2
40
30
20
0.5 0.8
10
0.98
10 20 30 40 50 60 70 80 90 100
迭 代 次 数
VFSA的温度衰减曲线：
VFSA的降温速度是比较快的
y
3 2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5
-2
VFSA方 式 扰 动 全 局 随 机 扰 动
-3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3
-2.5
-3
x
高温下VFSA算法模型状态分布图：
模型试验—Z=f(x,y)型：
模拟退火计划表 表 3-1
算法 VFSA MVFSA
初试温度 200 200
温度衰减率 0.998 0.998
叠代次数 500 500
扰动次数 3 3
初始位置
x0=2.5, y0=2.5 x0=2.5, y0=2.5
3 2.5 2 1.5 1 0.5 0 -0.5 -1 -1.5 -2 -2.5
y
寻优轨迹 接受状态
3
起 点
y
寻优轨迹 接受状态
2.5 2 1.5 1 0.5 0 -0.5 -1 -1.5 -2 -2.5
起 点
最 优 解 -3 -3 -2.5 -2 -1.5 -1 -0.5
0
0.5
1
1.5
2
2.5
3
x
最 优 解 -3 -3 -2.5 -2 -1.5 -1 -0.5
0
0.5
1
1.5
高温下VFSA算法的状态空间遍历能力逊于随机数 发生器的遍历能力
退火温度
20 15 10 5 0 0 1 0.5 10 高 温 带 20 30 过 渡 带 40 50 60 70 低 温 带 80 90 100
VFSA
迭代次数
yi
0 -0.5 -1
VFSA算法迭代次数k与系数yi的关系示意图：

低温下模型扰动的空间过大，扰动后模型被接受 的机率必然降低，势必影响寻优效率，最终影响 算法完成后最终解的精度
模拟退火算法原理及应用研究
主讲: 陈 华 根 同济大学海洋与地球科学学院
一 模拟退火算法及VFSA算法
模拟退火算法在反演中的应用：
• 非线性组合优化算法：模型扰动，模拟 退火，全局寻优。 • 能量函数—目标函数 • 模拟退火过程—反演迭代
随机选择初始模型m0 计算能量函数E(m0)
模型扰动产生新模型 m1=m0+△m0 计算能量函数E(m1)
2
2.5
3
x
VFSA算法扰动状态分布和寻优轨迹图
MVFSA算法扰动状态分布和寻优轨迹图
局 部 放 大
扰 动 状 态
10
10
接 受 状 态 寻 优 轨 迹
5
目 标 函 数 之 差
5
0
0
20
40
60
80
50
100
150
200
250
300
350
400
450
500
迭 代 次 数
VFSA算法目标函数之差与迭代次数关系图
过程一：模拟退火，全局搜索
T = T0*EXP(-α *( j-1)1/2)
' i
m Bi uBi Ai
过程二：回火升温，局部搜索 T = T0*EXP(-α *( j-k0/β)1/2)
mi' mi (u 0.5)Bi Ai / L ( j)
退 火 温 度
二 改进的VFSA算法—MVFSA算 法
MVFSA有以下改进：
• 过程一：较高的初始温度，VFSA算法的 退火计划，模型作全局随机扰动—搜索 并锁定最优解区间； • 过程二：较低的初始温度，适当回火的 退火计划，模型作局部随机扰动--扰动 在当前模型周围进行—在锁定最优解空 间后，由于其搜索空间变得较小，以此 提高模型接受效率。
过 程 一
VFSA
过 程 二
改 进 算 法
0
迭 代 次 数
图3-5 VFSA与MVFSA算法的退火温度曲线比较
20 15 10
退火温度
MVFSA
0 10 高 温 带 20 30 过 渡 带 40 50 60 70 低 温 带 80 90 100
5 0
迭代次数
1 0.5
yi
0 -0.5 -1
MVFSA算法迭代次数k与系数yi的关系示意图
算法稳健性试验：
模拟退火计划表 表 3-3
算法 VFSA MVFSA
初试温度 温度衰减率 2 0.98 2 0.98
叠代次数 30 30
扰动次数 1 1
初始位置 x0=2.5,y0=2.5 x0=2.5,y0=2.5
3 2.5 2 1.5 1 0.5 0 -0.5 -1 -1.5 -2 -2.5
局 部 放 大
扰 动 状 态
10 10
接 受 状 态 寻 优 轨 迹
5
目 标 函 数 之 差
5
0
0
20
40
60
80
50
100
150
200
250
300
350
400
450
500
迭 代 次 数
MVFSA算法目标函数之差与迭代次数关系图
• VFSA及MVFSA算法在退火计划十分完备的情况下,表 现相当完美：算法起点相同，寻优路径不同，最终找 到的都是同一最优解 • VFSA与MVFSA算法的模型状态均分布这个状态空间， 但VFSA模型状态在最优解点出现一个十字型状态， MVFSA算法在整个最优解区域形成一个矩形，这与它 们的模型扰动方式有关。 • 在相同的退火计划下两种算法的时间，VFSA算法约为 103秒，而MVFSA算法只用时约75秒，多次试验表明： MVFSA算法计算时间约比VFSA算法少20-30%。
火温度控制下全局寻优。
VFSA算法分析：
•
' m 模型扰动： i mi yi Bi Ai
yi T sgn u 0.51 1 / T

2 u 1
1

3－7 3－8
• 接收概率：
• 退火计划：
P 1 1 hE / T
1/ 1h