基于元胞自动机的冲突对抗模型问题研究

Research on Interception Force Deployment Based on Genetic Algorithm

摘要: 港口的封控作战筹划问题是保护我方海上运输线和生命线，增加发现敌对船只的可能，从而减少敌对势力对我方利益威胁，对港内安全与稳定有着重要影响，甚至关乎临战状态下港口保卫的重要问题。本文针对现阶段港口封控兵力规划存在效率低、耗时长、对突发情况应对能力低等问题，通过海警船和护卫舰在拦截行动中的优化运用，利用元胞自动机和马尔可夫过程的冲突对抗模型，从复杂系统和随机过程的特征去分析、建模，并求解拦截率最高规划，以最优化解决封控兵力规划问题。该方法具有兵力规划快速高效、精准可靠、行动要素覆盖全面等特点，在反潜和防空领域有重大意义。

Abstract: The problem of port containment operation planning is to protect our sea transportation line and lifeline, increase the possibility of finding hostile ships, so as to reduce the threat of hostile forces to our interests, has an important impact on the security and stability of the port, and even relates to the important issue of port protection in the state of war. Aiming at the problems of low efficiency, long time consuming and low ability to respond to emergencies in port force planning, we use the optimized use of coast guard ships and frigates to establish a conflict confrontation model. Cellular automat and Markov process are used to analyze, model and solve the maximum interception rate planning problem from the characteristics of complex systems and random processes, so as to solve the containment force planning problem. This method has the characteristics of rapid, efficient, ac-curate and reliable force planning and comprehensive coverage of operational elements, which is of great significance in the field of anti-submarine and air defense.

1. 引言

封控拦截的冲突对抗处置是港口封控作战研究的热点问题。目前，对于突击事件的处置问题，可以利用元胞自动机模型 [1] [2] [3]，建立基于元胞自动机和马尔可夫过程 [4] [5] 的冲突对抗模型。具体来说，利用精确的定位信息利用元胞自动机的自适应变化情况，以马尔可夫过程为变化的概率分布，建立有向元胞自动机运动规则，确定有向元胞自动机的运动方向，从而构建了无人机空中自动导航的算法，该算法的仿真在复杂环境中，能够规避障碍物，自动生成飞行路径，从而得到最佳的兵力调整和拦截策略方案。

2. 冲锋和拦截兵力调配的模型

假设港口对外航线位于以港口为圆心、方位在与正北方向顺时针夹角20˚~70˚之间的扇形区域，驶向某港的商船航向均指向圆心，拦截处置区为图示ABCD，如图1所示。

Figure 1. Schematic diagram of port

图1. 港口示意图

针对拟进港商船全部完成类型识别后的处置问题，处置规则是：对I类商船予以放行；对II类商船，派出护卫舰或海警船，迫其停船、大幅度改变航向或掉头；对III类商船需实施临检拿捕，由护卫舰将其拦截。拦截处置过程中，可能会有个别商船抱有侥幸心理，在临近CD线时突然加速到最高航速发起冲锋，试图逃避检查，冲过红方拦截处置区(称为突击事件)。我方在第一时间发现其企图，调整封控兵力实施拦截。对正在执行III类船处置任务的舰船，不能停止当前任务；对正在执行II类船处置任务的舰船，必要时其剩余任务可转交其它舰船执行。拦截或追击过程中，可能会涉及到转向能力。船舶的转向能力表征为其旋回性能，即下达转向命令后航向改变180˚ (掉头)所需时间及旋回直径，如下图2所示。

Figure 2. Steering cycle diameter of the ship

图2. 船舶的转向旋回直径

在处置商船的过程中，实际发生的突击事件至多一次，但无法确定是哪一艘会发起突击。针对这一类突发事件要考虑地方有：海警船加速，具体是那一只商船具有概率性，为了实现给出双方的兵力调整和拦截策略，需要考虑如何分析给定的双方动态。因此，为了实现双方的冲锋和拦截兵力调配问题，需要利用模拟分析的方法模拟双方的决策过程，并从而给出对应的最好的调整和应对方案。

