遗传算法在微动反演中的应用与研究

  • 投稿止水
  • 更新时间2015-09-23
  • 阅读量947次
  • 评分4
  • 60
  • 0

王鹏飞

(桂林电子科技大学信息与通信学院,广西 桂林 541004)

【摘 要】微动勘探近年来备受关注。针对遗传算法在微动反演中收敛速度慢和早熟的缺点,改进了原有适应值函数,并引入变异算子,从而优化了遗传算法,并通过实验验证优化后的遗传算法在微动反演计算中提高了反演精度。

教育期刊网 http://www.jyqkw.com
关键词 云微动;遗传算法;变异算子;适应值函数

0 引言

微动指来自于地表和底下深处的随机振动源引起的振幅非常小的地面微弱振动。包括人类等人工源引起的短周期震动和海浪及地球内部活动等自然力引起的长周期震动。

微动探测的主要方法有空间自相关法(SAC)[1]和频率-波数法(F-K)[2]两种。本文研究的是基于空间自相关法的微动勘探反演算法中遗传算法的应用于优化。

遗传算法( Genetic Algorithms ,简称GA)[3]是一种基于生物自然选择与遗传机理的随机搜索与优化方法,是由美国Michigan 大学的John Holland 教授创建的。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说,其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。它本身不仅具有极强的鲁棒性,还隐含着并行性,同时还具有全局寻优能力。因此,从一定意义上说,遗传算法是一种普遍适用于各种问题的简单而有效的搜索方法。

1 遗传算法优化研究

1.1 遗传算法基本原理

基本遗传算法有五大要素构成:参数的编码方式、初始种群规模的设定、适应度函数的设计方法、各种遗传算子的设计和控制参数的设定,他们组成了遗传算法的核心内容。[4]

(1)编码:遗传算法不能直接处理问题空间的参数,必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码。

(2)个体适应度:在遗传算法中,搜索进化的过程是根据评估函数值来对每个个体进行优劣评估的,这个过程不需要其他外部信息作为参考。这里的评估函数值就是适应度。

(3)算子;遗传操作中算子主要包括:选择算子、交叉算子以及变异算子三种类型。

(4)控制参数:遗传算法中有其运行的基本参数被称作操作参数,在研究优化问题之前必须提前设定这些参数。主要的参数有4种:

N:种群规模,即种群中个体的数量

T:算法停止条件,即种群进化代数

Pc:交叉概率

Pm:变异概率

遗传算法实质上是一种以群体和遗传操作为基础进行繁衍、监测和评价的迭代算法。在搜索之前,将问题的解映射为一个解集空间,解集空间是由一定数量的二进制个体组成的种群,以这些代表问题假设解的种群开始,我们要解决的一个问题就是根据问题的目标函数构造一个适应度函数,以适应度函数为依据,对种群中的个体进行评估,从一大堆数据中寻找一个解。图1为遗传算法的流程图。

1.2 遗传算法优化研究

凭借遗传算法具备的非线性全局优化的能力,它已经被广发的应用到了诸多领域中,在微动面波反演的研究中也引入了此方法。但是在解决反演问题的过程中也暴露了一些不足之处,首先标准遗传算法的计算过程中有早熟收敛[5]的现象,这一现象致使算法全局寻优的优良性能不能完全显示出来,其次遗传算法的收敛速度相比于其他传统算法比较慢,效率低。因此,针对以上暴露的不足,本文从四个方面入手,提出了遗传算法的优化策略,具体的策略实施过程如下:

(1)自适应函数的优化

在遗传算法中目标函数通常会作为评估函数值即适应性函数,在遗传进化中,超级个体可能会在群体中出现,就是适应值比群体平均值大很多的个体,如果根据适应值的比例选择时,这类超级个体就会占有群体中的绝对比例,这样算法在运算时就会过早的收敛于一个局部最优值,这就是所说的早熟现象。下面通过引进一种线性变换来使原有适应性函数得到改变,避免早熟收敛的发生。这里设f为已有的适应值函数,F为改变的适应值函数用线性组合F=af+b表示。并设定

Fmax=kfmax+b:Favg=favg(1)

公式(1)中k为一个固定的增量系数。

由上式得:

a=(k-1)favg/(fmax-favg)

b=-favg(fmax-kfavg)/(fmax-favg)(2)

原有适应度经过线性的变换之后他们之间的差距得到了调整,群体内多样性的个体得到了保证,而且这个方法简便计算,容易实现。

(2)选择策略的优化

利用最优保存和赌轮[6]选择两种方式相结合的策略作为选择的方法。在群体中首先找到适应值最佳和最差的个体,把最差的个体用最佳个体替换,然后允许最佳的两个个体不经过交叉编译而进入下一代,剩下的个体按正常进行排列,最后再进行赌轮选择,这样群体中平均适应值不断得到提高,而且还使最佳个体的适应值不再减小。

(3)变异策略的优化

在标准遗传算法中,群体中单一性的产生有一部分原因是近亲繁殖造成的,因此为了避免这类事件的发生,可以让父母 A,B 多次交叉变异,在产生的不同的多个个体中筛选出最佳个体放入子代中,对上述步骤反复执行,直到子个体数量得到满足。

(4)遗传操作算子的优化

遗传算法有收敛过早的缺点,这一缺点是由于同位基因数目不同概率不等,在进化中某些特定基因越来越少,造成基因缺失,致使收敛过早。针对这一现象,本文引入多元算子到遗传算法中来。例如对二元字符串结构进行变异,通过同或异或的运算保留了特定基因的多样性,极大地避免了收敛过早的问题。例如:

10011010 同或后 10111100

