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

doi:10.3785/j.issn.1008-9497.2024.01.004

浙江大学学报（理学版）

2024, Vol. 51

Issue (1): 21-28 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

Guojun LI¹,Ziwan ZHENG²(

),Yingsheng FAN¹,Tiantian LU¹,Zhijiang XU³

^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

全文: PDF(940 KB)

HTML( 4 )

摘要：

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

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

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.

Key words: genetic algorithm hill-climbing algorithm patrol path optimization

收稿日期: 2023-02-01 出版日期: 2024-01-10

CLC:

O 224

基金资助: 2023JC32;浙江省“尖兵”“领雁”攻关计划项目(2023C01030);国家自然科学基金青年项目(41901160)

通讯作者: 郑滋椀 E-mail: zhengziwan@zjjcxy.cn

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

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	李国军
	郑滋椀
	范英盛
	卢甜甜
	徐志江

引用本文:

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

Guojun LI,Ziwan ZHENG,Yingsheng FAN,Tiantian LU,Zhijiang XU. The optimization of multi-UAVs patrol path with hybrid genetic algorithm. Journal of Zhejiang University (Science Edition), 2024, 51(1): 21-28.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2024.01.004 或 https://www.zjujournals.com/sci/CN/Y2024/V51/I1/21

图1 路径规划算法流程

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

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

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

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

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

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

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

