混合編碼遺傳算法及其在非線性反演中的應(yīng)用

1、混合編碼遺傳算法及其在非線性反演中的應(yīng)用核心提示：中文摘要：遺傳算法中編碼機制對交換和變異的搜索能力有重要影響.本文分析了二進(jìn)制與十進(jìn)制編碼的搜索特點,提出了混合編碼遺傳算法的技術(shù)構(gòu)想,并結(jié)合大變異技術(shù),有效地提高搜索及產(chǎn)生有效基因物質(zhì)的能力.論文結(jié)合地球物理反演問題的非線性特點,應(yīng)用混合編碼遺傳算法求解地球物理位場反演問題,取得了良好的效果. 目.中文摘要：遺傳算法中編碼機制對交換和變異的搜索能力有重要影響.本文分析了二進(jìn)制與十進(jìn)制編碼的搜索特點,提出了混合編碼遺傳算法的技術(shù)構(gòu)想,并結(jié)合大變異技術(shù),有效地提高搜索及產(chǎn)生有效基因物質(zhì)的能力.論文結(jié)合地球物理反演問題的非線性特點,應(yīng)用混合編碼遺傳

2、算法求解地球物理位場反演問題,取得了良好的效果. 目第五課題 (96 - 914 - 05) 、湖北省自然科學(xué)基金項目 (02065012) 及國土資源部礦產(chǎn)資源定量預(yù)測及勘查評價開放式重點實驗室研究基金項目 (MGMR2001 - 9)資助。陳超 ,副教授 ,長期從事地球物理數(shù)據(jù)處理及軟 件開發(fā)工作?；旌暇幋a遺傳算法及其在非線性反演中的應(yīng)用陳 超 陳家聯(lián) 余 豐 (中國地質(zhì)大學(xué)地球物理系武漢 430074) 摘 要 遺傳算法中編碼機制對交換和變異的搜索能力有重要影響。本文分析了二進(jìn)制與十進(jìn)制編碼的搜索特點 ,提出了混合 編碼遺傳算法的技術(shù)構(gòu)想 ,并結(jié)合大變異技術(shù) ,有效地提高搜索及產(chǎn)生有效基

3、因物質(zhì)的能力。論文結(jié)合地球物理反演問題的非線性特點 ,應(yīng)用混合編碼遺傳算法求解地球物理位場反演問題 ,取得了良好的效果。 關(guān)鍵詞 遺傳算法 混合編碼 反演 ( China University of Geosciences , Wuhan , 430074) 1 引 言 遺傳算法是模擬自然界生物進(jìn)化過程的搜索最優(yōu)解的方法 ,它問世于二十世紀(jì) 60 年代 ,由美國密西根大學(xué)的教授 J1H1Holland 和他的同事們首次提出。二十世紀(jì) 80 年代末 ,D.遺傳算法最顯著的能力是解決非線性最優(yōu)化問題 ,其特點可歸納為 :算法不是直接作用在參變量集上 ,而是利用參變量集的某種編碼 ;不是從單個點 ,

4、而是從一個點的群體開始搜索 ;僅利用適應(yīng)值信息 ,無需導(dǎo)數(shù)或其它輔助信息 ;利用概率轉(zhuǎn)移規(guī)則 ,而非確定性規(guī)則。地球科學(xué)中的許多問題屬非線性 ,尤其是地球物理反演問題 ,近年來國內(nèi)外學(xué)者們在不斷努力嘗試應(yīng)用遺傳算法求解地球物理反演問題 27 。但由于這些問題非線性程度高、情況復(fù)雜 ,如地球物理反演的多解性、地質(zhì)變量及參數(shù)分布和函數(shù)表達(dá)的不確定性等 ,傳統(tǒng) (或標(biāo)準(zhǔn)) 的遺傳算法在解決這些地學(xué)問題時往往不能取得預(yù)想的效果。另一方面 ,遺傳算法也存在自身的弱點 ,如“早熟”問題等。“早熟”是指群體過早地趨于局部最優(yōu)而不是全局最優(yōu) ,它是阻礙遺傳算法發(fā)展的一個最大障礙。此外 ,搜索效率低也是影響遺傳

