郭文强, 李子展, 候勇严, 薛博丰

(1.陕西科技大学 电子信息与人工智能学院, 陕西 西安 710021; 2.陕西科技大学 电气与控制工程学院, 陕西 西安 710021)

0 引言

舰艇编队作为海上军事力量的直接体现,为其提供必要的物资保障对于增强舰艇编队的作战能力、扩大舰艇编队的作战半径来说是不可或缺的.如何合理规划物资补给路径,提高物资补给效率,对于提升舰艇编队作战能力具有重大意义[1].无人机基于其自身的多功能、高移动、易部署和低成本等优势,被用作空天地海一体化网络架构中空域辅助平台,在越来越多的场景中承担重要角色[2].

驱逐舰、护卫舰、航母等构成的舰艇编队中的补给舰,其特点是吨位较大(以美军供应级支援舰为例,该级舰满载排水量近5万吨)、专业舱室多、所带物资齐全、补给设施配套,既有淡水、粮食、蔬菜、水果等生活物资,也有柴油、航空燃油、弹药等作战物资,还有各种用于应急抢修的备品、备件.它能在通过“吞吐”大量物资,对各类舰艇进行补给.

规模较大的舰艇编队远航,需要的补给舰往往不止一艘.目前针对舰艇编队的物资补给规划研究主要利用“补给舰”对舰艇进行补给,同时构建约束规划模型并对其进行求解得出最优补给方案.文献[1]构建了以补给舰艇数量最少和补给时间最短为目标的多目标约束规划模型,并利用改进后的遗传算法对其进行求解;文献[3]构建了以最小化补给成本为目标,以补给水平为约束的分段式补给模型;文献[4]建立了以最大化作战效能为目标的补给规划模型并使用模拟退火算法对其进行求解.然而,在浪、风、涌等复杂海况下,舰艇操作难度大,稍有不慎就会出现撞船事故[5].

相较补给舰,无人机作为一种补给装置,其智能性与安全性水平不断快速提升,装置结构易于标准化,批量化设计、生产使其造价较低,可减少补给设备种类、降低补给成本、方便操作与维修的同时,另外无需要飞行人员,所以最大可能地保障了人的生命安全.上述突出的优点可使无人机保障系统达到最佳补给效果.

但现有文献中利用无人机集群对舰艇编队进行物资补给的研究较少,使用无人机进行物资补给具有在特殊环境下可以实现人员零伤亡、自身极强的隐蔽性等优势.本文探讨了利用无人机集群针对舰艇编队进行物资补给规划的问题,使用非线性自适应遗传算法(Nonlinear Adaptive Genetic Algorithm ,NLAGA)对构建的多约束条件下的物资补给规划模型进行求解,得到所需的无人机群数量、最优补给路径以及最小时间成本.

1 面向舰艇编队的物资补给规划模型

1.1 问题描述

假设现有一个由M架无人机组成的无人机集群,计划利用其对某舰艇编队进行弹药补给(该舰艇编队由N艘舰艇组成).规定所有无人机均从补给中心起飞,并且每架无人机的补给能力有限,无人机的补给路线长度满足各自通航距离.同时,由于通行时刻不同导致同一路径上无人机的行驶速度也不同.无人机从物资补给中心出发,在规定时间窗内对舰艇编队进行补给,完成对所有舰艇的补给后返回物资补给中心.每个舰艇都有设定的服务时间窗(仅在此时间范围内能进行补给作业)和不同的物资需求量,目标是确定无人机群所需无人机数量,并确定补给路线,用最少的时间完成所有补给任务,实现补给成本最优的目标.

1.2 无人机飞行时间成本

无人机在执行任务时的飞行时间与无人机的飞行速度以及舰艇之间的距离相关.飞行时间Tf为:

(1)

1.3 补给作业时间成本

到达舰艇后的物资准备时间Tp为:

(2)

式(2)中:pi为舰艇i的物资准备时间.

补给花费时间Ts为:

(3)

式(3)中:si为无人机在舰艇i的物资补给作业所花费的时间.

综上,无人机的总补给作业时间成本Tw为:

Tw=Tf+Tp+Ts

(4)

1.4 时间惩罚成本

(5)

令M2表示延误到达的惩罚系数,则延误到达的时间惩罚成本为:

(6)

因此考虑无人机允许补给作业时间窗的时间惩罚成本Tpc为:

Tpc=Cae+Cal

(7)

1.5 面向舰艇编队的无人机物资补给规划模型

考虑将无人机的作业时间以及时间窗约束而产生的惩罚成本,同时将无人机作业时间窗、安全返航、物资需求量与无人机总最大载重量等约束条件,本文构建的面向舰艇编队的无人机物资补给规划模型如下:

(8)

2 求解补给规划问题的NLAGA算法

对于每架无人机来说,补给任务可视为带时间窗限制的车辆路径规划问题,此类问题已被证明是NP(non-deterministic polynomial,非确定性多项式)[8]难题.启发式算法是目前解决NP难题的有效方法之一[9].在这些启发式算法中,遗传算法(Genetic Algorithm ,GA)和改进的遗传算法因其快速收敛而被广泛采用,故本文采用遗传算法对物资补给规划路径进行染色体(基因)编码,并对物资补给规划模型进行求解.

遗传算法本质上是一种通过模拟自然进化来搜寻最优解的方法,其中交叉、变异概率(Pc、Pm)对算法的性能起着决定性的作用.传统GA中交叉、变异概率为定值,在进化后期容易对最优解造成破坏,因此可能会导致早熟收敛现象的产生.文献[10]提出了一种改进的自适应遗传算法(Improved Adaptive Genetic Algorithm ,IAGA),其中交叉、变异概率计算方法如下:

