一種用于匹配場反演的遺傳算法

張學磊，馮杰

?

一種用于匹配場反演的遺傳算法

張學磊，馮杰

(中國電子科技集團公司第三研究所，北京100015)

遺傳算法在接近全局最優(yōu)解時，存在搜索速度變慢、過早收斂、個體的多樣性減少很快、甚至陷入局部最優(yōu)解等問題。通過在遺傳算法中引入模擬退火因子、混沌因子和多樣性測度因子，在很大程度上克服了原有遺傳算法的早熟、局部搜索能力差的缺點。同時，又能發(fā)揮原有遺傳算法的強大的全局搜索能力，保證了改進后的混合遺傳算法能較好地收斂于其全局最優(yōu)值。

匹配場反演；遺傳算法；模擬退火；混沌；多樣性測度

0 引言

匹配場法反演經(jīng)常涉及到幾個，甚至十幾個待定參數(shù)的反演問題，可以看成是一個非線性的、有眾多局部最優(yōu)點的全局優(yōu)化問題。傳統(tǒng)的搜索方法，如窮舉法，在現(xiàn)有的計算條件下，所耗費的時間是一個天文數(shù)字，是難以承受的；又如局部搜索算法，這種算法的最終解只是某個局部最優(yōu)解，往往不是全局最優(yōu)解，而且最終解的質量還嚴重依賴于初始解的選擇。智能優(yōu)化算法，又稱為現(xiàn)代最優(yōu)化算法，從一組隨機生成的初始個體出發(fā)，按照一定的規(guī)則，并根據(jù)適應度(代價函數(shù)值)大小進行個體的優(yōu)勝劣汰，提高新一代群體的質量，再經(jīng)過多次反復迭代，逐步逼近全局最優(yōu)解，而且這種算法一般具有嚴密的理論依據(jù)，理論上可以在一定的時間內找到全局最優(yōu)解或近似全局最優(yōu)解。常用的智能優(yōu)化算法有神經(jīng)網(wǎng)絡優(yōu)化算法、遺傳算法(Genetic Algorithm, GA)[1]、模擬退火算法(Simulated Annealing, SA)[2]等。由于遺傳算法在海洋地聲參數(shù)反演方面已經(jīng)得到了廣泛的應用[3]，并得到了很好的結果，因此本文將采用遺傳算法作為反演的全局優(yōu)化算法。

1 遺傳算法的缺點、改進方向

遺傳算法是借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。它通過模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，將問題的求解表示成“染色體”的適者生存過程。在每次迭代中都保留一組候選“染色體”，并按某種指標從種群中選取較優(yōu)的“染色體”，利用遺傳因子，也就是選擇因子、交叉因子和變異因子，對這些“染色體”進行組合，產(chǎn)生新一代的候選種群，重復此過程，直到滿足某種收斂指標或達到設定的最大代數(shù)為止。

由于遺傳算法主要的遺傳操作都是在一定概率條件下隨機發(fā)生的，因此，它在為種群中個體提供進化機會的同時，也不可避免地產(chǎn)生退化的可能，使得在接近全局最優(yōu)解時搜索速度變慢、過早收斂、個體的多樣性減少很快、甚至陷入局部最優(yōu)解。其中很大原因要歸咎于遺傳算法對現(xiàn)實生物演化過程過于簡化的模擬。而實際上，遺傳算法中的群體是偽多樣性的：首先，初始化群體的多樣性難以實現(xiàn)；其次，即使假設傳統(tǒng)的初始化方法可以保證初始群體在空間上均勻分布，但并不能保證它們在質量上也是均勻分布的；最后，群體的多樣性在選擇壓力下也很難保持。因此，改善群體的多樣性是提高遺傳算法性能的重要研究方向，即設計產(chǎn)生的初始群體與遺傳因子。