5、算法應(yīng)用的一個主要問題。本文針對地球物理位場反演問題的特點 ,提出了混合編碼結(jié)合大概率變異技術(shù)的遺傳算法 ,在提高搜索效率方面 ,取得較好的效果。 2 編碼機制對遺傳算法搜索能力的影響 遺傳算法是利用參數(shù)編碼來進(jìn)行的 ,編碼是遺傳算法的基礎(chǔ)。通常用于遺傳算法的碼制有兩種 ,即二進(jìn)制和十進(jìn)制。關(guān)于二進(jìn)制編碼和十進(jìn)制編碼在搜索能力方面的特點 ,有不少學(xué)者做了許多理論上的探討 ,如文獻(xiàn) 1 對二進(jìn)制與十進(jìn)制編碼在搜索能力方面進(jìn)行了分析和模擬。這里我們首先回顧一下十進(jìn)制和二進(jìn)制的編碼過程。將十進(jìn)制參數(shù) z 表示成 z = zmin + k?,其中為分辨力 ,k 0 ,N為整數(shù)且 N = int (zm

6、ax - zmin) / ,這里 int ?表示取整數(shù)。編碼前要預(yù)先確定參數(shù)的定義域 zmin ,zmax 和分辨精度,參數(shù)由另一種量化形式即整數(shù) k 來表示。把由 m 個參數(shù)組成的個體視為一個基因串 ,其中每一個元素或基因均為十進(jìn)制整數(shù)。二進(jìn)制編 碼則需要預(yù)先確定編碼位長。對參數(shù) z a ,b ,若按位長 L 進(jìn) 2004 年 3 月 Computer Applications and Software Mar1 ,2004轉(zhuǎn)載行編碼 ,參數(shù)分辨力則為= int (b - a) / (2L - 1) ,z 的可能值為 z = a + k,k 0 ,1 , ?,2L - 1。把由 m 個參數(shù)組

7、成的個體視為各參數(shù)二進(jìn)制碼構(gòu)成的基因串 ,其中每一個元素或基因均為二進(jìn)制數(shù) (0 或 1) 。211 交換操作搜索能力分析對于十進(jìn)制編碼 ,假設(shè)群體中個體數(shù)目為 n ,xit 表示第 t 代的第 i 個個體 ,i (1 ,2 , ?,n) ,個體的基因數(shù)目 (串長) 為 m ,即有 m個整數(shù)構(gòu)成 ,xit Rm ,xit 可表示成 m維行向量 xit = xi (1)t ,xi (2)t?xi (m)t 。這樣第 t 代群體 Xt 可表示成一個 n m 階矩陣 Xt = x1t x2t ?xnt T。若初始群體 X0 = x10x20 ?xn0 T 中所在個體互異 , 即 : 0 xj0 i

8、j i ,j (1 ,2 , ?,n) (1) 且任意兩個個體的基因互異 ,即 : 0 xj (k)0 i j i ,j (1 ,2 , ?,n) k (1 ,2 , ?,m) (2) 交換所產(chǎn)生的新個體的集合 D 中的數(shù)目 TD 為 :對于二進(jìn)制編碼 ,假設(shè)上述問題中每個基因?qū)崝?shù)用 L 位二進(jìn)制數(shù)表示 ,每個個體 xit (BI) mL ,BI 0 ,1 ,這樣個體的基因數(shù)目 (串長)為 mL ,個體 xit 可表示為 mL 維的行向量 ,第 t 代群體為 B ,B 中個體的數(shù)目 TB ,則有 :可以證明1 ,當(dāng)交換分別在 L ,2L , ?, (m - 1) L 時 ,與十進(jìn)制碼交換位置相

