王鵬飛

（桂林電子科技大學(xué)信息與通信學(xué)院，廣西 桂林541004）

0 引言

微動(dòng)指來(lái)自于地表和底下深處的隨機(jī)振動(dòng)源引起的振幅非常小的地面微弱振動(dòng)。包括人類(lèi)等人工源引起的短周期震動(dòng)和海浪及地球內(nèi)部活動(dòng)等自然力引起的長(zhǎng)周期震動(dòng)。

微動(dòng)探測(cè)的主要方法有空間自相關(guān)法（SAC）[1]和頻率-波數(shù)法（FK）[2]兩種。本文研究的是基于空間自相關(guān)法的微動(dòng)勘探反演算法中遺傳算法的應(yīng)用于優(yōu)化。

遺傳算法(Genetic Algorithms,簡(jiǎn)稱(chēng)GA)[3]是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索與優(yōu)化方法,是由美國(guó)Michigan大學(xué)的John Holland教授創(chuàng)建的。它來(lái)源于達(dá)爾文的進(jìn)化論、魏茨曼的物種選擇學(xué)說(shuō)和孟德?tīng)柕娜后w遺傳學(xué)說(shuō),其基本思想是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種過(guò)程搜索最優(yōu)解的算法。它本身不僅具有極強(qiáng)的魯棒性,還隱含著并行性,同時(shí)還具有全局尋優(yōu)能力。因此,從一定意義上說(shuō),遺傳算法是一種普遍適用于各種問(wèn)題的簡(jiǎn)單而有效的搜索方法。

1 遺傳算法優(yōu)化研究

1.1 遺傳算法基本原理

基本遺傳算法有五大要素構(gòu)成：參數(shù)的編碼方式、初始種群規(guī)模的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)方法、各種遺傳算子的設(shè)計(jì)和控制參數(shù)的設(shè)定，他們組成了遺傳算法的核心內(nèi)容。[4]

（1）編碼：遺傳算法不能直接處理問(wèn)題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體。這一轉(zhuǎn)換操作就叫做編碼。

（2）個(gè)體適應(yīng)度：在遺傳算法中，搜索進(jìn)化的過(guò)程是根據(jù)評(píng)估函數(shù)值來(lái)對(duì)每個(gè)個(gè)體進(jìn)行優(yōu)劣評(píng)估的，這個(gè)過(guò)程不需要其他外部信息作為參考。這里的評(píng)估函數(shù)值就是適應(yīng)度。

（3）算子；遺傳操作中算子主要包括：選擇算子、交叉算子以及變異算子三種類(lèi)型。

（4）控制參數(shù)：遺傳算法中有其運(yùn)行的基本參數(shù)被稱(chēng)作操作參數(shù)，在研究?jī)?yōu)化問(wèn)題之前必須提前設(shè)定這些參數(shù)。主要的參數(shù)有4種：

N：種群規(guī)模，即種群中個(gè)體的數(shù)量

T：算法停止條件，即種群進(jìn)化代數(shù)

Pc：交叉概率

Pm：變異概率

圖1 標(biāo)準(zhǔn)遺傳算法流程圖

遺傳算法實(shí)質(zhì)上是一種以群體和遺傳操作為基礎(chǔ)進(jìn)行繁衍、監(jiān)測(cè)和評(píng)價(jià)的迭代算法。在搜索之前，將問(wèn)題的解映射為一個(gè)解集空間，解集空間是由一定數(shù)量的二進(jìn)制個(gè)體組成的種群，以這些代表問(wèn)題假設(shè)解的種群開(kāi)始，我們要解決的一個(gè)問(wèn)題就是根據(jù)問(wèn)題的目標(biāo)函數(shù)構(gòu)造一個(gè)適應(yīng)度函數(shù)，以適應(yīng)度函數(shù)為依據(jù)，對(duì)種群中的個(gè)體進(jìn)行評(píng)估，從一大堆數(shù)據(jù)中尋找一個(gè)解。圖1為遺傳算法的流程圖。

1.2 遺傳算法優(yōu)化研究

