MT资料反演的一种实数编码混合遗传算法
柳建新,童孝忠,李爱勇,许建荣
(中南大学 信息物理工程学院,湖南 长沙,410083)
摘要:设计了一种求解一维大地电磁测深反演问题的实数编码混合遗传算法,它是通过单纯形搜索与遗传算法结合而成。针对传统的遗传算法在优化应用中存在局部搜索能力弱、计算量大、对较大空间适应能力弱和早熟收敛,而基于局部线性化的单纯形法易使解陷入局部极小值,严重依赖初始模型的选择等问题,在遗传算法中加入一个改进的单纯形搜索算子,并采用最优群体保留策略。该新算法既具有遗传算法的全局收敛性,又具有单纯形法的快速收敛性。对各种类型的大地电磁测深理论曲线进行计算,结果表明:采用实数编码混合遗传算法进行反演具有收敛速度快、解的精度高和避免出现早熟等优点,可用于大地电磁资料解释。
关键词:大地电磁测深;混合遗传算法;单纯形法;反演
中图分类号:P631.3 文献标识码:A 文章编号:1672-7207(2007)01-0160-04
A real coded hybrid genetic algorithm in magnetotelluric
sounding data inversion
LIU Jian-xin, TONG Xiao-zhong, LI Ai-yong, XU Jian-rong
(1. School of Info-physics and Geomatics Engineering, Central South University, Changsha 410083, China)
Abstract: The inverse problem of MT for 1-D was studied by using a real coded hybrid genetic algorithm, which was based on the combination of simplex method and genetic algorithm. Due to the fact that the standard genetic algorithm has poor local search ability, large amounts of calculation, and adaptability to large space, and that simple method based on local linearization is usually lost in local minimum values, a new method was put forward through a promoted simple operator embedded into genetic algorithm and the strategy was adopted to keep the group of best individuals. The new algorithm has not only the global of genetic algorithm, but also the fast convergence of the simplex algorithm. The inversion results of synthetic magnetotelluric sounding data are ideal, which indicates that the algorithm possesses advantages of expediting convergence, avoiding earliness and improving precision, and can be used in MT data analysis.
Key words: magnetotelluric sounding; hybrid genetic algorithm; simplex method; inversion
大地电磁测深(Magnetotelluric sounding,简称MT)资料反演的任务是将实测的MT资料(包括视电阻率和相位曲线)转化为地电断面参数,建立用于解释的地电模型。目前,二维、三维数据处理技术日趋成熟,比较典型的有快速直接的Bostick反演法[1]、基于D+模型的Rhoplus反演法[2]、基于最小层状模型的Automod反演法[3]和基于最平缓模型的Occam反演 法[4]。而一维反演的优化算法也很多,如梯度法、高斯—牛顿法、马夸特方法和广义逆矩阵法等[1]。这些一维反演算法属于线性或局部线性法,由于MT反演的多解性,此类方法比较依赖于初始模型,并且容易陷入局部最优解。因此,人们致力于某些非线性反演方法如遗传算法、蒙特卡洛法、模拟退火法的研究。
遗传算法GA(Genetic Algorithm)[5-6]作为一种全局搜索策略,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法简单通用,鲁棒性强,适于并行处理,具有收敛速度快,能对多变量的复杂情况进行反演等特点[7-11]。遗传算法与传统的优化算法(如梯度法、单纯形法等)相比有明显的优势,但简单遗传算法也存在一些缺点,如收敛速度太慢、容易陷入局部最优等。为了克服遗传算法的这些特点,本文作者提出把单纯形搜索融入基本遗传算法中,把单纯形搜索作为与选择、交叉、变异平行的一个算子,构成混合遗传算法(HGA)。
1 混合遗传算法
1.1 编 码
为了克服二进制编码的缺点,对于问题的变量是实向量的情形,可以直接采用实数编码。这样,便可直接在解的表现型上进行遗传操作,从而便于引入与问题领域相关的启发式信息,以增强演化算法的搜索能力[12-13]。采用实数编码,即利用如下线性变换:
式中:i=1,2,…,n;xu(i)和xl(i)为变量的上下边界值;y(i)为[0,1]内的随机数,所以把变量对应的x(i)依次连在一起构成问题解的编码形式为(x(1),x(2),…,x(n))。
1.2 基本遗传算子
1.2.1 选择算子
采用比例选择算子即进行赌轮或蒙特卡罗选择,各个个体的选择概率与其适应值呈正比。设群体数为m,其中个体i的适应值为fi,则i被选择的概率 psi为
显然,概率psi反映了个体i的适应值在整个群体的个体适应值总和中所占的比例。个体的适应值越大,其被选择的概率就越高,反之亦然。根据选择概率,就可以决定哪些个体被选出。
1.2.2 交叉算子
采用算术交叉,给定个体x和y,经过算术交叉后得到的个体为:
1.2.3 变异算子
采用非一致性变异算子,若个体x=[x1,x2,…,
xk,…,xn]的元素xk被选择变异,,则变异结果为。其中:
Δ(t,dx)返回区间[0,dx]里的1个值,使Δ(t,dx)靠近0的概率随代数t的增加而增加。其中:r为[0,1]区间的随机数;t为群体的当前代数;D为最大代数;b为决定非一致性程度的1个参数(一般取值为2~5)。
1.3 单纯形搜索
初始步 给定,令xi=x0+hei,i=1,…,n(h>0为常数),形成一个单纯形,选α>0,β>0,
r>1。
1.4 算法实现
混合遗传算法的执行步骤如下。
步骤1 给遗传算法参数赋值。这些参数包括种群体规模m,变量个数n,交叉概率pc,变异概率pm,进行单纯形搜索的概率ps和遗传计算所允许的最大代数D。
步骤2 随机产生初始群体,并计算其适应值。
步骤3 执行比例选择算子进行选择操作。
步骤4 按概率pc执行算术交叉算子进行交叉操作。
步骤5 按照概率pm执行非一致性变异算子运算。
步骤6 对每个个体按照概率ps进行单纯形搜
索。若个体被选择进行模式搜索操作,则以作为初始点执行模式搜索法得。若≤≤,则把所得计算结果作为子代;否则,若<,则取;若>,则取,1≤i≤m。
步骤7 计算个体适应值,并执行最优个体保存策略。
步骤8 判断是否终止计算条件,若不满足,则转向步骤3;若满足,则输出计算结果。
1.5 复杂函数优化实例
求解Schwefel[14]函数的极小值为:
其中:-500<xi<500;i=1,2,…,n。该函数的三维网格图如图1所示。这是典型的多峰值问题,采用普通的优化算法很难得到局部最优解。采用本文提出的实数编码混合遗传算法,取群体规模m=100,交叉概率pc=0.3,变异概率pm=0.1,单纯形搜索概率p=0.05,最大迭代次数D=10,求得该函数的全局极小点为(-420.968 70,-420.977 87), 最优值为-837.965 70。
图1 函数的三维网格图
Fig.1 The function’s 3D graph
2 一维MT正演
2.1 正演计算
假定地电剖面是水平分层均匀的,若地电剖面共有N层,则共有2N-1个参数,hi(i=1,2,…,N-1)和ρi(i=1,2,…,N)分别代表第层的厚度和电阻率。对于上述一维模型,计算视电阻率ρa和相位φa的公式为:
式中:Z1为第1层地表的波阻抗;μ为导磁率,ω=,
为角频率;Re[Z1]和Im[Z1]分别为Z1的实部和虚部。Z可用下面的递推公式[1]计算:
,为第层的复传播系数;Z0i为第i层的特征阻抗;Zi为第i层顶面的波阻抗。由此可见,对于N层地电断面,视电阻率ρa可表示为关于信号周期及断面参数之间的函数,即
2.2 目标函数
所采用的目标函数为
3 一维MT反演
3.1 3层K型理论曲线反演
表1给出了大地电磁测深3层理论模型参数及其实数编码混合遗传算法的搜索范围。取群体规模为100,交叉概率为0.2,变异概率为0.1,单纯形搜索概率为0.05,最大迭代次数为10(实际上只需要迭代1次即可得到最优值),得到的反演结果(表1)非常理想。从图2也可以看出,理论模型的正演曲线和由反演所得模型的正演曲线重合。
图2 3层(K型)理论视电阻率及相位曲线和
混合遗传算法反演的电阻率曲线
Fig.2 Theoretical and calculated apparent resistivity and
phase curves by HGA inversion for three-layer models (K-type)
3.2 5层HKH型理论曲线反演
表2所示为广义逆算法和混合遗传算法对5层
表1 3层地电模型参数及反演结果
Table 1 Theoretical resistivity and thickness and inversion results for three-layer geo-electrical mosel(K-type)
表2 混合遗传算法和广义逆法对5层(HKH型)地电模型的反演结果
Table 2 Inversion results of HGA and generalized method for five-layer models (HKH-type)
HKH型理论数据反演的结果。可见,广义逆反演的结果也接近真实模型,但结果的好坏与初始模型的选取有关,混合遗传算法反演的结果与真实模型完全吻合并且不依赖于初始模型的选取。
4 结 论
a. 实数编码混合遗传算法是一种非线性优化方法,它既具有遗传算法的全局收敛性,又具有单纯形算法的快速收敛性。
b. 通过对复杂函数的优化求解和大地电磁测深一维理论模型的反演计算结果表明,实数编码混合遗传算法是一种比较实用的非线性反演方法,它可以较快地逼近全局最优解。
c. 实数编码混合遗传算法是在解空间进行高效启发式搜索,因此,计算速度较快。
d. 在反演大地电磁测深资料时,由于反演过程中需要经过反复正演计算,因此,必须改进正演算法,从而节省混合遗传算法搜索到全局最优解的时间。
参考文献:
[1] 陈乐寿, 刘 任, 王天生. 大地电磁测深资料处理与解释[M]. 北京: 石油工业出版社, 1989: 80-109.
CHEN Le-shou, LIU Ren, WANG Tian-sheng. The magnetotelluric sounding data processing and interpretation methods [M]. Beijing: Petroleum Industry Press, 1989: 80-109.
[2] Parker R L, Booker J R. Optimal one-dimensional inversion and bounding of magnetitelluric apparent resistivity and phase measurement[J]. Phys Earth Planet Int, 1996, 98: 269-282.
[3] Weaver J T, Angarwal A K. Automatic 1-D interpretation of magnetotelluric data by the method of modeling[J]. Geophys J Int, 1993, 112: 115-123.
[4] Constable S C, Parker R L, Constable C G.. Occam’s inversion: A practical algorithm for generating smooth models from electromagnetic sounding data[J]. Geophysics, 1987, 52(3): 289-300.
[5] Holland J H. Adaptation in natural and artificial systems[M]. Cambridge: MIT Press, 1992.
[6] Michalewicz Z. Genetic algorithms+dara structures=evolution programs[M]. Berlin: Springer-Verlag Berlin Heidelberg, 1996.
[7] 罗润林, 张小路. 电阻率测深数据的遗传算法和最小二乘法反演[J]. 桂林工学院学报, 2004, 24(2): 152-154.
LUO Run-lin, ZHANG Xiao-lu. Inversion of GA and least square for resistivity sounding data[J]. Journal of Guilin University of Technology, 2004, 24(2): 152-154.
[8] 姚 姚. 用非线性遗传反演算法进行自动校正[J]. 地球科学, 1992, 21(1): 89-92.
YAO Yao. Automatic static correction by nonlinear genetic inverse method[J]. Earth Science, 1992, 21(1): 89-92.
[9] 赵改善. 求解非线性最优化问题的遗传算法[J]. 地球物理学进展, 1992, 7(1): 90-97.
ZHAO Gai-shan. Nonlinear optimization using genetic algorithms[J]. Progress in Geophysics, 1992, 7(1): 90-97.
[10] 石耀森, 金 文. 面波频散反演地球内部构造遗传算法[J]. 地球物理学报, 1995, 21(1): 189-198.
SHI Yao-sen, JIN Wen. Genetic algorithms inversion of lithospheric structure from surface wave dispersion[J]. Chinese J Geophysics, 1995, 21(1): 189-198.
[11] Sen M K, Stoffa P L. Rapid sampling of model space using genetic algorithms: examples from seismic waveform inversion[J]. Geophys J Int, 1992, 108(1): 281-292.
[12] Goldberg D E. Real-code genetic algorithm[J]. Complex Systems, 1991, 5: 139-167.
[13] 张小贵, 方 浩, 戴冠中. 遗传算法的编码机制研究[J]. 信息与控制, 1997, 26(2): 134-139.
ZHANG Xiao-gui, FANG Hao, DAI Guan-zhong. Studies on encoding mechanism of genetic algorithms[J]. Information and Control, 1997, 26(2): 134-139.
[14] Schwefel H P. Numerical optimization of computer models[M]. Chichester: John Wiley and Sons, 1981.
收稿日期:2006-08-24
基金项目:国家“863”高技术项目(863-820-03-04);国家自然科学基金资助项目(60672042)
作者简介:柳建新(1962-),男,湖南岳阳人,博士,教授,博士生导师,从事大地电磁理论研究
通讯作者:童孝忠,男,博士研究生;电话:13469439855;E-mail: csumaysnow@126.com