(14)

(15)

式(14)、(15)中:fmax表示种群中染色体适应度最大值,f代表交叉操作染色体中的适应度值,fa代表种群染色体适应度均值,f′代表待变异操作染色体的适应度值,其它参数常取Pc1=0.9、Pc2=0.6、Pm1=0.1、Pm2=0.01.

IAGA可以通过自适应调节概率来保留最优解,在一定范围可缓解GA早熟收敛现象.但在进化中段,种群中染色体的交叉、变异概率普遍很低,从而可能导致交叉、变异操作失效,出现进化停滞的现象.为了减少此类风险,本文对IAGA进行了进一步的改进.

2.1 非线性概率函数

本文引入Sigmoid函数[11]设计了一类非线性的交叉概率和变异概率计算函数,分别表达如下:

(16)

(17)

(18)

2.2 舰艇编队的无人机物资补给规划算法-NLAGA

基于非线性概率函数设计的补给规划模型的NLAGA算法步骤如下:

第1步:确定各舰艇物资需求量Qi(i=1,2,…,N)、舰艇坐标、舰艇补给时间窗、补给作业时间,惩罚系数M1、M2,输入每架无人机的最大补给量、速度范围,以及进化算法操作系数A、B、C,最大迭代次数MaxGen和寻优收敛误差ε.

第2步:根据公式(8)至(13)描述的规划模型,利用文献[12]的方法将其表示为2N条补给规划的初始染色体.

第3步:令迭代次数iter=1.

第4步:根据公式(8)计算每条染色体的适应度函数,并选择目标函数最小的Ztemp.

第5步:利用式(14)计算交叉概率并执行交叉操作[13].

第6步:利用式(15)计算变异概率并执行变异操作[12],形成新的染色体种群.

第7步:根据公式(8)计算每条染色体的适应度Znew.

第8步:若Znew

第9步:若Znew-Z*<ε,则跳转至第11步;否则iter=iter+1,执行第10步.

第10步:若iter=MaxGen,进入第11步;否则返回执行第4步,继续进化寻优.

3 实验结果与分析

3.1 算法性能测试

为了验证NLAGA算法在求解补给规划问题中的优越性的性能,本文将无人机补给规划问题抽象为带时间窗约束的车辆路径问题(VRPTW)并使用经典的Solomen数据集[14]中r101的算例进行测试.将NLAGA算法与文献[13]中所提出的AGA算法以及IAGA算法进行对比.

61个待补给点位置已知,所需物资量均为Qi=150 kg(i=1,2,…,61),时间惩罚系数M1=10、M2=100;无人机速度vmin=0 km/min,vmax=0.8 km/min,单架最大补给量50 kg;最大迭代次数:MAXGEN=6 000;步长λ=200;交叉、变异系数:A=4、B=6、C=0.55;为了达到相同的迭代次数,实验中将收敛误差ε设为0.其它参数选择参考同文献[13].

仿真平台为Matlab版本R2016a,所有测试都在配置了2.3 GHz Intel Core i10处理器和8.0 GB内存、Windows 10系统的计算机上进行.

为了减少随机性对实验结果的影响,实验中将不同求解方法独立运行15轮,记录其均值.求解后该补给任务均需15架无人机参与补给任务,得到目标函数值变化曲线如图1所示.

图1 目标函数值变化曲线

不同算法求解的最优值、均值以及方差,分别如表1、表2、表3所示.

表1 不同算法求解的目标函数最优值

表2 不同算法求解的目标函数的均值

表3 不同算法求解的目标函数的方差

由图1可看出,在本实验中,不同算法求解在迭代至3 500轮时寻优过程趋于稳定.在相同迭代次数时,由表1至表3可知,利用NLAGA得到的最优解及其均值、方差均优于AGA和IAGA方法.

分析可知:在计算机模拟随机取值条件下,NLAGA中的非线性概率函数可以在进化中段,通过本文设计的非线性函数的拉伸,扩大了概率的取值范围,有利于采样到更丰富的交叉和变异概率值,提高了算法在求解空间的寻优探索能力,有利于保留最优解,有效避免了进化停滞的现象.

3.2 面向舰艇编队的无人机物资补给规划实验与分析

本实验针对某舰艇编队的补给规划任务进行了求解.假设该舰艇编队的待补给舰艇数量为15艘.补给中心的相对坐标为(660,750)km,现利用相同性能的无人机执行补给规划任务,飞行速度为vmin=0 km/min,vmax=0.8 km/min,此外假设每艘舰艇所需的物资准备时间pi均为5 min(i=1,2,…,N),其他参数如表4所示.利用本文提出的NLAGA算法求解该问题,将收敛误差ε设为0.001,其他参数取值同3.1.

表4 补给任务相关参数

利用本文提出的NLAGA算法解算出完成该补给规划任务需要5架无人机,完成补给规划任务最短耗时为291.309 1 min.

完成本次补给规划任务的无人机群最优补给路径、目标函数值及规划耗时的变化分别如图2和图3所示.

图2 无人机补给路径示意图

图3 目标函数值及规划耗时变化曲线

4 结论

本文针对无人机集群对舰艇编队的物资补给规划问题,以舰艇补给时间窗、无人机最大载重量等为约束条件,构建了无人机集群补给规划模型.在自适应遗传算法的基础上,设计了非线性的交叉概率函数和变异概率函数,并提出了一种无人机物资补给规划算法NLAGA.实验结果表明:NLAGA法的性能要优于AGA和IAGA方法,可有效地解决无人机集群对舰艇编队的物资补给规划问题,为实现舰艇编队的物资补给提供科学的决策支持.