憑借遺傳算法具備的非線(xiàn)性全局優(yōu)化的能力，它已經(jīng)被廣發(fā)的應(yīng)用到了諸多領(lǐng)域中，在微動(dòng)面波反演的研究中也引入了此方法。但是在解決反演問(wèn)題的過(guò)程中也暴露了一些不足之處，首先標(biāo)準(zhǔn)遺傳算法的計(jì)算過(guò)程中有早熟收斂[5]的現(xiàn)象，這一現(xiàn)象致使算法全局尋優(yōu)的優(yōu)良性能不能完全顯示出來(lái)，其次遺傳算法的收斂速度相比于其他傳統(tǒng)算法比較慢，效率低。因此，針對(duì)以上暴露的不足，本文從四個(gè)方面入手，提出了遺傳算法的優(yōu)化策略，具體的策略實(shí)施過(guò)程如下：

（1）自適應(yīng)函數(shù)的優(yōu)化

在遺傳算法中目標(biāo)函數(shù)通常會(huì)作為評(píng)估函數(shù)值即適應(yīng)性函數(shù)，在遺傳進(jìn)化中，超級(jí)個(gè)體可能會(huì)在群體中出現(xiàn)，就是適應(yīng)值比群體平均值大很多的個(gè)體，如果根據(jù)適應(yīng)值的比例選擇時(shí)，這類(lèi)超級(jí)個(gè)體就會(huì)占有群體中的絕對(duì)比例，這樣算法在運(yùn)算時(shí)就會(huì)過(guò)早的收斂于一個(gè)局部最優(yōu)值，這就是所說(shuō)的早熟現(xiàn)象。下面通過(guò)引進(jìn)一種線(xiàn)性變換來(lái)使原有適應(yīng)性函數(shù)得到改變，避免早熟收斂的發(fā)生。這里設(shè)f為已有的適應(yīng)值函數(shù)，F(xiàn)為改變的適應(yīng)值函數(shù)用線(xiàn)性組合F=af+b表示。并設(shè)定

公式（1）中k為一個(gè)固定的增量系數(shù)。

由上式得：

原有適應(yīng)度經(jīng)過(guò)線(xiàn)性的變換之后他們之間的差距得到了調(diào)整，群體內(nèi)多樣性的個(gè)體得到了保證，而且這個(gè)方法簡(jiǎn)便計(jì)算，容易實(shí)現(xiàn)。

（2）選擇策略的優(yōu)化

利用最優(yōu)保存和賭輪[6]選擇兩種方式相結(jié)合的策略作為選擇的方法。在群體中首先找到適應(yīng)值最佳和最差的個(gè)體，把最差的個(gè)體用最佳個(gè)體替換，然后允許最佳的兩個(gè)個(gè)體不經(jīng)過(guò)交叉編譯而進(jìn)入下一代，剩下的個(gè)體按正常進(jìn)行排列，最后再進(jìn)行賭輪選擇，這樣群體中平均適應(yīng)值不斷得到提高，而且還使最佳個(gè)體的適應(yīng)值不再減小。

（3）變異策略的優(yōu)化

在標(biāo)準(zhǔn)遺傳算法中，群體中單一性的產(chǎn)生有一部分原因是近親繁殖造成的，因此為了避免這類(lèi)事件的發(fā)生，可以讓父母A,B多次交叉變異，在產(chǎn)生的不同的多個(gè)個(gè)體中篩選出最佳個(gè)體放入子代中，對(duì)上述步驟反復(fù)執(zhí)行，直到子個(gè)體數(shù)量得到滿(mǎn)足。

（4）遺傳操作算子的優(yōu)化

遺傳算法有收斂過(guò)早的缺點(diǎn)，這一缺點(diǎn)是由于同位基因數(shù)目不同概率不等，在進(jìn)化中某些特定基因越來(lái)越少，造成基因缺失，致使收斂過(guò)早。針對(duì)這一現(xiàn)象，本文引入多元算子到遺傳算法中來(lái)。例如對(duì)二元字符串結(jié)構(gòu)進(jìn)行變異，通過(guò)同或異或的運(yùn)算保留了特定基因的多樣性，極大地避免了收斂過(guò)早的問(wèn)題。例如：

10011010 同或后 10111100