9、同 ,可能的新個體數(shù)目與十進(jìn)制編碼相等 ,即體數(shù)的可能性將大于 TD。當(dāng) L 越大 ,群體規(guī)模 n 越大 ,TB 與 TD的差異就越大。新個體集合規(guī)模越大 ,交換操作的搜索能力越強?？梢?,就遺傳算法中占主導(dǎo)地位的交換操作而言 ,二進(jìn)制碼的交換操作比十進(jìn)制碼搜索能力強。遺傳算法的變異操作是針對個體基因串上某一位基因進(jìn)行的。在十進(jìn)制碼中 ,變異是對選定的基因 (整數(shù))進(jìn)行 (在其定義域內(nèi)隨機選出一個整數(shù)取代) ,顯然這種變異搜索可遍歷參數(shù)定義域全空間。在二進(jìn)制碼中 ,變異是對選定的基因 (0 或 1) 進(jìn)行 (取其反值代替) ,它只改變某一參數(shù)基因段中的某一位。對于 用位長為 L 的二進(jìn)制碼表示

10、的參數(shù) ,其可以有 2L 種不同的取值。由于二進(jìn)制碼決定了變異只改變碼串中 1 位 (在此僅討論單點變異問題) ,實際上變異后參數(shù)值的變化只有 L 種可能 ,僅占所有可取值的 L/ 2L ,與 L 位二進(jìn)制碼串所能表達(dá)數(shù)值的范圍差別甚遠(yuǎn) ,而且 L 越大 ,這種差別也越大。例如 ,對于 L = 4 的碼串 (1011) 2 = (11) 10 ,變異后可能的數(shù)為 4 個 ,即 (101 0) 2 = (10) 10 , (10 01) 2 = (9) 10 (1 111) 2 = (15) 10 , (0011) 2 = (3) 10 . 而該碼串所有可能的取值有 16 個 ,則變異搜索 率為

11、 (4/ 16) 100 % = 25 %。若 L = 8 ,變異搜索率僅為 3 %?？梢姸M(jìn)制碼的變異搜索存在較大的盲區(qū) ,其變異操作搜索能力是很有限的。 分析 對群體的部分個體進(jìn)行交換和變異操作是遺傳算法的精髓 ,群體在進(jìn)化過程中在不斷搜尋有效基因物質(zhì) (即最優(yōu)解的參數(shù)) ,當(dāng)群體不含某些有效基因物質(zhì)時 ,就要求遺傳過程能夠源源不斷地產(chǎn)生新的基因物質(zhì)。十進(jìn)制編碼的交換操作是在兩“個體”中的參數(shù)之間進(jìn)行 ,通過參數(shù)的交換形成兩個新“個體”,此過程中并不產(chǎn)生新參數(shù) ,如同兩個向量間元素交換而不產(chǎn)生新元素一樣 ,其產(chǎn)生新參數(shù)的概率為零。二進(jìn)制編碼的交換操作則是在兩“個體”的二進(jìn)制基因串之間進(jìn)行

12、,通過部分基因段的分割與互換 ,形成的兩個新“個體”,同時也可能 (具有較大概率) 產(chǎn)生出新的參數(shù)。對于變異操作 ,無論十進(jìn)制編碼還是二進(jìn)制編碼 ,總是能產(chǎn)生新物質(zhì)的 ,而十進(jìn)制編碼產(chǎn)生有效基因物質(zhì)的可能性要比二進(jìn)制編碼更大一些。二進(jìn)制編碼的交換操作具有較強的搜索能力 ,而十進(jìn)制編 碼變異操作的搜索范圍更大。若將兩者結(jié)合起來 ,把兩種編碼 機制引入算法進(jìn)行不同碼制的基因操作 ,顯然可改善遺傳算法的搜索性能。因此 ,我們提出了混合編碼遺傳算法 ( Hybrid En2混合編碼遺傳算法的基本要點在兩種編碼并行。HEGA 的實現(xiàn)過程是 ,首先對所有參數(shù)進(jìn)行二進(jìn)制編碼 ,形成個體基因串 (或稱染色體)

13、 。除進(jìn)行變異操作外 ,染色體始終保持二進(jìn)制碼 形式 ,所有其它基因操作均按二進(jìn)制碼進(jìn)行。當(dāng)某個參數(shù)所對應(yīng)的碼段被確定要進(jìn)行變異時 ,則先將該參數(shù)轉(zhuǎn)換成同精度的十進(jìn)制碼 ,然后對該基因進(jìn)行隨機變異。最后再將變異后的新 參數(shù)按同精度逆變?yōu)槎M(jìn)制碼。例如 ,假設(shè)某參數(shù)的二進(jìn)制碼 為 (1101101) 2 ,其十進(jìn)制數(shù)值為 (109) 10 ,從 0109 之間隨機挑選一個整數(shù) (假設(shè)) 52 作為變異后的參數(shù)值 ,然后將其轉(zhuǎn)換為二進(jìn)制碼 (0110100) 2 。從上面參數(shù)變異前后的二進(jìn)制碼結(jié)構(gòu)上看 ,在第 1、3、4、7位上都發(fā)生了變化 ,即一次十進(jìn)制碼變異操作相當(dāng)于四次二進(jìn)制碼變異操作。實現(xiàn)

