无人机在多目标工程侦察中的路径优化问题研究

Research on Path Optimization of Unmanned Aerial Vehicles in Multi-Target Engineering Reconnaissance

摘要: 使用四旋翼无人机实施工程侦察，已经成为指挥所构筑与伪装行动中选址侦察的重要手段，无人机对多个工程作业目标实施侦察时的路径优化问题，是旅行商问题(Travelling Salesman problem, TSP)的典型应用，属于组合优化中的非确定性多项式完全(Non-deterministic Polynomial Complete, NPC)问题之一。头脑风暴优化算法(Brain Storm Optimization Algorithm, BSO)、模拟退火算法(Simulated Annealing Algorithm, SA)和遗传算法(Generation Algorithm, GA)都属于解决此问题的启发式智能优化算法，本文通过问题描述、数学建模和算法原理逐步介绍求解思路与方法，并将求解结果进行对比分析，数据表明，头脑风暴优化算法求解速度快、收敛度好、结果更优，能够更好地解决当前部队面临的无人机多目标侦察任务中的路径优化问题。

Abstract: The use of four-rotor unmanned aerial vehicles (UAVs) in engineering reconnaissance has become an important means of location reconnaissance in command post construction and camouflage operations. The path optimization problem of UAVs for reconnaissance of multiple engineering targets is a typical traveling salesman problem. It’s one of the nondeterministic polynomial complete problems in combinatorial optimization. Brain Storm Optimization Algorithm (BSO), Simulated Annealing Algorithm (SA) and Genetic Algorithm (GA) are heuristic optimization algorithms to solve this problem. In this paper, through problem description, mathematical modeling and algorithm principle, the solution ideas and methods are introduced step by step, and the results are compared and analyzed. The Brain Storming Optimization Algorithm has the advantages of high speed, good convergence and better results, which can better solve the path optimization problem of UAV multi-target reconnaissance mission.

1. 引言

随着近年来俄乌战争、巴以冲突等军事对抗中，广泛使用各型无人机成功执行多种任务，无人机在现代战争中扮演着越来越重要的角色，它集情报收集、目标定位打击、通信中继、隐蔽性好等多种特性于一体，世界各国都在加强它的开发与作战应用研究。当前，在遂行多目标工程侦察任务中，通常使用小型四旋翼侦察无人机实施现地侦察，不仅可以提高侦察效率，降低人员伤亡概率，还可以到达人车不便于抵达的位置实施侦察。因此，无人机对多目标实施工程侦察时的路径优化问题就受到了广泛关注和研究，达到进一步提高侦察效率、缩短侦察时间和抢占先机的目的。

平原微丘地形下的无人机多目标工程侦察路径优化问题，可以视为平面TSP问题[1]的典型应用。本文重点对多种头脑风暴算法(BSO) [2]、模拟退火算法(SA) [3]、遗传算法(GA) [4]三种算法进行实验，并对求解结果进行分析对比，选出解决当前部队无人机多目标工程侦察路径优化问题的最佳方法。

2. 问题描述

某部队在平原微丘地域(地形最大起伏不超过90米)遂行指挥所构筑与伪装行动前，将对指挥员在地图上标定的33个车辆掩体预构筑点(以最近的点O为坐标原点，其余坐标为其相对坐标，详见表1。指挥所车辆掩体预构筑点坐标信息表见图1。指挥所车辆掩体预构筑点分布图)实施工程侦察，核实现地情况是否与图上信息一致，并查明构筑点周围交通、水系、地质、植被、可利用场所等工程信息，形成工程侦察报告，为指挥员计算工程作业量和行动决策提供现地情报支撑。

现工程侦察组已经携带四旋翼无人机抵达原点O (0, 0)，求侦察其余33个目标点一遍(每个目标点有且只经过一次)后回到点O (0, 0)的最短距离及路由。

Table 1. Coordinate information table for pre-construction point of vehicle shelter in command post

表1. 指挥所车辆掩体预构筑点坐标信息表

