中国指挥与控制学会会刊 
编队应召反潜搜索[1]作为编队反潜搜索的一种常用形式,是在其他兵力的召唤下,前往发现有敌潜艇活动的海域进行的对潜搜索,搜索已被发现但又失去接触的潜艇。搜索编队通常由2艘以上舰艇组成,采取单横队或人字队向丢失点海域进行平行搜索,但由于没有考虑目标的运动特性,发现概率不高。因此运用计算技术和现代搜索理论对编队搜索路径进行规划,提高舰艇编队的搜索效能,具有重要的现实意义。
对于单搜索者搜索路径规划问题,Kierstead[6]首次将遗传算法应用其中,得到了令人满意的搜索方案。随后也有不少研究者通过改进遗传算法来解决此类问题,体现出该方法对于路径规划问题有良好的适应性,但对于多搜索者的路径规划问题,遗传算法缺乏协同机制,存在一定的应用困难。
本文研究了编队应召反潜最优搜索路径规划问题。首先对搜索问题进行了描述,建立了目标的运动模型、搜索者的探测和运动模型。然后在协同进化算法[14]的基础上,提出了一种多种群协同自适应遗传算法(Multiple Coordinated Adaptive Genetic Algorithm,MCAGA),该算法基于环形传递思想,利用种群之间等效距离上的关系,保持种群之间的差异性进化,扩大协同路径搜索范围,同时在种群内部采用分类选择,自适应交叉和变异的遗传操作,动态调节局部寻优和全局寻优的平衡,提高了整体搜索效率。最后通过仿真分析和方法对比验证了该算法的有效性。
1 搜索问题描述
常规的编队应召搜索问题可以描述成如下形式:在T0时刻,有情报显示在某一海域内发现一水下目标在TS点浮出水面并迅速下潜逃离出水点。在T1 时刻位于该海域另一点OS处的舰艇编队接到搜索命令后,开始进行出航准备。在T2时刻编队各舰从OS点出发向TS点机动,各舰航速为巡航速度VC,编队组成密集队形,航向为OS点到TS点的连线方向。在T3时刻编队到达FS点组成单横队,航向航速不变,舰与舰之间的距离为D,单横队以OS点到TS点的连线为轴,使编队各舰位置成轴对称布置。在T4时刻,横队中心到达开始搜索点ES,此时编队各舰以搜索航速VS开始对潜搜索,搜索点ES为目标以最大速度与横队中心相向运动的相遇点。当编队搜索到目标或者搜索行动达到上级要求的搜索时长TS后,编队应召搜索行动完毕。
以3艘舰艇为例,整个过程如图1 所示,但在实际行动的过程中,由于开始搜索延误时间产生的目标信息的模糊性,目标运动要素的不确定性,以及搜索区域的延伸对搜索资源(时间、兵力)的依赖性,使得常规的编队搜索效率不高,要获得较高的发现概率必须投入大量的时间和搜索兵力。
针对这个问题,本文采用最优搜索路径规划方法,根据目标的运动特点来规划整个搜索时长TS内的搜索者路径,使编队的搜索路径能够较大程度地覆盖到潜艇的活动区域,减少重复搜索,提高搜潜效率。
2 目标运动模型
在应召搜索行动中,水下运动目标在发现运动要素没有暴露的情况下,一般仍将继续保持原先的运动规律。从T0时刻开始,目标潜入水下远离TS点作匀速直线运动,航向服从[0,2π]上的均匀分布,速度服从正态分布[2],通过模拟仿真即可获得目标随时间变化的分布情形。
3 搜索者运动模型
4 搜索者探测模型
当目标与搜索者的距离不大于有效搜索宽度w时,探测到目标的概率为1,否则为0。在探测过程中,模型不考虑探测信号延迟,在每次的声呐探测中,搜索者可以立刻得到声呐所判定的目标状态信息,且探测模型为二维模型,不考虑目标深度对探测的影响,声呐探测模型如图3 所示。即在任意t时刻进行一次探测,对于任意一个搜索者(Xi,Yi),要能搜索到目标(X,Y),需要满足如下公式:
5 编队搜索阶段的路径规划
5.1 积累探测概率
FCDP(t)= ×100%,t∈[0,TS]
其中NT表示目标仿真的总数,ND(t)表示已探测到的目标个数。
5.2 路径规划模型
针对编队搜索问题,需要使得编队整体对目标的积累探测概率最大,将其作为目标函数即可建立编队在搜索阶段中关于各舰航向优化的路径规划模型:
max FCDP (X1,X2···Xj···XS,t)s.t.
式中,X1,X2···Xj···XS代表编队中S艘舰艇的路径方案,决策变量Xj=(xj1,xj2,···,xjN)T表示编队中某一舰艇的某一种搜索路径方案;N表示搜索路径分阶段数;(xj1,xj2,···,xjN)T表示搜索路径各阶段的航向θS;FCDP (X1,X2···Xj···XS,t)表示搜索时长t内编队整体的积累探测概率,问题的可行解范围为:
Ψ={X1,X2···Xj···XS|xji∈[0,2π]}
其中1≤i≤N,1≤j≤S,由于FCDP是t的单调递增函数,t取为TS。
6 协同进化自适应遗传算法
协同进化自适应遗传算法(MCAGA)则是在一般进化算法的基础上,考虑种群与种群之间的相互作用,使多个种群向着有利于共同适应的方向进化,提高所有种群的适应能力,提高系统的有序性和多样性,通过在种群间筛选有利于合作的个体进化,有利于整个生态系统的稳定和效能传递。
对于编队搜索最优路径规划过程,可以转化为一个生态系统里(搜潜编队)的多种群(每艘舰艇),在合作机制的作用下,共同进化到最优的生存状态,使得整个生态系统运行效率最大的过程。
6.1 个体编码方案
本文采用实数编码方案,进化过程中,每艘舰艇在搜索时长内的完整搜索路径作为一个种群Popj(k),种群中的每一条染色体 代表一条搜索路径,染色体中的基因由搜索路径中各分阶段的航向构成,可以表示为
Popj(k)={ , ,··· ,···
=[, ,··· ,··· ]
其中k表示进化代数;M表示种群的规模;S表示编队的规模;θ表示航向的基因编码;N表示一条搜索路径的阶段数;Gmax表示种群的最大进化代数;1≤j≤S,1≤i≤M,1≤b≤N,1≤k≤Gmax。
6.2 种群协同方式
设编队最优的积累探测概率为 ,可以通过协同关系下各种群的最优FCDP来确定。各搜索者种群中的个体先通过协同关系相互作用后,再各自独立进化得到最优值。现引入基于环形传递的协同进化思想[12],每个种群在每个进化周期内选出适应度值最优的个体作为局部代表个体,参与到相邻种群的内部进化之中,依次传递形成一个循环,如图4 所示。
6.3 信息交互协同
根据竞争排除原理[15]思想,在编队搜索问题中,需要通过种群之间的信息交互对各搜索者的路径进行差异化处理,减少已探测区域的重复搜索,提高搜索资源的利用效率。对于搜索路径间的相似程度,本文用染色体间的等效距离来衡量。
等效距离为任意两条搜索时长相同的路径上,所有相对应探测时刻点之间距离和的平均值,等效距离越长则路径的相似度越低,距离越短则路径的相似度越高。本文利用等效距离将协同因子ai(t)定义如下:
ai(t)= exp(- )
其中MDi(t)表示搜索者种群P中搜索时长为t的个体i与相邻种群的局部代表个体的等效距离。AMD(P,t)表示整个种群P中的所有个体与相邻种群的局部代表个体的等效距离和的平均值,每个种群的局部代表个体即为每个进化周期初始阶段种群中拥有最大染色体适应度的个体。
由于不考虑通信延迟,各种群可以迅速获得相邻种群的局部代表个体,并与该种群内的待评价个体共同作用,计算出协同关系下的待评价个体的生存适应度,各种群再基于生存适应度来完成自身的进化过程。
当进化满足设定的代数后,各种群输出染色体适应度最大的个体所对应的染色体适应度,以及路径中各分阶段的航向,即为各搜索者基于协同搜索的最优积累探测概率 (Xj,t)和最优搜索路径 ,所有搜索者最优积累探测概率 (Xj,t)的和再减去重复搜索的概率即可得到编队整体的积累探测概率。
6.4 自适应遗传操作
MCAGA算法的每个运算周期内除了考虑群体间的关系进行协同进化外,还要考虑种群内部的遗传进化。为了克服传统遗传算法局部搜索能力差,寻优精度不高,收敛速度慢等缺点,本文针对搜索问题设计了一种改进型遗传操作。首先基于精英保留策略和轮盘赌法改进选择算子,然后通过设定自适应的交叉率Pc和变异率Pm动态调节种群多样性和收敛性的平衡,并通过两种变异算子分别作用于种群中的不同个体完成遗传操作。
6.4.1 分类选择
设一个种群的个体数量为M,每个个体的基因数为N,选择后的个体序列标记为 (C1,C2,···CM),选择过程如下:
1) 将父代中生存适应度最大的个体放入C1中,不参加交叉变异过程,直接遗传到下一代。
2) 将父代中生存适应度靠前的前l个精英个体,依次放入(C2,···Cl+1)中,不参加交叉过程,进行有指向性的更优变异,产生下一代。
3) 将父代的所有个体通过轮盘赌方法依次选出(M-l-1)个个体(当遇到最差个体时,放弃重选),将它们放入到(Cl+2,···CM)中,进行自适应的交叉和变异操作,产生下一代。
6.4.2 自适应交叉
本文采用自适应交叉操作[16]:对于通过轮盘赌法选出来的个体序列(Cl+2,···CM),随机两两配对,自适应交叉操作根据每一对的情况,自适应产生每一对交叉概率Pc,对符合交叉要求的个体对,采用单点策略,交叉点在染色体的 到 处随机选择。通过该自适应策略,生存适应度高于平均生存适应度的个体可以得到保护,而低于平均适应度的个体,则通过交叉进行组合,丰富种群的多样性。
6.4.3 更优变异和非均匀变异
6.5 MCAGA算法流程
步骤1 从搜索阶段开始,每个搜索者初始化搜索时长为TS的路径种群,此时进化代数k=1。
步骤2 评价各种群中个体的染色体适应度,即每个个体的积累探测概率FCDP,每个种群选出染色体适应度最大的个体作为局部代表个体。
步骤3 通过环形传递,每个种群结合相邻种群的局部代表个体,计算协同因子,评价种群中每个个体的生存适应度。
步骤4 种群代数若达到设定的进化代数,输出种群中染色体适应度最大的个体所对应的积累探测概率和个体的分阶段航向,将各种群的最优方案组成编队的最优方案。若未达到进化代数,则各种群继续进行遗传操作,进入步骤5。
步骤5 每个种群根据生存适应度来评价个体,进行分类选择自适应遗传操作。
步骤6 各搜索者种群通过遗传操作得到子代种群,进化代数k=k+1。各搜索者子代种群转至步骤2进行操作。
7 模拟仿真及算法实现
7.1 编队搜索算例描述
假设T0=0时刻(h),有一水下目标在点TS=(100,100)n mile处浮出水面,随后立即潜入水下离开出水点。目标的速度VT(kn)服从正态分布N(7,1),目标的航向θT服从[0,2π]上的均匀分布,通过对目标进行大量仿真可得到目标的运动分布,如图5 所示。
在T1=0.2时刻,位于点OS=(70,70)处的2艘舰艇接到搜索命令后开始出航准备,在T2=0.5时刻编队组成密集队形进入航渡阶段,各舰以最大巡航速度VC=20kn向TS点机动。在T3=1时刻,编队组成单横队,舰与舰之间的距离为D=1.5kn。
根据正态分布的3σ准则,目标的可能最大速度取为 =10kn,则可以确定假设相向运动时目标与编队的相遇点ES。考虑到实施搜索中,舰壳式声呐的有效探测范围为舰艏方向的扇形区域,编队在距相遇点还有w距离的T4时刻位置开始展开搜索。
进入搜索阶段,各舰均以搜索航速VS=15kn向目标可能的逃逸方向搜索,路径方向不定,根据搜索任务要求,各艘舰艇搜索时长均为TS=15h,在时刻T5=T4+TS完成搜索行动。编队在搜索时长内根据协同进化自适应遗传算法规划各舰的搜索路径。
7.2 算法实现与结果分析
进入搜索阶段后,对于任意一艘舰艇,搜索航速VS=15kn,搜索时长TS=15h,搜索路径分阶段时长SteptS=1h,总阶段数NStep=15。探测方面,由积累探测概率公式计算探测效能,且探测间隔ΔtD=0.2h。每个搜索者路径种群的初始化为:每个搜索者均为匀速直线运动,路径航向在初始航向左右各60度的扇面内等间隔选取。
设定算法参数,种群数S=2,每个种群的规模 M=80,染色体长度N=15,最大进化代数Gmax=60,每次进化选出来进行更优变异的父代精英个体数l=19。通过30次独立的协同进化算法仿真实验,得到的最优结果如图6 所示,编队整体积累探测概率为93.82%,其中两条路径的角度解为:
通过对结果和图像进行分析,可以看出基于MCAGA算法的编队路径规划有如下特点:
1)根据搜索者数量自动匹配不同的搜索路径,在有限的时间内,根据目标的运动规律,尽可能使搜索路径覆盖到目标所有的运动范围,并减少对相同区域的重复搜索。
2)由于目标的圆周扩散特性,两条路径对目标可能的扩散范围进行了近似对称地包围,在搜索初始阶段保证了对相向运动目标的覆盖,又确保了搜索中段不漏掉可能向两侧运动的目标,同时对可能一开始就背离编队运动的目标进行了拦截,最后采用近似对数螺旋线的方式来检查之前可能遗漏的目标。
3)文献[17]指出,针对此类问题基于遗传算法的求解路径近似于对数螺旋曲线,而且由于目标分布的时空对称性,对于单搜索者路径,存在顺时针搜索和逆时针搜索两种情况。而本算法对于两个搜索者路径的优化,正好可以使得两个搜索者从顺时针和逆时针方向同时对目标进行类似对数螺旋线的搜索,进一步证实了该方法在求解编队搜索问题上的合理性和有效性。
7.3 方法对比与性能验证
对于常规的编队应召搜索,可以通过搜索能力计算公式[20]来确定编队对目标的搜索概率,以此方法来对搜索资源进行调整,满足任务要求。
P发现=1-exp
其中U搜索为编队的整体搜索能力,T延误为编队开始展开搜索前延误的时间,T搜索为编队搜索阶段所用的时长,V潜艇为估计的潜艇最大速度。在保持之前算例相同的参数设定条件下,可以得到2艘舰艇在常规搜索模式下,对目标的探测概率为70.34%,当在相同时间内组织5艘舰艇进行应召搜索时,对目标的探测概率为91.72%。而采用本文优化方法的算例所得到的编队搜索路径,在相同条件下,只需要2艘舰艇便可以达到常规方法5艘舰艇同时搜索的效果,表明该优化方法有效提高了搜索效率,降低了对搜索资源的依赖程度。
对于2艘舰艇以上的多艘舰艇编队搜潜,运用MCAGA算法同样能得到类似的优化效果。通过各30次的独立实验,3艘和4艘舰艇优化后的路径整体积累探测概率分别为95.79%和97.43%,由图7 、8可以看出,通过MCAGA算法编队各舰的搜索路径均能够做到对目标运动分布区域的大范围覆盖,同时在一定程度上减少了各搜索路径之间重复搜索的区域。
7.4 不同速度分布目标的搜索问题
通过对3艘舰艇和4艘舰艇的搜索路径图进行分析可以看出,虽然能得到比较高的积累探测概率,但由于目标分布的时空对称性,编队中舰艇路径还是存在较多的搜索重复区域,相比2个搜索者的路径优化效果,3个搜索者和4个搜索者的路径优化效果提升程度并不算太大,对搜索资源的利用并不充分,2个搜索者能够保证足够大的搜索效果。
实际反潜搜索行动中,很多情况下不能准确判断目标的速度范围,同时搜索兵力的探测能力和航行能力也可能不一致,所以对于2艘以上的编队应召搜索问题可以采取对目标可能的不同速度分布情形分别展开搜索的方法。假设目标可能服从N(12,1)和N(6,1)两种正态分布,以4艘舰艇组成搜索编队,其中2艘搜索能力强速度快,2艘搜索能力弱速度慢,利用MCAGA进行路径规划,可以安排编队中速度快,探测能力强的舰艇对目标速度高的分布区域进行搜索,安排速度慢探测能力弱的舰艇对目标速度低的分布区域进行搜索,使搜索路径与目标的速度分布相匹配,在有限的搜索时长内进一步提高搜索资源的利用效率。
通过计算,利用分速度层次搜索的方法,4艘舰艇的整体搜索概率为95.44%。 从搜索路径图9 可以看出,相比4艘舰艇同时搜索目标的一种速度分布情形,搜索路径覆盖的探测区域进一步得到了扩大,同时减少了路径之间的重复搜索区域,并保持了较高的搜索效能,因此编队基于MCAGA算法对目标的不同速度分布情形分别进行反潜搜索的方法,能够给无法准确掌握目标速度信息的反潜搜索问题提供一种比较合理的思路,有助于编队应召反潜搜索方法研究的丰富和发展。
8 结束语
本文针对水面舰艇编队协同应召搜索运动目标的最优路径规划问题进行了研究,根据种群之间的相互作用和种群内部的进化关系,提出了一种多种群协同进化自适应遗传算法。在整体进化方面,采用环形传递的协同方式,保证了各种群进化的差异性,增强了种群间的多样性;在局部进化方面,对各种群内部采用分类选择进化和自适应的交叉变异操作,有针对性地挑选和产生较优秀个体,动态调节多样性和收敛性的平衡,增强了算法的稳定性和寻优能力。在仿真实验中运用该方法得到了比较合理的编队应召搜索方案,提高了编队的搜索效能,对多搜索者协同搜索路径控制研究具有一定的应用价值和启发意义。