14、參數(shù)的十進(jìn)制與二進(jìn)制互換的計算程序并不復(fù)雜 ,可通過位操作技術(shù)來實現(xiàn)11 。事實上 ,用十進(jìn)制編碼進(jìn)行變異時 ,對于某參數(shù)定義域內(nèi)一個確定的值來說 ,能被搜索到的概率并不高。因此 ,應(yīng)該考慮設(shè)置較大的變異概率或同一基因接受多次變異以產(chǎn)生更多新個體 ,保證新的有效基因物質(zhì)不斷涌現(xiàn)?；旌暇幋a遺傳算法的流程由圖 1 示。 圖 1 混合編碼遺傳算法流程 第 3 期 陳超等 :混合編碼遺傳算法及其在非線性反演中的應(yīng)用 17位場數(shù)據(jù)反演是地球物理反演問題的一個方面 ,其過程是將理論模型計算出的異常值與實測異常值相比較 ,根據(jù)其差異對模型參數(shù)進(jìn)行修改 ,如此反復(fù)迭代直到滿足要求為止 ,最終確定一個最佳地質(zhì)體

15、模型作為反演問題的解。這類問題一般具有非線性性質(zhì) ,傳統(tǒng)的做法是首先把它們轉(zhuǎn)化為線性問題 ,利用求解線性問題的方法去解非線性問題 ,如梯度法、最小二乘法、馬奎特法等。盡管非線性問題線性化是一條有效的途徑 ,但也帶來了許多的問題。首先 ,由于它是把非線性問題近似表達(dá)成一種線性形式 ,這種表達(dá)是有條件有范圍的 ;其次 ,對于多元非線性最優(yōu)化問題 ,線性方法有局限性 ,它屬于局部搜索而不是全局搜索 ,這將可能導(dǎo)致求解過程陷入局部極值不能自拔 ;再者 ,一般求解非線性最優(yōu)化問題都要涉及到目標(biāo)函數(shù)的高次偏導(dǎo)數(shù)計算 ,對于復(fù)雜形體問題無疑是十分困難的。這些問題不僅普遍存在 ,而且隨著問題的非線性程度的增高

16、而愈加嚴(yán)重。對于位場反演 ,通常把觀測值與計算值之均方差定義為目 標(biāo)函數(shù) ,為了保證有足夠的信息量 ,一般又是建立超定方程求 解 ,這將使所得到的解具有“圓滑”特征而又缺少分辨能力。另一方面 ,用線性化方法反演 ,其解的準(zhǔn)確程度與初值的好壞有 關(guān) ,初值不好 ,容易陷入局部極小 ,導(dǎo)致無法達(dá)到全局極小。用 遺傳算法求解位場反演問題的優(yōu)勢在于 :它具有全空間搜索能力 ,它不受觀測數(shù)據(jù)的限制 ;它屬于群體進(jìn)化或者說是多點搜索技術(shù) ,不會因個別解的停滯而停止搜索 ;它可以有效地避免陷入局部極值 ,一旦陷入也容易從中“爬”出來。合編碼遺傳算法策略多邊形截面水平柱體可以極好地擬合在走向方向上變化不大的地

