改进遗传算法求解电力网攻击无人机分队任务分配*

何 凡，任向东，吴 桐，2

（1.中国洛阳电子装备试验中心，河南 洛阳 471003；2.湖南大学，长沙 470082）

改进遗传算法求解电力网攻击无人机分队任务分配*

何 凡1，任向东1，吴 桐1，2

（1.中国洛阳电子装备试验中心，河南 洛阳 471003；2.湖南大学，长沙 470082）

遗传算法因其出色的寻优能力，自提出后就被广泛用于工程技术上的最优化问题求解。根据电力网攻击无人机分队任务分配的实际需要，提出基于遗传算法思想的解决方案，并在原算法基础上，采用种群分组进化的策略进行改进。详细介绍算法的基本原理和仿真步骤，再举出实际算例进行仿真，实验结果证明算法的改进取得了良好效果。

遗传算法，电力网攻击无人机，任务分配

0 引言

无人机（Unmanned Aerial Vehicle，简称UAV）是由动力驱动、机上无人驾驶的航空飞行器的简称［1］。军用无人机是指军事用途的飞行器。根据无人机任务分工及配置的设备（侦察设备、炮兵校射装置、电子对抗设备、靶标设备、攻击弹药等），可将其分为侦察无人机、校射无人机、电子对抗无人机、靶机、攻击无人机等。电力网攻击无人机就是攻击无人机的一种，它利用携带的电力网攻击弹药（通常是石墨炸弹或箔条炸弹等）在距目标（电力网枢纽）等一定距离上投掷以达到目标内部短路、烧毁以至瘫痪的目的，使敌因电力系统的故障在战争的诸多方面受到损失，形成关联和叠加，最终达到严重削弱其作战能力的目的。

通常认为电力网攻击无人机分队由多个电力网攻击无人机系统和相关人员组成，具备多机协同攻击能力和一定的作战保障能力，作为作战单元具备独立遂行作战任务（电力网攻击）的能力。

对电力网攻击无人机分队进行任务分配，其主要目的就是摸清攻击目标的基本情况，找出攻击的突破口，规划攻击的路线及兵力投放和运用的相关问题，最终实现以可能小的代价达成预期的攻击效果。

电力网攻击无人机分队任务分配问题属于任务分配的NP完备问题，其可能解的复杂程度会随目标数和分队无人机数的增加而呈指数倍增大。

遗传算法（Genetic Algorithm）是一类群体智能算法，由Holland J教授于1975年首先提出［2］，该算法以进化论的自然选择和变异过程为计算模型，用以寻找最优解。遗传算法自提出后，被广泛应用于组合优化问题求解。

已有不少学者尝试将群体智能算法用于无人机任务规划或路径分配，冯琦等［3］运用单亲策略的遗传算法对多无人机任务分配问题进行求解。段海淇等［4］将并行蚁群算法运用于多无人机任务分配，给出了求解步骤，并进行了仿真。杜继永等［5］针对不同无人机提出任务载荷限制，并利用粒子群算法对多无人机任务分配问题求解。以上研究其算法均有一定局限性，寻优速度不高或易陷入局部最优。

本文将电力网无人机分队任务分配问题转化为路径代价问题，利用遗传算法的寻优机制求解，运用种群分组进化的方法对遗传算法选择、交叉和变异的方法进行有效改进，提高了算法的寻优机制。

1 电力网攻击无人机分队任务分配的数学模型

目前对于电力网攻击无人机分队的模型研究尚属空白，但对于攻击型无人机任务分配的数学建模，已有不少学者进行了探索：将攻击威胁度和收益综合考虑，转化为目标分配问题［6］。应用最广的是多旅行商（Multiple Traveling Salesman Problem，MTSP）问题模型［7-8］；带有约束的车辆路由问题（Vehicle Routing Problem，VRP），相对于MTSP问题，更接近实际情况［3，9］。本文主要采用VRP问题的思想对电力网攻击无人机分队任务分配进行建模。

假设要取得电力网攻击的作战效果，某区域内需要打击的关键节点目标数为n，电力网攻击无人机分队拥有无人机数为m，无人机可携带弹药量有限，因此，单架无人机可打击的目标数最多为p，为每架无人机分配作战任务（打击目标及航行路线），每个目标只进行一次计划性打击。分队中各无人机均从同一地点起飞，对指定目标进行打击，完成任务后返航，如图1所示。

图 1中，起点为点（5，0），目标分布于（0～10，0～10）区域内，m=5，n=40，不同颜色的路线代表各无人机的航行路线，

