考虑分配次序的无人机协同目标分配建模与遗传算法求解论文

考虑分配次序的无人机协同目标分配建模与遗传算法求解

陈志旺^{1, 2},夏 顺^1† ,李建雄^{1, 2},王 航¹,王昌蒙¹

(1.燕山大学工业计算机控制工程河北省重点实验室,河北秦皇岛066004;2.燕山大学国家冷轧板带装备及工艺工程技术研究中心,河北秦皇岛066004)

摘要: 本文研究了动态战场环境中的多无人机协同目标分配(MUCTA)问题.首先通过分析无人机(UAV)分配次序对打击任务总收益的影响,设计了动态战场环境的更新规则.将航程代价和任务代价作为惩罚项修正目标函数,建立了考虑分配次序的UAVs协同目标分配优化模型.然后针对模型的物理意义改进了遗传算法基因编码方式,设计了MUCTA遗传算法.该算法利用状态转移思想,引进SDR算子获得多种分配次序种群,同时以单行变异算子修正UAV与目标对应关系,并采用最优个体法和轮盘赌法筛选子代个体.最后仿真结果验证了所设计算法的有效性.

关键词: 无人机;遗传算法;目标分配;分配模型

1 引言

面对日趋复杂的战场环境和日益多样的作战任务,单架无人机有限的飞行能力和载弹负荷使其所发挥的功能极为有限,相比于单机作战,多无人机协同作战因其灵活度大、执行任务时间短、任务完成效率和成功率更高,因此成为现代战场上提高我方作战能力的关键技术之一^[1-2].多无人机协同目标分配是指基于一定的环境知识和任务要求,为编队中的无人机分配一组有序任务,以达到整体作战收益最大或作战代价最小的目的^[3].制定分配方案时,不但要处理无人机的本体约束,还要兼顾任务间相互协同的约束.且战场态势瞬息万变,态势的改变可能降低原方案分配效能甚至导致完全失效,因此对多无人机协同目标分配方案提出了较高的要求.多无人机协同目标分配问题是一类典型的整数规划问题,也是最优化NP问题^[4].具体来看,该问题等同于运筹学中的指派问题.对于此类问题,研究难点主要包括建模和求解方面.

在建模方面,既要考虑到无人机的数量、是否异构、攻击能力、目标数量和权重等因素;也要考虑任务约束、执行任务代价、飞行环境等问题.因此,考虑问题是否全面是衡量多无人机协同目标分配模型好坏的标准之一.文献[5]以异构无人机执行SEAD(suppression of enemy air defences)任务为背景,将无人机本体等效为Dubins Car模型,建立了带有路径末端角度约束的任务分配模型.文献[6]针对无人机与目标的数量关系,设计了以航程代价最小为寻优目标的统一分配模型.文献[7]将Dubins旅行商模型(dubins traveling salesman problem,DTSP)引入协同目标分配问题,并根据目标几何特征和传感器视野特征,将目标划分为点目标、直线目标和区域目标,建立了扩展Dubins旅行商模型.

在协同目标分配问题的求解方面,常采用集中式或分布式目标分配系统,集中式系统^[8]能集中控制,但是扩展性不足,计算量大.为使UAV具有更好的可靠性和单点决策能力,现常采用分布式求解算法^[9-10],但对通信要求较高.文献[11]设计了基于相邻局部通信的分布式拍卖算法,实现了协同任务分配问题的优化求解.文献[12]利用马尔科夫决策过程为多架无人机分配监测目标.文献[13]提出了一种分布式并行P学习算法也获得了较好的效果.近年来,针对多无人机协同目标分配的其他求解算法也逐渐增多,如文献[14]所述层次分析法,通过评估空战威胁指数为无人机分配攻击目标.文献[15]基于环境辨识记忆策略,通过改进分布估计算法实现目标分配.文献[16]提出了一种基于一致性协调算法的在线协同策略,建立了一种冲突调解规则和分布式任务分配求解算法.文献[6,17]以三维航程代价为优化对象,利用差分进化算法分配目标.遗传算法作为最成功的智能算法之一,易于使用、扩展性好、适用性强,因此,文献[18-19]将遗传算法应用于协同目标分配,对遗传算法进行不同程度、不同形式的扩展,均取得了良好的分配效果.

绿色低碳革命正在成为引领新一代产业革命的大势所趋，创新驱动的过程中重视绿色低碳发展是中国经济转型升级、产业迈向中高端，最终促进中国经济社会可持续发展的根本出路。一方面，绿色低碳可持续发展必须依赖创新驱动；另一方面，创新驱动发展必须围绕绿色低碳方向展开。

根据以上研究现状分析可知,现有的多机协同目标分配问题考虑任务空间较为理想,模型覆盖问题因素不全面.具体来说存在以下问题:1)真实战场环境是复杂且动态的,多数目标分配模型为静态模型,对真实场景适用性不强.对敌方目标建模过于简单,对敌方防空阵地和目标结构差异及能力发挥考虑欠缺.2)对无人机火力配置等异构特性考虑不足,导致模型难以应对多架异构无人机共同执行任务的大规模作战场景.3)较少考虑UAV执行任务时的航程代价,或对航程距离估算不够准确.4)模型约束条件有限,对复杂的任务协同约束关系处理能力不足.

针对以上问题,本文面向真实战场环境,首先充分考虑我方无人机火力配置差异,基于对敌方目标的真实考虑,将敌方基地各目标视为相互联系、相互依赖的整体.同时通过对约束关系进行合理处理,建立了考虑分配次序的多无人机协同目标分配模型.最后,设计了多无人机协同目标分配遗传算法(multi-UAVs cooperative target assignment,MUCTAGA),完成对多无人机协同目标分配问题的求解.

2 MUCTA问题建模

2.1 考虑分配次序的优化目标建模

在实际应用中,多无人机任务分配往往是多种类型目标分配的综合求解.多机协同目标分配问题求解策略如图1所示,实线箭头表示分配过程,虚线箭头表示更新过程.我方指挥所根据我方无人机数n 将一次战术分配过程分为n 个轮次,每一轮次根据战场环境分配出一架无人机攻击相应目标,评估该次分配结果后更新战场环境,依据更新的战场环境进行下一轮任务分配,如此循环直到所有无人机被全部分配.

