匹配場目標定位的并行遺傳算法實現

趙博，董姝敏，李運赫，樸勝春

(1.哈爾濱工程大學水聲技術國家級重點實驗室，黑龍江哈爾濱150001;2.海軍92330部隊，山東青島266061;3.吉林師范大學信息技術學院，吉林四平136000)

匹配場聲源定位方法能夠突破傳統被動定位方法的極限，正確估計遠程和超遠程聲源的距離和深度.但由于匹配場定位技術需要利用聲傳播模型來反復計算拷貝場向量，然后將拷貝場與測量場進行“匹配”，從而實現水下目標的定位;而且，在實際應用中，由于水聲環境條件十分復雜，匹配場定位方法面臨著計算拷貝場的計算量大、耗時長、占用存儲空間大等問題［1］，不能快速為仿真環境提供數據支持.并行處理技術正是為了解決實際工程應用中的計算量問題得以發展的［2］，因此將并行處理技術引入到匹配場定位中，能夠將拷貝場計算等處理任務合理地分配到計算機系統的多個處理機上，使各處理機的工作負載保持相對均衡，整個計算機系統在較短的時間內協同完成處理任務，從而加快計算速度，提高計算效率.為了從本質上減少拷貝場計算的工作量，尋優算法的選取起著至關重要的作用，遺傳算法具有全局收斂、并行計算、快速搜索多峰值復雜空間等特點，作為一種概率搜索算法，它可以在搜索空間內快速向目標解逼近，最終收斂于全局最優解.將并行計算和遺傳算法結合起來用于匹配場定位中，可以有效地解決計算量問題，提高計算效率.并行遺傳算法［3］已經發展成熟，在許多實際應用領域中得到廣泛應用，但國內文獻中還未見將其應用于匹配場定位的計算中，國外文獻也不多見.因此選用并行遺傳算法實現匹配場定位具有一定的理論研究意義和實際應用價值.

1 匹配場定位原理

1.1 匹配場定位的基本思想

聲場建模、拷貝場計算、相關處理是匹配場聲源定位的重要研究內容.首先，獲取實際測量場數據，它是涵蓋信道特征和聲源特征的聲壓場;其次，根據聲場模型與已知的環境參數(如聲速分布、海底地形等)對假定的聲源進行拷貝場計算;最后，利用匹配場處理算法對測量場與建模獲得的拷貝場作相關處理，找到與測量場匹配的最佳的拷貝場，則計算該拷貝場時所假定的聲源位置就認為是實際的聲源位置［4］，以此估計聲源的距離和深度，從而實現對水下目標的定位，如圖1［5］所示.

圖1 匹配場定位的原理示意Fig.1 Principle block diagram of matched field localization

由于簡正波理論適合于水平分層介質，計算速度快，論文選擇簡正波理論進行拷貝聲場計算.采用kraken簡正波模型［6］將波動方程的解表示為

式中:krm為第m個特征值，zs為聲源深，Zm為求得的第m階本征函數.使用Kraken方法求解本征值和本征函數后，將其代入聲壓函數表達式(1)中便可

1.2 匹配處理算法

自適應匹配場處理器將自適應陣列信號處理的優點融合到匹配場處理中，能夠有效抑制旁瓣和干擾，提供了理論上的最佳陣增益和定位精度，比線性處理器具有更好的性能［7］.本文選用使測量場數據與拷貝場數據在輸出噪聲功率最小的意義上構建的最小方差處理器.最小方差處理器的代價函數計算公式［8］如下: 1;N代表水聽器的個數;C是N×N的互譜矩陣.

2 匹配場定位中的并行性分析

2.1 拷貝場計算的并行性

匹配場目標定位的主要計算量來自拷貝場計算.拷貝場計算需要在空間覆蓋區域內進行距離、深度空間采樣，每個采樣點處假定存在一個聲源，聲源的距離和深度可當作已知量，然后采用簡正波方法的kraken軟件計算假定聲源的聲壓，以此得到拷貝場.拷貝場各點的假定聲源聲壓的計算是相互獨立的，彼此沒有耦合關系，可以并行地進行計算，并行系統的每臺處理機分別單獨地負責某些采樣點的聲壓場計算，各臺處理機同時并行工作，可有效縮短拷貝場計算時間.

2.2 匹配處理的并行性

