海军大连舰艇学院室，辽宁 大连

收稿日期：2021年12月24日；录用日期：2022年1月14日；发布日期：2022年1月27日

摘要

水雷具有低成本、高杀伤的特点，合理运用水雷进行作战将产生巨大的杀伤效果。本文基于协同进化理论，从“水雷布设”和“航迹规划”两方面考虑，协同进化，完成迭代，形成“对抗–筛选–进化”的闭合循环，从而建立了舰艇毁伤期望模型，作为水雷杀伤力的评估。本文主要采用遗传算法，采用分段式编码策略，能够较精确地表征水雷以及航迹的要素，同时引入了模拟退火算法，以加强全局的收敛性。

关键词

协同进化，水雷布设，航迹规划，遗传算法，模拟退火算法

The Research of Torpedoes Deployment Based on Coevolution

Xiaolong Wu, Yue Yang

Dalian Naval Academy, Dalian Liaoning

Received: Dec. 24^th, 2021; accepted: Jan. 14^th, 2022; published: Jan. 27^th, 2022

ABSTRACT

Torpedoes have the characteristics of low cost and high killing. Rational use of torpedoes will produce great killing effect. Based on the coevolution theory, this paper considers “torpedoes deployment” and “track planning” at the same time and forms a closed cycle of “confrontation-screening-evolution”. Consequently, the ship damage expectation model has been established as the evaluation of torpedoes lethality. This paper mainly adopts genetic algorithm and segmented coding strategy, which can accurately characterize the elements of torpedoes and tracks. Additionally, simulated annealing algorithm is introduced to strengthen the global convergence.

Keywords:Coevolution, Mine Deployment, Track Planning, Genetic Algorithm, Simulated Annealing Algorithm

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

布雷作战，是以水雷武器达成攻防作战目的的一种海战样式。水雷武器是一种成本较为低廉、杀伤能力较为突出的作战武器，少量水雷得到合理运用即可对敌方产生强大威慑作用 [1]。随着科学技术的创新发展，水雷的种类样式日新月异，水雷战斗力将会更加突出，因此研究水雷作战和反水雷作战意义重大。在水雷布设问题研究领域中，许多学者将启发式算法运用于水雷布设问题的研究，文献 [1] 中着重研究沉底水雷毁伤能力，文献 [2] 运用了蒙特卡洛算法进行二维水雷空间的布设探，具有一定的启发价值。

而港口雷障布设 [3] 问题是一类陷阱部署问题，传统的研究陷阱布设问题，由于建模难度复杂，考虑因素较多，通常采用智能算法进行陷阱部署方案的选择，现代陷阱布设问题大多采用的智能算法，如遗传算法、模拟退火算法等。传统的航迹规划问题，是一类在避障模型基础上的TSP模型，通常也采用智能算法进行计算。

本文结合协同进化理论，利用遗传算法和模拟退火算法，形成了一种基于协同进化理论的遗传模拟退火算法。同时从水雷布设方角度和舰艇出航方角度考虑，采用“协同进化”的思想，将“布雷方”和“出航方”视作两个互相“对抗的物种”，进行相互筛选，将对立方适应力较差的个体筛选剔除，与此同时自身种群也将依照种群进化的原则不断地迭代，形成较为“对抗–筛选–进化” [4] 的闭合循环，建立了舰艇毁伤期望模型作为水雷杀伤力的考量。

2. 算法介绍

2.1. 协同进化理论 [5]

由于生物个体的进化过程是在其环境的选择压力下进行的，而环境不仅包括非生物因素也包括其他生物。因此一个物种的进化必然会改变作用于其他的生物的选择压力，引起其他生物也发生变化，这些变化又反过来引起相关物种的进一步变化，在很多情况下两个或更多的物种单独进化常常会相互影响形成一个相互作用的协同适应系统。例如，猎豹和羚羊的协同进化关系，羚羊会不断进化提升自身奔跑的速度以此来逃避猎豹的追捕，而猎豹也会相应进化提升自己的速度以此来捕猎羚羊。

2.2. 遗传算法 [6]

遗传算法(GA)是一种智能优化算法，该算法基于进化论：首先确定研究对象，明确基因编码策略，产生初始化种群；其次，根据优化对象建立相应的优化模型，并确定算法迭代次数；再次，通过选择，交叉，变异改变种群中所有个体的基因信息，并不断重复迭代；最后，当算法的迭代次数达到规定次数之后，输出目标函数的全局最优解和最优值。交叉算子为该种算法中的核心算子，模拟生物进化当中基因的交叉结合。变异算子是该种算法中的辅助算子，能够在迭代的中后期更好地寻找满意解，但是变异算子在前中期会对种群整体产生震荡效应。

2.3. 模拟退火算法 [7]