图1 考虑分配次序的目标分配
Fig.1 Target assignment based on allocation order

在一次战术分配中,需要着重考虑以下3点:

1)对于敌方目标,存在着相互依赖关系和主次次序的敌方目标称之为联合目标,联合目标的生存概率和权重构成战场环境.而每一轮攻击结果都将变更环境情况,因此两轮任务分配之间具有相关性.例如,实际战场中雷达和指挥所失去功能会对地空导弹阵地和导弹发射架等其他目标产生影响.即某个目标被摧毁后可能引发其他一个或多个目标丧失功能,继而引发其他目标权重变化,最终影响整体战场环境.故分配次序是否合理,较大程度影响着战术分配的优劣.

从客观的角度来分析，林下套种中草药的栽培进行，已经在我国的很多地方积极落实，并且取得了非常好的收益。但是，并非所有地方都适合落实林下套种中草药的栽培模式，应坚持结合地方优势和相关规范来进行。我国在林下套种中草药的栽培方面，正不断的尝试进行创新，所以未来的发展空间是比较大的。日后，应继续对林下套种中草药的栽培开展深入研究，争取推动我国多个产业的协调进步。

2)对于我方来说,我方无人机火力配置存在差异,本文将该差异考虑为无人机携弹类型和攻击命中率.同时由于攻击对象为联合目标,攻击一个目标所得收益可能来源于多个目标.如何为我方无人机分配最适合的攻击目标,以期能够获得最大程度收益,同样是制定战术分配中需要考虑的核心问题.

为扩大事务所规模，树立自己的民族品牌，A会计师事务所于2013年4月合并，一跃成为国内事务所的领军人物。从中注协发布的数据来看，A事务所合并后无论是规模还是业务收入都名列前茅。这次大规模的特殊普通合伙制会计师事务所的整合，涵盖了人员、资产、市场、技术、品牌等多方面的整合过程，合并之后A的审计质量如何也成为人们关注的重要问题。下面笔者将通过两大指标对A会计师事务所合并给审计质量带来的影响进行具体分析。

3)实际战场复杂多样,我方无人机将面临多种限制因素.首先在保证飞行安全的前提下,如何规划有效可飞航迹,是需要解决的首要问题.其次各机航程大小不一,所付出航程代价(如消耗燃料)应当分别考虑.最后,无人机可能面临一系列任务要求,违背任务要求则需付出任务代价.考虑上述因素,更符合真实战场环境,也增加了一次战术分配的合理性和全面性.

以上3种问题不以某个问题单独存在,而是共存于整体分配过程中的,将其分别归纳为分配次序问题、攻击对应关系问题和实际约束问题.为有效解决考虑分配次序的多无人机联合目标分配问题,分别定义关系依赖矩阵、目标权重矩阵以及次序权重矩阵.

1)路径层:无人机本体安全飞行.本文主要考虑的约束为敌方目标防空阵地导弹威胁.敌方雷达的侦测区域是对UAV飞行的最大威胁,以雷达所在地点(x ₀,y ₀,z ₀)为球心,最大侦测距离为r ₀半径用来表示雷达区域^[6].

定义2 m 个目标组成的目标联合体的权重矩阵为,其中表示第u 轮分配时第i 个目标的权重值.

定义3 m 个目标组成的次序权重矩阵为B =[b ₁b ₂···b_m ],其中b_i 表示第i 次分配所占的权重值.

假设我方指挥所布置n 架无人机,执行攻击m 个散布在不同位置的目标.不同携弹类型无人机的命中率以及不同导弹对于不同目标的攻击效果存在差异,建立一种无人机对目标毁伤概率的模型如下^[15]:

式中:分别表示第i 枚导弹对第j 个目标的摧毁概率和命中概率;p ^air表示拦截机对导弹的拦截概率;p ^gun表示高炮对导弹的拦截概率;O_ij 表示第i 个导弹类型摧毁目标j 所需的导弹数量.

设X_i =[x_{i 1}x_{i 2}···x_ij ···x_im ]^T为定义无人机i 的任务分配向量,其中:

假设无人机收益满足可加性,即作战总收益满足各无人机收益之和.第u 轮分配时从n 架无人机与m 个目标中,选择一对最大收益配对方式

假设第u 次分配结果为目标j 被分配无人机i ,此时收益值计算方式为

其中E_k∈ R^n×n 为交换算子,是一个带有交换变换功能的随机0-1矩阵.X_k 是由x_ij 组成的n× 1维列向量,表示一个染色体上的所有基因型.该算子具有交换染色体中随机两个位置基因的能力.比如一个由5个基因组成的染色体可表示为

由于目标的联合依赖关系,在计算第u 次分配收益时,若目标j 被攻击,则目标v (j v )的生存概率也受到影响,从而影响本轮次分配收益,即攻击收益从所有存在依赖关系的目标中产生,因此式(2)是一个考虑所有目标的累加求和过程.在第u 次分配完成后,对参数进行更新,更新对象为所有目标,其中对目标v 的更新规则为^[15]

式(5)中j^′ 表示第u− 1次分配时被攻击的目标.需要说明的是式(3)-(5)中的v 要遍历所有目标,包括目标j .当n 架无人机全部分配完成后.此时该次任务获得总收益为

综上所述,计算一次战术分配的总打击收益是一个迭代过程,该过程计算步骤如下:

步骤1 令分配轮次u =1,定义参数初始值:

任务窗口约束和攻击时刻约束表示为

步骤2 根据式(1)计算f_u .

步骤3 根据式(3)-(5)更新战场环境.

步骤4 若u =n ,转步骤5;否则令u =u +1转步骤2.

