遺傳算法在微動(dòng)反演中的應(yīng)用與研究.doc

遺傳算法在微動(dòng)反演中的應(yīng)用與研究 王鵬飛 （桂林電子科技大學(xué)信息與通信學(xué)院，廣西桂林541004） 【摘要】微動(dòng)勘探近年來(lái)備受關(guān)注。針對(duì)遺傳算法在微動(dòng)反演中收斂速度慢和早熟的缺點(diǎn)，改進(jìn)了原有適應(yīng)值函數(shù)，并引入變異算子，從而優(yōu)化了遺傳算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證優(yōu)化后的遺傳算法在微動(dòng)反演計(jì)算中提高了反演精度。 關(guān)鍵詞云微動(dòng)；遺傳算法；變異算子；適應(yīng)值函數(shù) 0引言 微動(dòng)指于地表和底下深處的隨機(jī)振動(dòng)源引起的振幅非常小的地面微弱振動(dòng)。包括人類等人工源引起的短周期震動(dòng)和海浪及地球內(nèi)部活動(dòng)等自然力引起的長(zhǎng)周期震動(dòng)。 微動(dòng)探測(cè)的主要方法有空間自相關(guān)法（SAC）1和頻率-波數(shù)法（F-K）2兩種。本文研究的是基于空間自相關(guān)法的微動(dòng)勘探反演算法中遺傳算法的應(yīng)用于優(yōu)化。 遺傳算法(GeicAlgorithms,簡(jiǎn)稱GA)3是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索與優(yōu)化方法,是由美國(guó)Michigan大學(xué)的JohnHolland教授創(chuàng)建的。它達(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 （）編碼：遺傳算法不能直接處理問(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）算子；遺傳操作中算子主要包括：選擇算子、交叉算子以及變異算子三種類型。 （4）控制參數(shù)：遺傳算法中有其運(yùn)行的基本參數(shù)被稱作操作參數(shù)，在研究?jī)?yōu)化問(wèn)題之前必須提前設(shè)定這些參數(shù)。主要的參數(shù)有4種： N：種群規(guī)模，即種群中個(gè)體的數(shù)量 T：算法停止條件，即種群進(jìn)化代數(shù) Pc：交叉概率 Pm：變異概率 遺傳算法實(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)化研究 憑借遺傳算法具備的非線性全局優(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í)，這類超級(jí)個(gè)體就會(huì)占有群體中的絕對(duì)比例，這樣算法在運(yùn)算時(shí)就會(huì)過(guò)早的收斂于一個(gè)局部最優(yōu)值，這就是所說(shuō)的早熟現(xiàn)象。下面通過(guò)引進(jìn)一種線性變換來(lái)使原有適應(yīng)性函數(shù)得到改變，避免早熟收斂的發(fā)生。這里設(shè)f為已有的適應(yīng)值函數(shù)，F(xiàn)為改變的適應(yīng)值函數(shù)用線性組合F=af+b表示。并設(shè)定 Fmax=kfmax+b：Favg=favg（1） 公式（1）中k為一個(gè)固定的增量系數(shù)。 由上式得： a=（k-1）favg/（fmax-favg） b=-favg（fmax-kfavg）/（fmax-favg）（2） 原有適應(yīng)度經(jīng)過(guò)線性的變換之后他們之間的差距得到了調(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)生有一部分原因是近親繁殖造成的，因此為了避免這類事件的發(fā)生，可以讓父母A,B多次交叉變異，在產(chǎn)生的不同的多個(gè)個(gè)體中篩選出最佳個(gè)體放入子代中，對(duì)上述步驟反復(fù)執(zhí)行，直到子個(gè)體數(shù)量得到滿足。 （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)化策略優(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ī)則采用二元變異； 查看終止條件是否滿足,如過(guò)滿足,就退出； 如果進(jìn)化代數(shù)滿足了重新分配子群體的數(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é)果如下表。 通過(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ì)算得到理論頻散曲線。 層狀介質(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ì)算式為 反演結(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所示可以看出，優(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é) 本文通過(guò)對(duì)適應(yīng)值函數(shù)的改進(jìn)和變異算子的引入，優(yōu)化了遺傳算法，有效地抑制了遺傳算法收斂過(guò)快早熟的缺陷，并將優(yōu)化后的遺傳算法應(yīng)用與微動(dòng)反演中，提高了反演精度。 參考文獻(xiàn) 徐佩芬,李世豪,凌甦群,郭慧麗,田寶卿.利用SPAC法估算地殼S波速度結(jié)構(gòu)J.地球物理學(xué)報(bào),xx,56(11):3846-3854. 丁連靖,冉偉彥.天然源面波頻率-波數(shù)法的應(yīng)用J.物探與化探,xx.2:183-141. 孫栩,王福林,文士發(fā).遺傳算法的一種改進(jìn)進(jìn)化策略J.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),xx(9). 彌寶福.遺傳算法進(jìn)化策略的改進(jìn)研究D.東北農(nóng)業(yè)大學(xué),xx. 付旭輝,康玲.華中科技大學(xué)水電與數(shù)字化工程學(xué)院.遺傳算法的早熟問(wèn)題探究J.華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,xx,31(7):53-54. 周濤.基于改進(jìn)遺傳算法的TSP問(wèn)題研究J.微電子學(xué)與計(jì)算機(jī),xx:104-106. 周國(guó)法.具有空間自相關(guān)殘差的回歸模型及其應(yīng)用J.生物數(shù)學(xué)學(xué)報(bào),1997,12(2):158-163. 彭志勇,鄧世權(quán).遺傳算法的研究及應(yīng)用J.計(jì)算機(jī)光盤(pán)軟件與應(yīng)用,xx:109-110. 宋建萍.函數(shù)優(yōu)化的遺傳算法代碼實(shí)現(xiàn)J.軟件導(dǎo)刊,xx,20(2):40-42. 劉國(guó)華,包宏,李文超.用MATLAB實(shí)現(xiàn)遺傳算法程序J.計(jì)算機(jī)應(yīng)用研究,xx,18(8):80-82. 蔣冬初,何飛,向繼文.遺傳算法求解函數(shù)優(yōu)化問(wèn)題的Matlab實(shí)現(xiàn)J.吉首大學(xué)學(xué)報(bào):自然科學(xué)版,xx,26(2). 楊啟文,蔣靜坪,張國(guó)宏.遺傳算法優(yōu)化速度的改進(jìn)J.軟件學(xué)報(bào),xx,12(2):270-275. DebK,PratapA,AgarwalS,etal.Afastandelitistmultiobjectivegeicalgorithm:NSGA-IIJ.EvolutionaryComputation,IEEETransactionson,xx,6(2):182-197. ZhangW,GenM,JoJ.Hybridsamplingstrategy-basedmultiobjectiveevolutionaryalgorithmforprocessplanningandschedulingproblemJ.JournalofIntelligentManufacturing,xx,25(5):881-897. GenM,LinL.Multiobjectiveevolu