建立基于元胞自动机和马尔可夫过程的冲突对抗模型，利用元胞自动机的自适应变化情况，以马尔可夫过程为变化的概率分布，根据题意条件建立模拟分析的规则。通过迭代分析，可得到最佳的兵力调整和拦截策略方案。根据分析，及时按照方案进行拦截，将不会影响固有的任务完成情况。

3. 马尔可夫模型

马尔科夫是一种预测事件发生的概率的方法，它基于马尔科夫链，根据事件目前的状况预测其将来各个时刻变动状况。

马尔可夫过程是一个满足马尔可夫性的随机过程。马尔可夫过程是以俄罗斯数学家安德烈·马尔可夫命名的。马尔可夫链是一类马尔可夫过程，在现实世界中有着广泛的应用。谷歌的页面排名算法是基于马尔可夫链的，马尔可夫链可以应用于语音识别、统计力学、排队论、经济学等领域。

马尔可夫链是一个用来描述连续事件序列的模型，其中一个事件的概率或机会只取决于它之前的事件。如果一系列事件表现出对前一状态依赖的马尔可夫性，那么这个序列在本质上就叫做马尔可夫过程。在马尔可夫链中，过程的下一个状态只取决于前一个状态，而不取决于事件的先前序列。对于一个随机过程 $\left\{x_n\right\},n=0,1,2,3,4$。它具有离散的状态空间，并满足马尔可夫性，这是一个马尔可夫链。由于这个随机过程服从马尔可夫性，过程未来状态的条件概率分布只取决于当前状态。一阶马尔可夫过程是一个随机过程，其中未来状态仅仅依赖于当前状态。一阶马尔可夫过程通常简称为马尔可夫过程。如果它是在一个离散的空间，它被称为马尔可夫链。

现将马尔科夫链应用到本文中，首先要对所有I、II、III商船进行了编号，通过给定的坐标信息，采用遗传算法或者蚁群算法对商船分类识别后，将要对其中的III类船进行拦截。

III类商船状态改变概率：商船逃避检查的发展过程中，从某一种状态出发，到下一时刻转移到其他状态的可能性。由状态 $E_i$ 转为 $E_j$ 的概率记为

$•$

III类商船状态转移概率矩阵：商船逃避检查的发展过程有N个可能状态， $E_1$， $E_2$， $\cdots$， $E_n$。记为 $P_{i,j}$ 状态 $E_i$ 转为 $E_j$ 的概率，则

$P=\left(\begin{array}{cccc}{p}_{1,1}& p_{1,2}& \cdots & p_{1,n}\\ p_{2,1}& p_{2,2}& \cdots & p_{2,n}\\ ⋮& ⋮& \ddots & ⋮\\ p_{n,1}& p_{n,2}& \cdots & p_{n,n}\end{array}\right)$

P为状态转移概率矩阵，其中 $P_{i,j}$ 满足条件