目前，派驻人员尤其是基层派驻机构工作人员素质参差不齐、经验缺乏，且短期内很难形成专业化派驻队伍，影响监督效能的发挥，成为目前制约派驻组织功能发挥的短板之一。诸如某基层派驻纪检组共5人，原来分别在卫计、编办、学校和市场监管等单位工作，共同特点是之前都没有从事过纪检监察工作，工作第一步还需从最基本的“打铁还需自身硬”这一概念入手[2]。作为极其重要的党内监督中专职履行监督执纪问责功能的派驻机构，高素质的专业化人员队伍是必须且必要的。当前，我国纪检监察派驻制度中人员素质这一点仍需进一步提高。

步骤5 根据式(6)计算总打击收益F .

2.2 约束处理策略

本文考虑主要路径层与任务层2层约束关系,其含义及处理可描述为

想要确保整个建筑工程现场施工管理工作的稳定开展，需要将监管制度和奖罚机制明确出来，只有这样，才能使整个施工建设工作显得更加合理、有序。除此之外，为了实现工程建设质量的全面提升，管理人员需要根据不同情况制定出不同制度内容，实现建筑质量和水平的有效强化。在管理方式的选择上，管理人员也要以工程实际情况为主，确保管理方式的科学合理，将监管工作作用展示出来。通过制度内容的合理设计，工作人员的工作积极性也能逐渐激发出来，看清自己在工作中的责任和义务，利用自身价值发挥，维护管理工作的顺利开展，在此种情况之下，整个建筑工程施工现场管理工作也会变得更加真实、可靠[2]。

定义1 若目标联合体由m 个目标组成,则关系依赖矩阵为A_mm ,其中a_ij 表示第i 个目标失去功能后第j 个目标也失去功能的概率.

这对于不同层次、不同水平的学生来说当然是不一样的！从最粗略的划分来说，首先钢琴学生可分为专业和非专业两大类。

为保障无人机飞行安全,无人机规划的航迹要能最大限度规避威胁区.本文航迹规划采用文献[6]中基于垂直切面的三维航程代价算法进行规划,该算法在规划安全飞行航迹的同时可以进行航程估算.因此算法满足路径层约束,故下文只需处理任务层约束.

拓展阅读是完成写作学习目标的基础条件，所以在语文阅读教学期间，需要加强初中生的阅读拓展性教学。但受到目前我国教育体制的影响，教师在授课期间基于学生升学目标所需，常常会在拓展性的阅读教学出现单一化的现象并根据教材内容设置，进行单元化的课程教学指导。教师在阅读教学期间，为了方便管理以及传导学习技巧，教师会带领学生进行个统一的结构分析引导。从提出教学问题开始，让学生在既定的模式下开展的单一的、流程化的写作练习，学生如果长期受到这种阅读训练与指导，不仅仅会影响阅读学习质量，还有可能丧失写作兴趣。

2)任务层:无人机任务构成.根据第2.1节多无人机协同目标分配模型,本文主要考虑最大航程约束、任务窗口约束和到达时刻约束的3种任务层约束关系.其中无人机燃料可支持飞行最大航程约束式如下:

式中d_ij 表示无人机i 到目标j 的估算航程.在运用文献[6]算法进行航程估算时为避免“大数吃小数”,需要对航程进行归一化处理:

一天晚上，麦小秋还是把汪小波带到了苇湖小区，D城的夜晚展示着它的魅力，树叶经秋风一吹落在坚硬的地面上。当麦小秋打开屋门时，汪小波的身上嗖地冒出一股冷气，一瞬间他曾经有过的预测复活了，他的心疼起来。

其中:式(9)表示某一轮分配的无人机必须早于下一轮分配无人机到达指定目标点,为第u 次分配无人机到达目标实际时间;式(10)表示无人机执行任务时间交集为空,τ_u 其中表示第u 轮分配的无人机执行攻击任务所需时间.

1945年时可能没多少美国人听过披萨这项食物，但十年过后，报纸文章却称披萨是席卷全美的新潮食物。媒体认为披萨在美国会大受欢迎，因为第二次世界大战时美军在意大利吃过这种食物。金德斯泰特同意这种看法，他认为披萨在美吸引力大增，部分是因为参加二战的美军返国，他们品尝过披萨的美味。另外二战后经济繁荣，让更多人有能力负担在餐馆用餐。

在处理任务层约束关系时,将式(7)定义为航程代价,式(9)-(10)定义为任务代价,采用惩罚因子将2种代价作为惩罚项修正目标函数.以下叙述为第u 次分配违背约束时的代价计算方式.

1)最大航程约束^[6]:表示在完成任务过程中各UAV的最大航程限制.如果分配的目标不可达,将对其进行惩罚.最大航程约束能够协调不同能力的UAV共同完成指定的任务.

其中表示无人机i 的最大可飞行航程.

2)任务窗口约束和到达时刻约束.这两种约束条件是密不可分的.任务窗口要求在上一轮无人机完成攻击任务后其他无人机才能开始进行下一轮次攻击,从而使两轮无人机执行任务时间相互错开,保证指挥所顺利评估战场环境并进行下一步攻击分配.而到达时刻约束则为上一轮UAV攻击任务结束后,本轮无人机到达相应目标开始攻击,通过调节飞行速度进行飞行时间控制,保证各UAV依据攻击次序顺次攻击,并消除攻击等待时间带来的负面影响和安全威胁.在求解时为满足上述约束,对式(9)-(10)中实际到达时间进行如下取值:

其中分别为第u 轮所分配无人机到达相应分配目标所需最小与最大时间,式(12)中讨论了2种取值情形,其他所有情形都将被视为约束情况并根据式(13)进行处理.

在当今社会，固守陈规永远是发展不下去的，只有在独立思考和研究的基础上不断进行创新才是真正的发展之路.要真正的提高学生的核心素养，也需要在高中数学的教学过程中培养学生独立思考和创新的能力.仍以必修二《直线与平面垂直判定》为例，教师应该给学生更多的时间和空间进行思考：如何证明一条直线垂直于一个平面；如何去验证学校广场上的旗杆与地面垂直?…….通过这一系列问题的环环引入和抛出，可以不断地让学生对知识进行思考，并且将课本中的理论知识不断的联系实际，进而促进创新能力的不断培养.