模拟退火算法(SA)来源于固体退火原理，将固体加温至充分高，再让其慢慢冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而慢慢冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为 $e^{\frac{\Delta E}{kT}}$，其中E为温度T时的内能，为 $\Delta T$ 其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数 $e^{\frac{\Delta E}{kT}}$，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子 $\Delta t$ 、每个t值时的迭代次数L和停止条件S。该算法的特点在于能够在与选择的全局性较好，缺点在于容易陷入迭代速度较慢，在运算量较大的情况之下，难以快速的求解最优解。

3. 基于协同进化的“布雷–避雷”模型

水雷的港口封锁 [8] 是一类火力布设、障碍部署问题，需要综合考虑封锁海区的水深，地质，以及所使用的水雷的类型，定次，以及水雷布设的三维坐标，舰船航迹规划 [8] 问题一类典型的带有约束的TSP和避障问题，需要综合考虑舰船的旋回半径，前进速度，吃水深度，以及编队抗击打能力。港口布雷与航迹避雷是两种需要对立考虑的问题，基于协同进化的理论，同时从两个角度出发，相互进行筛选与进化，能够使布雷方案和航迹规划都能更快地达到最优理想解。如同自然界中猎豹与羚羊的协同进化，使得猎豹和羚羊不断淘汰速度较慢的个体，从而筛选进化得到速度较快的个体。

3.1. 舰艇毁伤期望与适应度函数 [2]

一般假设舰船单艘离开港口，以保证每支舰船在港口直航时的机动性和整体舰队出港的有序性，假设舰队中先出发舰船触雷后将会对之后舰船发出警告。本文引出舰船毁伤期望 $E{N}_{hc}$ 作为评判布雷方案和航迹规划的标准。

$E{N}_{hc}={\displaystyle \underset{k=1}{\overset{n}{\sum }}{P}_h^{\left(k\right)}}$ (1)

其中第k艘舰船遭遇水雷障碍时至少被一枚水雷毁伤的概率为 $P_h$，在本文中，舰船毁伤期望 $E{N}_{hc}$ 与水雷毁伤的概率为 $P_h$ 满足上式(1)。k表示舰船编号，n为舰队中总舰船数。舰艇毁伤期望主要取决于水雷动作概率 $P_d$ 及水雷命中目标舰只的概率 $P_m$，于是本文给出式(2)表达第k艘舰船遭遇水雷障碍时至少被一枚水雷毁伤的概率 $P_h$ ：

$P_h^{\left(k\right)}\left(x\ge 1\right)=1-{\displaystyle \underset{i=1}{\overset{2}{\sum }}{a}_k^{\left(i\right)}{\left(1-P_d{P}_m\right)}^{n_k^{\left(i\right)}}}$ (2)

下面对式(2)中 $a_k^{\left(i\right)}$ 和 $n_k^{\left(i\right)}$ 给出具体定义：

$\begin{array}{l}{a}_k^{\left(2\right)}=E{M}_k-\lfloor E{M}_k\rfloor \\ a_k^{\left(1\right)}=1-a_k^{\left(2\right)}\\ n_k^{\left(1\right)}=\lfloor E{M}_k\rfloor \\ n_k^{\left(2\right)}=n_k^{\left(1\right)}+1\end{array}$ (3)

其中， $E{M}_k$ 为第k艘舰船遭遇水雷障碍的有效水雷期望值，即初始定次k为且具有战斗能力的水雷数量的期望，其中 $E{M}_k$ 满足如下公式成立：

$E{M}_k=D_k{\lambda }_k$ (4)

$\lambda$ 即为沿舰船航行正面方向上的水雷密度，满足：

${\lambda }_j=\frac{N_{mj}}{w}$ (5)

其中 $N_{mj}$ 即为引信定次为j的水雷数量(j = 1, 2, 3, 4)，而第k艘舰船的水雷有效作用宽度 $D_k$ 则定义其满足：

$D_k=m{P}_{k}w$ (6)

其中 $P_k$ 的具体含义为：第k艘舰船经过水雷障碍区时被水雷有效作用区至少覆盖一次的概率。一组舰艇编队的“航迹规划”包含k次单艘舰艇的“航迹规划”。m为水雷毁伤系数，与水雷种类有关。

舰艇毁伤期望的建立具有双向性，既可以立足于“布雷方”，又可以立足于“航迹方”，用以判断方案的好坏。本文在舰艇毁伤期望的基础上，建立适应度函数。立足于“布雷方”，舰艇毁伤期望越大越好，所以适应度函数取舰艇毁伤期望，立足于“航迹方”，舰艇毁伤期望越小越好，适应度函数取舰艇毁伤期望的倒数。

3.2. 种群初始化及质量