以Si（i=1，2，…，m）表示每架无人机完成任务航行的里程，分队中无人机为同一类型，可认为其速度相同，对目标进行攻击的时间较短，可以忽略，以Ej（j=1，2，…，m）表示分配给每架电力网攻击无人机的目标数。任务分配目的：①使所有无人机航行总里程最短；②考虑到任务的威胁程度，应使任务的执行时间最短，在无人机速度相同的情况下，任务执行时间最短即分队中无人机最长航行里程数最小；③每架无人机最多打击的目标数为p；④考虑任务分配的均衡度，限定每架无人机至少打击的目标数为q。其任务分配的目标为：

图1 电力网攻击无人机分队任务分配示意图

J为完成任务的开销，任务分配的目标是使J最小，1、2为系数。

2 算法设计与改进

传统遗传算法有性能较低、易陷入局部最优解等缺陷。将遗传算法用于电力网攻击无人机分队任务分配，需要对算法进行改进。

2.1 个体编码方式

在本问题中，电力网攻击无人机航行的起点和终点为固定点。以点1，2，…，n表示n个待打击的目标，这n个整数的组合，即代表一条染色体。若n为10，即目标数为10，则一条打击所有可能的染色体编码为：

采用设置断点的方式解决分队多架无人机任务分配，个体编码由染色体和断点集两部分组成。若分队执行任务无人机数为m，则设置m-1个断点，断点值代表在染色体中的位置，断点将染色体分割开，形成m个较短的片段，即m无人机的航行路线。假设分队有3架无人机参与任务，q为2，p为5，一种可能的分割方式如图2所示。

图2 编码方式示意图

若以0代表出发点，由上图可知3架无人机的路线分别为：0-5-2-10-0、0-6-7-4-1-0、0-3-8-9-0。

2.2 断点集生成方法

自由度dof表示满足所有无人机至少分配数后，剩余的目标数，即：

将dof个目标随机分给m个染色体片段，即生成相应的分割断点集。若某段染色体长度大于最大值p，则将该段染色体长度限定为p，并将多余部分分给最短染色体，以此类推，直至所有染色体段长度符合要求为止。

2.3 适应值函数

本问题的目的是，综合考虑无人机航行总路线和任务执行时间，找出代价最小的方案。根据式（1），适应值函数为：

规定系数1为1，2为ceil（m/2），即m/2向上取整。

2.4 种群分组进化策略

为避免算法陷入局部最优，扩大搜索范围，同时充分利用较优解，采用种群分组进化策略对遗传算法进行改进。

以10个个体为一组，将种群分组，分别规定每组10个个体不同的进化方式：

个体1：最优保留操作，找出该组最优个体，将其作为个体1保留；

个体2：杂交操作，计算除最优个体外，其余个体的适度值，以轮盘赌的方法按概率选择个体与最优个体进行杂交，适度值越大的个体选择的可能性越大，将杂交得到的个体作为个体2保留；

个体3：互换操作，随机生成1到n之间的两个数a、b，将最优个体染色体a、b位置之间的所有数前后互换，得到新个体作为个体3保留；

个体4：下滑操作，将最优个体染色体a位置的数取出，a+1至b位置之间的数前移1位，将原a位置的数放于b位置之后，得到的新个体作为个体4保留；

个体5：交换操作，将最优个体染色体a、b位置上的数作为个体5保留；

个体6：断点操作，生成新断点集，更新最优个体断点集，作为个体6保留；

个体7～个体10：分别在个体2～个体5的基础上加入断点操作。

这样分组进化的方法，利用了多种进化方式，既保留了个体的优势基因，又较大扩展了搜索范围，是对传统遗传算法交叉、选择、变异等操作的有利改进。

2.5 种群规模选择

因采用分组进化的方法，种群的规模数规定为10的倍数，规模较小，不利于搜索，规模较大，代价较高，按照效果来看，种群规模100～200为宜。

3 算法仿真步骤

Step1：初始化。设置初始适应度值为无穷大，迭代次数num_iter，种群个数pop_size，需要打击的关键节点目标数n，区域中n个节点的位置（随机生成），电力网攻击无人机分队拥有无人机数m，单架无人机可打击的目标数最大值p，最小值q，随机生成第一代种群所有个体的编码。

Step2：计算种群中所有个体适应度值，找出本代种群个体适应度最小值min_iter，令全局最小值globle_min=min_iter，并保留最优个体编码。

Step3：按照2.4节所述，以种群分组进化的方法对种群进行更新，生成新种群，取代旧种群。

Step4：进化代数iter=iter+1。