$\{\begin{array}{l}0\le P_{i,j}\le 1\left(i,j=1,2,\cdots ,n\right)\\ {\displaystyle \underset{j=1}{\overset{n}{\sum }}{P}_{i,j}}=1\left(i,j=1,2,\cdots ,n\right)\end{array}$

在这里，设 $P_{i,j}$ 为商船从i区域转移到j区域的概率，则每一个区域间的转移概率的集合为概率矩阵。如图3所示。

$\begin{array}{l}\begin{array}{cccc}& s_1& s_2& s_3\end{array}\\ \begin{array}{c}{s}_1\\ s_2\\ s_3\end{array}\left[\begin{array}{ccc}0.5& 0.1& 0.7\\ 0.3& 0.5& 0.2\\ 0.2& 0.4& 0.1\end{array}\right]\end{array}$

Figure 3. Markov chain transfer matrix

图3. 马尔可夫链转移矩阵

这个转移矩阵也被称为马尔可夫矩阵，元素是从状态过渡到状态的概率。注意，有些文献可能使用过渡符号，其中每个元素是从状态过渡到的概率，马尔可夫矩阵的列加起来等于1，也就是说，从任何可能的状态到达一个状态的概率是1。

我们设 $\left\{{\xi }_n,n=1,2,\cdots \right\}$ 是一个随机序列，海绵上的状态空间E为有限或可列集，对于任意的正整数m，n，若

$i,j,i_k\in E\left(k=1,\cdots ,n-1\right)$

有

$P\left\{{\xi }_{n+m}=j|{\xi }_n=i,{\xi }_{n-1}=i_{n-1},\cdots ,{\xi }_1=i_1\right\}=P\left({\xi }_{n+m}=j|{\xi }_n=i\right)$

则称 $\left\{{\xi }_n,n=1,2,\cdots \right\}$ 为商船状态转移的马尔科夫链。

4. 元胞自动机

广义地说，细胞自动机是一个包含细胞网格的系统，其中每个细胞都有一个状态。系统进展的离散时间步长和每个新的时间步长细胞可能改变他们的状态取决于一些规则或条件(通常与相邻细胞的状态)。细胞自动机是一种抽象的计算系统，通常以具有值的网格形式进行可视化表示。然而，最近的可视化效果是黑白方格组成的网格，这个网格中的每个元素都称为单元格。一般来说，在不同的计算模型中，细胞可以有一个无限的值集合，然而，在简单的细胞自动机的情况下，每个细胞可以只有两种状态中的一种：1 (黑色)或0 (白色)。在初级细胞自动机的情况下，我们的“网格”实质上是一个一维的细胞数组，每个细胞可以有两种可能的状态之一。决定每个时间步的状态变化的规则与细胞本身及其近邻的位置有关。所以如果我们在时间步骤 ，想知道细胞在时间t + 1处的新状态，我们需要观察细胞在时间t处的状态。

这样一个系统的必要组成部分包括一个网络(一维的、二维的，甚至更复杂的)、一组值(通常是二进制的)，以及一组简单的确定性迭代规则，这些规则通常依赖于每个单元格邻域中的值。原有的元胞自动机具有不可逆规则，但有些元胞自动机在时间上是完全可逆的——行为完全相同的前向和后向。因此，这些可逆形式与牛顿运动定律有一些相似之处，它们具有离散的时间步长，而非微分方程控制的连续行为，如图4所示。

Figure 4. Cellular automata

图4. 元胞自动机

在拦截或追击过程中，可能会涉及到两个问题，一是什么时间，二是什么方向，而使用元胞自动机的原理去解决该问题时，假设时间和空间都离散，建立海上商船随机转向的动力学模型，涉及到船的转向能力船舶的转向能力表征为其旋回性能，即下达转向命令后航向改变180˚ (掉头)所需时间及旋回直径。旋回性能与船舶类型、航速、舵角、海况等密切相关。

对突击商船，若拦截成功，则可交由其它空中支援力量处置，海警船、护卫舰仍执行封控任务。若突击商船被拦截前已突破AB线，则可认为拦截失败，海警船、护卫舰在确认无法成功拦截的第一时间即放弃拦截。

通过商船状态转移的马尔科夫链，利用元胞自动机，代入III类商船编号、位置数据以及转化矩阵等信息，按照上述商船拦截规则，进行分析求解，如图5所示。

Figure 5. Solution results of cellular automata

图5. 元胞自动机求解结果

结果表明：在模型能够保障这个港口的安全，阻止敌方的入侵行动个规则下，31艘III类商船通过代之后，将生成相同的下一代，也就是编号为18，26，82，146，154，210，218的III类商船，它们将突破AB线，需要海警船或护卫舰拦截，且其运动轨迹分别要沿着与拦截区的等分面进行规划和拦截。

5. 结论和分析

通过本文的研究和论证，在对抗冲突模型中，利用元胞自动机与马尔可夫过程相结合，描述相互对抗袭击的规则进行分析，具有很好的研究价值。当然，在研究过程中，我们需要确定k的值，这可能是复杂的一段时间，而且由于需要计算所有训练样本数据点之间的距离，因此计算量较大。另外，元胞自动机具有一定的偶然性和概率性，存在一定的分析误差，在分析问题时，需要反复进行分析，反复准备，尽可能地使解决方案更精确、更严谨，从而达到模型的求解更贴近于军事实际问题。

基金项目

海军大连舰艇学院科研基金项目(DJYKKT2021-026, DJYKYKT2021-018)；海军大连舰艇学院学员科研课题立项(DJYKKT2022-007, DJYKKT2022-003)。