上述航程代价与任务代价加入到收益函数,对式(1)进行改进可得

式中:α 为比例缩放因子,β 为航程代价因子.

此时,总收益式(6)相应改变为

以上的优化问题建模,既考虑了空间要素,又考虑了时间要素,因此模型更加完整,更接近真实战场环境.

2.3 求解难点

无人机与目标不相等的多机多目标分配问题属于非标准形式的指派问题,考虑分配次序的多机协同目标分配问题是在非标准形式的任务指派问题中考虑指派次序,本文称之为特殊的指派问题.该问题求解难度较大,主要体现为

1)指派问题可以用多种相应的解法来求解,如匈牙利解法^[20],而非标准形式指派问题,通常的处理方法是先将其转化为标准形式再进行求解.一般称矩阵C _m为指派问题的系数矩阵(coefficient matrix).在实际问题中,矩阵C _m可以有不同的含义,如费用、成本、时间等,该矩阵在指派问题中以确定形式存在.而本文协同目标分配模型中不同分配次序打击目标收益值不同,即不同次序下的式(1)-(2)所得结果都不相同,故该矩阵为不确定形式.导致一般求解指派问题的数学解法无法求解.

2)一架无人机被分配后的战场情况变化没有一般性规律,下一个将被攻击目标无法预测,即式(3)-(5)仅为更新规则,不能决定被更新对象.

3)分配次序是该问题的重点和难点,分配次序作为未知因素,需要在算法中作为变量进行考虑.

3 MUCTAGA算法

3.1 基因编码设计

式中一个满足定义6的随机5阶方阵对原序列实现了基因交换.SDR算子与交换算子的共同点在于都具有交换基因位置的功能,而区别在于交换算子以单位矩阵为基础,依靠基础行变换产生,SDR算子则是通过由满足SDR定义多个向量组合而成.一个SDR矩阵可以看作是一个单位矩阵通过数次基础行变换变换而来,包含数个交换过程.故SDR算子可以视为交换算子的一个通用性概括,是随机交换结果的高度总结,用来增加算子的适用范围,能够较为准确描述随机性状态转移过程.

图2中一个染色体序列包含无人机序列和目标序列.无人机序列由无人机编号构成,无重复编号,对应每架无人机只能获得一次分配权利.目标序列由目标编号构成,允许重复编号,对应一个目标可被多架无人机攻击.将相对应的无人机与目标视为一个基因,每个基因对应一轮分配结果,适应值序列由每对分配结果的收益值(式(15))构成.一次战术分配的总收益由适应值序列之和求出,即式(16).染色体中基因个数由无人机数量决定,同时对应分配轮次,相邻基因之间存在战场环境变化.

图2 基因编码方式
Fig.2 Gene code

与二进制编码相比,上述编码过程除了计算效率高的优点外,还保留了优化问题相关概念的具体含义,这也便于把分配次序交换、无人机-目标匹配等具体概念和下文第3.2节SDR(system of distinct representative)算子、第3.3节单行变异算子直接对应,使得求解过程更为直观.

为使下文叙述更加清晰,对MUCTAGA算法中涉及术语进行如下定义:

交叉父代:初始种群中用以交叉操作的个体.

SDR子代:交叉父代通过SDR运算后产生的子代个体.

变异父代:SDR子代中用以变异操作的个体.

变异子代:变异父代单行变异后产生的子代个体.

最优子代:变异子代中适应值最大的子代个体.

“现在已经处于价格的底点，未来价格将稍有反弹并逐渐趋于平稳。”杨同宇认为，磷复肥会议结束后，许多肥料厂家已陆续出台了订肥政策。进入12月份，将进入生产、备肥的关键时期，需求将逐渐显现，并为市场提供支撑。

下一步的修改提升要把握三点。第一，更加扣准主题，主题是上书松绑，在这样一条线上要更集中。我感觉现在一二三幕前面的铺垫过程稍微长了一点，笔墨要放到后面，那些厂长遇到的体制机制，怎么谋划松绑放权、上书的事。而且不是某一个厂的问题，是有共识，集体的力量，群众是真正的英雄。在整个剧幕的构建，材料的取舍，要更加突出这个事件，跟松绑放权没有关系的要精练压缩，如非要这样说虽能引发观众笑声，但不扣题。比如跳舞跳那么久，说明什么问题？它对松绑放权有什么促进？或者说明上书的艰难还是什么？仅仅只是调动气氛？这些地方再思考一下，点到为止即可。

3.2 SDR算子

交叉是产生新个体的重要方法,交叉算子的设计和编码方式密切相关.鉴于本文编码方式的特殊性,本文将状态转移思想引入交叉算子设计.状态转移的基本思想是将优化问题的一个可行解作为一种状态,可行解的更新过程被视为从一种状态向另一种状态变化.离散状态转移算法产生候选解的基本框架可描述如下^[21]:

其中:X_k 表示当前的状态,对应优化问题的一个解;E_k,H_k∈ R^n×n 为状态转移矩阵,可视为优化算法中的算子;⊕ 是联系2种状态的运算符;U_k 是关于当前状态和历史状态的函数;ϑ (X_{k +1})是代价函数或评价函数;Y_{k +1}为下一时刻状态评价值.

文献[21]设计了3种变换算子:交换变换算子、移动变换算子和对称变换算子.而后两者的实质则为交换变换算子通过二次或多次转移变换而成,可以视为同一种算子,本文统称为交换算子.利用交换算子实现状态转移的过程可描述为

其中:为第u 次分配时目标j 的权重,为第u− 1次分配后目标j 的生存概率;为第u− 1次分配后目标j 的死亡概率,即;v 表示第v 个目标(1 6v 6m ),a_jv 表示目标j 失去功能后目标v 也失去功能的概率.

表1 元素表示
Table 1 Element expression

一个染色体经过5维交换算子E ₅运算后

式中E ₅交换第2行和第4行元素使得原序列的第2和第4个基因发生了交换,可见,5维交换矩阵E ₅是在5阶单位矩阵基础上通过一次基础行变换变换而来.但交换算子交换能力有限,交换算子改进而来的移动变换算子和对称变换算子只能实现某种特定转移功能.为了提高算子交换能力,增加算子的适用性,将交换算子进行扩展,则可以视为相异代表系问题.