17、質(zhì)體 ,如圖 2 所示 ,它是一個常用模擬地質(zhì)體的模型。方程 (5)給出了參數(shù)與異常值g 之間的數(shù)學(xué)關(guān)系 ,即 :g = 2G (xk + 1 - xk) 2 + (zk + 1 - zk) 2 + (xk + 1 - xk) tg - 1xk + 1) (5)式中 xk ,zk 為第 k 個角點的水平坐標(biāo)和垂直坐標(biāo) ,一般情況下這些坐標(biāo)為待求參數(shù)。其中 xn + 1 = x1 ,zn + 1 = z1 ,G為萬有引力常數(shù) ,為柱體剩余密度?？梢?,這是一個非線性程度較高的問題。值得注意的是 ,該反演問題在數(shù)學(xué)上屬于不適定問題 ,即方程 (5)左端異常值的微小變化會導(dǎo)致右端參數(shù)的劇烈振蕩。盡管

18、這不是我們在此所要討論的問題 ,但以此模型進(jìn)行試驗 ,有益于檢驗遺傳算法的能力。 圖 2 多邊形水平 柱體截面示意圖在下面的試驗中 ,我們根據(jù)重力異常數(shù)據(jù)反演求解坐標(biāo)參數(shù)。由于參數(shù)的定義域很大 ,為了保證有效地搜索 ,我們采用以下策略 :保證在計算的群體規(guī)模不變的前提下 ,采用動態(tài)編碼技術(shù) ,將進(jìn)化過程中群體較優(yōu)和較差個體之間的參數(shù)值作為調(diào)整定義域的依據(jù) ,逐步將搜索空間收縮到較優(yōu)的群體周圍。取交換操作概率為 Pc = 016018 ,采用多點交換 ,使群體 中的有效基因物質(zhì)充分實現(xiàn)交換。 自適應(yīng)調(diào)整變異操作概率 Pm = 0. 010. 3 ,采用十進(jìn)制 碼變異 ,參加變異的個體中 ,50

19、%為單次變異 ,50 %為多次變異 , 以提高搜索效率。按 Pt = 0. 010. 03 的概率對較優(yōu)個體直接復(fù)制到下一代。上述遺傳操作的父代和子代個體以同等概率進(jìn)入下一代群體的生存競爭 ,按優(yōu)勝劣汰原則 ,用適應(yīng)度輪盤的方法進(jìn)行篩選 ,保持群體規(guī)模不變。當(dāng)群體中最優(yōu)個體適應(yīng)度達(dá)到充分高且其群體適應(yīng)度與其充分接近時 ,終止進(jìn)化迭代。由于初始群體是隨機確定的 ,當(dāng)全局最優(yōu)解包含在初始群體之中時 ,進(jìn)化過程將迅速結(jié)束。這種情況是個別的 ,大多數(shù)情況下初始群之中不包括全局最優(yōu)解。因此 ,產(chǎn)生新的有效基因物質(zhì)的基因操作就變得尤為重要。表 1 中列出了三種理論模型試驗的結(jié)果 ,其中用混合編碼遺傳算法反

20、演 ,100 %收斂到全局最優(yōu)解 ?理論模型真值。而 標(biāo)準(zhǔn)遺傳算法收斂極不穩(wěn)定 ,且收斂速度慢。從搜索到全局最 優(yōu)解的平均進(jìn)化次數(shù)來看 ,混合編碼遺傳算法的收斂速度隨著 參數(shù)數(shù)目的增加而降低 ,表明問題復(fù)雜程度隨著參數(shù)數(shù)目的增 加而增加。另一方面 ,由于混合編碼遺傳算法不受初始模型的影響 ,可以搜索到真解 ,理論上這種算法對模型具有較高的分辨能力。表 1 標(biāo)準(zhǔn)遺傳算法與混合編碼遺傳算法執(zhí)行 20 次結(jié)果對比模型 (參數(shù)數(shù)目) 搜索到全局最優(yōu)的次數(shù)搜索到全局最優(yōu)的平均進(jìn)化次數(shù) 標(biāo)準(zhǔn) GA 混合編碼 GA 標(biāo)準(zhǔn) GA 混合編碼 GA 三角形柱體 (6) 6 20 131 15四邊形柱體 (8) 2

