基于混合遗传算法的多无人机巡逻路径优化

doi:10.3785/j.issn.1008-9497.2024.01.004

基于混合遗传算法的多无人机巡逻路径优化

李国军¹, 郑滋椀^,², 范英盛¹, 卢甜甜¹, 徐志江³

1.浙江警察学院公共基础部，浙江杭州 310053

2.浙江警察学院大数据与网络安全研究院，浙江杭州 310053

3.浙江机电职业学院自动化学院，浙江杭州 310053

The optimization of multi-UAVs patrol path with hybrid genetic algorithm

LI Guojun¹, ZHENG Ziwan^,², FAN Yingsheng¹, LU Tiantian¹, XU Zhijiang³

1.Basic Courses Department，Zhejiang Police College，Hangzhou 310053，China

2.School of Big-Data and Network Security，Zhejiang Police College，Hangzhou 310053，China

3.School of Automation，Zhejiang Institute of Mechanical & Electrical Engineering，Hangzhou 310053，China

通讯作者: E-mail：zhengziwan@zjjcxy.cn.

收稿日期: 2023-02-01 修回日期: 2023-02-28 接受日期: 2023-03-15

基金资助:

2023JC32

浙江省“尖兵”“领雁”攻关计划项目. 2023C01030
国家自然科学基金青年项目. 41901160

Received: 2023-02-01 Revised: 2023-02-28 Accepted: 2023-03-15

作者简介 About authors

李国军（1979—），男，硕士，副教授，主要从事机器学习、学习控制、舆论动力学以及智慧警务等研究。

摘要

假设无人机巡逻的起、终点均为派出所，提出了一种融合传统遗传算法和爬山算法的警用无人机巡逻路径优化模型——混合遗传算法。按照轮盘赌法则，进行种群个体的选择，以增大优秀种群个体被选中的概率，达到较好的优化效果。同时定义了与路径优化相适应的基因交叉和变异规则。仿真结果表明，提出的混合遗传算法在寻优效果上明显优于传统遗传算法。

关键词： 遗传算法 ; 爬山算法 ; 巡逻 ; 路径优化

Abstract

Aiming at the optimization of multi-UAVs patrol path, a patrol model of multi-UAVs based on hybrid genetic algorithm is proposed. When constructing the patrol model, each UAV must start from the police station and return to the police station at the end of the patrol. The algorithm is designed by combining traditional genetic algorithm and hill-climbing algorithm. In order to achieve a better optimization effect, the roulette wheel method is employed to select the excellent individuals with higher probability when selecting individuals of the population. In the application of genetic algorithm, the rules of gene crossover and mutation adapted to path optimization are defined. The simulation results show that the proposed hybrid genetic algorithm is significantly better than the traditional genetic algorithm on the optimization effect.

Keywords： genetic algorithm ; hill-climbing algorithm ; patrol ; path optimization