定义4 设Y 是有限集合,Γ =(π ₁,π ₂,···,π_k )是集合Y 的k 个子集族.Y 元素的一个族(e ₁,e ₂,···,e_k )如果满足e ₁在π ₁中,e ₂在π ₂中,··· ,e_k 在π_k 中.称(e ₁,e ₂,···,e_k )为Γ 的一个代表系^[22](system of representative),简记为SR.

定义5 在一个代表系中,元素e_i 属于π_i ,即e_i 是子集π_i 的代表.若所有子集的代表e ₁,e ₂,··· ,e_k 都是不同的,那么称(e ₁,e ₂,···,e_k )为相异代表系^[22](system of distinct representative),又称SDR.

定义6 设有限集合Y 为{ 1, 2,···,n} ,子集族Γ 的个数为n ,每一个子集集合为{ 1, 2,···,n} ,(e ₁,e ₂,···,e_n )为一组满足SDR定义的向量.对于n 维矩阵,矩阵的第i 行构成元素为:第i 个子集的代表e_i 在子集中所在的位置j 处置1,该行其余元素置0.此时,矩阵称之为SDR算子.

一个染色体经过SDR算子运算后

根据第2节的优化问题建模,该问题可以采用普通的遗传算法求解,即使用二进制编码方式.但由于该问题具有0-1型整数规划的特点,因此本文对基因编码方式做如下改进:

将以上任务层约束进行求和可表示为

抗战爆发后，时代的影响，使得朱自清的散文风格由抒情转向说理，这时他写的大多是有感于现实生活的论说类文章。他经常对社会时局发表议论，并在激情呐喊中，宣传正义力量及爱国思想。当闻一多被暗杀后，面对动荡的形势，朱自清不顾个人安危，毅然前往参加他的追悼会并发表演讲，还写了文章《中国学术的大损失——悼闻一多先生》，沉痛哀悼了闻一多先生，并对闻一多的出众才华以及在文学方面的卓越成就给予了高度评价，批判了国民党的残暴和反动的本质。

SDR交换能力分析如下:在产生一个随机SDR矩阵时,矩阵第1行有种选择,第2行有种选择,第n 行有种选择,共有n !种选择,其中有一种选择使得原序列不发生变化,故一个SDR算子有(n !−1)种交换方式交换原序列.而交换算子每次都在n 维单位矩阵的基础上交换2个元素,共有种交换方式,故SDR算子具有更强的交换能力.

SDR算子相比于交换算子的优势体现为:1)SDR算子交换能力更强,产生子代解的空间更大,随机性更强,更易于跳出局部最优解;2)相对于父代基因,SDR算子子代“混乱”程度更高,增加了子代种群多样性,当子代规模较大时,子代重复率更低.

MUCTAGA算法针对分配次序问题,把SDR算子设计为GA算法中的交叉算子.由于MUCTA问题的特殊性,与传统GA算法相比,MUCTAGA算法只对一个父代个体进行操作,通过改变交叉算子的作用方式,即通过状态转移方式实现攻击排序要求,以一种新的交换方法产生子代,能够较好应对考虑分配次序的多无人机任务分配问题.

3.3 单行变异算子

在遗传算法中,变异算子用来模拟生物变异过程.变异算子将个体编码串中某些基因用其他等位基因来替代,从而形成一个新的个体.变异可以提供初始种群中不含有的基因,或找回选择过程中丢失的基因,为种群提供新的内容,是改善GA算法局部搜索能力,维持种群多样性的重要算子.SDR子代是由一个染色体交换基因位置而来,并不能处理攻击对应关系,因此MUCTAGA算法通过变异算子实现这一功能.算法的变异算子只对染色体序列中的目标序列进行变异,故称之为单行变异,可知同一变异父代产生的变异子代仅存在对应关系差异,这是与传统遗传算法不同的特点之一.变异率(记为λ )定义为种群中变异染色体数在总染色体中的百分比.设计变异算子描述如下:

式中为变异算子.该算子能够将目标序列中某几个元素随机变为其他任意目标元素.变异算子只对染色体中目标序列操作,取变异后的目标序列与原无人机序列组成新的染色体,即变异子代.操作过程如图3所示.

图3 变异操作示意
Fig.3 Graphical representation for mutation operation

传统遗传算法的变异算子通常作为辅助算子出现,使算法具有局部随机搜索能力,同时防止最优解被破坏,一般变异率取值很小.与之不同的是,MUCTAGA算法针对攻击对应关系问题,设计单行变异算子目的为产生同一序列下多个不同对应关系的子代,为寻找最优对应关系提供可能.而不发生变异的变异父代几乎没有作用,因此变异率取值为1.同时为保持变异父代序列信息可用,在编码设计时,变异父代在变异前将其进行存储,变异结束后同变异子代共同组成新种群.

3.4 选择算子

选择的目的是从当前种群中选出优良的个体,使它们作为父代为下一代繁殖子孙.本文使用2种选择方法.

1)最佳个体法.是指在所有候选种群中选择最佳个体进入后续操作,本文定义最佳个体为适应度值最大个体.

2)轮盘赌法.选择对象为所有SDR子代,每个染色体被选择概率和其适应度值成正比.对染色体i ,设其适应值为Fit(i ),SDR子代个数为ξ ,则该染色体被选中的概率P _M如式(17)所示.可以看出,SDR子代适应值越大,被选择作为变异父代的概率越大.

4 算法步骤

MUCTAGA求解多机协同目标任务分配问题过程为

步骤1 初始化进化代数k =0,设置进化总代数K ,种群规模pop,交叉次数ξ ,变异父代个数ξ^′ ,变异次数γ ,变异率λ =1.

步骤2 随机产生pop个初始种群,若k >2,将k− 1代最优解个体加入初始种群.根据式(15)计算(pop+1)个个体中所有个体适应值,以最佳个体法选择交叉父代.