序号	X坐标	Y坐标	序号	X坐标	Y坐标	序号	X坐标	Y坐标
1	0	0	13	243.09	680.11	25	624.08	924.12
2	43.72	75.25	14	275.15	762.13	26	640.03	302.12
3	69.23	180.20	15	312.42	200.12	27	675.32	831.11
4	87.24	475.12	16	331.00	904.10	28	709.60	107.14
5	120.18	369.78	17	332.11	682.32	29	733.24	231.08
6	125.00	75.30	18	379.03	81.17	30	763.62	275.14
7	143.00	709.14	19	383.15	825.12	31	890.15	432.13
8	147.23	540.38	20	476.13	108.43	32	894.08	755.23
9	174.06	442.18	21	477.46	215.18	33	921.08	548.72
10	175.18	12.13	22	501.92	912.12	34	928.18	649.16
11	215.17	132.14	23	542.12	829.31
12	223.12	568.21	24	561.14	275.12

Figure 1. Distribution diagram of pre-construction points of vehicle shelter in command post

图1. 指挥所车辆掩体预构筑点分布图

3. 数学模型

在平原微丘地域(地形最大起伏不超过90米)，四旋翼无人机(一般正常飞行高度超过地面90米)对多目标实施工程侦察的路径优化问题，是旅行商问题(Traveling Salesman Problem，简称TSP)的典型应用，可以描述为：1架无人机将对n个目标实施工程侦察，每两个目标点之间距离为d_ij ($i,j=1,2,\cdots ,n$ ；且$i\ne j$ )，求从点O (0, 0) (以出发点为原点，正东方向为x轴，正北方向为y轴)出发，遍历所有目标点有且仅有1次后回到出发点O (0, 0)的最短距离。其数学模型如下：