11011001 異或后 01000011

經(jīng)過(guò)同或異或后兩種邏輯狀態(tài)必定互補(bǔ)。

根據(jù)以上優(yōu)化策略?xún)?yōu)化后的遺傳算法執(zhí)行順序如下：

①子群體的個(gè)數(shù)要首先確定,對(duì)子群體初始化,子群體每個(gè)的規(guī)模是N,進(jìn)一步對(duì)重新分配的子群體確定進(jìn)化代數(shù)；

②根據(jù)規(guī)則1，把各子群體的父代適應(yīng)值求解；

③對(duì)各個(gè)子群進(jìn)行選擇操作；

④獲取各子群體繁殖的下一代,變異的規(guī)則采用二元變異；

⑤查看終止條件是否滿(mǎn)足,如過(guò)滿(mǎn)足,就退出；

⑥如果進(jìn)化代數(shù)滿(mǎn)足了重新分配子群體的數(shù)量,就開(kāi)始對(duì)子群體重新分配；

⑦回到②。

1.3 實(shí)驗(yàn)測(cè)試

遺傳算法的隨機(jī)優(yōu)化計(jì)算的特點(diǎn)，使其受參數(shù)的影響很大，參數(shù)的不同會(huì)使算法對(duì)問(wèn)題的計(jì)算產(chǎn)生不同的影響，恰當(dāng)?shù)膮?shù)可以加速算法早熟收斂，相反不合適的參數(shù)會(huì)致使遺傳算法收斂變慢，因此使得計(jì)算后無(wú)法尋得最優(yōu)解。然而確定選取什么樣的參數(shù)目前還沒(méi)有有效的解決辦法。本節(jié)從兩個(gè)不同的方面對(duì)優(yōu)化后的遺傳算法進(jìn)行了測(cè)試，驗(yàn)證優(yōu)化后的效果和其對(duì)參數(shù)的敏感度。實(shí)驗(yàn)所用函數(shù)為

遺傳算法對(duì)比實(shí)驗(yàn)

將遺傳算法同優(yōu)化后的遺傳算法進(jìn)行對(duì)比。種群規(guī)模設(shè)為100，交叉概率0.72，變異概率0.15。實(shí)驗(yàn)結(jié)果如下表。

表1 實(shí)驗(yàn)結(jié)果

通過(guò)以上實(shí)驗(yàn)，可以看出，優(yōu)化后的遺傳算法增強(qiáng)了自身的尋優(yōu)能力，減少了迭代次數(shù)，明顯改善了早熟收斂的情況，另外優(yōu)化后的算法參數(shù)的選擇范圍擴(kuò)大，參數(shù)的選擇對(duì)算法的影響減小了，使得算法能夠更方便的在實(shí)際中應(yīng)用。

微動(dòng)反演中遺傳算法的實(shí)際應(yīng)用與優(yōu)化。

選擇表2中的模型進(jìn)行反演，理論數(shù)據(jù)根據(jù)knoppoff算法的速度遞增層模型正演計(jì)算得到理論頻散曲線(xiàn)。

層狀介質(zhì)微動(dòng)面波速度反演中反演參數(shù)是橫波速度VS以及厚度d?？v波速度VP通過(guò)下面關(guān)于橫波速度VS與泊松比μ關(guān)系的公式計(jì)算：

密度ρ根據(jù)縱波速度和密度的統(tǒng)計(jì)關(guān)系得到。因此實(shí)際反演中只對(duì)各層的橫波速度和層厚度參數(shù)反演。因此，輸入?yún)?shù)為各層橫波速度和層厚度的上下限。 算法目標(biāo)函數(shù)計(jì)算式為

式中Viobs是第i個(gè)頻點(diǎn)上觀測(cè)的微動(dòng)面波速度，Vithe是每代在確定模型參數(shù)后，計(jì)算得到的同一頻點(diǎn)的微動(dòng)面波速度值，N是頻點(diǎn)的個(gè)數(shù)，每次迭代時(shí)的每個(gè)個(gè)體是F，就是模型的參數(shù)。

