基于改进野马算法与A-_算法融合的分段路径规划_李广源.pdf

第 31 卷 第 4 期 2023 年 8 月Vol.31 No.4Aug.2023电脑与信息技术Computer and Information Technology文章编号：1005-1228（2023）04-0006-05基于改进野马算法与 A*算法融合的分段路径规划李广源1，魏永勇2，霍少凯3，白梅娟1，侯帅1（1河北工程大学，河北 邯郸 056038；2中国兵器科学研究院，北京 100089；3.中华通信系统有限公司，河北 石家庄 050299）摘要：作战过程的路径规划问题属于仿真过程中的一个重要决策环节，针对作战路径规划问题，文章提出了一种考虑作战特性的分段混合的路径优化算法。首先，提出了一种融合个体自适应精度约束的野马优化算法和 A*算法的分段混合（Improved Wild Horse Optimization Algorithm and A*Algorithm Based On Fusion,IAWHO_A*）路径优化算法模型，该模型由路径阶段划分模型、自适应个体精度约束的野马优化算法和 A 算法构成。其次，提出了一种考虑火力覆盖范围特性的路径阶段划分模型，将路径划分快速突进段和隐蔽突进段两个阶段；最后，提出了一种改进的个体自适应精度约束的野马优化算法（IAWHO）优化快速突进段的路径，IAWHO 引入个体自适应精度约束以提高算法的全局最优解。文章算法在已有的城市路径规划上进行了仿真实验研究，并取得了良好的实验效果，本文的研究内容为作战路径规划奠定了重要的理论研究基础。关键词：分段混合；个体自适应精度；野马优化算法；A*算法中图分类号：TP18文献标识码：AImproved Wild Horse Optimization Algorithm and A*Algorithm Based On Fusion to Solve Route PlanningLI Guang-yuan1,WEI Yong-yong2,HUO Shao-kai3,BAI Mei-juan1,HOU Shuai1（1.Hebei University of Engineering,Handan 056038,China;2.China Academy of weapons science,Beijing 100089,China;3.China Communications System Co,Shijiazhuang 050299,China）Abstract：The path planning problem of combat process is an important decision link in the simulation process.Aiming at the path planning problem of combat,this paper proposes a piecewise hybrid path optimization algorithm considering combat characteristics.Firstly,an Improved Wild Horse Optimization Algorithm and A*Algorithm Based on On Fusion(IAWHO_A*)path optimization algorithm model is proposed,which is composed of path stage division model,adaptive individual precision constraint wild horse optimization algorithm and A*algorithm.Secondly,a path stage division model considering the characteristics of fire coverage is proposed,which divides the path into two stages:fast penetration stage and hidden penetration stage.Finally,an improved individual adaptive precision constrained wild horse optimization algorithm(IAWHO)is proposed to optimize the path of the fast advance segment.IAWHO introduces individual adaptive precision constraints to improve the global optimal solution of the algorithm.The algorithm in this paper has carried out simulation experiments on the existing urban path planning,and achieved good experimental results.The research content of this paper lays an important theoretical research foundation for the path planning of combat.Key words:path stage division;adaptive individual precision;Wild Horse Optimization;A*;algorithm收稿日期：2022-09-22基金项目：河北省重点研发计划项目（项目编号：21350101D）；国家自然科学基金项目（项目编号：61802107）作者简介：李广源（1997-），男，山东临沂人，硕士研究生，主要研究方向为人工智能；（通信作者）魏永勇（1978-），男，湖北广水人，研究员，硕士研究生，主要研究方向为装备体系设计与仿真评估；霍少凯（1993-），男，研究员，硕士研究生，主要研究方向为通信；白梅娟（1990-），女，河北邯郸人，实验师，硕士研究生，主要研究方向为人工智能与智能信息处理；侯帅（1984-），男，河北邯郸人，副教授，博士，主要研究方向为人工智能。作战路径规划是战场指挥过程中的重要环节，以往路径规划研究方法通常将整条路径作为一个整体的来考虑，实际上作战中红方进入蓝方的火力覆盖范围之前的时候，更加注重抢占先机以达到快到达火力范DOI:10.19414/ki.1005-1228.2023.04.024第 31 卷 第 4 期7李广源等，基于改进野马算法与 A*算法融合的分段路径规划围覆盖点，而在进入蓝方火力覆盖范围后，更应该注意隐蔽性，避免红方遭受蓝方打击。目前尚未见有相关研究。因此本文拟开展相关的研究工作。路径规划算法主要有传统算法（如 Dijkstra 算法1、A*算法2）、蚁群算法3、粒子群算法4和遗传算法 5 等。由于遗传算法具有较好的并行性和鲁棒性，被广泛应用于 AGV 路径规划中6，但算法本身却有早熟收敛和局部搜索能力较弱等缺点7。本文提出一种改进的野马优化算法与 A*算法融合的分段混合路径规划算法（Improved Wild Horse Optimization Algorithm and A*Algorithm Based On Fusion），首先通过火力覆盖范围特性，建立路径阶段划分模型8将路径划分为快速突进段和隐蔽突进段，其次，基于快速突进段的特性，提出一种改进的野马优化算法规划快速突进段路径，野马优化算法是一种按照野马社会行为而设计的新型算法9，具备寻优能力强，收敛速度快等特点10，截止目前，还未有文献将 WHO 应用于路径规划。其次，基于隐蔽突进段的特性，提出 A*算法对隐蔽突进段进行路径规划11。最后，提出的基于个体自适应精度约束的野马优化算法（IAWHO），采用自适应精度约束参数控制个体的优劣，能有效地提高个体精度，筛掉不良个体，提高收敛效率。1问题建模与分析在仿真路径规划的过程中，从起始点到目标点具有路程长、耗能高和威胁性高等特点，整段路径根据蓝方火力覆盖范围可以划分为快速突进段和隐蔽突进段。快速突进阶段，即当红方处于敌人火力覆盖范围前的阶段，红方为了保障抢夺先机和后期燃料保障，就需要采用速度快和消耗低的方式到达火力范围边缘路径交叉点。隐蔽突进段，即当红方实体进入蓝方的火力范围覆盖范围后，红方应当注意隐蔽性，靠近障碍物和避免通视的方式到达目标点。1.1问题优化目标计算模型红 方 速 度 为 V，地 图 纵 坐 标 上 下 限（ybottom,ytop），横坐标左右限为（xleft,xright），起始点为PA=（xA,yA），目标点为 PB=（xB,yB），整个路径网由 u 个关键节点),(kikikiyxP=组成，快速突进最优路径 Sq由 n 个路径关键点),(qiqiqiyxP=组成，其次，隐蔽突进最优路径Sh由 m 个路径关键点),(riririyxP=组成，其中可行火力覆盖范围与路径交叉点为),(eieieiyxP=，相邻两个路径关键点连接成的线段 si如式（1）所示：)()(11+=iiiiiyyxxs（1）快速突进段需要保证红方可以快速到达目标点，其优化目标为行进时间如下所示：快速突进段所需的行进时间 T 如式（2）所示：=niiVsnT11（2）隐蔽突进段需要保证红方可以在通视性低和行进时间短的条件下到达目标点，往往路径关键点kiP与目标点之间的通视性会被树林、高楼、山丘这些遮蔽物所影响，优化目标通视性如下所示：设隐蔽突进段中各路径关键点kiP与目标点之间等距离分成g个节点，每个节点上可能会出现遮蔽物，遮蔽物的等级分别为 1，2，3 级，最高等级为 3，因此可设路径关键点的通视性矩阵为 dij，则当前路径关键点的通视性可设如式（3）所示：（3）隐蔽突进段当前路径关键点预估到达时间如式（4）所示：Vstii=（4）快速突进段路径方案价值目标函数如式（5）所示：min(T)=T （5）隐蔽突进段路径关键点代价函数如式（6）所示：min(Di+ti)=Di+ti（6）问题约束条件如式（7）所示：（7）1.2环境模型建立路径规划前，需要对地图环境进行建模，采用拓图 1地理信息图电脑与信息技术 2023 年 8 月8扑地图法对路径规划空间进行环境建模，地图模型如图 1 所示：图中黄色路径代表路径网，19、13 和 14 代表路径关键点，红色圆圈代表火力覆盖范围，A 点和 B点分别代表起始点和目标点。可达火力覆盖范围与路径的交叉点为 10、11 和 12。1.3野马优化算法野马优化算法是模仿野马的社会行为所设计的算法，用于求解多维空间中整体的最优解8。通过随机生成初始种群，以种群中每个个体适应度值为选择标准进行迭代优化，主要包括小马驹的放牧行为，马的交配行为，种马的团队带领行为，以及各种群领导者的选拔行为12。1.3.1 自然数编码解码本文采用的自然数编码的方式。每个个体为n维，每维上的数字代表要走的一个关键节点，其中编码按顺序生成路线，自然数编码如图 2 所示。3 2 1 4 6 7 5个体编码图 2自然数编码图如图所示，路径方案可以表示为 A-3-2-1-4-6-7-5-B。IAWHO_A*采用循环的方式进行编码，首先，对维度为 Z 的个体使用 IAWHO 进行优化，其次，使用维度为 Z+1 的个体进行优化，直到使用维度为 L的个体进行优化，最后，生成 L-Z+1 个路径方案并进行比较，选取价值最高的路径方案。1.3.2 适应度函数适应度是评价个体位置优劣和更新个体位置的关键元素。最优的个体是适应度最高的种群个体。快速突进段的目标函数为该路径方案的时间成本，当前路径方案时间成本越低，该个体的适应度越高，反之则相反。则适应度函数设置如式（8）所示：2001.0