李少林，周偉，馬剛，常曉林，胡超

?

基于改進(jìn)遺傳交叉算子的高心墻堆石壩參數(shù)反演

李少林1, 2，周偉1，馬剛1，常曉林1，胡超1

(1. 武漢大學(xué) 水資源與水電工程科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430072；2. 長(zhǎng)江勘測(cè)規(guī)劃設(shè)計(jì)研究院，湖北 武漢，430010)

受基因工程選擇性克隆優(yōu)秀基因片段的啟發(fā)，提出一種基于基因片段差異度的自適應(yīng)交叉算子(genetic crossover based on the difference of gene fragment，DGFX)。在改進(jìn)的交叉算子中，隨機(jī)確定基因片段長(zhǎng)度，計(jì)算父代個(gè)體對(duì)應(yīng)基因片段的差異度，根據(jù)差異度選擇基因片段進(jìn)行交叉操作，能有效避免近親繁殖，減少無(wú)效交叉操作，加快收斂速度。此外，根據(jù)演化代數(shù)自適應(yīng)調(diào)整基因片段長(zhǎng)度系數(shù)，增強(qiáng)算法全局收斂能力。將該交叉算子與帕累托交叉算子、啟發(fā)式交叉算子運(yùn)用標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行對(duì)比分析。研究結(jié)果表明：利用DGFX交叉算子時(shí)能快速收斂到全局最優(yōu)解，且算法魯棒性強(qiáng)、精度高。將DGFX交叉算子運(yùn)用于瀑布溝心墻堆石壩堆石體力學(xué)參數(shù)反演，利用反演的力學(xué)參數(shù)進(jìn)行計(jì)算，各測(cè)點(diǎn)計(jì)算值和實(shí)測(cè)值在發(fā)展趨勢(shì)和數(shù)值上均吻合較好，說(shuō)明DGFX交叉算子運(yùn)用于多變量、強(qiáng)非線性復(fù)雜巖土工程位移反演中的優(yōu)越性，具有良好的實(shí)際應(yīng)用價(jià)值。

心墻堆石壩；參數(shù)反演；遺傳算法；交叉算子；RBF神經(jīng)網(wǎng)絡(luò)

堆石壩壩料物理力學(xué)參數(shù)的取值是堆石壩設(shè)計(jì)、壩體應(yīng)力變形分析的基礎(chǔ)。堆石體力學(xué)參數(shù)一般由室內(nèi)試驗(yàn)或現(xiàn)場(chǎng)試驗(yàn)獲得，然而由于受試驗(yàn)條件、縮尺效應(yīng)[1]、施工質(zhì)量等影響，測(cè)定的力學(xué)參數(shù)與實(shí)際值存在較大差異，由此計(jì)算的堆石壩應(yīng)力、變形不可避免的與實(shí)際值相差較大。因此，有必要利用壩體位移監(jiān)測(cè)資料對(duì)堆石體的參數(shù)進(jìn)行位移反分析，并由此預(yù)測(cè)壩體的后期變形。目前，基于現(xiàn)場(chǎng)實(shí)測(cè)信息的位移反分析方法已成為確定堆石體力學(xué)參數(shù)的一條有效途徑[2]。巖土工程中的反演常采用直接法，將土體參數(shù)反演問(wèn)題轉(zhuǎn)換成優(yōu)化問(wèn)題，將計(jì)算位移與監(jiān)測(cè)位移的最小誤差函數(shù)作為目標(biāo)函數(shù)，通過(guò)反復(fù)迭代逼近待定參數(shù)的最優(yōu)值。堆石壩力學(xué)參數(shù)反演是一個(gè)非線性、多參數(shù)組合的大空間復(fù)雜優(yōu)化問(wèn)題，傳統(tǒng)的優(yōu)化方法因初值難選、易陷入局部最優(yōu)等不足，很難求解該復(fù)雜問(wèn)題。遺傳算法[3?4]、粒子群算法[5?7]、蟻群算法[8]、序列二次規(guī)劃法[9]等具有全局優(yōu)化特點(diǎn)的智能搜索算法被用于求解該問(wèn)題，取得了較好效果。遺傳算法(genetic algorithm，GA)因其魯棒性好、簡(jiǎn)單通用、效率高等優(yōu)點(diǎn)，在其首次提出后獲得很大發(fā)展，并廣泛運(yùn)用于巖土工程參數(shù)反演中[10?12]。但進(jìn)一步研究發(fā)現(xiàn)，遺傳算法在應(yīng)用中存在早熟、收斂慢等現(xiàn)象。雖然該問(wèn)題得到了初步解決，但仍有待進(jìn)一步研究和實(shí)踐。遺傳算法是模擬生物界遺傳和進(jìn)化過(guò)程的一種隨機(jī)搜索算法，它提供了一種求解復(fù)雜優(yōu)化問(wèn)題的通用框架，不依賴于具體的領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性。交叉算子是遺傳算法的主要進(jìn)化手段，但是傳統(tǒng)交叉算子的實(shí)質(zhì)是隨機(jī)選擇基因片段進(jìn)行交叉，當(dāng)所選擇基因片段的具有相同或高度近似的基因時(shí)，近親繁殖很難產(chǎn)出新的個(gè)體，是無(wú)效的交叉操作，從而使得遺傳算法出現(xiàn)收斂速度慢、早熟現(xiàn)象，不易跳出局部極值點(diǎn)。本文作者針對(duì)遺傳算法在搜索過(guò)程中的不足，借鑒基因工程中選擇性克隆優(yōu)良基因片段的思想，提出一種基于基因片段差異度的遺傳交叉算子(genetic crossover based on the difference of gene fragment, DGFX)。在介紹DGFX算法的原理、特點(diǎn)、算法后，利用標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)其性能進(jìn)行測(cè)試，將其運(yùn)用于瀑布溝心墻堆石壩力學(xué)參數(shù)反演中，證明這種算法在解決復(fù)雜工程問(wèn)題中的優(yōu)越性。

