張學(xué)磊，馮杰

?

一種用于匹配場(chǎng)反演的遺傳算法

張學(xué)磊，馮杰

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

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

匹配場(chǎng)反演；遺傳算法；模擬退火；混沌；多樣性測(cè)度

0 引言

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

1 遺傳算法的缺點(diǎn)、改進(jìn)方向

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

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

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

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

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

2 混合遺傳算法的構(gòu)造

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

2.1 群體的多樣性的改進(jìn)

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

(3)

或：(5)

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

2.2 局部搜索能力的改進(jìn)[8]

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

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

2.3 遺傳算子的改進(jìn)

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

(8)

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

(2) 將所有個(gè)體譯為二進(jìn)制編碼；

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

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

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

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

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

4 混合遺傳算法與改進(jìn)前遺傳算法的性能比較

4.1 仿真實(shí)驗(yàn)環(huán)境設(shè)定

以兩層海底模型作為基準(zhǔn)測(cè)試模型，見(jiàn)圖2。海水中聲速?gòu)暮Ｆ矫娴?480 m/s單調(diào)下降到海底(海平面下40 m處)的1460 m/s，聲源頻率采用三個(gè)頻率：100、200、300 Hz，聲源深度為20 m，接收器陣為垂直陣，陣元共有16個(gè)，間距為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è)定其搜索范圍，即可對(duì)算法性能進(jìn)行仿真。待反演參數(shù)設(shè)定為：聲源與接收器間距為、海水厚度1、以及沉積層的聲速1、密度sed和衰減系數(shù)sed。

4.2 混合遺傳算法性能仿真結(jié)果

在仿真實(shí)驗(yàn)中，采用非相干的Bartlett匹配器，其定義如下：

CASE1 加入所有因子的情況

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

CASE3 無(wú)多樣性測(cè)度因子、無(wú)交叉概率和變異概率自適應(yīng)因子的情況

CASE4 無(wú)多樣性測(cè)度因子、無(wú)模擬退火因子的情況

CASE5 無(wú)多樣性測(cè)度因子、無(wú)模擬退火因子、無(wú)交叉概率和變異概率自適應(yīng)因子的情況

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

表1 無(wú)噪聲時(shí)算法性能仿真結(jié)果

表2 SNR=3 dB的算法性能仿真結(jié)果

表3 SNR = 0dB的算法性能仿真結(jié)果

5 結(jié)論

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

致謝：本文對(duì)應(yīng)的研究工作得到了中國(guó)科學(xué)院聲學(xué)研究所李整林研究員的指導(dǎo)，在此表示感謝。

[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ù)值并行算法——模擬退火算法(第一冊(cè))[M]. 北京: 科學(xué)出版社, 1998.

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

[5] 張彤, 王宏偉, 王子才. 變尺度混沌優(yōu)化方法及其應(yīng)用[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] 陳炳瑞, 楊成祥, 馮夏亭, 等. 自適應(yīng)混沌遺傳算法及其參數(shù)敏感性分析[J]. 東北大學(xué)學(xué)報(bào): 自然科學(xué)版, 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] 李敏強(qiáng), 寇紀(jì)松, 林丹, 等. 遺傳算法的基本理論與應(yīng)用[M]. 北京: 科學(xué)出版社, 2002.

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

[8] 田東平, 遲洪欽. 混合遺傳算法與模擬退火法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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

張學(xué)磊(1981－), 男, 山東濰坊人, 博士, 高級(jí)工程師, 研究方向?yàn)樗曅盘?hào)處理。

張學(xué)磊, E-mail: jonseray@163.com