$\begin{array}{l}\min f={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{d}_{ij}{X}_{ij}}}\text{ (1)}\\ \text{s}\text{.t}\text{.}\{\begin{array}{ll}{d}_{ij}=\sqrt{{\left(x_j-x_i\right)}^2+{\left(y_j-y_i\right)}^2},i\ne j,i\in V,j\in V\hfill & (2)\hfill \\ {\displaystyle \sum _{j=1}^n{X}_{ij}}=1,i\in V\hfill & (3)\hfill \\ {\displaystyle \sum _{i=1}^n{X}_{ij}}=1,j\in V\hfill & (4)\hfill \\ {\displaystyle \sum _{i,j\in s}{X}_{ij}}\le \left|s\right|-1,\forall s\subset V,2\le \left|s\right|\le n-2\hfill & (5)\hfill \\ X_{ij}\in \left\{0,1\right\}\hfill & (6)\hfill \end{array}\end{array}$

其中：公式(1)是目标函数，即从第一个点O (0, 0)出发，侦察其余n − 1个目标点后回到出发点O (0, 0)的最短距离；公式(2) d_ij为第i点到第j点的欧氏距离；公式(3)、(4)为无人机经过每一个点1次，且只经过1次；公式(5)确保无子回路解产生；公式(6)无人机从i点到j点，则状态改为1，否则为0。x_i、y_i分别为第i点的横坐标和纵坐标，X_ij为第i点到第j点的边。V为所有车辆掩体预构筑点的序号集合；s为第2个点到n − 1点。

4. 算法原理

4.1. 头脑风暴优化算法(BSO)原理

头脑风暴优化算法的灵感源自于头脑风暴法，头脑风暴法为：针对某一问题，聚集不同专业背景的多个专家，遵循延迟评判、自由畅想、以量求质和综合改善的原则，充分开发人类创造性思维来得到最优解决方案的方法。头脑风暴优化算法就是通过模拟头脑风暴过程，综合运用聚类(每类为一个专家头脑)和变异等策略[5]，探索和开发搜索空间，从而达到优化的目标。

使用BSO算法解决无人机多目标侦察问题的基本原理：随机生成一组(NIND个)遍历序列(除了出发点和结束点均为O点，其余各点有且仅经过一次)的路径距离组成初始种群，每一个随机序列的路径距离为一个个体，使用K-means聚类算法对初始种群的NIND个个体分成m类，把每一类中的个体按照目标函数值进行排序并选出最优的个体作为聚类中心，以一定的概率随机地从这m个新的聚类中心选出1个或2个聚类，并用一个新产生的随机解更新这个聚类中心。如果更新后的聚类中心优于个体i，则更新个体i，否则不更新个体i。按照此方法迭代到最大迭代次数后，得到当前最优解。这样，通过聚类得到局部最优，再通过比较局部最优得出全局最优，加之采用变异思想来增加算法的多样性，很好地避免了陷入局部最优[6]。主要求解步骤为：

(1) 初始化。先设置种群数、聚类数目、替换概率、选择1个和2个聚类中心概率等参数。然后初始化种群：随机生成NIND个遍历所有侦察目标点有且仅有1次的序列(见函数InitPop.m)作为初始种群，每一个遍历序列为1个个体。

(2) K-means聚类。聚类就相当于模拟m个专家，进行独立思考，能够更高效地找到各自的局部最优，降低了陷入局部最优的概率。具体做法：将NIND个个体用K-means聚类算法分成m类。计算出每一个个体的遍历距离(见函数RouteLength.m)作为适应度，将每一个聚类的适应度值(遍历距离)最小的作为聚类中心，这样就得到m个聚类中心并存储。

(3) 变异。变异的主要目的是能够更好地避免陷入局部最优。具体做法是：生成一个(0, 1)的随机数R1，如果R1小于替换概率p_replace，就从m个聚类中心中随机选择一个聚类中心，用一个随机产生的新个体替换掉这个随机选出来的聚类中心。否则不做操作继续下一步。

(4) 更新个体。针对NIND个个体，采用两种方法更新种群。使用随机函数rand()产生一个(0, 1)的随机数。当随机数小于p_one是选择一个聚类，否则选择2个聚类；选择一个聚类时，如果随机数小于p_one_center，Select_ind更新为这个聚类的聚类中心，否则更新为这个聚类的一个随机个体，再使用函数Swap.m将Select_ind的随机交换两个序号后赋值给indi_temp (交换的目的是为了避免陷入局部最优)。选择两个聚类时，如果随机数小于p_two_center，就把两个聚类中心分别赋值给Select_ind1和Select_ind2，否则就在每个聚类里各选择一个随机个体赋值给这两个变量，再使用heuristic_crossover.m进行启发式交叉操作，把适应度值小的赋值给indi_temp(启发式交叉的目的也是为了避免陷入局部最优)。最后，如果indi_temp的适应度值小于个体i的适应度值，则更新个体I = indi_temp；否则，不更新个体i。

(5) 当迭代到最大迭代次数后，迭代过程终止，将当前种群按照适应度排序(遍历路径长度值从小到大排序)，输出最小值即为最优值。

算法流程图见：图2。头脑风暴优化(BSO)算法流程图。

Figure 2. Flow chart of brainstorming optimization algorithm

图2. 头脑风暴优化算法(BSO)流程图

4.2. 模拟退火算法(SA)原理

模拟退火算法的灵感来源于固体物理学中的退火过程，即将物质加热后再缓慢冷却，从而达到更稳定的结构，是一种启发式搜索算法[7] [8]。模拟退火算法求解无人机多目标侦察路径优化问题，可分为初始化、迭代循环、降温更新、终止条件判断和输出最优解5个部分[9]。基本步骤是：

(1) 初始化：设置初始温度和冷却因子，当温度逐渐冷却到冷却因子温度则停止，初始解空间s (每个目标点1至目标点n的随机序列就是一个解)；

(2) 每个T值设置2层循环，对外层循环OutIter = 1到MaxOutIter，和内层循环InIter = 1到MaxInIter，做第(3)至第(6)步；

(3) 通过领域函数(采用轮盘赌的方式产生选择，index为1时交换，为2时逆转，其他情况插入)产生新解s′，目的是避免陷入局部最优；

(4) 计算新解的评价函数值newL，即为按照解s′序列侦察所有目标点回到起点的总距离；

(5) 若新解距离小于当前最优解距离，即newL < currL则接受s′作为新的当前解，并更新当前最小距离currL；否则，按照公式(7)计算出概率P。

$P=\exp \left(-\left(\left(\text{ne}w\text{L}-\text{currL}\right)/\text{currL}\right)/T\right)$ (7)

产生一个0到1的随机数rand，如果rand < P，则接受新解和新解的最小距离，更新为当前最优解和最优距离，否则，不更新，从而得到当前最优解。

(6) 如果当前最优距离小于全局最优距离，即currL < bestL，则更新全局最优距离(即全局最优解) bestL = currL，更新温度T = alpha*T，以此影响解更新的可能。

满足内外层迭代次数的终止条件，则输出当前解作为最优解，结束程序。算法流程图见：图3。模拟退火算法(SA)算法流程图。

Figure 3. Flow chart of simulated annealing algorithm

图3. 模拟退火算法(SA)流程图

4.3. 遗传算法(GA)原理

遗传算法(Genetic Algorithm, GA)灵感来源于自然界的生物进化原理，是人工智能领域中的一种重要的启发式搜索算法[10] [11]，主要包括编码、初始化、评估、选择、交叉、变异和终止6个部分[12] [13]。

(1) 编码策略

遗传算法的编码方式一般由二进制编码、十进制编码、格雷码等编码方式；编码的作用是便于基因分离、统一所有个体表达。我们采用十进制编码更方便，每一组遍历所有点一次回到出发点的路径顺序为一组编码(即为一个解)。例如：遍历3个点的遗传算法编码策略见图4。遗传算法编码策略示意图。

Figure 4. Schematic diagram of genetic algorithm coding strategy

图4. 遗传算法编码策略示意图

(2) 适应度函数

适应度函数又叫做评价函数，是用来判断群体中的优势程度的指标，它是根据所求问题的目标函数来进行评估的。对于TSP问题来说，我们目标是让总距离最短，个体的适应度(Fitness)就可以定义为该个体的距离(f_i，即为第i个个体的TSP问题公式(1)中的目标函数)的倒数，见公式(8)。总距离越短 −> 适应度越高 −> 越容易被选择。

$Fitness=\frac{1}{f_i}$ (8)

(3) 选择

通过适应度函数来作出选择，选出来的个体作为父代个体进入到后续繁殖环节，将其基因进行遗传。通常的选择方式有1) 轮盘赌选择法；2) 锦标赛选择法；3) 截断选择法。本文采用轮盘赌选择法：将种群中所有个体的适应度值进行累加然后归一化，最终通过随机数落在的区域对应的个体进行选择，见公式(9)。

