匹配场目标定位的并行遗传算法实现

赵博，董姝敏，李运赫，朴胜春

(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.