1 遺傳算法及改進(jìn)的交叉算子

1.1 遺傳算法

遺傳算法是一種借鑒生物界自然選擇和自然遺傳的隨機(jī)搜索算法，由HOLLAND[13]于1975年提出。它借鑒達(dá)爾文“優(yōu)勝劣汰、適者生存”的自然進(jìn)化理論和孟德?tīng)柕倪z傳變異理論，將問(wèn)題的求解轉(zhuǎn)化為“個(gè)體”的適者生存過(guò)程，反復(fù)進(jìn)行選擇、交叉和變異等操作，不斷進(jìn)化，從而使群體最終搜索到“最適應(yīng)環(huán)境的個(gè)體”，即求得問(wèn)題的最優(yōu)解或滿意解。選擇操作根據(jù)個(gè)體適應(yīng)度來(lái)確定個(gè)體的生存能力，適應(yīng)度高的個(gè)體具有高的生存概率，相反，適應(yīng)度低的個(gè)體則將遭到淘汰，選擇操作使種群的平均適應(yīng)度不斷提高，但不產(chǎn)生新的個(gè)體；交叉操作是對(duì)父代雙親進(jìn)行基因片段的交換和重組，產(chǎn)生新的個(gè)體，可采用精英保留策略，使更優(yōu)個(gè)體的出現(xiàn)成為可能。變異操作是通過(guò)隨機(jī)改變個(gè)體內(nèi)部的基因，產(chǎn)生新個(gè)體，豐富種群個(gè)體多樣性和基因多樣性。標(biāo)準(zhǔn)遺傳算法的具體流程如下：

1) 種群初始化，在搜索空間中隨機(jī)產(chǎn)生個(gè) 個(gè)體；

2) 計(jì)算適應(yīng)度，根據(jù)適應(yīng)度函數(shù)計(jì)算個(gè)體的適 應(yīng)度；

3) 選擇，根據(jù)個(gè)體適應(yīng)度選擇個(gè)體進(jìn)入下一代；

4) 交叉，將選出的個(gè)體兩兩交換基因，產(chǎn)生的新個(gè)體進(jìn)入新群體；

5) 變異，隨機(jī)改變某一個(gè)體的某個(gè)基因，然后將個(gè)體添入新群體；

6) 迭代演化，判斷算法優(yōu)化準(zhǔn)則，若滿足則結(jié)束演化，輸出結(jié)果；否則轉(zhuǎn)到第2)步。

1.2 基于基因片段差異度的自適應(yīng)交叉算子

1.2.1 遺傳算法交叉算子的改進(jìn)

交叉算子是遺傳算法中非常重要的遺傳操作，決定著算法的全局收斂能力，影響著算法的收斂速度。傳統(tǒng)的交叉算子采用隨機(jī)選擇基因片段的方式進(jìn)行交叉，當(dāng)所選擇基因片段的具有相同或高度近似的基因時(shí)，近親繁殖很難產(chǎn)出新的個(gè)體，是無(wú)效的交叉操作，從而使得遺傳算法出現(xiàn)收斂速度慢、早熟等現(xiàn)象。為了克服這一不足，改善算法的收斂性能，受基因工程克隆優(yōu)良基因片段的啟發(fā)，基于基因片段差異度進(jìn)行交叉操作。根據(jù)基因片段差異度，計(jì)算片段交叉概率，選擇基因片段進(jìn)行交叉，減少近親繁殖和無(wú)效交叉 操作。

文中將染色體中任意長(zhǎng)度為的一段連續(xù)基因編碼稱為基因片段，將基因片段首個(gè)基因所處基因位稱為交叉點(diǎn)，并給出基因片段差異度和片段交叉概率的定義。

定義1 任意優(yōu)化問(wèn)題的實(shí)數(shù)編碼空間為R，種群個(gè)體和長(zhǎng)度為的基因片段的差異度為