$P_j=\frac{Fitnes{s}_j}{{\displaystyle \sum _{i=1}^{n}Fitnes{s}_i}}$ (9)

(4) 交叉

交叉就是把种群中选择出来的两个父代个体的部分结构加以替换重组生成新个体的操作方式，通常交叉操作包括：单点交叉、多点交叉和部分映射交叉等交叉方式，本文采用部分映射交叉。5个点的原理见图5。遗传算法交叉策略示意图。

如果新的个体比父代个体的适应度高，那么就用新的个体替代对应的父代个体进入种群，如果新的个体比父代个体的适应度低，则继续保留父代个体不更新。这样就完成一轮遗传。

Figure 5. Schematic diagram of crossover strategy of genetic algorithm

图5. 遗传算法交叉策略示意图

(5) 变异

为了避免陷入局部最优的情况，常常采取变异方式随机地搜索解可能存在的整个空间，极大地增加求得全局最优解的可能性。变异就是对种群中的个体某些基因上的基因值进行变换。通常有单点变异、多点变异、均匀变异、翻转变异。本文采用单点变异，5个目标点的原理见图6。遗传算法变异策略示意图：

Figure 6. Schematic diagram of genetic algorithm mutation strategy

图6. 遗传算法变异策略示意图

当变异后个体的适应度更高时，保留变异后个体，变异后个体适应度低时继续保留变异前的个体。遗传算法的流程图见：图7。遗传算法流(GA)程图。

Figure 7. Flow chart of genetic algorithm

图7. 遗传算法(GA)流程图

5. 求解情况及结论

为了验证头脑风暴优化算法(BSO)、模拟退火算法(SA)和遗传算法(GA)对问题描述中数据的优化效果，我们先分别独立运行，确定出各自优化算法的较优初始参数设置，再进行统一求解，对相关数据进行对比分析，得出结论。

5.1. 初始参数设置

先将三种算法分别独立运行，经多次测试，在优先保证目标函数更优的情况下，找出各自算法的较优初始参数设置。头脑风暴算法的较优初始参数设置情况见表2。头脑风暴优化算法较优初始参数设置表，模拟退火算法的较优初始参数设置情况见表3。模拟退火算法较优初始参数设置表，遗传算法的较优初始参数设置情况见表4。遗传算法较优初始参数设置表。

5.2. 求解结果对比