反演結(jié)果（表2所示）就是獲得一組模型的參數(shù)，此組模型參數(shù)讓上式表述的目標(biāo)數(shù)取值達(dá)到最小。所以，這里就是求解目標(biāo)函數(shù)的最小值。從表2中可以看到優(yōu)化后的遺傳算都各參數(shù)的反演結(jié)果的相對(duì)誤差均優(yōu)于標(biāo)準(zhǔn)遺傳算法，各層的相對(duì)誤差均不超過(guò)10%。 結(jié)合實(shí)際，進(jìn)行多次的試算，具體采用以下參數(shù):種群大小為40-60個(gè)，遺傳代數(shù)為160代;交叉概率為Pc1=0.92，Pc2=0.75，Pc3=0.6，遺傳概率Pm1=0.1，Pm2=0.09，Pm3=0.01。

表2

由表2和圖2所示可以看出，優(yōu)化的遺傳算法反演結(jié)果的相對(duì)誤差均低于標(biāo)準(zhǔn)遺傳算法。從圖3和4中可知，兩種方法一般在40-60代就得到最佳解，其中優(yōu)化的遺傳算法反演1的收斂速度最快，約在第25代即獲得最佳解的。優(yōu)化的算法運(yùn)算速度比標(biāo)準(zhǔn)算法提升了2個(gè)數(shù)量級(jí)。

圖2 橫波速度反演結(jié)果對(duì)比

圖3 標(biāo)準(zhǔn)遺傳算法兩次反演的目標(biāo)函數(shù)值隨進(jìn)化代數(shù)的變化

圖4 優(yōu)化的遺傳算法兩次反演的目標(biāo)函數(shù)值隨進(jìn)化代數(shù)的變化

2 小結(jié)

本文通過(guò)對(duì)適應(yīng)值函數(shù)的改進(jìn)和變異算子的引入，優(yōu)化了遺傳算法，有效地抑制了遺傳算法收斂過(guò)快早熟的缺陷，并將優(yōu)化后的遺傳算法應(yīng)用與微動(dòng)反演中，提高了反演精度。

［1］徐佩芬,李世豪,凌甦群,郭慧麗,田寶卿.利用SPAC法估算地殼S波速度結(jié)構(gòu)[J].地球物理學(xué)報(bào),2013,56(11):3846-3854.

［2］丁連靖,冉偉彥.天然源面波頻率-波數(shù)法的應(yīng)用[J].物探與化探,2005.2:183-141.

［3］孫栩,王福林,文士發(fā).遺傳算法的一種改進(jìn)進(jìn)化策略[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2014(9).

［4］彌寶福.遺傳算法進(jìn)化策略的改進(jìn)研究[D].東北農(nóng)業(yè)大學(xué),2014.

［5］付旭輝,康玲.華中科技大學(xué)水電與數(shù)字化工程學(xué)院.遺傳算法的早熟問(wèn)題探究[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2003,31(7):53-54.

［6］周濤.基于改進(jìn)遺傳算法的TSP問(wèn)題研究[J].微電子學(xué)與計(jì)算機(jī),2006:104-106.

［7］周?chē)?guó)法.具有空間自相關(guān)殘差的回歸模型及其應(yīng)用[J].生物數(shù)學(xué)學(xué)報(bào),1997,12(2):158-163.

［8］彭志勇,鄧世權(quán).遺傳算法的研究及應(yīng)用[J].計(jì)算機(jī)光盤(pán)軟件與應(yīng)用,2013:109-110.

［9］宋建萍.函數(shù)優(yōu)化的遺傳算法代碼實(shí)現(xiàn)[J].軟件導(dǎo)刊,2013,20(2):40-42.

［10］劉國(guó)華,包宏,李文超.用MATLAB實(shí)現(xiàn)遺傳算法程序[J].計(jì)算機(jī)應(yīng)用研究,2001,18(8):80-82.

［11］蔣冬初,何飛,向繼文.遺傳算法求解函數(shù)優(yōu)化問(wèn)題的Matlab實(shí)現(xiàn)[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2005,26(2).

［12］楊啟文,蔣靜坪,張國(guó)宏.遺傳算法優(yōu)化速度的改進(jìn)[J].軟件學(xué)報(bào),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.