1	卢文忠，杨俊峰. 抗疫精神融入公安院校治安学专业课程的教学实践探索［J］. 铁道警察学院学报， 2022， 32（6）： 120-124. DOI：10.19536/j.cnki.411439. 2022.06.020 LU W Z， YANG J F. Exploring the teaching practice of integrating the spirit of anti epidemic into the public security course in public colleges and universities［J］. Journal of Railway Police College， 2022， 32（6）： 120-124. DOI：10.19536/j.cnki.411439. 2022.06.020 doi: 10.19536/j.cnki.411439. 2022.06.020
2	邹青，刘小丽. 屯警街面全天候巡逻：潜江市推出警务综合服务新模式［J］. 领导科学论文（下）， 2015（4）： 37-38. DOI：10.3969/j.issn.2095-5103.2015. 04.015 ZOU Ｑ， LIU X L. Police patrol on the street all day ： Qianjiang city launched a new model of comprehensive police service［J］. Leadership Science Thesis （Volume II）， 2015（4）： 37-38. DOI：10.3969/j.issn.2095-5103.2015.04.015 doi: 10.3969/j.issn.2095-5103.2015.04.015
3	董晓霖. 大数据在社会治安防控中的应用探索［J］. 中国新通信， 2021， 23（13）： 147-148. DOI：10.3969/j.issn.1673-4866.2021.13.075 DONG X L. Application of big data in social security prevention and control［J］. China New Communications， 2021， 23（13）： 147-148. DOI：10.3969/j.issn.1673-4866.2021.13.075 doi: 10.3969/j.issn.1673-4866.2021.13.075
4	张叶彤. 社区警务网格化管理的优化研究：以南京市G区J派出所为例［D］. 南京：南京大学， 2019. ZHANG Y T. Research on Optimizing Grid Management of Community Policing： J Police Station in G District， Nanjing City is Taken as an Case［D］. Nanjing： Nanjing University， 2019.
5	沈建十，叶宏杰. 关于深化完善社会治安巡逻防控体系建设的实践与思考：以宁波市社会治安四级巡逻防控体系建设为例［J］. 公安研究， 2012（12）：22-27. SHEN J S， YE H J. Practice and thinking on perfecting the construction of social security patrol prevention and control system： Take the construction of the four-level patrol prevention and control system of social security in Ningbo as an example［J］. Policing Studies， 2012（12）：22-27.
6	李路，王行愚，江开忠. 基于k阶不可逆邻接矩阵的警车巡逻［J］. 电气自动化， 2010， 32（4）： 32-34.DOI：10.3969/j.issn.1000-3886.2010.04.012 LI L， WANG X Y， JIANG K Z. Police cars patrol based on k-order irreversible adjacency matrix［J］. Electrical Automation， 2010， 32（4）： 32-34. DOI：10.3969/j.issn.1000-3886.2010.04.012 doi: 10.3969/j.issn.1000-3886.2010.04.012
7	吴思远. 全局最优警车巡逻区域最大覆盖调度策略［J］. 广西师范大学学报（自然科学版）， 2010（1）：96-99. DOI：10.3969/j.issn.1001-6600.2010.01.022 WU S Y. Global optimum maximal coverage scheduling strategy for police cars deployment［J］. Journal of Guangxi Normal University （Natural Science Edition） 2010（1）： 96-99. DOI：10.3969/j.issn.1001-6600.2010.01.022 doi: 10.3969/j.issn.1001-6600.2010.01.022
8	FRAZIER A E， BAGCHI-SEN S， KNIGHT J. The Spatio-temporal impacts of demolition land use policy and crime in a Shrinking city［J］. Applied Geography， 2013， 41：55-64. DOI：10.1016/j.apgeog.2013.02.014 doi: 10.1016/j.apgeog.2013.02.014
9	LERMAN Y， ROFE Y， OMER I. Using space syntax to model pedestrian movement in urban transportation planning［J］. Geographical Analysis， 2014， 46（4）：392-410. DOI：10.1111/gean.12063 doi: 10.1111/gean.12063
10	JIANG B， OKABE A. Different ways of thinking about street networks and spatial analysis［J］. Geographical Analysis， 2014， 46（4）： 341-344. DOI：10.1111/gean.12060 doi: 10.1111/gean.12060
11	SHIODE S， SHIODE N. Network-based space- time search-window technique for hotspot detection of street-level crime incidents［J］. International Journal of Geographical Information Science， 2013， 27（5）： 866-882. DOI：10.1080/13658816. 2012.724175 doi: 10.1080/13658816. 2012.724175
12	SHIODE S， SHIODE N， BLOCK R， et al. Space- time characteristics of micro-scale crime occurrences： An application of a network-based space-time search window technique for crime incidents in Chicago［J］. International Journal of Geographical Information Science， 2015， 29（5）： 697-719. DOI：10.1080/13658816.2014.968782 doi: 10.1080/13658816.2014.968782
13	WEISSBURD D L， GROFF E R， YANG S. The Criminology of Place： Street Segments and Our Understanding of the Crime Problem［M］. New York：Oxford University Press， 2012. DOI：10.1093/acprof：oso/9780195369083.001.0001 doi: 10.1093/acprof：oso/9780195369083.001.0001
14	DINC S， DINC I. Evaluation of unsupervised classification on police patrol zone design problem［C］// IEEE SoutheastCon 2018. St Petersburg： IEEE， 2018： 1-7. DOI：10.1109/secon.2018.8478908 doi: 10.1109/secon.2018.8478908
15	ALLEN B. Case study： Using crime data and open source data to design a police patrol area［J］. SMU Data Science Review， 2018， 1（1）： 1-22.
16	MUKHOPADHYAY A， CHAO Z， VOROBEYCHIK Y， et al. Optimal allocation of police patrol resources using a continuous-time crime model［C］// International Conference on Decision and Game Theory for Security. New York ： GameSec， 2016： 139-158. DOI：10.1007/978-3-319-47413-7_9 doi: 10.1007/978-3-319-47413-7_9
17	SAINT-GUILLAIN M， PAQUAY C， LIMBOURG S. Time-dependent stochastic vehicle routing problem with random requests： Application to online police patrol management in Brussels［J］. European Journal of Operational Research， 2020， 292（3）： 869-885. DOI：10.1016/j.ejor.2020.11.007 doi: 10.1016/j.ejor.2020.11.007
18	HUTT O K， BOWERS K， JOHNSON S D. The Effect of GPS refresh rate on measuring police patrol in microplaces［J］. Crime Science， 2021， 10（1）：1-14. DOI：10.1186 /s40163-021-00140-1 . doi: 10.1186 /s40163-021-00140-1
19	PIZA E L， GILCHRIST A M， CAPLAN J M， et al. The financial implications of merging proactive CCTV monitoring and directed police patrol： A cost-benefit analysis［J］. Journal of Experimental Criminology， 2016， 12（3）： 403-429. DOI：10.1007/s11292-016-9267-x doi: 10.1007/s11292-016-9267-x
20	RYDBERG J， MCGARRELL E F， NORRIS A， et al. A Quasi-experimental synthetic control evaluation of a place-based police-directed patrol intervention on violent crime［J］. Journal of Experimental Criminology， 2018， 14（1）： 83-109. DOI：10.1007/s11292-018-9324-8 doi: 10.1007/s11292-018-9324-8
21	CHEN X. Fast patrol route planning in dynamic environments［J］. IEEE Transactions on Systems Man and Cybernetics， Part A： Systems and Humans， 2012， 42（4）： 894-904. DOI：10.1109/tsmca.2012.2183361 doi: 10.1109/tsmca.2012.2183361
22	CHEN X. Police patrol optimization with security level functions ［J］. IEEE Transactions on Systems Man and Cybernetics Systems， 2013， 43（5）： 1042-1051. DOI：10.1109/tsmca.2012.2226025 doi: 10.1109/tsmca.2012.2226025
23	ZHU S， BUKHARIN A W， LU L， et al. Data-driven optimization for police beat design in South Fulton， Georgia［Z］. （2021-08-24）. https：//doi.org/10.48550/ arXiv.2004.09660.
24	ZHU S， WANG H， XIE Y. Data-driven optimization for police zone design［Z］. （2021-11-02）. https：//doi.org/10.48550/arXiv.2104.00535.
25	杨旭，王锐，张涛. 面向无人机集群路径规划的智能优化算法综述［J］. 控制理论与应用， 2020， 37（11）： 2291-2302. DOI：10.7641/cta.2020.00157 YANG X， WANG R， ZHANG T. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization［J］. Control Theory & Applications， 2020， 37（11）： 2291-2302. DOI：10. 7641/cta.2020.00157 doi: 10. 7641/cta.2020.00157
26	郎茂祥，胡思继. 用混合遗传算法求解物流配送路径优化问题的研究［J］. 中国管理科学， 2002， 10（5）： 51-56. DOI：10.3321/j.issn：1003-207x.2002.05.011 LANG M X HU S J. Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm［J］. Chinese Journal of Management Science， 2002， 10（5）： 51-56. DOI：10. 3321/j.issn：1003-207x.2002.05.011 doi: 10. 3321/j.issn：1003-207x.2002.05.011
27	胡小建，杨智. 基于混合遗传算法的多拣货小车路径规划研究［J］. 合肥工业大学学报（自然科学版）， 2022， 45（12）： 1715-1722. DOI：10.3969/j.issn.1003-5060.2022.12.019 HU X J， YANG Z. Research on path planning of multi-picking car based on hybrid genetic algorithm［J］. Journal of Hefei University of Technology（Natural Science）， 2022， 45（12）： 1715-1722. DOI：10.3969/j.issn.1003-5060.2022.12.019 doi: 10.3969/j.issn.1003-5060.2022.12.019
28	丛玉良，孙闻晞，薛科，等. 基于改进的混合遗传算法的车联网任务卸载策略研究［J］. 通信学报， 2022， 43（10）： 77-85. DOI：10.11959/j.issn.1000-436x.2022188 CONG Y L， SUN W X， XUE K， et al. Research on task offloading strategy of internet of vehicles based on improved hybrid genetic algorithm［J］. Journal on Communications， 2022， 43（10）： 77-85. DOI：10. 11959/j.issn.1000-436x.2022188 doi: 10. 11959/j.issn.1000-436x.2022188
29	张铁，胡亮亮，邹焱飚. 基于混合遗传算法的机器人改进摩擦模型辨识［J］. 浙江大学学报（工学版）， 2021， 55（5）： 801-810. DOI：10.3785/j.issn.1008-973X.2021.05.001 ZHANG T， HU L L， ZOU Y B. Identification of improved friction model for robot based on hybrid genetic algorithm［J］. Journal of Zhejiang University（Engineering Science）， 2021， 55（5）： 801-810. DOI：10.3785/j.issn.1008-973X.2021.05.001 doi: 10.3785/j.issn.1008-973X.2021.05.001
30	张玉州，徐廷政，郑军帅. 基于混合遗传算法的紧急程度不确定应急物流问题求解［J］. 系统科学与数学， 2020， 40（4）： 714-728. DOI：10.12341/jssms13847 ZHANG Y Z， XU T Z， ZHENG J S. Solving emergency logistics problem with uncertain urgency based on a hybrid genetic algorithm［J］. Journal of Systems Science and Mathematical Sciences， 2020， 40（4）： 714-728. DOI：10.12341/jssms13847 doi: 10.12341/jssms13847

[1]	肖冉, 安新磊, 祁慧敏, 乔帅. 电场作用下HR神经元的分岔分析及参数辨识[J]. 浙江大学学报（理学版）, 2022, 49(6): 691-697.
[2]	厉康平, 汪鹏君, 张会红. 基于模拟退火遗传算法的三值FPRM电路功耗优化[J]. 浙江大学学报（理学版）, 2016, 43(2): 190-194.
[3]	卜登立. 基于混合遗传算法的MPRM最小化[J]. 浙江大学学报（理学版）, 2016, 43(2): 184-189.
[4]	何江平 1,唐景昌 1,唐叔贤 2. 遗传算法在低能电子衍射结构分析中的应用[J]. 浙江大学学报（理学版）, 2000, 27(5): 503-507.
[5]	邓明荣　鲍永广　沈祖志 . 遗传算法在热电厂生产调度优化中的应用 [J]. 浙江大学学报（理学版）, 1998, 25(4): 24-27.

Viewed

Full text

Abstract

Cited

Shared

Discussed