步骤3 随机产生SDR算子对交叉父代执行ξ 次交换操作,以轮盘赌法从产生的SDR子代选取ξ^′ 个个体作为变异父代.

步骤4 通过单行变异算子对步骤3产生的每个变异父代执行γ 次变异操作,获得(ξ^′×γ )个变异子代,同时联合所有变异父代,在(ξ^′ +ξ^′×γ )个个体中以最佳个体法选择最优个体作为第k 代最优子代.

步骤5 若k 6K ,令k =k +1,转到步骤2,否则算法结束,步骤4中最优子代即为最优解.

5 实验结果与分析

假设我方无人机基地接到作战任务,对某地防空阵地实施空中打击,我方指挥所根据先验信息已知敌方目标信息,当作战指令发出后,启动目标分配程序,无人机根据分配结果对敌方阵地实施攻击.假设执行任务的空间尺度为:180km× 220km× 50km,随机设定3个固定位置雷达威胁区,验证本文协同目标分配模型合理性及MUCTAGA算法的有效性.

我方无人机实验初始数据设定如表2所示,设定我方UAV的数量n =10,起飞点的坐标矩阵S _T;无人机飞行能力矩阵E _n(UAV最小、最大飞行速度);无人机最大航程矩阵D ;无人机携弹类型矩阵E _m,共AGMA和AGMB2种导弹类型,其命中率分别为0.8和0.85;表3为敌方目标数据设置,设定目标TAR数量m =4,目标点坐标矩阵E _D;目标点权重矩阵G ;目标被摧毁所需弹药矩阵T _G([i ,j ])分别表示目标被摧毁所需AGMA型和AGMB型导弹数量;表4为设定次序权重矩阵B .如无特殊交代,以下实验参数设置为初始种群数pop=50,参 数ξ =10,ξ^′ =2,γ =10,α =20,β =0. 1,变异率λ =1.

表2 无人机初始信息
Table 2 Initial values of UAVs

表3 目标初始信息
Table 3 Initial values of targets

表4 次序权重矩阵
Table 4 The weight matrix

目标关系依赖矩阵是攻击方对联合目标内在关系的理解,将其设为

该作战场景中,只考虑敌方高炮自卫防空,故p ^air=0.p ^gun与来袭无人机数量n 之间关系设为^[15]

5.1 实验1

为验证算法搜索最优解和处理协同约束的能力,对模型进行20次仿真实验,算法迭代代数K 为200代,分配结果如表5所示;将各种约束关系表示为布尔值,值为1表示满足该约束条件,为0表示违背该约束条件;是每一步分配的收益值(见式(15)),是综合了目标收益和航程代价的适应度值,通过惩罚因子对约束关系和航程代价进行了适当调整,所以收益值为无量纲单位.

从实验1结果可以看出,多次实验均收敛到一致的解,证明算法能够有效解决考虑分配次序的多无人机目标分配问题.图4(a)和图4(b)分别为目标权重和目标被摧毁概率与分配轮次的对应关系,可见,目标权重整体呈下降趋势,目标被摧毁概率整体呈上升趋势.且由于联合目标之间存在依赖关系,曲线发生改变不止发生在该目标被攻击时刻.图4(c)中为某次实验总收益值随算法迭代代数的变化关系,在某次实验第112代达到最优解11.63.图4(d)中为目标分配结果的三维航迹表示.表5为实验1最优解的详细数据.表中可以看出,目标权重大的目标与攻击能力强的无人机被优先分配,每一步分配攻击收益呈下降趋势,在第4轮分配后出现负收益,这是因为随着目标权重和目标生存概率的不断降低,满足协同约束的攻击收益小于航程代价.表6为20次实验中某次实验的第50代分配结果,对比表5可以看出,表6中有7架无人机与表5中分配到的目标相同,但存在分配次序差异,导致同一对应关系下却收益差异较大,如同一对应关系(1,1),即目标1被分配给无人机1,在表5-6中的收益值却分别为10.412和−3.376.可见分配次序对多机协同目标分配模型有较大影响.表6中与表5打击目标相异的其他3架无人机打击目标的变更则是在后续更新时通过单行变异实现,可见最优解是在满足各种协同约束条件的基础上,无人机与目标对应关系和考虑分配次序的综合结果.

图4 实验1仿真结果
Fig.4 The simulation result of experiment 1

表5 实验1分配结果数据
Table 5 The assignment result of Experiment 1

表6 某次实验第50代分配结果数据
Table 6 The 50th generation assignment result of a certain experiment

5.2 实验2

本实验对比交换算子和SDR算子性能作用.令:a)ξ =1;b)ξ∈ [1, 30].设定算法在找到最优解后停止运行.两者仿真结果分别为图5(a)和5(b)所示.

图5 算子性能比较
Fig.5 Comparison of operator performance

1)在图5(a)中,交换算子出现2个极端情况,一是理想情况下较易找到最优解(第18次实验迭代代数75代),另一种是不理想情况下更难找到最优解(第2次实验迭代代数2500代).这是其算子属性决定的,交换算子交换能力较弱,故产生子代的空间狭窄,容易陷入局部最优解.而SDR算子,由于交换幅度更大,子代多样性更强,更注重全局寻优能力,故表现出更强的稳定性.

2)在图5(b)中,随着交叉次数的增加,SDR算子表现明显优于交换算子,相比于图5(a),增大ξ 参数能够丰富SDR算子子代多样性,加快寻优速率,且ξ 参数越大该效果越明显.而交换算子容易产生重复子代,使得子代多样性不强,ξ 参数的增益效果不明显,增益趋势不稳定.故MUCTAGA算法中选择SDR算子较为合理.

5.3 实验3