模擬退火算法一種隨機組合優(yōu)化方法，它模擬熱力學中固體退火的過程，并廣泛應用于組合優(yōu)化問題，是局部搜索算法的擴展[4]。它同局部搜索算法一樣，具有強大的局部搜索能力，不同于局部搜索之處是其改變了只接收優(yōu)化迭代的準則，在一定范圍內接收惡化解。將模擬退火算法與遺傳算法結合，來解決遺傳算法局部搜索能力的不足。

混沌[5,6](Chaos)是一種普通的非線性現(xiàn)象，貌似一片混亂實則具有內在的規(guī)律性。Logistic映射作為重要的混沌映射之一，定義為一種不可逆映射: (0, 1)→(0, 1)。對于某個變量，其第+1個值由式(1)所示的Logistic映射迭代得到：

式中，是個重要參數(shù)，當=4，系統(tǒng)輸出可在(0, 1)上取到不重復的任何值，三個不動點(0.25，0.5，0.75)除外。

2 混合遺傳算法的構造

由第1節(jié)的分析可知，在遺傳算法的基礎上，將遺傳算法、模擬退火和混沌有機結合，優(yōu)勢互補，發(fā)揮各自的優(yōu)勢，克服遺傳算法(GA)局部搜索能力差、偽多樣性、早熟現(xiàn)象等問題，就可構造出一種快速準確的搜索算法——混合遺傳算法(Hybrid GA, HGA)。

2.1 群體的多樣性的改進

利用混沌映射的優(yōu)秀特性，同時針對本文的實際問題，首先將待反演參數(shù)空間進行歸一化，即進行變換：

(3)

或：(5)

當種群的多樣性測度減小時，種群有早熟趨勢。圖1給出了在一次反演過程中，種群的多樣性測度的函數(shù)值隨進化代數(shù)的變化圖，可以認為遺傳算法30代以后種群進入了早熟狀態(tài)，由此引出早熟定義：當種群的多樣性測度函數(shù)值在連續(xù)代內，變動幅度小于設定值時，可認為種群進入早熟狀態(tài)。此時需要對進行種群的多樣化處理。當種群的多樣性測度函數(shù)值小于設定值，且未達到最大收斂代數(shù)時，需要重新對種群中的不良個體進行處理，以改善種群的多樣性。用隨機數(shù)發(fā)生器產(chǎn)生一個的隨機數(shù)，對全體個體中個劣質個體，按照式(2)進行全參數(shù)空間的混沌操作，產(chǎn)生新種群中的個新個體。

2.2 局部搜索能力的改進[8]

模擬退火作為局部搜索算法的改進算法，與局部搜索算法不同之處在于采用Metropolis準則，并用一組稱為冷卻進度表的參數(shù)控制算法進程。Metropolis準則為：模擬退火處于狀態(tài)和狀態(tài)的幾率的比值等于相應Boltzmann因子的比值，即：

式中：為冷卻進度表參數(shù)中的溫度控制參數(shù)(在海底參數(shù)反演領域，Gerstoft[1]給出了一個較好的設定：設定為每一代中染色體適應度函數(shù)值的最小值)，若>1，則始終接是收狀態(tài)；若<1，則用隨機數(shù)發(fā)生器產(chǎn)生一個的隨機數(shù)，若>，則接受狀態(tài)為新狀態(tài)，否則舍棄狀態(tài)。在遺傳算法產(chǎn)生新種群的新染色體時，將按照Metropolis準則決定是否接收新產(chǎn)生的染色體。

2.3 遺傳算子的改進

在遺傳算法的進化過程中，影響種群收斂性的最重要的參數(shù)為交叉因子和變異因子。為了防止因早熟得不到全局最優(yōu)解，將、設計成種群多樣性測度函數(shù)的函數(shù)，Gerstoft[1]曾給出了設定：=0.8、=0.05，以此為藍本設定本文中交叉因子和變異因子：

(8)

3 混合遺傳算法的具體實現(xiàn)步驟

(2) 將所有個體譯為二進制編碼；

(3) 計算種群中每個個體的適應度函數(shù)。判斷是否滿足結束條件，若是則算法終止運行并輸出最終結果，若否，進入步驟(4)；