按照较优初始参数设置，三种算法同时运行，选择三种算法均较优的数据进行对比，相关情况见图8。头脑风暴优化算法(BSO)路由图、图9模拟退火算法(SA)路由图、图10遗传算法(GA)路由图、图11 BSO-SA-GA三种算法收敛度对比图、表5 BSO-SA-GA三种算法实验数据对比一览表。

Table 2. Optimal initial parameter setting table of brain storming optimization algorithm

表2. BSO算法较优参数设置表

参数意义	参数名	参数值
最大迭代次数	MAXGEN	200
种群数	NIND	50
聚类数	Cluster_num	5
替换一个聚类中心的概率	p_replace	0.1
选择一个聚类的概率	p_one	0.5
选择聚类中心1的概率	p_one_center	0.3
选择聚类中心2的概率	p_two_center	0.2

Table 3. Optimal initial parameter setting table of simulated annealing algorithm

表3. 模拟退火算法较优初始参数设置表

参数意义	参数名	参数值
外层迭代次数	MaxOutIter	200
内层迭代次数	MaxInIter	50
初始温度	T0	0.005
冷却因子	alpha	0.99
交换概率	pSwap	0.2
逆转概率	pReversion	0.5
插入概率	pInsertion	0.3

Table 4. Optimal initial parameter setting table of genetic algorithm

表4. 遗传算法较优初始参数设置表

参数意义	参数名	参数值
最大迭代次数	MAXGEN	200
种群数	NIND	50
交叉概率	Pm	0.005
变异概率	Pc	0.99
交换概率	pSwap	0.2
逆转概率	pReversion	0.5
插入概率	pInsertion	0.3
染色体长度	N	34

Figure 8. Brainstorming algorithm routing graph

图8. 头脑风暴优化算法(BSO)路由图

Figure 9. Simulated annealing algorithm routing graph

图9. 模拟退火算法(SA)路由图

Figure 10. Genetic algorithm routing graph

图10. 遗传算法(GA)路由图

Figure 11. BSO-SA-GA comparison chart of convergence degree of three algorithms

图11. BSO-SA-GA三种算法收敛度对比图

Table 5. BSO-SA-GA comparison list of experimental data of three algorithms

表5. BSO-SA-GA三种算法实验数据对比一览表

算法	时间(s)	最短距离(m)	路由(目标点序号)	收敛度	结论
BSO	2.2018	4097.1814	1→6→10→11→15→18→20→21→24→26→28→29→30→31→33→34→32→27→25→23→22→16→19→14→17→13→7→12→8→4→9→5→3→2→1	第41次迭代到最优解4093.3417米	最优
SA	3.9672	4097.1814	1→6→10→11→15→18→20→21→24→26→28→29→30→31→33→34→32→27→25→23→22→16→19→14→17→13→7→12→8→4→9→5→3→2→1	第86次迭代到最优解4093.3417米	较优
GA	9.7642	4406.7594	1→6→10→11→18→20→15→21→24→28→29→26→30→31→33→34→32→27→25→23→22→16→19→17→14→13→7→8→12→9→4→5→3→2→1	第200次迭代到最优解4406.7594米	一般

5.3. 结论

依据4.1的初始参数较优设置和4.2的求解数据结果分析可知，传统的遗传算法(GA)，虽然设置了交叉、变异、交换、逆转多个操作，避免陷入局部循环，但依旧较难得到最优解(4406.7594米 > 4093.3417米)，而且收敛度也不理想；模拟退火算法(SA)改进后，通过轮盘赌法选择随机个体和使用一定概率的交换、逆转、插入操作，极大地避免了陷入局部循环，所以收敛度较好(第86次得到最优解4093.3417米)，但因为2层循环和退火的固有机制，导致求解速度相对较慢(3.9672秒)；BSO算法由于采用了聚类算法，先各自求出局部最优，再得到全局最优，保证了效率，同时，使用一定概率选择随机个体，采用交换(Swap.m)和启发式交叉(heuristic_crossover.m)算法，进一步避免了陷入局部最优，因此，在第41次迭代即可达到最优值4093.3417米，并且时间也是最优。所以，我们能够得出综合结论：头脑风暴优化算法(BSO)能够更好地解决当前部队使用无人机对多目标实施侦察时的路径优化问题。

NOTES

^*通讯作者。