交换和变异操作是MUCTAGA算法的核心,影响算法的收敛速度的参数有ξ ,ξ^′ ,γ .其中ξ^′∈ (0,ξ ],为测试各参数对算法收敛速度的影响,分析各参数在MUCTAGA算法中的性能,运用控制变量法对各参数进行仿真实验.现设a)ξ^′ =1,γ =50,对[1, 100]范围内ξ 取值进行实验;b)ξ^′ =1,ξ =50,对[1, 100]范围内γ 取值进行实验;c)ξ =γ =50,由于ξ^′∈ [1, 50],对[1, 50]范围内取值ξ^′ 进行实验.设定算法在找到最优解后停止运行,对每一组参数取值进行20次仿真实验,取平均值作为实验结果.实验的结果分别如图6(a)-6(c)所示,从图6(a)-6(b)出可以看出,随着ξ ,γ 参数的增大,算法能以更少的迭代代数找到最优解,ξ ,γ 参数决定子代产生的规模,也是决定子代多样性的关键因素,从而极大的影响算法收敛速度,种群多样性程度越高,算法收敛速度越快,这与传统遗传算法的收敛规律是相同的.而对于图6(c)可知随着ξ^′ 的增大,迭代代数有减小趋势并逐渐趋于稳定,可见保留较多SDR子代用于变异可以有效加快算法收敛速度,但随着保留个数的增加这一效果将明显减弱,因为保留的SDR子代过少时,种群多样性有限,此时增加SDR子代能够扩大种群规模,加快收敛速度,而保留的SDR子代过多时,一些较差的SDR子代即使被保留下来,在变异择优的过程中也将被淘汰,并不能改善收敛速度,反而会增加算法执行时间.故ξ^′ 参数存在一个上限值,能够最大化利用优秀SDR子代、摒弃劣质子代的同时考虑算法计算量.为兼顾算法收敛速度和算法执行时间,选择ξ^′ 参数为10～20(即选择比例为20%～40%)之间较为合理.

在MUCTAGA算法中,各参数之间相互促进,同时也相互制约,某些参数设置无法得到图6(a)-6(b)的规律,例如:设图6(d)ξ^′ =γ =1,对[1, 100]范围内ξ 取值进行实验;图6(e)ξ =ξ^′ =1,对[1, 100]范围内γ 取值进行实验.2次实验的结果分别如图6(d)和图6(e)所示,对比于图6(a)-6(b),图6(d)-6(e)中折线变化无显著规律,遗传算法规律没有明显体现出来,且平均迭代代数明显相对较大.分析其具体原因,参数ξ ,γ 在算法中的作用都用以扩大种群规模,对于图6(d),当参数ξ^′ =γ =1时,由ξ 参数扩大而来的种群,在选择SDR子代时,即使此时子代规模很大,但由于ξ^′ 参数限制只能选择一个子代进行变异操作,虽然选择的是最优解,但多样性的遗传特性无法保留,故ξ 参数的功能被一定程度的限制,又因为γ =1,即仅对一个个体进行一次变异操作进入下一代,同样限制了γ 参数的作用.同理,在图6(e)中,参数ξ =ξ^′ =1时同样限制了子代多样性,导致实验结果不符合理论规律.

图6 实验3仿真结果
Fig.6 The simulation result of experiment 3

可见,参数取值是MUCTAGA算法的重要部分,在实际应用中,通过合理的参数取值快速而有效的找到问题最优解,这对于真实战场情况至关重要.

6 结论

本文面向实际战场环境,充分考虑目标之间的依赖关系和我方火力配置差异,建立了考虑分配次序的多无人机协同目标分配模型.通过改进遗传算法,设计了多无人机协同目标分配遗传算法,算法针对优化问题的物理概念改进了基因编码方式,并分别设计了SDR算子、单行变异算子以及选择算子,完成对MUCTA的求解.

参考文献:

[1]BEARD R W,MCLAIN T W,GOODRICH M.Coordinated target assignment and intercept for unmanned air vehicles.IEEE International Conference on Robotics and Automation .Washington,DC:IEEE,2002,3(6):2581-2586.

[2]ZHOU S,YIN G,WU Q.UAV cooperative multiple task assignment based on discrete particle swarm optimization.International Conference on Intelligent Human-Machine Systems and Cybernetics .Hangzhou,China:IEEE,2015:81-86.

[3]HU X,MA H,YE Q,et al.Hierarchical method of task assignment for multiple cooperating UAV teams.Journal of Systems Engineering and Electronics ,2015,26(5):1000-1009.

[4]EDISON E,SHIMA T.Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms.Computers & Operations Research ,2011,38(1):340-356.

[5]WU Weinan,GUAN Yingzi,GUO Jifeng,et al.Research on cooperative task assignment method used to the mission SEAD with real constraints.Control & Decision ,2017,32(9):1574-1582.

(吴蔚楠,关英姿,郭继峰,等.基于SEAD任务特性约束的协同任务分配方法.控制与决策,2017,32(9):1574-1582.)

[6]ZHAO Ming,SU Xiaohong,MA Peijun,et al.A unified modeling method of UAVs cooperative target assignment by complex multiconstraint conditions.Acta Automatica Sinica ,2012,38(12):2038-2048.

(赵明,苏小红,马培军,等.复杂多约束UAVs协同目标分配的一种统一建模方法.自动化学报,2012,38(12):2038-2048.)

[7]WANG Z,LIU L,LONG T,et al.Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding.Chinese Journal of Aeronautics ,2018,31(2):339-350..

[8]SHIMA T,RASMUSSEN S J,SPARKS A G,et al.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms.Computers & Operations Research ,2006,33(11):3252-3269.

[9]TURNER J,MENG Q,SCHAEFER G,et al.Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system.IEEE Transactions on Cybernetics ,2017,(99):1-15.

[10]YAN Ji,LI Xiangmin,LIU Bo.Multi-agents cooperative task allocation with precedence constrains.Control & Decision ,2015,30(11):1999-2003.

(颜骥,李相民,刘波.考虑时序约束的多智能体协同任务分配.控制与决策,2015,30(11):1999-2003.)

[11]DI Bin,ZHOU Rui,DING Quanxin.Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles.Control & Decision ,2013,28(2):274-278.

(邸斌,周锐,丁全心.多无人机分布式协同异构任务分配.控制与决策,2013,28(2):274-278.)