(4) 判斷是否滿足結束條件，若是則算法終止運行并輸出最終結果，若否，將每個個體按照適應度函數(shù)值進行排序，決定溫度控制參數(shù)，進入步驟(5)；

(5) 按照式(3)和式(4)，計算種群的多樣性測度函數(shù)值。按照早熟定義判斷種群是否進入早熟狀態(tài)，若進入早熟狀態(tài)，轉至步驟(7)，若否，轉至步驟(6)；

(6) 按照式(7)和式(8)計算交叉因子P、變異因子P，對父代進行選擇、交叉和變異操作，產(chǎn)生子代，計算子代中個體的適應度函數(shù)值。按照Metropolis準則，決定是否接受子代中的當前染色體。在上述過程中保留最佳染色體，而后轉至步驟(4)；

(7) 用隨機數(shù)發(fā)生器產(chǎn)生一個[0,1)的隨機數(shù)，舍棄全體個體中個劣質個體，并按照式(1)進行全參數(shù)空間的混沌操作，產(chǎn)生新種群中的pop個新個體，并將之譯為二進制編碼，計算子代中個體的適應度函數(shù)值，轉至步驟(4)。

4 混合遺傳算法與改進前遺傳算法的性能比較

4.1 仿真實驗環(huán)境設定

以兩層海底模型作為基準測試模型，見圖2。海水中聲速從海平面的1480 m/s單調下降到海底(海平面下40 m處)的1460 m/s，聲源頻率采用三個頻率：100、200、300 Hz，聲源深度為20 m，接收器陣為垂直陣，陣元共有16個，間距為2 m，分布于2~32 m的海水中。聲源與接收器的間距為=5 km，沉積層厚度2=30 m、聲速1=1600 m/s、密度sed=1.7 g/cm3、衰減系數(shù)sed=0.23 dB/λ，基底的聲速2、密度b、衰減系數(shù)b分別為：1700 m/s、1.85 g/cm3、0.23 dB/λ。

假定上面的某些參數(shù)為未知，設定其搜索范圍，即可對算法性能進行仿真。待反演參數(shù)設定為：聲源與接收器間距為、海水厚度1、以及沉積層的聲速1、密度sed和衰減系數(shù)sed。

4.2 混合遺傳算法性能仿真結果

在仿真實驗中，采用非相干的Bartlett匹配器，其定義如下：

CASE1 加入所有因子的情況

CASE2 無多樣性測度因子情況(包括混沌因子)

CASE3 無多樣性測度因子、無交叉概率和變異概率自適應因子的情況

CASE4 無多樣性測度因子、無模擬退火因子的情況

CASE5 無多樣性測度因子、無模擬退火因子、無交叉概率和變異概率自適應因子的情況

在每種情況下，遺傳算法獨立運行100次，基因的總數(shù)為256^5≈1.0995×1012個。遺傳算法在每次運行時，調用的基因總數(shù)為6400次。對遺傳算法最終的輸出結果進行統(tǒng)計分析，不同信噪比下的仿真結果(見表1、表2和表3)表明，改進后的HGA較原有的遺傳算法有更加優(yōu)異的尋優(yōu)性能。這具體表現(xiàn)在：HGA待反演參數(shù)的均值更加接近于預設值，其標準差更小。

表1 無噪聲時算法性能仿真結果

表2 SNR=3 dB的算法性能仿真結果

表3 SNR = 0dB的算法性能仿真結果

5 結論

本文提出一種用于匹配場反演的遺傳算法，并進行了計算機仿真分析。仿真分析結果表明，改進后的HGA可以將遺傳算法、模擬退火、混沌各自的優(yōu)點結合起來，揚長避短，并引入了多樣性測度因子來監(jiān)測種群的多樣性，隨時改善種群性能以及動態(tài)自適應調節(jié)交叉概率和變異概率，使得進化前期交叉明顯，后期變異顯著，更符合遺傳規(guī)律。改進措施在很大程度上克服了原有遺傳算法的早熟、局部搜索能力差的缺點，同時，發(fā)揮了原有遺傳算法的強大的全局搜索能力，保證了改進后的混合遺傳算法能較好地收斂于其全局最優(yōu)值。