PDF (940KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

李国军, 郑滋椀, 范英盛, 卢甜甜, 徐志江. 基于混合遗传算法的多无人机巡逻路径优化. 浙江大学学报(理学版)[J], 2024, 51(1): 21-28 doi:10.3785/j.issn.1008-9497.2024.01.004

LI Guojun, ZHENG Ziwan, FAN Yingsheng, LU Tiantian, XU Zhijiang. The optimization of multi-UAVs patrol path with hybrid genetic algorithm. Journal of Zhejiang University(Science Edition)[J], 2024, 51(1): 21-28 doi:10.3785/j.issn.1008-9497.2024.01.004

0　引言

2021年，公安部以全国社会治安防控体系建设“示范城市”创建活动为牵引，更大范围、更宽领域、更深层次推进治安防控体系建设，全面落实保平安、护稳定、促发展各项关键举措。全国共建成街面警务站16 000余个，日均投入50万警力进行巡逻防控，有力震慑和打击了街面现行违法犯罪^［1］。因此，在投入如此多的警力开展警务巡逻的同时，如何优化警务巡逻策略，提升防控水平，不仅具有理论意义，更具有实践意义。

自1994年公安部颁布《城市人民警察巡逻规定》至今，我国已摸索出一套符合自身国情的警务巡逻模式，巡逻勤务也发挥了预想中防治犯罪、维护社会治安的作用。一些数字化、可视化、动态化、网格化的巡逻模式和防控体系相继建立，巡逻模式和巡逻手段的创新极大地丰富了我国的警务巡逻实践^［2⁃5］。随着时代的进步，互联网、大数据等现代科学技术的高速发展，以及西方治警观念的输入，不少学者开始对巡逻勤务这一常见警务模式的发展以及巡逻策略的优化进行了思考^［6-7］。李路等^［6］提出了基于遗传算法的警车巡逻路线优化算法，保持警车的最大覆盖面。吴思远^［7］针对警察巡逻问题，利用K-means聚类算法提出了一种全局优化的巡逻区域最大覆盖调度方案。这些研究在一定程度上提高了警务巡逻的效率，但因在分析过程中假设条件过于严苛，没有考虑实际情况，且模型固定，实践意义不强。

国外关于该主题的研究，已从以人为导向转向以地点为导向的警务模式，其中最重要的一项就是热点警务巡逻。理论和实践表明，将主要巡逻力量精确投放在犯罪热点区，能有效预防犯罪^［8-9］。另一方面，基于图论的路网分析技术迅速发展^［10-13］。例如，基于路网的Voronoi图、最近邻、K函数、点聚类、核函数等分析手段得到广泛应用。在警务巡逻优化方面，国外开展研究较早，成果也较丰富^［14-22］。ALLEN^［15］研究了如何使用现有的犯罪数据以及开源数据设计巡逻区。MUKHOPADHYAY等^［16］开发了双层优化框架用于解决巡逻警力分配问题，并且该方法考虑了犯罪分子可能对警察巡逻的反应，从而改变犯罪的空间和时间分布。MICHAEL等^［17］提出的基于资源策略的计算框架使得巡逻警车能在概率意义下应对动态求助。CHEN^［21-22］基于交叉熵提出了一种在动态环境中进行实时巡逻路线规划的方法，并在交叉熵的最优巡逻策略基础上，设计了一种随机化策略应对巡逻的不确定性。ZHU等^［23-24］利用基于数据驱动的优化框架，重新设计警察巡逻区，减少对紧急呼叫的响应时间，并在南福尔顿市和亚特兰大市得到验证。

由于路径优化问题为NP问题，当节点数较多时，很难在短时间内得到最优解。目前用于路径优化的算法主要包括精确算法、启发式算法和元启发式算法三类^［25-26］。作为启发式算法的遗传算法，在路径优化中得到了广泛应用。考虑遗传算法较优的全局性能和较差的局部性能，在实际应用中，常将遗传算法与其他算法相结合得到最优解^［27-28］。郎茂祥等^［27］先用遗传算法求解准最优解，再通过爬山算法求解最优解，以解决物流配送过程中的路径优化问题。胡小建等^［28］将遗传算法与A^*算法相结合进行多车路径规划。丛玉良等^［29］则通过改进遗传算法和人工鱼群算法，实现对车联网任务卸载策略的优化。张铁等^［30］利用模拟退火混合遗传算法辨识摩擦参数，令建立的机器人动力学模型更加准确。

综合现阶段的研究，警务巡逻工作已受地理学、犯罪学、公共安全学、信息学等领域的关注。本文将传统遗传算法与爬山算法相融合，将其应用于警用无人机巡逻路径优化，开发了适应本地区的无人机巡逻策略，最大限度地优化警力资源配置。

1　问题描述与模型构建

1.1　问题描述

警务巡逻是公安机关震慑违法犯罪分子、维护社会稳定、保障人民群众生命财产安全的重要措施。随着无人机的广泛应用，警用无人机已成为提高我国公安机关警务巡逻效率的重要手段。根据警务巡逻要求，公安机关需要不定时对政府所在地、车站、码头、商场、步行街、幼儿园、中小学校、居民小区等重点区域、重点设施进行巡逻。假设警用无人机从派出所出发，完成对各个点的巡逻后返回派出所。根据派出所辖区内重点巡逻场所、区域的空间分布位置以及对每个区域巡逻的时间要求，用最少的无人机完成巡逻任务。

1.2　模型构建

1.2.1　模型假设

无人机采用直线巡逻方式，匀速飞行，飞行速度为15 km·h^-1。飞行距离不超过18.000 km，每架无人机空中停留时间不超过2.00 h。

1.2.2　模型构建

设派出所有K台无人机，每台无人机的续航时间为 $T_{k} (k = 1, 2, \dots, K)$ ，总共需要巡逻的地点有L个，在每个巡逻点的巡逻时间为 $t_{i} (i = 1, 2, \dots, L)$ ，巡逻点i到j的距离为 $d_{i j}$ ，巡逻点i到派出所的距离为 $d_{0 i}$ ，设 $R_{k}$ 表示第k台无人机的飞行路径，路径中的元素 $r_{k i}$ 表示第k台无人机的第i个途经点，需要注意的是路径的起点和终点皆为派出所，记派出所为 $r_{k 0}$ ， $n_{k}$ 为第k台无人机的途经点数（不含起点和终点）。若以航程最短为目标函数，则可建立以下的无人机巡逻路径优化模型：

m i n Z = \sum_{k = 1}^{K} \{\sum_{i = 1}^{n_{k}} [d_{r_{k (i - 1)} r_{k i}} + d_{r_{k n_{k}} r_{k 0}} s i g n (n_{k})]\}

，（1）

\sum_{i = 1}^{n_{k}} t_{r_{k i}} \leq T_{k}

，（2）

\sum_{i = 1}^{n_{k}} [d_{r_{k (i - 1)} r_{k i}} + d_{r_{k n_{k}} r_{k 0}} s i g n (n_{k})] \leq 15 (T_{k} - \sum_{i = 1}^{n_{k}} t_{r_{k i}})

，（3）

0 \leq n_{k} \leq L

，（4）

\sum_{k = 1}^{K} n_{k} = L

，（5）

R_{k} = {r_{k i} | r_{k i} \in \{1,2, \dots, L\}, i = 1,2, \dots, n_{k}}

，（6）

R_{k_{1}} ⋂ R_{k_{2}} = \emptyset, k_{1} \neq k_{2}

，（7）

s i g n (n_{k}) = \{\begin{matrix} 1, & n_{k} \geq 1, \\ 0, & 其他 。 \end{matrix}

（8）

其中，式（1）为目标函数；式（2）表示每架无人机在所有巡逻点逗留时间的总和不超过无人机的额定时间；式（3）表示每台无人机的飞行距离不超过其最大飞行距离；式（4）表示每架无人机经过的巡逻点数不超过总巡逻点数；式（5）表示每个巡逻点均需巡逻，且只需巡逻1次；式（6）表示每条巡逻路径所包含的巡逻点；式（7）表示任意2条巡逻路径之间无交集，即每个巡逻点只需1台无人机巡逻；式（8）表示当第k台无人机的巡逻点数大于等于1时，该台无人机参与了巡逻，取 $s i g n (n_{k}) = 1$ ，当第k台无人机的巡逻点数小于1时，该台无人机没有参与巡逻，取 $s i g n (n_{k}) = 0$ 。

2　算法介绍

2.1　遗传算法

遗传算法（genetic algorithm，GA）于20世纪70年代由美国科学家John Holland提出，主要借鉴生物界适者生存、优胜劣汰的遗传机制，并由此演化而来的一种搜索最优解的算法。在运用遗传算法时，一般将具体的搜索过程转化为满足适应度函数条件下染色体的交叉、变异过程。在选择个体时，一般保留使适应度函数达到最优的个体。

2.1.1　种　群

在搜索过程中，一条可行的路径是构成1个个体。比如，如果有10个巡逻点，编号为 $1 ， 2 ， \dots ， 10$ ，则这10个数的任意排列构成1个个体。由于采用的是无人机巡逻方式，所以路径中无重复节点。本文中，假设群体规模为N，则随机产生的N个个体便可形成初始群体。

2.1.2　进化机制

为实现对从混沌运动到问题可行解的充分搜索，本文依据染色体的编码方式，即路径信息的编码方式，提供以下进化机制。

2.1.2.1　遗　传

能使每代种群中适应度函数最小的个体自动遗传到下一代。

2.1.2.2　交　叉

选择2个个体，Population 1和Population 2，其序列顺序分别为：

Population 1： $5 4 3 6 8 10 9 2 1 7$ ，

Population 2： $3 8 9 4 7 5 6 2 1 10$ 。

随机产生2个在［1， L］（此处L为10）区间的自然数 $λ_{1}$ 和 $λ_{2}$ （ $λ_{1} \neq λ_{2}$ ），分别表示个体序列的第 $λ_{1}$ 和第 $λ_{2}$ 个位置。不妨假设 $λ_{1} < λ_{2}$ ，如 $λ_{1} = 2$ ， $λ_{2} = 7$ ，在Population 1中，第2~7位置的元素分别为4，3，6，8，10，9。这6个元素在Population 2中的次序为3，8，9，4，6，10，将序列3 8 9 4 6 10分别插入Population 1的第2~7位置，即可得到新的个体Population 1'，并将序列4 3 6 8 10 9分别插入Population 2的第3，8，9，4，6，10位置，即可得到Population 2'。 Population 1'和Population 2'的序列顺序分别为：

Population 1'： $5 3 8 9 4 6 10 2 1 7$ ，

Population 2'： $4 3 6 8 7 5 10 2 1 9$ 。

经交叉操作后，一共可得到4个个体，Population 1，Population 2，Population 1'和Population 2'，计算这4个个体的适应度，将较优的2个遗传至下一代。

2.1.2.3　变　异

随机产生2个在［1， L］区间的自然数 $λ_{1}$ 和 $λ_{2}$ （ $λ_{1} \neq λ_{2}$ ）。不妨假设 $λ_{1} < λ_{2}$ ，将序列中位于 $λ_{1}$ 和 $λ_{2}$ 之间的元素逆序排列。如 $λ_{1} = 5$ ， $λ_{2} = 8$ ，则长度为10的序列 $5 4 3 6 | 8 10 9 2 | 1 7$ ，变异后的顺序为 $5 4 3 6 |2 9 10 8| 1 7$ 。

2.2　爬山算法

爬山算法主要用于搜索当前个体邻域内的最优个体。具体操作如下：

对于选中的个体，交换任意2个个体的位置，得到新的个体。比较当前个体与新个体的适应度，将适应度较小的个体遗传至下一代。比如对长度为10的某个体序列 $5 4 3 | 6 | 8 10 9 | 2 | 1 7$ ，交换第4和第8位置，得到 $5 4 3 | 2 | 8 10 9 | 6 | 1 7$ ，计算这2个个体的适应度，选择适应度较小的个体。其伪代码如下：

tempRoute = currentRoute； %tempRoute为路径变量，currentRoute为当前路径

for i = 1： L-1 % L为巡逻点数

for j = i+1： L

temp = tempRoute （i）； % temp为临时变量

tempRoute（i） = tempRoute（j）；

tempRoute（j） = temp；

获取新路径的适应度；

如果原路径的适应度 > 新路径的适应度

% 更新路径和适应度

保存当前路径；

更新原路径适应度；

end

2.3　路径规划算法流程

由已有设备信息、地理信息以及各巡逻点所需的巡逻时间，可实现对无人机巡逻路径的规划。主要流程如下：

（1）初始化。

输入已有设备信息、巡逻点需要巡逻的时间信息以及巡逻点的坐标信息，并计算任意两个巡逻点之间的距离。随机产生初始种群，并计算种群的适应度。

（2）选择个体。

按照轮盘赌法则，选择种群个体，即计算个体的适应度 $F_{i}$ ，个体i被选择的概率为 $\frac{1 / F_{i}}{\sum_{j = 1}^{L} 1 / F_{j}}$ 。

（3）选择操作。

对种群个体按一定概率选择相应的操作（交叉或变异）搜索路径。比如，随机产生数P，若 $P < 0.9$ ，选择交叉操作；否则，选择变异操作。

（4）路径搜索。

有交叉和变异2种路径搜索方式，本文根据概率大小选择路径搜索方式，设交叉的概率为0.9，变异的概率为0.1。根据所选择的操作（交叉或变异），随机产生2个数 $λ_{1}$ 和 $λ_{2}$ ，搜索新的路径。

（5）路径更新。

计算新路径的适应度，并与上一代个体的适应度做比较，将适应度小的个体遗传至下一代。

（6）路径优化。

运用爬山算法优化路径，得到每代种群的最优路径，以实现全局最优。

（7）迭代循环。

重复步骤（2）~步骤（6）。当搜索次数等于 $m_{s}$ 时，停止搜索，输出最优路径和最优路径适应度。

（8）完成路径规划。

将当前最优路径信息传输至决策终端，指导无人机巡逻。

路径规划算法流程如图1所示。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 路径规划算法流程

Fig.1 Flow of path planning algorithm

3　仿真及比较

3.1　数值仿真

为验证算法的有效性，以杭州市滨江区长河派出所辖区为巡逻区域，辖区和巡逻地点示意如图2所示，其中，红色圆圈表示巡逻点，红色倒三角形表示派出所。在仿真过程中，所有无人机都从派出所出发，巡逻结束后返回派出所。各巡逻点的相对坐标信息及巡逻点需要巡航的时间如表1所示。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 长河派出所部分巡逻点相对位置示意

Fig.2 Schematic diagram of the relative positions of some patrol points under the jurisdiction of Changhe Police Station

表1 巡逻点的相对坐标信息及停留时间

Table 1 Relative coordinate information of patrol points and cruise time of patrol points

编号	巡逻点名称	横坐标x/km	纵坐标y/km	停留时间/h
1	中南乐游城	0.219	1.717	0.30
2	滨兴家园	0.421	1.591	0.30
3	杭州滨兴学校	0.781	1.727	0.30
4	滨兴小区	0.929	1.615	0.30
5	杭州蓝臣大酒店	0.463	0.859	0.30
6	英飞特大厦	1.011	0.991	0.12
7	新鸿宾大酒店	0.357	0.579	0.12
8	杭州森浩国际酒店	0.259	0.359	0.12
9	伟星旅馆	0.261	0.249	0.12
10	杭州乐天派英智康复医院	0.405	0.113	0.12
11	春波小区	1.879	1.521	0.12
12	春波南苑	1.937	1.303	0.12
13	滨康小区	1.535	0.609	0.12
14	滨康二苑	1.531	0.417	0.12
15	康庭酒店	1.709	0.468	0.12
16	西兴街道办事处	1.847	0.385	0.12
17	迎春南苑	2.385	1.713	0.12
18	滨江御滨府	2.687	1.701	0.12
19	三江商厦	2.799	1.429	0.12
20	铁岭花园西区	2.247	1.461	0.12
21	云厦连园	2.563	1.303	0.30
22	西陵社区	2.811	1.185	0.12
23	西陵饭店	2.743	1.091	0.12
24	东方花城	3.127	1.051	0.30
25	滨安小区	2.327	1.019	0.21
26	官河锦庭	2.507	0.899	0.12
27	玲珑府	2.675	0.925	0.12
28	速8酒店	2.897	0.755	0.12
29	映映红园区	2.771	0.618	0.10
30	湖头陈农贸市场	3.175	0.177	0.20
31	湖头陈花苑	3.091	0.069	0.10
32	长河派出所	0.385	0.485	0

新窗口打开| 下载CSV

若无人机巡逻了点1，2，3，则无人机实际飞行距离为 $d = d_{01} + d_{12} + d_{23} + d_{30}$ 。假设派出所有5架无人机，每架无人机的最大飞行距离均为18.00 km，每架无人机空中最长停留时间皆为2.00 h。在仿真过程中，种群规模（number of population）为200，迭代次数（number of iteration）为200。仿真结果如图3~图5所示。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 第1代种群中最优个体的巡航路径

Fig.3 Patrol path of the best individual in the first generation population

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 迭代200次的最优巡航路径

Fig.4 Optimal patrol path after 200 iterations

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 迭代过程最短路径的变化

Fig.5 Shortest path changes during iteration process

图3为第1代种群中最优个体的巡航路径，不同颜色的箭头表示不同无人机巡航所经过的巡逻点。从图3中可以看出，共需3架无人机，其中，第1架无人机的巡逻路线为32→29→12→28→14→19→5→24→11→18→26→2→15→32；第2架无人机的巡逻路线为32→16→4→20→13→21→17→6→23→27→32；第3架无人机的巡逻路线为32→31→1→22→7→8→10→25→9→30→3→32，3架无人机总巡航距离为37.07 km。

图4为经过遗传迭代200次后的最优巡航路径。从图4中可以看出，仍需3架无人机，其中，第1架无人机的巡逻路线为32→13→14→15→16→31→30→29→28→24→22→23→27→26→25→32；第2架无人机的巡逻路线为32→12→21→19→18→17→20→11→4→3→6→32；第3架无人机的巡逻路线为32→5→ 2→1→7→8→9→10→32，3架无人机总航行距离为17.36 km。当然，这并不是全局最优路径，比如将图4中第2架无人机的巡逻路线更换为32→12→20→21→19→18→17→11→4→3→6→32，则总航行距离为17.31 km，达最优。图5显示了迭代过程最短路径的变化。由图5可知，在寻优过程中，寻优前期适应度变化明显，后期变化不明显，这从另一方面说明所设计的种群遗传算法迭代200次是合理的。

3.2　算法比较

遗传算法对求解路径优化类问题效果较好，本文运用融合爬山算法的混合遗传算法，取得了较好的优化巡航路径效果。为更好地说明算法的优越性，将传统遗传算法和混合遗传算法进行了比较。为方便比较，先将种群规模设置为80，重复运行20次，结果如表2所示；再将种群规模设置为200，重复运行20次，结果如表3所示。从表2和表3中可以看出，同一种算法，种群规模越大，寻优的平均结果越好，但花费的平均时间更多。无论种群规模是80还是200，混合遗传算法的寻优平均结果均明显优于传统遗传算法，但所花费的时间略长。

表2 种群规模为80运行20次的结果

Table 2 Results of 20 runs when population size is 80

算法	获得全局最优数/次	最优路径平均巡航距离/km	搜索最优路径所花费的平均时间/s
传统遗传算法	0	20.236 7	16.789 2
混合遗传算法	1	19.558 9	70.161 7

新窗口打开| 下载CSV

表3 种群规模为200运行20次的结果

Table 3 Results of 20 runs when population size is 200

算法	获得全局最优数/次	最优路径平均巡航距离/km	搜索最优路径所花费的平均时间/s
传统遗传算法	1	19.557 8	36.852 1
混合遗传算法	4	18.159 1	88.181 5

新窗口打开| 下载CSV

4　结论

针对警用无人机的巡逻问题，结合实际巡航任务提出了针对性优化模型。考虑遗传算法具有较好的全局特性、爬山算法具有较优的局部特性，在无人机巡逻路径优化中，将遗传算法与爬山算法相融合，提出了混合遗传算法。仿真结果表明，提出的混合遗传算法在寻优效果上明显优于传统遗传算法。

http://dx.doi.org/10.3785/j.issn.1008-9497.2024.01.004

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

卢文忠，杨俊峰.

抗疫精神融入公安院校治安学专业课程的教学实践探索

［J］. 铁道警察学院学报， 2022， 32（6）： 120-124. DOI：10.19536/j.cnki.411439. 2022.06.020