Step5：若iter=num_iter，则循环停止，输出最优分配方案，否则跳转Step2。

4 算例及仿真结果

算例：电力网攻击无人机分队4架无人机参与任务，待打击目标20个，每架无人机至少打击目标2个，最多打击目标7个。目标分布如图3所示。

图3 算例目标分布图

图3 中空心圆圈为起点，实心黑圈为待打击目标点。

设定算法最大迭代次数为5 000，种群规模为100，采用matlab编程进行仿真。

根据任务分配模型以传统遗传算法求解，得到分配结果如下：

图4 传统遗传算法分配结果

图5 传统遗传算法进化过程

算法耗时156.08 s，在进化至4 022代取得最优解，分配后各无人机航行代价为（22.14，19.42，22.00，15.39），根据式（2）得出总代价为145.36。

再以种群分组进化遗传算法求解，得到分配结果如下：

图6 种群分组进化遗传算法分配结果

图7 种群分组进化遗传算法进化过程

算法耗时24.97 s，在进化至231代取得最优解，分配后各无人机航行代价为（22.62，23.15，20.31，3.34），根据式（2）得出总代价为138.86。

将两种算法性能进行比较，如表1所示。

表1 两种算法性能比较

改进后的种群分组进化遗传算法的运算时间大大缩短，说明新算法的性能优于传统算法；新算法获得的最优解适应值小于传统算法，说明新算法的寻优能力好于传统算法；新算法获得最优解的迭代次数远小于传统算法，说明新算法寻优速度远高于传统算法。综上所述，种群分组进化遗传算法取得了良好的寻优效果，各方面性能均优于传统算法。

5 结束语

本文首先对电力网攻击无人机分队任务分配问题进行建模，并采用遗传算法的思想求解，提出断点集染色体的编码方式，并采用种群分组进化的策略，对传统遗传算法进行改进，再举实际算例，证明改进后的新算法取得明显效果，在性能、寻优速度和能力等方面明显优于传统算法。

［1］Fahlstrom P G，Gleason T J.著，吴汉平，等译.无人机系统导论［M］.北京：电子工业出版社，2003.

［2］Holland J H.Adaptation in Natural and Artificial Systems［M］.Ann Arbor:The University of Michigan Press，1975.

［3］冯琦，周德云.应用单亲遗传算法进行大规模UCAV任务分配［J］.火力与指挥控制，2006，31（5）:18-21.

［4］段海淇，丁全心，常俊杰，刘森琪.基于并行蚁群优化的多无人作战任务分配仿真平台［J］.航空学报，2008，5（增1）: 192-197.

［5］杜继永，张凤鸣，黄国荣，杨骥.基于改进粒子群算法的多UCAV任务分配仿真研究［J］.系统仿真学报，2013，25（4）:650-655.

［6］余周毅，陈宗基，周锐.基于遗传算法的动态资源调度问题研究［J］.控制与决策，2004，19（11）:1308-1311.

［7］Secrest B R.Traveling Salesman Problem for Surveillance Mission Using Particle Swarm Optimization［D］.Master's thesis，Air Force Institute of Technology，Wright-patterson Air Force Base，Ohio，USA，2001.

［8］叶媛媛.闵春平，朱华勇，等.基于整数规划的多UCAV任务分配问题研究［J］.信息与控制，2005，34（5）:548-552.

［9］Philemon S.UAV Mission Planning under Uncertainty［D］. Cambridge：USA Massachusetts Institute of Technology，2006.

Improved Genetic Algorithm to Solve Power Grid Attack Unmanned Aerial Vehicle Squads Tasks Assignment

HE Fan1，REN Xiang-dong1，WU Tong1，2
（1.Luoyang Electronic Equipment Testing Center，Luoyang 471003，China；2.Hunan University，Changsha 470082，China）

Genetic algorithm is based on its excellent optimization ability，it is widely used in engineering optimization problem solving after proposed.Based on the actual needs of power grid attack unmanned aerial vehicle squads tasks assignment，solution based on genetic algorithm is proposed，and on the basis of the original algorithm，the population group evolution strategy is used to improve.The basic principle of algorithm and simulation steps in detail and practical examples are given to the simulation，the experimental results prove the algorithm improvement has obtained the good effect.

genetic algorithm，power grid attack unmanned aerial vehicle，tasks allocation

TP391

A

1002-0640（2015）04-0051-04

2014-03-16

2014-04-25

军队试验技术研究重大课题资助

何 凡（1987- ），男，安徽合肥人，工程师。研究方向：电子对抗训练评估。