徐慧威¹，陈信至¹，侯明鑫²，苏永杰¹，吴少彬²，李军^2*

¹广东海洋大学数学与计算机学院，广东 湛江

²广东海洋大学机械工程学院，广东 湛江

收稿日期：2024年1月25日；录用日期：2024年2月22日；发布日期：2024年2月29日

摘要

针对现代战争中红蓝双方物资分配问题，为了优化分配供应，提出一种基于蚁群算法优化现代战争物资分配的方法。引入蚁群算法构建最短路径模型，模型充分考虑约束条件，确保每个位置唯一访问；综合考虑火力打击目标，同时分析不考虑时间窗的多目标优化情况；通过信息素初始化、状态转移率标准和信息素更新，构建有效的路径规划模型；构建判断矩阵对目标因素进行一致性检验；最终通过蚁群算法获得红队和蓝队的最短路径长度并得出红蓝方运输车辆最优配置及总人数。

关键词

蚁群算法，物资分配供应，多目标优化，最短路径

Research on Material Distribution in Modern War

—Ant Colony Algorithm Model Based on Multi-Objective Optimization

Huiwei Xu¹, Xinzhi Chen¹, Mingxin Hou², Yongjie Su¹, Shaobin Wu², Jun Li^2*

¹School of Mathematics and Computer Science, Guangdong Ocean University, Zhanjiang Guangdong

²College of Mechanical Engineering, Guangdong Ocean University, Zhanjiang Guangdong

Received: Jan. 25^th, 2024; accepted: Feb. 22^nd, 2024; published: Feb. 29^th, 2024

ABSTRACT

Aiming at the problem of material distribution between red and blue in modern war, in order to optimize the distribution and supply, a method of material distribution optimization in modern war based on an ant colony algorithm was proposed. The ant colony algorithm is introduced to construct the shortest path model, which fully considers the constraints to ensure the unique access of each location. Considering the firepower attack target comprehensively, the multi-objective optimization without considering the time window is analyzed. Through pheromone initialization, state transition rate standard and pheromone update, an effective path planning model was constructed; The judgment matrix was constructed to test the consistency of the target factors. Finally, the ant colony algorithm was used to obtain the shortest path length of the red team and the blue team, and the optimal configuration of the red and blue transport vehicles and the total number of people.

Keywords:Ant Colony Algorithm, Material Distribution and Supply, Multi-Objective Optimization, Shortest Path

Copyright © 2024 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] 、遗传算法 [2] 、A*算法 [3] 、Dijkstra算法 [4] 等。众多学者基于上述算法针对该问题进行了研究：文献 [1] 采用模拟退火算法更新群体极值的策略，避免粒子搜索陷入局部最优解；文献 [2] 引入自适应交叉算子和变异算子有效减少了传统算法迭代次数较多的问题；文献 [3] 通过在传统A*算法中加入新的启发函数项来改变路径点代价值的计算规则 [5] ；文献 [4] 用Dijkstra算法进行节点选取，使搜索导向性更加明确。上述算法从一定程度上减少了路径规划的长度，降低了收敛速率，但也增大了算法的复杂程度，对于能否处理大规模的规划问题还需进一步地研究。蚁群算法是一种基于大量个体的分布式计算方法，具有较强的并行性能、鲁棒性和自适应性，对初始解和参数设置相对不敏感，能够应对复杂的物资分配环境和变化，可以有效处理大规模的物资分配问题 [6] 。

鉴于此，本文提出了基于蚁群算法的现代战争中红蓝双方医疗用品、军需物资和日常物资如何最优分配供应问题的研究。首先构建最短路径模型，考虑约束条件和唯一访问性。其次，综合考虑火力打击目标和无时间窗的多目标优化 [7] 。通过信息素初始化、状态转移率标准和信息素更新，构建有效的路径规划模型。使用判断矩阵进行目标因素的一致性检验 [8] 。最后，利用蚁群算法获得红队和蓝队的最短路径长度，并确定最优的运输车辆配置和总人数。

2. 分析

主要目标是构建一个最短路径模型，以确保运输车辆从任一位置出发，穿越所有点一次，避免重复经过已穿越的点，从而使总路径最短 [9] 。这有助于提高作战效率和减少资源损耗。本文选择蚁群算法作为建模工具。

蚁群算法模拟了蚂蚁在寻找食物时的行为，通过模拟蚂蚁在路径上释放信息素来引导其他蚂蚁，从而找到最短路径。这种模型在解决旅行商问题等最短路径问题上表现出色。

需要注意的是添加约束条件确保每个位置只被访问一次，车辆从每个位置只能离开一次，并且路径形成一个闭环。这些约束条件对于模型的现实可行性至关重要。