11011001 异或后 01000011

经过同或异或后两种逻辑状态必定互补。

根据以上优化策略优化后的遗传算法执行顺序如下:

①子群体的个数要首先确定,对子群体初始化,子群体每个的规模是 N,进一步对重新分配的子群体确定进化代数;

②根据规则 1,把各子群体的父代适应值求解;

③对各个子群进行选择操作;

④获取各子群体繁殖的下一代,变异的规则采用二元变异;

⑤查看终止条件是否满足,如过满足,就退出;

⑥如果进化代数满足了重新分配子群体的数量,就开始对子群体重新分配;

⑦回到②。

1.3 实验测试

遗传算法的随机优化计算的特点,使其受参数的影响很大,参数的不同会使算法对问题的计算产生不同的影响,恰当的参数可以加速算法早熟收敛,相反不合适的参数会致使遗传算法收敛变慢,因此使得计算后无法寻得最优解。然而确定选取什么样的参数目前还没有有效的解决办法。本节从两个不同的方面对优化后的遗传算法进行了测试,验证优化后的效果和其对参数的敏感度。实验所用函数为

遗传算法对比实验

将遗传算法同优化后的遗传算法进行对比。种群规模设为100,交叉概率0.72,变异概率0.15。实验结果如下表。

通过以上实验,可以看出,优化后的遗传算法增强了自身的寻优能力,减少了迭代次数,明显改善了早熟收敛的情况,另外优化后的算法参数的选择范围扩大,参数的选择对算法的影响减小了,使得算法能够更方便的在实际中应用。

微动反演中遗传算法的实际应用与优化。

选择表 2 中的模型进行反演,理论数据根据 knoppoff 算法的速度递增层模型正演计算得到理论频散曲线。

层状介质微动面波速度反演中反演参数是横波速度VS以及厚度d。纵波速度VP通过下面关于横波速度VS与泊松比μ关系的公式计算:

密度ρ根据纵波速度和密度的统计关系得到。因此实际反演中只对各层的横波速度和层厚度参数反演。因此,输入参数为各层横波速度和层厚度的上下限。 算法目标函数计算式为

式中是第i个频点上观测的微动面波速度,是每代在确定模型参数后,计算得到的同一频点的微动面波速度值,N 是频点的个数,每次迭代时的每个个体是 F,就是模型的参数。

反演结果(表 2 所示)就是获得一组模型的参数,此组模型参数让上式表述的目标数取值达到最小。所以,这里就是求解目标函数的最小值。从表 2 中可以看到优化后的遗传算都各参数的反演结果的相对误差均优于标准遗传算法,各层的相对误差均不超过 10%。 结合实际,进行多次的试算,具体采用以下参数:种群大小为 40-60 个,遗传代数为 160 代;交叉概率为Pc1=0.92,Pc2=0.75,Pc3=0.6,遗传概率Pm1=0.1,Pm2=0.09,Pm3=0.01。

由表 2 和图2 所示可以看出,优化的遗传算法反演结果的相对误差均低于标准遗传算法。从图 3 和 4 中可知,两种方法一般在 40-60 代就得到最佳解,其中优化的遗传算法反演 1 的收敛速度最快,约在第 25 代即获得最佳解的。优化的算法运算速度比标准算法提升了2个数量级。

2 小结

本文通过对适应值函数的改进和变异算子的引入,优化了遗传算法,有效地抑制了遗传算法收敛过快早熟的缺陷,并将优化后的遗传算法应用与微动反演中,提高了反演精度。

教育期刊网 http://www.jyqkw.com
参考文献

[1]徐佩芬,李世豪,凌甦群,郭慧丽,田宝卿.利用SPAC法估算地壳S波速度结构[J].地球物理学报,2013,56(11):3846-3854.

[2]丁连靖,冉伟彦.天然源面波频率-波数法的应用[J].物探与化探,2005.2:183-141.

[3]孙栩,王福林,文士发.遗传算法的一种改进进化策略[J].数学的实践与认识,2014(9).

[4]弥宝福.遗传算法进化策略的改进研究[D].东北农业大学,2014.

[5]付旭辉,康玲.华中科技大学水电与数字化工程学院.遗传算法的早熟问题探究[J].华中科技大学学报:自然科学版,2003,31(7):53-54.

[6]周涛.基于改进遗传算法的TSP问题研究[J].微电子学与计算机,2006:104-106.

[7]周国法.具有空间自相关残差的回归模型及其应用[J].生物数学学报,1997,12(2):158-163.

[8]彭志勇,邓世权.遗传算法的研究及应用[J].计算机光盘软件与应用,2013:109-110.

[9]宋建萍.函数优化的遗传算法代码实现[J].软件导刊,2013,20(2):40-42.

[10]刘国华,包宏,李文超.用 MATLAB 实现遗传算法程序[J].计算机应用研究,2001,18(8):80-82.

[11]蒋冬初,何飞,向继文.遗传算法求解函数优化问题的 Matlab 实现[J].吉首大学学报:自然科学版,2005,26(2).

[12]杨启文,蒋静坪,张国宏.遗传算法优化速度的改进[J].软件学报,2001,12(2):270-275.

[13]Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. Evolutionary Computation, IEEE Transactions on, 2002,6(2):182-197.

[14]Zhang W, Gen M, Jo J. Hybrid sampling strategy-based multiobjective evolutionary algorithm for process planning and scheduling problem[J]. Journal of Intelligent Manufacturing, 2014,25(5):881-897.

[15]Gen M, Lin L. Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey[J]. Journal of Intelligent Manufacturing, 2014,25(5):849-866.

[责任编辑:汤静]