基于遗传算法的多无人机对岸打击任务分配研究.pdf

总第352期1引言无人机（Unmanned Aerial Vehicle，UAV）发展迅速，已被广泛用于现代战争中1。随着现在战场环境日益复杂，完成任务目标往往需要完成多项不同的子任务，而单个无人机由于自身条件受限，无法完成复杂任务，所以使用多无人机进行作战任务将会是无人机参与作战的关键问题。目前针对多无人机任务分配问题已经展开了大量的研究，主要的研究方向一是利用合同网协议实现异构无人机任务分配24。二是传统算法例如丁家如采用匈牙利算法改进无人机任务分配5，Shima 等提出了针对典型的侦查、打击、评估任务的 CMTAP 模型，但并未考虑无人机火力不同对任务分配的影响6。收稿日期：2023年4月10日，修回日期：2023年5月27日作者简介：何应强，男，硕士研究生，研究方向：指挥控制信息系统。陈行军，男，博士，硕士生导师，副研究员，研究方向：作战指挥决策理论与方法。周晶，男，博士，副研究员，研究方向：模式识别与智能系统，辅助决策与智能系统。王义涛，男，博士，博士生导师，研究员，研究方向：指挥信息系统工程。基于遗传算法的多无人机对岸打击任务分配研究何应强陈行军周晶王义涛（海军大连舰艇学院作战软件与仿真研究所大连116018）摘要无人机在军事领域发展迅速，在对岸打击任务中无人机能够发挥打击作用，但无人机载弹量有限无法单独完成战备工程的打击任务，往往需要多种无人机共同完成打击任务。为实现最大化打击效果，需要找出最优任务分配完任务，针对异构无人机打击对岸目标的任务分配最优求解问题，采用遗传算法求解最优任务分配方案，通过对对岸打击任务分配模型建模，得出遗传算法的适应度函数。基于遗传算法容易“早熟”的问题，在遗传算法迭代过程中调整最优个体遗传数目和变异概率，提高遗传算法效率。最后通过仿真实验验证，改进的遗传算法能有效解决异构无人机打击对岸目标的任务分配问题。关键词异构无人机；遗传算法；对岸打击任务分配；动态调整中图分类号TP301.6DOI：10.3969/j.issn.1672-9730.2023.10.008Research on Task Assignment for Multi-UAV Shore StrikeBased on Genetic AlgorithmsHE YingqiangCHEN XingjunZHOU JingWANG Yitao（Institute of Operation Software and Simulation，Dalian Naval Academy，Dalian116018）AbstractUnmanned aerial vehicles（UAVs）have developed rapidly in the military field，and they can play a role in the onshore attack tasks.However，the limited amount of missiles on the UAVs can not complete the combat readiness project alone，andoften need a variety of UAVs to complete the attack tasks together.In order to maximize the hitting effect，it is necessary to find outthe optimal task assignment，and to solve the optimal task assignment problem for heterogeneous unmanned aerial vehicles hittingthe target on the shore.This paper uses the genetic algorithm to solve the optimal task assignment scheme.By modeling the task assignment model on the shore hitting，the fitness function of the genetic algorithm is obtained.Based on the problem that genetic algorithm is easy to premature.In the process of genetic algorithm iteration，the optimal individual genetic number and the probabilityof variation are adjusted to improve the efficiency of genetic algorithm.Finally，the simulation results show that the improved geneticalgorithm can effectively solve the task assignment problem of heterogeneous unmanned aerial vehicles hitting the target on the shore.Key Wordsheterogeneous UAV，genetic algorithms，shore strike task assignment，dynamic adjustmentClass NumberTP301.6舰 船 电 子 工 程Ship Electronic Engineering总第 352 期2023 年第 10 期Vol.43 No.1032舰 船 电 子 工 程2023 年第 10 期还有就是利用智能算法，有蚁群算法79、粒子群算法10、狼群算法11、遗传算法1213等以解决多无人机任务分配问题计算，但计算方案规模相对较小。遗传算法在进行多无人机任务分配问题计算时，具有可拓展性强，计算速度快等特点，但传统遗传算法计算过程中存在“早熟”情况，使算法陷入局部最优解。本文采用优化遗传算法求解异构多无人机对岸打击任务分配问题，对无人机对岸打击任务分配问题进行建模，用遗传算法求解优化目标的基础上，增加多种交叉变异算子，动态调整遗传算法的遗传率，避免遗传算法出现过度“早熟”现象，并提升迭代效率，相比于穷举法和传统遗传算法能在更短时间内求取可行解，完成异构多无人机的对岸打击任务分配。2多无人机对岸打击任务分配数学模型多无人机协同对岸打击任务是多无人机打击多个岸上目标，岸上目标均为固定目标，不会移动，无人机一次只能打击一个目标，而目标根据打击要求，可以被多个无人机同时打击。有多个无人机与目标的打击关系组成任务分配。本文对任务分配的目标是在一定约束条件下，实现整体作战效能最优。2.1输入参数假设有N个无人机，M个目标，无人机由多种型号组成，其中，无人机的序号为i，飞行速度为Vi（i=1，2，N），作战半径为Di（i=1，2，N），导弹射程为Ri（i=1，2，N），目标的序号为k，目标所需的兵力数量为Uk（k=1，2，M）。无人机与目标的距离为Tik（i=1，2，N，k=1，2，M），无人机与目标在染色体上的映射关系为 Yik（i=1，2，N，k=1，2，M）。2.2约束条件2.2.1各个无人机的分配逻辑在打击目标所需无人机数未达到目标时，可以分配无人机打击此目标。当打击目标所需无人机数达到目标时，无人机不能在分配到打击此目标的任务中。2.2.2各个无人机的作战半径当染色体中无人机与目标的映射对应的距离超出了无人机的作战半径时，则该无人机无法打击对应目标，无人机成功打击目标记为Sik（i=1，2，N，k=1，2，M），Sik满足：Sik=1TikDii，kYik0TikDii，kYik（1）2.2.3目标打击要求完成数量为实现整体作战效能最优，完成打击要求打击的数量应该越多越好。目标完成情况Ck用下式表示：Ck=1UkiNSik0(k0=k)0UkiNSik0(k0=k)（2）无人机数量如果没有满足目标所需兵力数量时，则没有完成目标打击任务，相当于为完成实验需求。目标完成总数 Cn为各个 Ck之和，Cn越大越好。2.2.4各个无人机的巡航速度为实现整体作战效能最优，作战总时长应该被尽可能地缩短。作战总时长用下式表示：Zn=i=1NTikSikVi（3）Zn越小越好。3遗传算法遗传算法（Genetic Algorithm，GA）是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的高效全局寻优搜索算法。其具体流程如图1所示。对岸任务分配兵力与目标编码产生初始种群计算适应度函数满足终止条件？否根据适应度选择个体交叉变异是形成新种群输出最优解图1遗传算法具体流程33总第352期3.1编码方法本文采用十进制编码方式表示，一条染色体对应无人机序列，另一条染色体对应目标序列，两条染色体结合形成无人机映射目标的任务分配方案，本文中一个无人机只能打击一个目标，因此其染色体长度应等于无人机数量。3.2适应度函数适应度函数也称评价函数，是根据目标函数确定的用于区分群体中个体好坏的标准。本文根据上一章模型，由式（3）作为适应度函数以判断任务分配方案的质量。3.3选择算子本文采用最佳保留策略，当前群体中适应度最高的个体结构完整地复制到下一代群体中。其主要优点是能保证遗传算法终止时得到的最后结果是历代出现过的最高适应度的个体。3.4交叉算子本文采用了翻转、交换、迁移策略，根据随机数确定两个交叉点，再利用两个交叉点进行基因翻转、交换、迁移变换，对无人机所对应的目标进行改变，形成新的个体，期望获得更好的适应度个体。3.5变异算子在遗传算法中引入了变异算子来产生新的个体。变异算子维持了群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有基因值，从未可以改变个体编码串的结构，维持群体的多样性，这样有利于防止出现早熟现象。变异算子是的遗传算法在接近最优解邻域时能加速像最优解收敛，并可以维持群体多样性避免未成熟收敛。3.6参数设置为了避免遗传算法出现“早熟”现象，本文动态的改变了遗传算法的个体遗传数。在多次没有更进一步获得最优适应度值时，减少个体遗传至下一代，提高变异效率，扩大搜索空间，提高搜索效率，使遗传算法能更快获得最优适应度值。4仿真实验实验设置种群大小为 80，为了避免遗传算法陷入局部最优解，初始时将适应度函数取值最低的前10个个体直接遗传到下一代，对遗传下来的各个个体进行一次翻转交叉、交换交叉、迁移交叉操作，四次变异交叉操作，组成新的群体进行下一次计算，在迭代过程中减少个体直接遗传到下一代的数量，增加变异交叉操作，提升遗传算法进化效率。4.1第一组实验假设有十架不同型号的无人机，无人机参数如表1所示。表1第一组、第二组仿真无人机参数无人机序号飞行速度/（m/s）作战半径/km导弹射程/km18090080285900803909509049510001005100110012061051050100711011001208115110010091201200120101251200100假设有十个目标，十个目标均只需一个无人机即可完成打击。无人机和目标分布如图2所示。01002003004005006007008009001000100090080070060050040030020010009546732 281010867324159红蓝图2第一、二组实验无人机（红）与目标（蓝）位置分布图这种情况下无人机数量与完成任务所需无人机数相等，分配逻辑相对简单，所以在此实验中最大遗传代数为 100，采取10代无优化开始减少遗传个数，只保留前5个个体，每个个体进行一次翻转交叉、交换交叉、迁移交叉操作和十二次变异交叉操作。实验结果如图3所示，在迭代5次之后，遗传算法的适应度值变化幅度减小，逐渐趋于稳定，在迭代到第27次时达到最小值，此时任务分配达到最优解。在本次实验过程中，100次迭代过程中遗传算法累计耗时 0.203529s，而此时用穷举法进行计算时所需时间为 1.027610s，表明遗传算法相比与传统穷举计算能提高计算效率，更快计算出最优对岸打击任务分配方案。4.2第二组实验在第一组实验中由于无人机和目标所需兵力数相等，分配逻辑相对简单，优化个体数并未发挥明显作用，前期适应度下降迭代间隔均未超过十次。为提升方案复杂度，在第二组实验中假设无人何应强等：基于遗传算法的多无人机对岸打击任务分配研究34舰 船 电 子 工 程2023 年第 10 期机和目标和第一组方案的位置一致，而完成目标所需无人机分别为（1，2，1，2，2，2，1，2，1，2）。此时，无人机数量不能满足打击全部目标的需求，为了最大化收益，遗传算法会倾向于选择完成打击目标最多的方案，容易出现“早熟”现象，在此实验中采取10代无优化开始减少遗传个数，只保留前 4个个体，每个个体进行两次翻转交叉、交换交叉、迁移交叉操作和十次变异交叉操作。遗传算法迭代过程如图4所示。01020304050600.520.50.480.460.440.420.4图3迭代历程图由图4可知，在4次实验后，遗传算法出现“早熟”现象，提前趋于稳定状态，此时改进遗传算法发挥较大作用，在第21次、第33次、第44次计算出了更优方案，最终形成了最优打击任务分配方案。01020304050607080901000.40.350.30.250.20.150.10.050图4迭代历程图4.3第三组实验由于第二组实验整体复杂度还是比较简单，遗传算法运算在迭代运算上都在100次迭代内完成最优任务分配方案计算，故进行第三组实验以比较遗传算法与动态调整的遗传算法之间的计算效率。假设飞机有20个，目标有10个，它们的性能参数如表2所示。表2第三次实验仿真无人机参数0100200300400500600700800900100010009008007006005004003002001000红蓝图5第三组实验无人机（红）与目标（蓝）位置分布图此时无人机和目标编组方式比前两组都多，需要的遗传算法迭代次数也更多，所以在此实验中最大遗传代数为 300，采取10代无优化开始减少遗传个数，只保留前5个个体，保留的每个个体进行一次翻转交叉、交换交叉、迁移交叉操作和十二次变异交叉操作。501001502002503000.320.30.280.260.240.220.20.18红色蓝色图6迭代历程图运算结果如图6所示，红曲线为优化后的遗传算法迭代曲线，蓝曲线为原遗传算法迭代曲线，在前30次迭代实验中，因为此时最优适应度不断下降，动态调整没有发挥作用，在遗传算法初期迭代时两者最优适应度都在持续下降，但是在后续迭代无人机序号飞行速度/（m/s）作战半径/km导弹射程/km无人机序号飞行速度/（m/s）作战半径/km导弹射程/km180800801185850852808008012858508539085090139595095490900100149590010051001000120151051000110610095010016105950100711010001201711510001208110100010018115110011091201100120191251300120101201100100201251200100（下转第92页）35总第352期wideband single feed circularly polarized microstrip antennas J.Progress in Electromagnetics research，2008，80：45-61.7赵红梅，牛艳娟，王云飞.一种新型的宽波束圆极化微带天线 J.电信科学，2010，26（10）：98-102.8SU C W，HUANG S K，LEE C H.CP Microstrip Antennawith Wide Beamwidth for GPS Band Application J.Electronics Letters，2007，43（20）：1062-1063.9INC T A.A miniature patch antenna for GPS applicationJ.Microwave Journal，1997：116-118.10DENG J Y，YIN Y Z，HUANG Y H，et al.Compact circularly polarized microstrip antenna with wide beamwidth for compass satellite serviceJ.Progress In Electromagnetics Research Letters，2009（11）：113-118.11姚保国.天线罩几何参数测量原理及关键技术研究D.大连：大连理工大学，2003：2-3.12鲁戈舞，张剑，杨洁颖，等.频率选择表面天线罩研究现状与发展趋势 J.物理学报，2013，62（19）：198401.过程中，由于动态调整个体遗传参数，优化后的迭代算法在93迭代后达到了最优适应度值，而没有动态调整的遗传算法则在缓慢下降，在迭代到124次迭代后才达到最优适应度值。实验表明，优化后的遗传算法能够提高遗传效率，能够更快获得最优任务分配方案。5结语本文为解决异构无人机的对岸目标打击任务分配问题，基于完成任务的约束条件，采用十进制编码的方式，最佳保留策略，以随机数决定自翻转、交换、迁移交叉变异和循环变异的染色体，遗传算法迭代过程中动态调整最佳个体保留数，对对岸目标任务分配问题进行了仿真验证，成功制定了多无人机多目标的任务分配。最后，通过不同参数无人机和不同参数目标进行实验对比，得出本文改进的遗传算法有效避免实验出现“早熟”情况，具有可靠的优化能力，能在较短时间完成异构无人机的多对岸目标任务分配问题。参 考 文 献1常晓飞，蒋邓怀，姬晓闯，等.无人作战系统仿真发展综述 J.无人系统技术，2021，4（06）：28-36.2王然然，魏文领，杨铭超，等.考虑协同航路规划的多无人机任务分配 J.航空学报，2020，41（S2）：24-35.3张梦颖，王蒙一，王晓东，等.基于改进合同网的无人机群协同实时任务分配问题研究 J.航空兵器，2019，26（04）：38-46.4严飞，祝小平，周洲，等.考虑同时攻击约束的多异构无人机实时任务分配 J.中国科学：信息科学，2019，49（05）：555-569.5丁家如.多无人机任务分配与路径规划算法研究 D.杭州：浙江大学，2016.6Tal S，Steven J R，Andrew G S，Kevin M P.Multiple taskassignments for cooperating uninhabited aerial vehicles using genetic algorithmsJ.Computers&；operationsresearch，2006，33（11）.7马培博，钟麟.基于蚁群算法的无人机侦察任务分配J.无线电通信技术，2022，48（02）：371-375.8罗云枫，张剑.基于蚁群算法的打击链方案推荐研究J.舰船电子工程，2022，42（07）：33-36.9Moysis L，Petavratzis E，Volos C，et al.A chaotic pathplanning generator based on logistic map and modulo tacticsJ.Robotics and Autonomous Systems，2019，124（C）：103377.10王峰，张衡，韩孟臣，等.基于协同进化的混合变量多目标粒子群优化算法求解无人机协同多任务分配问题J.计算机学报，2021，44（10）：1967-1983.11Chen Y B，Mei Y S，Yu J Q，et al.Three-dimensional unmanned aerial vehicle path planning using modified wolfpack search algorithm J.Neurocomputing，2017，266：445-447.12宋敏，魏瑞轩，冯志明.基于差分进化算法的异构多无人机任务分配J.系统仿真学报，2010，22（07）：1706-1710.13田震，王晓芳.基于多基因遗传算法的异构多无人机协同任务分配 J.飞行力学，2019，37（01）：39-44.（上接第35页）李光军等：一种多频微带卫星通信天线设计92