3. 建模

3.1. 多目标下的蚁群算法

分别研究红色和蓝色边，以红色边为例。在N个位置点(为了方便说明，这里假设为30)的散点图中，假设运输车辆从任何位置均为 $X_i\left(i=1,2,\cdots ,30\right)$ ，即确保运输车辆穿越所有的点，避免已经穿越的点，从而使总路径最短。构建基本的最短路径模型 [10] ：

$\begin{array}{l}\text{Min}f\left(x\right)={\displaystyle {\sum }_i{C}_i{X}_i}\\ \{\begin{array}{l}{g}_j\left(x\right)>0j=1,2,\cdots ,m\\ h_k\left(x\right)=0k=1,2,\cdots ,l\end{array}\end{array}$ (1)

其中：规定 $C_i$ 是第i条路径的权值， $f\left(x\right)$ 是约束条件； $g_j\left(x\right)$ ：约束函数，用于确保路径满足特定条件(例如避开已经穿越的点)；m：约束函数的数量； $h_k\left(x\right)$ ：等式约束函数，用于确保路径满足特定条件(例如必须经过某些点)；l：等式约束函数的数量。

我们的目标是最小化总路径长度，即最小化 $f\left(x\right)={\displaystyle \sum C_i{X}_i}$ ，其中i的取值范围是从1到N。同时，我们需要考虑约束条件。约束函数 $g_j\left(x\right)>0$ 表示我们需要避开已经穿越的点，而约束函数 $h_k\left(x\right)=0$ 表示路径必须经过某些指定的点。通过将最短路径问题转化为一个优化问题，我们可以使用各种优化算法来求解最优解。常见的方法包括蚁群算法、遗传算法、动态规划等。这些算法可以根据具体情况进行选择。总结起来，基于以上描述，我们可以构建一个最短路径模型，即最小化总路径长度，同时满足约束条件。通过选择适当的优化算法，可以找到最优的路径解决方案。

3.2. 不考虑时间窗(时间约束)对多目标优化算法的影响

将每个位置点视为N个城市，将交通工具视为M个蚂蚁，集合A为所有城市的节点集合，且 $L_i\left(i\in 1,2,\cdots ,n\right)$ 表示城市i与城市j之间的距离； $T_{ij}$ 表示路径中某一时刻的信息素值。

3.2.1. 信息素初始化

$T_{ij}\left(0\right)=constconst为常量$ (2)

它规定了每条路径在初始时刻具有相同的信息素浓度。

3.2.2. 状态转移率准则

在某一时刻，每只蚂蚁可以独立选择下一个尚未访问的城市，并将当前选取的城市记录在禁止表NoList中：

$P_{ij}\left(t\right)=\{\begin{array}{l}allowed=\left\{C-Nolist\right\}\\ {\left[T_{ij}\left(t\right)\right]}^a\ast {\left[n_{ij}\left(t\right)\right]}^b\\ {\displaystyle {\sum }_{s\in allowed}{\left[T_{ij}\left(t\right)\right]}^a\ast {\left[n_{ij}\left(t\right)\right]}^b}\end{array}$ (3)

其中： $P_{ij}\left(t\right)$ ：蚂蚁在时刻t选择从城市i转移到城市j的概率，allowed：表示蚂蚁可以选择的下一个城市集合；即所有尚未访问的城市减去禁止表NoList中已经访问过的城市；C：全部城市的集合；NoList：禁止表，记录了已经访问过的城市； $T_{ij}\left(t\right)$ ：表示城市i到城市j的信息素浓度； $n_{ij}\left(t\right)$ ：表示城市i到城市j的启发函数值；a：信息素的影响程度参数，控制信息素对蚂蚁选择路径的重要程度；b：启发函数的重要程度参数，控制启发函数对蚂蚁选择路径的重要程度。

在公式中，我们首先确定蚂蚁可以选择的下一个城市集合allowed，即所有尚未访问的城市减去禁止表NoList中已经访问过的城市。然后，我们计算蚂蚁从城市i转移到城市j的概率，该概率由信息素浓度和启发函数值的乘积决定。信息素浓度用于表示蚂蚁选择路径的历史信息，而启发函数用于表示城市间的启发式信息(例如距离、可行性等)。最后，我们将所有满足条件的概率进行求和，得到蚂蚁从城市i转移到下一个城市的总概率。根据这个概率，蚂蚁将基于一定的随机性选择下一个城市，并将其记录在禁止表NoList中，以避免重复访问。这样，通过不断迭代更新信息素浓度和禁止表，蚁群算法能够逐步搜索并优化出较好的路径解决方案。

3.2.3. 信息素的更新

当所有蚂蚁完成一次所有城市的遍历后，对各路径节点信息做更新：

$\{\begin{array}{l}{T}_{ij}\left(t+1\right)=\left(1-p\right)\ast T_{ij}\left(t\right)+\Delta T_{ij}\left(t\right)\\ \Delta T_{ij}\left(t\right)={\displaystyle {\sum }_{k=t}^m\Delta T_{ij}^k\left(t\right)}\end{array}$ (4)

其中： $T_{ij}\left(t+1\right)$ ：城市i到城市j的信息素浓度在时刻t + 1的值； $T_{ij}\left(t\right)$ ：城市i到城市j的信息素浓度在时刻t的值； $p$ ：信息素蒸发系数，控制信息素的蒸发率。通常取值范围为[0, 1]，表示信息素保留的比例； $\Delta T_{ij}\left(t\right)$ ：路径上信息素的增量。第二条公式中：k：路径上的步数；m：路径的总步数； $\Delta T_{ij}^k\left(t\right)$ ：表示第k步上的信息素增量。

简单来说，路径上信息素的增量是路径上每一步的信息素增量之和。每一步的信息素增量可以根据问题的具体情况进行定义和计算，例如蚂蚁经过某个路径后的适应度值、路径长度等。更新信息素浓度时，公式中的(1 − p)表示信息素的蒸发，旧的信息素浓度以(1 − p)的比例保留。而新的信息素增量 $\Delta T_{ij}\left(t\right)$ 则在原有信息素浓度的基础上进行累加。通过不断迭代更新信息素浓度，蚁群算法能够利用蚂蚁的搜索行为和启发式信息逐步优化出较好的路径解决方案。

4. 模型求解

如图1为蚁群算法流程图，图2为递阶层次结构模式图。

图1. 蚁群算法流程图

图2. 递阶层次结构模型图

用1~9表示各个因子之间的相对重要性，构造判断矩阵，如下表1所示。

表1. 判断矩阵

根据相关文献对判断矩阵的各个因素进行打分，对于构建每个标准的目标D，执行以下一致性测试：

各个目标的待检验权重系数： $W_i=\sqrt[n]{m_i}$ 其中表示第i行因子的乘积，n为矩阵的大小。

归一化处理，得到最大特征根：

${\lambda }_{\max }=\frac{1}{n}{\displaystyle {\sum }_m^n\frac{\left(A{w}_i\right)}{w_i}}=3.094$

计算一致性指标CI：

$CI=\frac{{\lambda }_{\max }-n}{n-1}=0.047$

计算一致型比例CR：

$CR=\frac{CI}{RI}=0.09$

显然，CR = 0.09 < 0.1通过了一致性检验，即该层次结构的权重系数合理。模型求解结果如图3、图4所示。

图3. 红方散点图——蚁群算法结果图

最短路径长度为61.2396。

图4. 蓝队散点图——蚁群算法结果图

最短路径长度为68.7824。

5. 结论

本文提出的基于蚁群算法的现代战争中红蓝双方医疗用品、军需物资和日常物资最优分配供应问题的研究，可以在快速搜索出一条路径长度短、转弯次数少的综合最优路径。首先构建最短路径模型，考虑约束条件和唯一访问性。其次，综合考虑火力打击目标和无时间窗的多目标优化。通过信息素初始化、状态转移率标准和信息素更新，构建有效的路径规划模型。使用判断矩阵进行目标因素的一致性检验。同时结合多目标优化函数来改进信息素增量，并动态调整信息素挥发因子来改进信息素更新规则，提高算法的收敛速度。最后，利用蚁群算法获得红队和蓝队的最短路径长度，并确定最优的运输车辆配置和总人数。

表2. 蓝方运输车辆调度分配

表3. 红方运输车辆调度分配

基于所提出的模型假设，我们得出了红蓝方运输车辆最优配置为各三辆，并且总共需要三十名人员，如表2、表3所示。研究结果表明：本文算法可以在系统作战中有效地寻找出最优方案以合理进行物资分配、组织作战力量，以取得最大的战功和最小的战损。

文章引用

徐慧威,陈信至,侯明鑫,苏永杰,吴少彬,李 军. 现代战争物资分配的研究——基于多目标优化的蚁群算法模型
Research on Material Distribution in Modern War—Ant Colony Algorithm Model Based on Multi-Objective Optimization[J]. 计算机科学与应用, 2024, 14(02): 428-437. https://doi.org/10.12677/CSA.2024.142043

参考文献