模拟退火算法原理及应用

迭 代 次 数
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算法模型状态分布图：
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算法目标函数之差与迭代次数关系图
重力正演计算：
计算单元：2.5度体的多边形截面棱柱体
Δ g(x,y,z)=G· б · ∑cosψ i[F1(y2-y,i)+ F1(y1-y,i)]
重力目标函数：
g x g 1 g /M i 1
M cal i obs i 2
目标函数的含义：正演值与实测值的相对均方误差。 优点：无量纲，并与测点数无关，便于与MT方法共同开 展联合反演
二 改进的VFSA算法—MVFSA算法
MVFSA有以下改进：
• 过程一：较高的初始温度，VFSA算法的 退火计划，模型作全局随机扰动—搜索 并锁定最优解区间； • 过程二：较低的初始温度，适当回火的 退火计划，模型作局部随机扰动--扰动 在当前模型周围进行—在锁定最优解空 间后，由于其搜索空间变得较小，以此 提高模型接受效率。
模 型 计 算 反 演 结 果
MVFSA
20
30
40
50 A
60
70
80
90
100 km
B 实 际 模 型 反 演 结 果 D 密 度 差 0.28 (g/cm )
3
C
垂直侧边梯形的MVFSA反演结果
△ g(mGal)
模 型 计 算
8 6 4 2 0 0 0 A -1 -2 km 实 际 模 型 J 反 演 结 果 B I H
△E= E(m1) -E(m0)
△E≤0? Yes No
m0= m1
新模型按 Metropolis准则接受
缓慢降低温度
满足收敛条件为止
传统模拟退火流程图
Metropolis接受准则：
• ⊿E<0，新模型无条件被接受—接受能量值较 小状态 • 否则，
E r exp( ) kbT
• 产生随机数ξ ∈[0，1] • 若r>ξ ，新模型被接受，否则被舍 弃。 —接受能量值较大状态，从而在模拟退
高温下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的关系示意图：
低温下模型扰动的空间过大，扰动后模型被接受 的机率必然降低，势必影响寻优效率，最终影响 算法完成后最终解的精度
电性与密度界面的GIS编码技术
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
-3 -3 -2.5 -2 -1.5 -1 -0.5
0
0.5
1
1.5
2
2.5
3
x
0
0.5
1
1.5
2
2.5
3
x
VFSA算法扰动状态分布和寻优轨迹 图
MVFSA算法扰动状态分布和寻优轨迹图
稳健性试验结论：
• 多次试验表明：在同等退火计划下， VFSA算法较易落入了局部极值区，而 MVSFA算法则比较稳健。
应用
MT-重力联合反演研究
• 一 从简单入手-重力模拟退火反演研究
算法稳健性试验：
模拟退火计划表 表 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
• 人机联作方式 • 修正在反演程序执行过程中进行，不需 暂停反演程序
Ti (T j 2 2T j 1 3T j 2T j 1 T j 2 ) / 9
'
Ti (T j 1 nTj T j 1 ) /(n 2)
'
△ g(mGal) 8 7 6 5 4 3 2 1 0 0 10 0 -0.5 -1 -1.5 -2 km
2
4
6
8
10
12
14
16
18
20
(km)
2.30(g/cm 3 )
2.52(g/cm 3 )
2.70(g/cm 3 )
(km)
背斜-向斜模型的模拟退火反演结果
MVFSA算法的实际资料处理：
g(mGal) 10 实 测 点 拟 合 曲 线 0 0 Q-J -2 -4 -6 -8 (km) T-C
D-S
5
5
10
15 2.34 2.60
20
25
新 87
30
Q-J
N12
35 (km)
Байду номын сангаас
2.60 2.60
2.60 2.54
2.54
反 演 界 面
AnS
2.70
MT解 释 综 合 解 释
3
目标函数
2 3 1 2 放 大 1 50 100 150 200
200
400
600
800
1000
1200
1400
模 型 修 正 阶 段
模型试验—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
MT的正演可以写为以下变分问题：
2 2 1 V 2 1 V 2 I V V dydz V dy y z 2 G z zmax
经比较，本文选用有限元法作为二维MT正演方法，既保 持较高的计算精度，又适应于复杂结构的地电模型。
局 部 放 大
扰 动 状 态
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%。
MT-重力联合反演必要性:
1.MT与重力联合可以使两方法相互弥补
• MT纵向分辨率与重力横向的分辨率的互补 • 实际工作中MT方法的测点点距一般较稀，而野 外重力数据的采集点较密。
2.充分利用野外资料：在生产实际中，非 地震方法一般同时开展。
MT-重力联合反演可能性:
• 电性与密度同源界面是两种方法联合的 前提 • 地下结构有可能以同源或部分同源的形 式出现
电性与密度界面有几个是一致的：
• 上第三系-下第三系的物性界面 • 下第三系-白垩系的物性界面 • 侏罗系-三叠系物性界面等。
开展MT与重力两者的联合反演是可能的。
MT与重力联合反演技术难点：
• 如何处理电性与密度界面的不一致情况 是首先要遇到的技术难点 • 如何构筑一个共同的目标函数—因为地 下界面的变化使MT与重力两者的场值变 化幅度是不同的
模拟退火算法原理及应用研究
主讲: 陈 华 根 同济大学海洋与地球科学学院
一 模拟退火算法及VFSA算法
模拟退火算法在反演中的应用：
• 非线性组合优化算法：模型扰动，模拟 退火，全局寻优。 • 能量函数—目标函数 • 模拟退火过程—反演迭代
随机选择初始模型m0 计算能量函数E(m0)
模型扰动产生新模型 m1=m0+△m0 计算能量函数E(m1)
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
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
过 程 二
改 进 算 法
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的关系示意图
△ g(mGal) 26 24
实 际 数 据 反 演 结 果
22 20 18 16 0 -1 -2 -3
0
1
2
3
4
5
6
7
8
9
10 km
2.30(g/cm 3 ) 2.70(g/cm 3 )
实 际 界 面 反 演 界 面
-4 -5
等 效 密 度 界 面
km
重力反演的等值效应现象
消除锯齿状界面的方法：
过程一：模拟退火，全局搜索
T = T0*EXP(-α*(j-1)1/2)
m Bi uBi Ai
' i
过程二：回火升温，局部搜索
T = T0*EXP(-α*(j-k0/β)1/2) mi' mi (u 0.5)Bi Ai / L ( j)
退 火 温 度
过 程 一
示例:
地 层 Q N E K2t K2p T1s T1x P1Q C3c C2n C1h C1g C1j D3w S3m S2f S1g O3d O2d O1I ε 3g 海安-盐城地区密度与电阻率统计表 表 5-1 密度 (×103kg/m3 ) 电 阻 率(Ω m) 16 2.13 8.7 2.30-2.31 3.9 4.8 2.46 11.9 150 84 2.60 275 3000 1617 100 18 2.58 600 2.53 87 58 2.54 66 27.5 118 5218 2.67 10051 2.70-2.73 2785
迭 代 次 数
目标函数与迭代关系曲线图
二
MT-重力联合反演研究
联合反演研究现状：
• 线性反演算法居多、非线性算法少，用模拟退 火算法进行联合反演研究更少。 • 尽管目前开展的联合反演研究已有多种，但研 究内容主要集中在地震与重力、地震与MT联合 反演的研究。 • 有关电磁测深与重力的联合反演研究只查阅到 一篇相关的论文，因此对这方面的研究基本上 还是空白。
反 演 结 果
MVFSA
10
20
30
40
50 C
60 D
70 E F
80
90
100 km
G 3 密 度 差 0.28 (g/cm )
垂直侧边梯形组合的MVFSA反演结果
△ g(mGal)
6 4 2 0 0 -1 -2 -3 -4 -5 -6 -7
模 型 界 面 反 演 结 果
模 型 计 算 反 演 结 果
火温度控制下全局寻优。
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