21、 20 1081 263五邊形柱體 (10) 0( 3000 次) 20 824 圖 3 四邊形柱體反演 的初值、局部最優(yōu)值與真值對比 圖 3 展示了“人”字形四邊形 水平柱體的真解與初始模型的對比。圖中給出了某次運算初始群體中適應(yīng)度最高的個體模型及其產(chǎn)生的異常 (長虛線) 和迭代過程 中某一局部最優(yōu)模型及其產(chǎn)生的 異常 (虛線) ,以及真實模型及其產(chǎn)生的異常 (實線) 。顯然 ,在繁衍進(jìn)程中群體逐漸趨向真實模型附近 ,當(dāng)群體收斂于一局部最優(yōu)解時 ,雖然計算異常與理論模型異常誤差很小 (均方差為 010176) ,但局部最優(yōu)解的模型形態(tài)與真實模型相差甚遠(yuǎn) ,欲從該局部極值中“跳出”,一般很難實

22、現(xiàn)。此例還說明用遺傳算法反演不僅不受初始模型的影響 ,同時具有很好的垂向分辨力。對于這樣的模型 ,一般方法幾乎無法完全收斂到真值。 (下轉(zhuǎn)第 69 頁) 一段時間后 ,實時庫的數(shù)據(jù)轉(zhuǎn)到歷史庫中存儲 ,實時庫中的數(shù)據(jù)量保持較小 ,查詢實時數(shù)據(jù)速度快。對于不同時期采集到的數(shù)據(jù) ,可以用不同的粒度進(jìn)行存儲。較早時期的數(shù)據(jù) ,可以用較粗粒度進(jìn)行存儲 ,如 :較早的數(shù)據(jù)流量數(shù)據(jù) ,可以通過計算其較長時間間隔的平均值來代替其實時的數(shù)據(jù) ,這對性能數(shù)據(jù)指標(biāo)不會造成影響 ,但對減少存儲空間非常有效。數(shù)據(jù)分析的模塊的功能是通過獲得的網(wǎng)絡(luò)性能的有關(guān)數(shù)據(jù) ,對網(wǎng)絡(luò)性能進(jìn)行動態(tài)分析 ,主要功能有 :包率、流量特性、利

23、用率、響應(yīng)時間等 ;歸分析、概率預(yù)測等 ;決策適當(dāng)?shù)奶幚矸绞?。?shù)據(jù)分析的結(jié)果 ,通過一定的方式進(jìn)行表現(xiàn)。對于統(tǒng)計和性能預(yù)測的結(jié)果 ,可以采用報表的方式提供 ,以及用可視化圖表的方式進(jìn)行表現(xiàn)。實時事件監(jiān)控的結(jié)果 ,可以通過彈出窗口 ,聲音報警來通知管理人員 ,并將結(jié)果寫入日志中。 圖 2 功能模塊示意圖 議 ,并成為一種事實上的網(wǎng)絡(luò)管理標(biāo)準(zhǔn)。本文通過闡述如何利用 SNMP進(jìn)行網(wǎng)絡(luò)性能實時監(jiān)控軟件開發(fā) ,分析了 SNMP的原理與工作模式以及各模塊開發(fā)的要點。而掌握 SNMP 的原理與工作模式 ,了解用 SNMP開發(fā)網(wǎng)絡(luò)管理軟件中各模塊實現(xiàn)的要點 ,對于在實際工作中進(jìn)行網(wǎng)絡(luò)管理軟件的開發(fā)是很有幫助的。 參 考 文 獻(xiàn) 現(xiàn)”,小型微型計算機系統(tǒng),Vol . 22 ,No. 8.