式中：()為2個(gè)個(gè)體的第個(gè)基因片段的差異度；和分別為2個(gè)體第個(gè)基因位上的基因編碼；表示個(gè)體(1)的基于編碼。

定義2 根據(jù)基因片段交叉概率選擇基因片段的交叉點(diǎn)，基因片段交叉概率為

式中：()和()分別為父代第個(gè)和第個(gè)基因片段的差異度。

()表示擬交叉基因片段的差異程度，()越大，表示個(gè)體(1)，(2)和第個(gè)基因片段的差異度越大，對(duì)2個(gè)個(gè)體第個(gè)基因片段進(jìn)行交叉時(shí)出現(xiàn)無(wú)效操作的可能性就越小。在交叉過(guò)程中，確定長(zhǎng)度系數(shù)并隨機(jī)確定片段的長(zhǎng)度比例，基因片段長(zhǎng)度為

式中：為片段長(zhǎng)度系數(shù)；chrom為基因編碼的總長(zhǎng)度；1是片段長(zhǎng)度比例，為隨機(jī)數(shù)?；蚱伍L(zhǎng)度系數(shù)從總體上控制片段的長(zhǎng)度，在總體控制的基礎(chǔ)上，引入隨機(jī)長(zhǎng)度比例增加交叉操作的多樣性。

1.2.2 自適應(yīng)基因片段長(zhǎng)度系數(shù)

DGFX交叉算子中，片段長(zhǎng)度系數(shù)直接影響算法的收斂性。在演化早期，高的長(zhǎng)度系數(shù)有利于鼓勵(lì)種群個(gè)體遍歷整個(gè)搜索空間，不至于聚集在超級(jí)個(gè)體周圍而導(dǎo)致早熟收斂；在演化后期，低的長(zhǎng)度系數(shù)有利于個(gè)體在最優(yōu)值附近搜索，以加速收斂。基于以上認(rèn)識(shí)，構(gòu)造了編碼長(zhǎng)度遞減策略，采用自適應(yīng)的編碼長(zhǎng)度系數(shù)。設(shè)min為最小基因片段長(zhǎng)度系數(shù)，max為最大變基因片段長(zhǎng)度系數(shù)，為當(dāng)前迭代次數(shù)，為最大迭代次數(shù)，即

編碼長(zhǎng)度系數(shù)隨著算法迭代的進(jìn)行而非線性 減小。

基于基因片段差異度的交叉算子(DGFX)具體步驟如下。

Step 1：確定編碼長(zhǎng)度系數(shù)min和max，生成隨機(jī)數(shù)，根據(jù)當(dāng)前迭代次數(shù)和最大迭代次數(shù)，由式(3)和(4)計(jì)算基因片段長(zhǎng)度。

Step 3：計(jì)算父代(1)和(2)對(duì)應(yīng)長(zhǎng)度為fragment的基因片段的差異度()(=1，2，…，(?fragment+1))，通過(guò)差異度計(jì)算基因片段的交叉概率，根據(jù)基因片段交叉概率選擇片段交叉點(diǎn)start。

式中：為基因編碼的基因位；start為基因片段的起點(diǎn)所在的基因位。

1.3 算法測(cè)試

為了驗(yàn)證本文提出的遺傳交叉算子DGFX的性能，將交叉算子DGFX與帕累托交叉算子(double pareto crossover, DPX)[14]、廣泛運(yùn)用的啟發(fā)式交叉算子(heuristic crossover, HX)[15?17]進(jìn)行了對(duì)比分析。3種遺傳算法中，選擇算子采用輪盤賭法，變異算子采用非均勻變異算子(non-uniform mutation，NUM)[17]，并采用精英保留策略，交叉算子分別采用DGFX，DPX和HX。

本文選擇了3個(gè)典型的非線性、多峰值函數(shù)。根據(jù)其特點(diǎn)可分為3類：一是無(wú)局部最優(yōu)解；二是有局部最優(yōu)解，但局部最優(yōu)和全局最優(yōu)解較易區(qū)分；三是有局部最優(yōu)解，且局部最優(yōu)解和全局最優(yōu)解很難區(qū)分。測(cè)試函數(shù)形式、取值范圍見(jiàn)表1，測(cè)試函數(shù)特性見(jiàn)表2，測(cè)試函數(shù)圖形見(jiàn)圖1~3。對(duì)于3類測(cè)試函數(shù)，種群規(guī)模為50，基準(zhǔn)測(cè)試函數(shù)的維數(shù)分別取30，60和90，相應(yīng)的迭代次數(shù)為1 500，2 500和3 500，交叉概率為0.8，變異概率為0.1。其中DGFX片段長(zhǎng)度系數(shù)min=0.1，max=0.9，采用自適應(yīng)片段長(zhǎng)度系數(shù)。

圖1 Sphere函數(shù)圖(n=2)

圖2 Ackley函數(shù)圖(n=2)

圖3 Rastrigin函數(shù)圖(n=2)

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)