用匹配場處理算法對測量場與拷貝場聲壓作匹配相關處理時，需要分別對指定采樣點的假定聲源聲壓與實際聲源聲壓進行相關運算，各點的相關運算是獨立進行的，彼此之間互不影響，為了節省處理時間，可以將相關運算的總任務合理地分配到并行計算機系統的多個處理機上，整個計算機系統可以在較短的時間內完成相關處理.

匹配場定位中也存在其他的并行機制，如簡正波解的并行性，以及進行匹配處理過程中的功能級并行處理等，不再累述.

3 并行計算系統結構

MPI是國際上通用的消息傳遞接口，是并行程序設計標準之一，它可與C，Fortran，C++，JAVA等語言結合而構成并行程序設計語言.MPI有許多實現版本，其中MPICH提供了接口一致的MPI標準函數庫和程序運行環境［9］.另外，MPI不僅支持各種硬件環境，幾乎支持各種操作系統Linux、Unix和Windows等.因此，采用MPI編寫的并行程序可移植性好，而且具有成熟的軟件開發工具，普通的PC機加上一個高速局域網即可實現，價格便宜，操作方便，易于實現，能夠為試驗性的仿真研究提供便捷的研究途徑和仿真試驗環境.

3.1 系統配置

采用基于Windows的PC機群系統實現并行計算.系統的具體配置情況如下:

1)硬件組成:2臺雙核PC機，網絡交換器.

PC機配置:Petium(R)Dual-core CPU處理器，2.26GHz處理器主頻，2G內存.

2)軟件組成:Windows XP操作系統，MPI并行環境，Microsoft.NET Framework 2.0，FORTRAN編譯器.

3.2 MPI并行環境搭建

1)每臺PC機中新建一個MPI用戶，該用戶應該具有管理員權限，隸屬Administrators組，各臺PC中的MPI用戶名和密碼均相同;

2)在各PC機上安裝Microsoft.NET Framework 2.0和MPICH2，各臺PC機安裝MPICH2時口令要一致，默認口令是“be happy”.MPICH2的默認安裝路徑為C:Program FilesMPICH2;

3)運行MPICH2中wmpiregister.exe注冊用戶;

4)用網絡交換器將PC機連接，把待測試的可執行程序拷貝到每臺PC機的同一目錄中，該目錄都應該在相同的位置，如C:MPI Program下，需要將windows系統的防火墻關閉;

5)用MPICH2所自帶的界面方式運行可執行程序，選擇“more option”打開下拉對話框，使用IP地址或者PC機器名連接各臺PC機，空格分隔.

4 并行遺傳算法實現匹配場聲源定位

若以串行遺傳算法作為匹配場尋優算法實現匹配場定位，因為群體規模較大，需要對較多的個體進行大量的遺傳和進化操作，特別是要對大量的個體進行適應度計算和評價，從而使算法的進化運算過程進展緩慢，難以達到計算速度上的要求，故采用并行遺傳算法作為匹配場處理的優化算法［10］，它可以同時對多個個體或種群進行遺傳和進化操作，不斷滿足計算速度上的需求.并行遺傳算法從并行形式上可分為4類［11］:1)個體適應度評價的并行性; 2)整個群體中各個個體適應度評價的并行性;3)算法基本操作內部的并行性;4)基于群體分組的并行性.本文選用基于群體分組的并行遺傳算法進行匹配場目標定位.

遺傳算法作為一個發展較完善的搜索算法，主要包括個體編碼策略、選擇策略、交叉策略、變異策略、個體適應度評價、算法停止準則等運算操作.因為遺傳算法是一種概率算法，沒有能力保證得到最優解，但是通過對遺傳算法進行合理的設計可以在合理的時間內求得可接受的解.

4.1 并行遺傳算法實現聲源定位過程

匹配場定位中，在計算區域內對距離方向和深度方向進行空間采樣，將各空間點對應的距離和深度信息進行編碼生成染色體，這樣空間采樣點與載有距離和深度信息的染色體一一對應起來.并行遺傳算法在計算區域內隨機、均勻地搜索空間點(對應著染色體信息)，生成初始群體;然后將整個群體分解為幾個子群體，并分配到不同的處理機上，各處理機獨自運行遺傳算法，分別進行選擇、交叉、變異運算，并完成適應度的計算和評價，計算對應個體的聲壓;再進行聲壓場匹配，找出各進程中靠近實際聲壓源的采樣點，由指定的某個進程進行統計處理，找到本代最優值，判斷其是否滿足解條件.為了提高計算效率，產生每一代新個體后，各進程之間需要相互交換信息，每個進程分別將各自的最優值傳遞給其他所有進程.反復迭代，逐漸靠近目標點，直到找到最優個體或滿足程序終止條件為止.具體執行過程如下:

1)在匹配場處理范圍內，隨機生成初始群體，群體中個體的參量包含拷貝場中隨機位置的距離和深度信息，由指定進程將初始群體分配給其他進程.

2)各進程分別計算個體適應度，并統計找出本代本進程的局部最優個體，適應度值最高的個體即為本代本進程局部最優個體.

3)找到所有進程的局部個體后，將這些個體和設定的閥值參數進行比較，滿足設定的適應度參數要求，即找到最優個體，程序結束，不滿足，繼續執行程序.

4)各進程之間相互通信，將本進程的最優個體通信給其他進程并替換掉其他進程的最差個體，形成新的群體，并對此群體進行遺傳算法的交叉變異操作，形成下一代群體.

5)回到步驟2)循環執行，直到找到最優個體或者滿足程序終止條件為止，程序退出.

采用并行遺傳算法實現匹配場定位的MPI程序示意圖如圖2所示.

圖2 并行遺傳算法實現匹配場定位示意Fig.2 Block diagram of implementation of matched field localization by parallel genetic algorithm

4.2 進程間的數據通信

1)進程0計算測量場聲壓P1，然后調用MPI庫函數MPI_Bcast()將P1廣播給其他進程，其他進程得到P1后才能進行匹配處理;

2)各進程完成一次迭代時，分別得到各自的局部最優解，進程0(或指定進程)調用MPI庫函數MPI_Gather()收集所有其他進程的局部最優解，對收集的結果進行統計處理;

3)各進程之間按照“島嶼模型”(見圖2)方式相互通信，將各自的局部最優解發送給其他各進程，并替代相應進程的最差解.

5 仿真實驗及性能分析

實際聲源距離為45 km，深度為100 m，頻率10 Hz.接收基陣由3個基元組成的水平陣(垂直陣)，基元間距為14.84 m，基陣與深度方向夾角為θ=90°，聲源方位角 φ=0°，中心基元深度 z0= 100 m.匹配場處理的距離取值范圍為 0.05～90.0 km，深度取值范圍為10.0～250.0 m，遺傳算法的群體采樣點數為400，將群體分為P組，即P個進程并行計算，每個進程負責400/P個個體，取P= 1，2，3，4.遺傳策略和評價函數按照參考文獻［12］選取.

2臺雙核 PC機通過網絡交換器互聯，安裝WindowsXP操作系統，在MPICH并行環境中對并行算法進行測試.

5.1 實驗1

驗證并行遺傳算法實現匹配場聲源定位的并行性能.按照上面實驗條件，重復10次Monte Carlo試驗，取統計平均，如表1所示.

表1 參數指標及性能評價Table 1 The parameter index and properties evaluation

表1中，隨著并行進程數目的增加，程序運行時間按一定規律遞減;通信開銷時間增加;加速比接近并行運行的進程數，但小于進程數，因為程序的非并行部分和各進程之間的通信開銷占用時間，而且該時間與用于并行計算的時間比例會都隨著進程數目增加而增加，所以導致并行效率隨著進程數目的增加而減小.

圖3給出了采用本文算法與傳統網格算法進行匹配場定位的加速比比較圖.2種方法的加速比都偏離理想情況，但并行遺傳算法的加速比更接近理想情況，因為在通信開銷和非并行程序耗時相同的條件下，并行遺傳算法的并行計算時間要遠小于網格法.由此可見采用并行遺傳算法作為匹配場計算的優化算法與傳統網格計算方法相比，能夠節省約5～8倍的時間.

圖3 加速比比較Fig.3 Comparison of speedup rate

5.2 實驗2

驗證匹配場定位精度，實驗條件不變，進行50次Monte Carlo試驗，取統計平均，定位結果如表2所示.

表2 匹配場定位精度Table 2 The locating accuracy of matched field

由表2可見，采用并行遺傳算法的匹配場定位精度高于串行算法的定位精度;而且定位精度隨著并行計算進程數目的增加而增加，這是因為并行算法中各個進程通過相互通信將各自的局部最優解傳遞給其他進程，統計比較然后在其中找最好的解將其保留到下一代，這樣有助于快速找到更精確解.