为了更好地贴近实战化，在初始化“航迹”种群时，一般选择某一个港口的出港计划航线，小幅度变更初始位置以及转向点(类似与模拟退火算法的小幅度振动)形成初始种群。初始化“布雷”种群时依据给定的港口海域情况以及水雷的种类以及定次，随机产生布雷方案即“布雷”种群，其中包括三维坐标以及定次种类。

由于舰艇毁伤期望需要同时考虑“布雷方”和“航迹方”，因此以舰艇毁伤期望为依据的个体适应度不能再作为种群进化程度的标准。因此，有必要引入种群质量与进化限度的概念。种群质量，作为判断种群整体水平的标准，可采用该种群所有个体的适应度的平均值。进化限度，即进化后的种群质量与进化前的之差，再与进化前种群质量做比，作为进化停止标准。

3.3. 协同进化策略

依据舰艇毁伤期望的计算方法，建立适应度函数作为个体选择标准。初始化产生“布雷种群”和“航迹种群”之后，进行首次选择，以确定初代种群质量。在利用遗传算法进行仿真时，由于“布雷种群”中个体的基因数量较多，本文采用了分段基因的编码策略，能够更加全面地表述水雷个体的特征 [9]，选择“布雷种群”和“航迹种群”时，采用“遍历互选”策略，“布雷种群”的所有个体与“航迹种群”某一个体进行匹配，计算相应的舰艇毁伤期望以及该个体的适应度。同时，“航迹种群”中所有个体与“布雷种群”中某一个个体进行匹配，计算相应的舰艇毁伤期望以及该个体的适应度，进而计算该种群质量。当种群进化限度达到某一标准时，停止进化。

由于个体中的部分“优势”基因可能在进化的前中期难以体现，所以处于“相对弱势”不能够提高种群质量 [10]。为了尽可能避免这种情况的发生，本文在确定该个体是否会被淘汰时，采用模拟退火算法在进化前期存留“潜力”个体，保存其“优势”基因，在进化后期提高选择标准，选择优势个体，提升种群质量。

具体的算法框架可见下图1。

图1. 算法框架图

4. 仿真实验及分析

假设某海域红方展开港口水雷封锁作战，港口可行海域宽度为1000米，长度为2000米，平均深度为50米，需要在该海域布设不同型号(型号1-3)，不同定次(定次1-4)的水雷共计10颗，考虑如何布设能够使杀伤效果最好。与此同时，蓝方需要在此海域出行4艘航行舰船，考虑如何规划航线能够使得航行舰船损失最小。

本文采用协同进化策略、遗传算法和模拟退火算法来进行对比研究。

情况一：给定蓝方初始计划航线。将本文算法与传统模拟退火算法及遗传算法的优化实验结果作对比，具体比较结果如表1所示。

表1. 本文算法与传统模拟退火算法及遗传算法的优化对比

图2. 给定计划航线下的协同进化策略航迹规划以及布雷方案

情况二：未给定初始计划航线。将本文算法与传统模拟退火算法及遗传算法的优化实验结果作对比，具体比较结果如表2所示。

表2. 本文算法与传统模拟退火算法及遗传算法的优化对比

图3. 未给定计划航线下的协同进化策略的航迹规划以及布雷方案

由表1和表2可知，该协同进化策略在已知计划航线的情况下与传统的模拟退火算法，遗传算法求解出来的结果差异度不大，由于算法本身相较于单纯的遗传算法和模拟退火算法更为复杂，所以在运行时间上更长，但是协同进化策略在迭代次数上更具优势，能够在更少的迭代次数的情况之下找到满意解。

除此而外，由图2和图3协同进化策略对于初始条件的要求较低，在未给定计划航线的情况之下，能够更加全面的寻找全局满意解，在这种情况之下，遗传算法以及模拟退火算法由于难以找到较好初始解，难以找到全局满意解。综上可知，协同进化策略在弱化初始条件的情况之下，具有更好的适用效果。

5. 总结

针对水雷布设问题，本文基于协同进化理论的思想，同时从“布雷方”和“航迹方”两个角度进行分析讨论，构成了“对抗–闭合–筛选”的闭合循环，能够更加快速地接近最优解，并且弱化了初始条件的选取，使得该模型在应用上更具有广泛性。

本文构建了舰艇毁伤期望模型，同时考虑“布雷方”的水雷毁伤效能和“航迹方”的航迹规划合理性，使得两个“物种”的“对抗”有了统一的筛选标准，能够更好地进行迭代选取。在后续的研究中，将考虑更多的随机因素，不断完善数学模型、优化算法，对实际水雷作战提供指导意义。

文章引用

伍晓龙,杨 悦. 基于协同进化的水雷布设问题的研究
The Research of Torpedoes Deployment Based on Coevolution[J]. 应用数学进展, 2022, 11(01): 334-341. https://doi.org/10.12677/AAM.2022.111041

参考文献