致謝：本文對應的研究工作得到了中國科學院聲學研究所李整林研究員的指導，在此表示感謝。

[1] Gerstoft P. Inversion of seismoacoustic data using genetic algorithms and a posteriori probability distribution[J]. J. Acoust. Soc. Am, 1994, 95(2): 770-781

[2] Lindsay C E, Chapman N R. Matched field inversion for geoacoustic model parameters using adaptive simulated annealing[J]. IEEE J. Oceanic Eng, 1993, 18(3): 224-231.

[3] Tolstoy A, Chapman N R, Brooke G. Workshop '97: Benchmarking for geoacoustic inversion in shallow water[J].J. Comp. Acoust, 1988, 6(1-2): 1-28.

[4] 康立山, 謝云, 尤矢勇, 等. 非數(shù)值并行算法——模擬退火算法(第一冊)[M]. 北京: 科學出版社, 1998.

KANG Lishan, XIE Yun, YOU Shiyong, et alNonnumeric parallel algorithm: simulated annealing(volume one)[M]. Beijing: Science Press, 1998.

[5] 張彤, 王宏偉, 王子才. 變尺度混沌優(yōu)化方法及其應用[J]. 控制與決策, 1999, 14(3): 285-288.

ZHANG Tong, WANG Hongwei, WANG Zicai, Mutative scale chaos optimization algorithm and it’s application[J]. Control and Decision, 1999, 14(3): 285-288.

[6] 陳炳瑞, 楊成祥, 馮夏亭, 等. 自適應混沌遺傳算法及其參數(shù)敏感性分析[J]. 東北大學學報: 自然科學版, 2006, 27(6): 689-693.

CHEN Bingrui, YANG Chengxiang, FENG Xiating, et al. Self-Adapting Chaos-Genetic Hybrid Algorithm and Sensitivity Analysis of Its Parameters[J]. Journal of Northeastern University: Natural Science, 2006, 27(6): 689- 693.

[7] 李敏強, 寇紀松, 林丹, 等. 遺傳算法的基本理論與應用[M]. 北京: 科學出版社, 2002.

LI MinQiang, KOU Jisong, LIN Dan, et alThe basic theory and application of genetic algorithm[M]. Beijing: Science Press, 2002.

[8] 田東平, 遲洪欽. 混合遺傳算法與模擬退火法[J]. 計算機工程與應用, 2006, 42(22): 63-65.

TIAN Dongping, CHI Hongqin, Hybrid genetic algorithm and simulated annealing[J]. Computer Engineering and Application, 2006, 42(22): 63-65.

[9] Miller J F, Wolf S N. Modal acoustic transmission loss(MOATL): A transmission-loss computer program using a normal-mode model of the acoustic field in the ocean[M]. Washington, DC: Naval Research Laboratory, 1980.

A new genetic algorithm for matched-field inversion

ZHANG Xue-lei, FENG Jie

(The No.3 Research Institute of China Electronic Technology Group Corporation, Beijing 100015,China)

When approaching the global optimal solution, some shortcomings of the genetic algorithm, such as slow search speed, premature convergence, quick reduction of the diversity of individuals, and even getting into the trouble for local optimal solution, are highlighted. By introducing the simulated annealing factor, chaos factor and diversity measure factor into the genetic algorithm, the original shortcomings,such as the premature convergence and the poor local search capability, are greatly overcome, and meanwhile, the original powerful global search capability of genetic algorithm is maintained. So the hybrid genetic algorithm improved by all the measures can better converge at its global optimal value.

matched-field inversion; genetic algorithm; simulated annealing; Chaos;diversity measure

TP3

A

1000-3630(2015)-05-0462-05

10.16300/j.cnki.1000-3630.2015.05.015

2014-11-25;

2015-01-14

張學磊(1981－), 男, 山東濰坊人, 博士, 高級工程師, 研究方向為水聲信號處理。

張學磊, E-mail: jonseray@163.com