實驗表明:采用并行技術進行匹配場聲源定位，可有效的節省計算時間，提高定位精度，并且本文并行遺傳算法的定位性能優于串行遺傳算法定位方法和傳統的網格法.

6 結束語

傳統網格法實現匹配場聲源定位，需要對指定區域內劃分的眾多網格進行大量重復計算，計算量大、耗時長.而本文以遺傳算法作為匹配場處理的尋優算法，無需計算所有網格點的聲壓，而是在指定空間范圍內隨機、均勻地搜索某些采樣點的聲壓，然后進行聲壓場匹配，有指導性地計算靠近實際聲壓源的采樣點聲壓，不必考慮遠離實際聲壓源處的采樣點.并行遺傳算法引入匹配場定位中，突破了單臺計算機計算性能有限的局限，在實際工程計算中具有廣闊的應用前景.使用MPI標準測試函數，在兩個互聯的雙核計算機上，以簡正波理論的聲場計算軟件Kraken為基礎，對匹配場聲源定位進行了測試和相應的分析.仿真實驗表明:采用并行遺傳算法實現匹配場聲源定位，可有效縮短計算時間，逐步滿足定位的作用距離和深度等數據的實時性及精度要求，與傳統網格法相比，在計算時間和加速比方面都具有很大優勢.

［1］楊坤德，馬遠良，張忠兵，等.不確定環境下的穩健自適應匹配場處理研究［J］.聲學學報，2006，31(3):255-262.

YANG Kunde，MA Yuanliang，ZHANG Zhongbing，et al.Robust adaptive matched field processing with environmental uncertainty［J］.Acta Acustica，2006，31(3):255-262.

［2］KILSEOK C，ALAN D，RAJ S.Parallel algorithms for adaptive matched-field processing on distributed array systems［R］.Florida:University of Florida，2003:1-23.

［3］李松斌.基于MPICH平臺的多種群并行遺傳算法［J］.廈門大學學報:自然科學版，2006，45(5):646-651.

LI Songbin.A multiple-population parallel genetic algorithm based on platform MPICH［J］.Journal of Xiamen University:Natural Science，2006，45(5):646-651.

［4］李建龍，潘翔.不確定海洋環境下的貝葉斯匹配場處理［J］.聲學學報，2008，33(3):205-211.

LI Jianlong，PAN Xiang.Bayesian matched field processing with ocean environmental uncertainty［J］.Acta Acustica，2008，33(3):205-211.

［5］楊坤德.水聲陣列信號的匹配場處理［M］.西安:西北工業大學出版社，2008:184-186.

YANG Kunde.The matched field processing of underwater acoustic array signals［M］.Xi＇an:Northwest Polytechnical University press，2008:184-186.

［6］PORTER M.The Kraken normal mode program［R］.Florida:Saclant Undersea Research Centre，2001:1-207.

［7］GEORGE A，GARCIA J，KIM K.Distributed parallel processing techniques for adaptive sonar beamforming［J］.J of Computational Acoustics，2002，10(1)，1-23.

［8］TOLSTOY A.Matched field processing for underwater acoustic［M］.Singapore:World Scientific Publishing Co Pte Ltd，1993:11-41.

［9］馮國富，董小社，胡冰，等.一種支持多種訪存技術的CBEA片上多核MPI并行編程模型［J］.計算機學報，2008，31(11):1-11.

FENG Guofu，DONG Xiaoshe，HU Bing，et al.A MPI parallel programming model for CBEA based on hybrid memory access technology［J］.Chinese Journal of Computers，2008，31(11):1-11.

［10］MORTEZA M，AMIR P，BABAK G.Application of genetic algorithm for optimization of control strategy in parallel hybrid electric vehicles［J］.Journal of the Franklin Institute，2006，343:420-435.

［11］SHISANU T，PRABHAS C.Parallel genetic algorithm with parameter adaptation［J］.Information Processing Letters，2002，82(1):1-8.

［12］梁國龍，董姝敏.相干源盲分離及方位估計的算法研究［J］.哈爾濱工程大學學報，2010，31(11):1478-1484.

LIANG Guolong，DONG Shumin.Study on algorithm of blind separation and DOA estimation aboutcoherent sources［J］.Journal of Harbin Engineering University，2010，31(11):1478-1484.

［13］CHEN Zhifei，SUN Jincai，HOU Hong.Phase difference method for DOA estimation［J］.Journal of Marine Science and Application，2010，4:445-450.