[12]JEONG B M,HA J S,CHOI H L.MDP-based mission planning for multi-UAV persistent surveillance.International Conference on Control,Automation and Systems .Seoul,South Korea:IEEE,2014:831-834.

[13]SU Zhaopin,JIANG Jianguo,LIANG Changyong,et al.A distributed algorithm for parallel multi-task allocation based on pro fit sharing learning.Acta Automatica Sinica ,2011,37(7):865-872.

(苏兆品,蒋建国,梁昌勇,等.一种基于P学习的分布并行多任务分配算法(英文).自动化学报,2011,37(7):865-872.)

[14]LI Qiang.Reasearch on target assignment and guidance law for cooperative engagement of multi-missile .Harbin:Harbin Institute of technology,2017.

(李强.多导弹协同作战目标分配和制导律研究.哈尔滨:哈尔滨工业大学,2017.)

[15]PENG Xingguang.Dynamic Evolutionary Algorithm for Unmanned System and Its Application .Beijing:Science Press,2017:114-125.

(彭星光.面向无人系统的动态进化算法及应用.北京:科学出版社,2017:114-125.)

[16]WU Weinan,CUI Naigang,GUO Jifeng.Distributed task assignment method based on local information consensus and target estimation.Control Theory & Applications ,2018,35(4):566-576.

(吴蔚楠,崔乃刚,郭继峰.基于目标信息估计的分布式局部协调任务分配方法.控制理论与应用,2018,35(4):566-576.)

[17]ZHAO M,ZHAO L,SU X,et al.Improved discrete mapping differential evolution for multi-unmanned aerial vehicles cooperative multitargets assignment under unified model.International Journal of Machine Learning & Cybernetics ,2017,8(3):765-780.

[18]ZHANG Y Z,HU B,LI J W,et al.Heterogeneous multi-UAVs cooperative task assignment based on GSA-GA.IEEE International Conference on Aircraft Utility Systems .Beijing,China:IEEE,2016:423-426.

[19]SHIMA T,SCHUMACHER C.Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms.Journal of the Operational Research Society ,2009,60(7):973-982.

[20]LIU Yi,TONG Mingan.An application of hungarian algorithm to the multi-target assignment.Fire Control & Command Control ,2002,27(4):34-37.

(柳毅,佟明安.匈牙利算法在多目标分配中的应用.火力与指挥控制,2002,27(4):34-37.)

[21]DONG Tianxue,YANG Chunhua,ZHOU Xiaojun,et al.A novel discrete state transition algorithm for staff assignment problem.Control Theory & Applications ,2016,33(10):1378-1388.

(董天雪,阳春华,周晓君,等.一种求解企业员工指派问题的离散状态转移算法.控制理论与应用,2016,33(10):1378-1388.)

[22]BRUALDI R A,FENG Su’s Translation.Introductory Combinatorics .The Fifth Edition.Beijing:China Machine Press,2012:198-209.

(Brualdi R A著,冯速等译.组合数学.第5版.北京:机械工业出版社,2012:198-209.)

Modeling of unmanned aerial vehicles cooperative target assignment with allocation order and its solving of genetic algorithm

CHEN Zhi-wang^{1, 2},XIA Shun^1† ,LI Jian-xiong^{1, 2},WANG Hang¹,WANG Chang-meng¹
(1.Key Lab of Industrial Computer Control Engineering of Hebei Province,Yanshan University,Qinhuangdao Hebei 066004,China;2.National Engineering Research Center for Equipment and Technology of Cold Strip Rolling,Yanshan University,Qinhuangdao Hebei 066004,China)

Abstract: This article is concerned with the Multi-UAVs cooperative target assignment(MUCTA)of dynamic battle field environment.Firstly,By means of the in fluence of unmanned aerial vehicle(UAV)allocation order on total revenue of strike task,the updating rules of dynamic battle field environment are designed.The cost of flight path length and task is used as penalty term in objective function,and the optimization model of UAVs cooperative target assignment with allocation order is established.Secondly,the coding method of genetic algorithm is improved based on the physical significance of the optimization model,and the MUCTA genetic algorithm is proposed.According to state transition,SDR operator is used to obtain different population of various allocation order,single mutation operator is used to adjust the correspondence relation between UAVs and targets,the methods of optimal individual selection and roulette are used to screen offspring individuals.Finally,simulation results verify the effectiveness of the algorithm.

Key words: unmanned aerial vehicles;genetic algorithms;target assignment;assignment model

引用格式: 陈志旺,夏顺,李建雄,等.考虑分配次序的无人机协同目标分配建模与遗传算法求解.控制理论与应用,2019,36(7):1072-1082

DOI: 10.7641/CTA.2018.80176

收稿日期: 2018−03−15;

录用日期: 2018−08−18.

^† 通信作者.E-mail:xiashun9388@163.com;Tel.:+86 15369748330.

本文责任编委:胡跃明.

国家自然科学基金项目(61573305)资助.

Supported by the National Natural Science Foundation of China(61573305).

Citation: CHEN Zhiwang,XIA Shun,LI Jianxiong,et al.Modeling of unmanned aerial vehicles cooperative target assignment with allocation order and its solving of genetic algorithm.Control Theory & Applications ,2019,36(7):1072-1082

作者简介:

陈志旺 副教授,博士,目前研究方向为多旋翼飞行控制、目标跟踪等,E-mail:czwaaron@ysu.edu.cn;

夏 顺 硕士研究生,目前研究方向为无人机路径规划、任务分配,E-mail:xiashun9388@163.com;

李建雄 博士,硕士生导师,目前研究方向为连铸轧钢自动化技术与应用、优化控制,E-mail:jxli@ysu.edu.cn;

王 航 硕士研究生,目前研究方向为飞行器视觉应用研究,E-mail:wanghang1205@163.com;

王昌蒙 硕士研究生,目前研究方向为飞行器视觉应用研究,E-mail:1506869347@qq.com.

标签：无人机论文;  遗传算法论文;  目标分配论文;  分配模型论文;  燕山大学工业计算机控制工程河北省重点实验室论文;  燕山大学国家冷轧板带装备及工艺工程技术研究中心论文;