混合引力搜索算法的多无人机协同时序耦合任务分配方法

摘要

本发明提供了一种混合引力搜索算法的多无人机协同时序耦合任务分配方法，涉及无人机协同任务分配领域，构建时间耦合约束下的多无人机协同任务分配模型，得到适应度函数和任务约束，在基于遗传算子的引力搜索算法中，对个体离散化编码及种群进行初始化后，对个体进行解码，利用适应度函数计算适应度，并进行个体更新，本发明由于在引力搜索算法中增加了遗传算子，具有较好的普遍适用性，通过长时间多次数的仿真试验和数据统计构建更为完善的数据库，使得模型更完善；与离散粒子群算法进行对比，混合引力遗传搜索算法能够更快地收敛，寻优结果更优，迭代过程简短，收敛速度快。

说明书

技术领域

本发明涉及无人机(Unmanned Aerial Vehicle，UAV)协同任务分配领域，尤其是一种具有时间耦合约束下的多无人机任务分配方法。

背景技术

多无人机协同时序耦合任务分配在科学研究与工程应用中都处于非常重要的地位。传统的引力搜索算法在解决此类问题中具备突出的全局寻优能力但也存在很多缺陷，例如容易陷入局部最优，全局最优粒子的质量较低。引力搜索算法(Gravitation SearchAlgorithm，GSA)其本质是模拟自然界中的万有引力现象，并将其演化成随机搜索最优解的过程。

由于在多无人机协同时序耦合任务分配中，全局最优粒子的计算与搜索(引导粒子的选取)，对多目标优化中解的收敛性与分布性具有重要影响，具备突出的全局寻优能力的进化算法被应用到多无人机协同时序耦合任务分配中。目前发展比较成熟的多无人机协同时序耦合任务分配算法主要包括基于引力搜索算法GSA的多任务分配和基于粒子群算法(Particle Swarm Optimization，PSO)的多任务分配。由于引力搜索算法GSA具备两个特殊的性质：(1)记忆性-用来存储全局最优粒子与个体历史最优值；(2)信息交流性-粒子之间依据记忆特性相互分享最优位置的信息，使得引力搜索算法在多无人机协同时序耦合任务分配领域表现出一定的实用性。

作为一种新型进化算法，引力搜索算法已经成功应用到单目标优化领域，其根本思想是基于牛顿的万有引力定律：“在宇宙间，每一个粒子由于万有引力的作用而彼此相互吸引，引力的大小与粒子的质量成正比，与他们之间的距离成反比”，所以，通过粒子间的相互吸引，引力搜索算法保证了所有粒子向着质量最大的粒子移动。

但是，当引力搜索算法运用到多无人机协同时序耦合任务分配中时，其自身的一些缺点导致该算法中全局最优粒子的质量较低，时序耦合任务分配的效果还有待提高。首先，在引力搜索算法中，只有当前的位置信息在迭代更新过程中起作用，即该算法是一种缺乏记忆性的算法，这就导致种群上下代之间没有信息交流，容易陷入早熟收敛。另一方面，由于引力搜索算法中粒子速度较大，全部都向质量较大的粒子移动，收敛非常迅速，所以种群的多样性降低快速，即多样性迅速流失，不能保证非支配解的多样性与分布性。

发明内容

为了克服现有技术的不足，本发明基于上述引力搜索算法在多无人机协同时序耦合任务分配的缺点，对引力搜索算法进行相关改进，包括编码与解码设计、种群初始化以及个体更新方式的改进，提出了基于遗传算子的离散引力搜索算法(Gravitation SearchAlgorithm-Genetic Algorithm，GSA-GA)，通过算例仿真验证了算法的有效性，并采用蒙特卡洛仿真方法与离散粒子群算法进行对比，仿真结果表明GSA-GA算法具备更好的全局收敛性和更快的收敛速度。

本发明解决其技术问题所采用的技术方案的详细步骤如下：

步骤一：构建时间耦合约束下的多无人机协同任务分配模型

对多无人机协同执行压制敌方防空系统(Suppression of Enemy Air Defence，SEAD)任务分配问题做出定义，并对适应度函数和任务约束进行说明，具体定义如下：

定义1：设U＝{1，2，3，...i...，M}表示无人机集合，其中元素i＝1，2，3，…，M，表示第i架无人机，M表示无人机的数量；

定义2：T＝{1，2，3，...j...，N}表示目标集合，其中元素j＝1，2，3，…，N，表示第j个目标，N表示目标的数量；

定义3：设Task＝{t₁₁，t₁₂，t₂₁.t₂₂，...，t_jh，...，t_N1，t_N2}表示任务集合，其中t_jh表示第j个目标上的第h种任务，h＝1，2，当h＝1表示打击任务，当h＝2表示毁伤评估任务；

定义4：U^jh表示能够执行任务t_jh的无人机集合；

定义5：TaskSequence_i＝{task1＞task2＞task3＞...＞taskl＞...taskn_i}表示一共i架无人机的任务序列，其中元素taskl∈Task，l＝1，2，3，…，n_i，n_i表示分配给第i架无人机的任务数量；

定义6：Route_i＝{UP_i，taskP₁，taskP₂，...，taskP_k，...，taskP_ni，BP}表示第i架无人机的路径序列，UP_i为第i架无人机的初始位置，taskP_k为任务序列TaskSequence_i表示第k个任务的位置，k＝1，2，3，…，n_i，BP为基地的位置；

定义7：Voy_i表示第i架无人机的航程；

定义8：Voy>i表示第i架无人机的最大航程；

定义9：R_i表示第i架无人机的武器载荷数量；

定义10：表示第i架无人机执行任务t_jh消耗的执行时间；

定义11：sT_g，g∈Task，表示任务g的开始被执行时刻；

定义12：eT_g，g∈Task，表示任务g的完成时刻；

定义13：Inter_min表示打击任务和毁伤评估任务间的最小时间间隔；

定义14：Inter_max表示打击任务和毁伤评估任务间的最大时间间隔；

定义15：定义二维决策变量表示每个任务的分配情况，下标i、j、h分别表示无人机编号、目标编号以及任务类型，其具体取值遵循如下规则：

定义16：其中G(t)表示t时刻的引力常数，G(t)初始值为9.8，计算公式为：

其中，T表示最大迭代次数，G₀和α为固定常数；

定义17：best和worst分别表示在迭代中GSA个体的最大适应度函数值和最小适应度函数值，M表示GSA个体的质量，a表示GSA个体的加速度；

1.构建适应度函数

本发明中选择无人机最大航程最短作为任务规划指标，即

F为本发明构造的适应度函数；

在定义4的前提下，以匀速运动规律计算无人机的航程，则第i架无人机的航程为：

式(2)中，是定义12中表示任务taskn_i的完成时刻，v_i表示无人机U_i的巡航速度，本发明假设无人机的巡航速度为固定值，dis(taskn_i，BP)为任务taskn_i与基地BP的欧式距离，计算公式为

式(3)中，x_BP、y_BP、分别为基地BP与任务taskn_i的横纵坐标；

2.任务约束

本发明任务分配问题中的约束条件如下：

(1)每个任务都必须被执行：

(2)每个任务只能被执行一次：

(3)每架无人机至少被分配一个任务，即：

(4)时序约束

公式(8)中是任务task_j(h+1)的开始被执行时刻；

(5)航程约束

Voy_i≤Voy>i>

(6)武器载荷资源约束

(7)打击任务和毁伤评估任务的时间间隔约束

eT_taskj2+Inter_min≤sT_taskj3(11)

eT_taskj2+Inter_max≥sT_taskj3>

步骤二：基于遗传算子的引力搜索算法设计

步骤2.1：个体离散化编码

本发明采用分段编码方式对引力搜索算法中的个体进行编码，以一个1×4N维向量表示引力搜索算法的个体；

个体编码分为两部分：任务分配(Task Allocation，TA))部分和任务排序(TaskSequencing，TS)部分；

定义18：设TG＝[TA TS]为一个1×4N维向量，表示一个引力搜索个体，TG分为两部分，其中TA表示任务分配部分，为2N维数组，TS表示任务排序部分，为2N维数组；

(1)任务分配部分：该部分表示N个目标共有2N个任务的分配情况，即N个目标的2N个任务如何分配给无人机i，共有2N个元素，分别代表着2N个任务，2N个元素从左往右，依次对应任务t₁₁、t₁₂、t₂₁、...、t_N1、t_N2，例如t₂₁表示无人机完成第二个目标的打击任务，t₂₂表示无人机完成第二个目标的毁伤评估任务；

(2)任务排序部分：该部分表示所有任务的排序情况，该部分2N个元素都有目标的编号编码，分别代表着2N个任务，2N个元素从左往右依次对应目标任务t₁₁、t₁₂、t₂₁、...、t_N1、t_N2，每个目标第一次出现即为打击任务，第二次出现即为毁伤评估任务；

步骤2.2：种群初始化

本发明采用随机产生的方式对个体种群进行初始化，具体方法为使用MATLAB仿真软件将一组自己设定的种群在任务约束条件下循环得出一组满足任务约束条件的初始种群，以随机初始化的方法对每个个体进行初始化编码，对于任务分配部分，每一位任务分配元素代表一个具体的任务t_jh，随机从能够执行任务t_jh的无人机集合U^jh中选取一个元素作为该位的取值，对于任务排序部分，以两组目标序号的随机排序表示该部分的位置，个体的速度初始化为0；

步骤2.3：个体解码

在任务分配部分，依次读取每一位元素的值VA_jh，其中j＝1，2，…，N，h＝1，2，VA_jh∈U，表示第VA_jh架无人机，并将任务t_jh添加到第VA_jh架无人机的任务集中，最终得到各无人机的任务分配集合；

在任务排序部分，每一个元素的值VS_d∈T，d＝1，2，…，2N，表示第VS_d个目标，每个目标有两种任务，因而每个目标会出现2次，第一次表示该目标的攻击任务，即代表任务第二次表示该目标的毁伤评估任务，即代表任务任务排序部分对所有任务进行顺序执行，对各无人机的任务分配集合中的元素进行排序，从而得到各无人机的任务执行序列；

综上，个体解码的具体步骤如下：

Step1：对任务分配部分进行解码

(1)初始化各无人机的任务集合为空集，即

(2)VA_k1＝TAL(2k-1)，其中TAL为目标数量，i＝VA_k1，将任务t_k1加入TaskSequence_i中；

(3)VA_k2＝TAL(2k)，i＝VA_k2，将任务t_k2加入TaskSequence_i中；

(4)k＝k+1，若k≤N，转到步骤(2)；否则结束；

Step2：对任务排序部分进行解码

(a)从左至右依次读取任务排序部分的第k位上的目标j的值，k＝1，2，…，2N，每个j代表目标T_j上的一个任务，若j是第h次出现，则表示Task_jh，当k＝2N得到所有任务的排列顺序TaskS；

(b)将TaskSequence_i根据TaskS重新排列任务顺序：当Task_jh和Task_kl都在TaskSequence_i中时，则以从左到右的顺序来比较；

至此，解码结束，得到各无人机的任务执行新序列TaskSequence_j；

步骤2.4：适应度函数计算适应度

依据步骤一中的适应度函数进行计算，即

F为本发明构造的适应度函数；

步骤2.5：更新种群的全局最优、局部最优和局部最差

根据步骤2.4中求得的种群中各个粒子的适应度函数值，更新种群的全局最优、局部最优和局部最差；

步骤2.6：个体更新

个体i在第l维获得的加速度等于其受到合力与其自身惯性质量的比值，计算公式为：

式(13)中M_ii(t)为个体i在t时刻的惯性质量；F_i^l(t)表示个体i在t时刻万有引力的大小，表示个体i在t时刻在万有引力F_i^l(t)作用下的加速度，l表示个体i的第l维；

每一次更新过程中，个体i根据引力产生的加速度更新自身的速度和位置，更新方式如公式(14)所示：

表示粒子i在t+1时刻的速度，表示粒子i在t时刻的速度，表示粒子i在t+1时刻的位置，表示粒子i在t时刻的位置，rand_i表示粒子i在MATLAB仿真下的一个随机数；

对更新后的个体位置进行修正：首先对每一个个体位置)采用对于小数点后的一位四舍五入进行取整，其次，对个体位置取整后的每一位进行合法判断：若该位的值不在该位表示任务的可执行无人机集合内，则将离该位最近的一位，以集合的离该位元素最近的元素代替；

判断整个种群的迭代次数是否达到设定的最大迭代次数，若是，则结束流程；否则返回步骤2.3中的step1继续循环求解。

对于步骤2.6的更新，本发明引入遗传算法的交叉和变异操作进行更新，所述的更新步骤为：

a)交叉：本发明利用POX交叉方法对个体的任务排序部分进行交叉操作，所述的交叉操作每一次只产生一个新个体，具体步骤如下：

Step1：从目标集{T1，T2，…，Tn}随机抽取一个目标子集T_set；

Step2：选择需要进行交叉操作的个体X1和X2，若X1的适应度函数值大于X2的适应度函数值，则将X1中包含在目标子集T_set中的目标复制到新的个体C中，X1保持位置和顺序不变；

Setp3：将X2中不包含在T_set中的目标同样复制到新的个体C中，保持个体X1和X2顺序不变；

Step4：若新个体C的适应度函数值大于X2，则保存新个体C，并替代原来的个体X2；

b)变异：本发明采用基于邻域搜索的变异方法，其具体操作步骤如下：

Step1：在个体的任务排序部分随机选择r个位，并生成个体排序的所有邻域；

Step2：计算任务元素所有邻域的适应度函数值，选出适应度函数值最大的个体作为子代，并代替原来的个体。

本发明的有益效果在于采用了在引力搜索算法中增加了遗传算子，具有较好的普遍适用性，通过长时间多次数的仿真试验和数据统计构建更为完善的数据库，使得模型更完善；与离散粒子群算法进行对比，混合引力遗传搜索算法(GSA-GA)能够更快地收敛，寻优结果更优，迭代过程简短，收敛速度快。

附图说明

图1是本发明的分段编码示意图。

图2是本发明的任务分配部分编码示意图。

图3是本发明的任务排序部分编码示意图。

图4是本发明的完整个体编码示意图。

图5是本发明的POX交叉操作示意图，其中X1和X2为进行交叉操作的两个个体元素，C为交叉操作所得的新个体元素。

图6是本发明的GSA-GA算法流程图。

图7是本发明的战场态势图。

图8是本发明的任务分配甘特图。

图9是本发明的GSA-GA收敛曲线。

图10是本发明的GSA-GA和DPSO的收敛曲线，其中，DPSO为离散粒子群算法。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

本发明要解决的技术问题是提供一种基于改进引力搜索算法的多无人机协同时序耦合任务分配问题，它能够有效避免多目标优化陷入局部极值，显著改善引力搜索算法运用到多无人机协同时序耦合任务分配领域时非支配解的收敛性、多样性与分布性。

本发明提供一种设计方法，根据已经获得的情报信息、任务要求以及地形、气象环境等因素，对多无人机制定任务规划，也就是预先规划。同时以多无人机协同执行SEAD任务为背景，要求对任务区域中每个目标依次执行打击和毁伤评估两种子任务，重点关注任务间的时间耦合关系，对时间耦合约束下的多无人机执行打击-毁伤评估任务分配问题进行数学建模。本发明改进的混合离散引力遗传搜索算法(GSA-GA)是在引力搜索算法(GSA)的基础上引入了遗传算法(GA)。

步骤一：构建时间耦合约束下的多无人机协同任务分配模型

对多无人机协同执行压制敌方防空系统(Suppression of Enemy Air Defence，SEAD)任务分配问题做出定义，并对适应度函数和任务约束进行说明，具体定义如下：

定义1：设U＝{1，2，3，...i...，M}表示无人机集合，其中元素i＝1，2，3，…，M，表示第i架无人机，M表示无人机的数量；

定义2：T＝{1，2，3，...j...，N}表示目标集合，其中元素j＝1，2，3，…，N，表示第j个目标，N表示目标的数量；

定义3：设Task＝{t₁₁，t₁₂，t₂₁.t₂₂，...，t_jh，...，t_N1，t_N2}表示任务集合，其中t_jh表示第j个目标上的第h种任务，h＝1，2，当h＝1表示打击任务，当h＝2表示毁伤评估任务；

定义4：U^jh表示能够执行任务t_jh的无人机集合；

定义5：TaskSequence_i＝{task1＞task2＞task3＞...＞taskl＞...taskn_i}表示一共i架无人机的任务序列，其中元素task>i，n_i表示分配给第i架无人机的任务数量；

定义6：Route_i＝{UP_i，taskP₁，taskP₂，...，taskP_k，...，taskP_ni，BP}表示第i架无人机的路径序列，UP_i为第i架无人机的初始位置，taskP_k为任务序列TaskSequence_i表示第k个任务的位置，k＝1，2，3，…，n_i，BP为基地的位置；

定义7：Voy_i表示第i架无人机的航程；

定义8：Voy>i表示第i架无人机的最大航程；

定义9：R_i表示第i架无人机的武器载荷数量；

定义10：t_ijh表示第i架无人机执行任务t_jh消耗的执行时间；

定义11：sT_g，g∈Task，表示任务g的开始被执行时刻；

定义12：eT_g，g∈Task，表示任务g的完成时刻；

定义13：Inter_min表示打击任务和毁伤评估任务间的最小时间间隔；

定义14：Inter_max表示打击任务和毁伤评估任务间的最大时间间隔；

定义15：定义二维决策变量表示每个任务的分配情况，下标i、j、h分别表示无人机编号、目标编号以及任务类型，其具体取值遵循如下规则：

定义16：其中G(t)表示t时刻的引力常数，G(t)的初始值为9.8，计算公式为：

其中，T表示最大迭代次数，G₀和α为固定常数，G(t)随着时间的推移，迭代步数的增加不断地减小。

定义17：best和worst分别表示在迭代中GSA个体的最大适应度函数值和最小适应度函数值，M表示GSA个体的质量，a表示GSA个体的加速度；

1.构建适应度函数

本发明中的无人机在执行任务时候不考虑飞行高度的变化，其速度始终不变，因而能够通过S＝V*t方便地将时间代价转化为航程代价，选择无人机最大航程最短作为任务规划指标，该指标是将各无人机中的最大航程最小化，引导着任务分配策略朝着最小化每架无人机航程的方向进行，本发明中选择无人机最大航程最短作为任务规划指标，即

F为本发明构造的适应度函数；

根据无人机执行SEAD任务过程中，可能会因为时间约束的关系导致无人机到达任务执行点而不能立刻执行任务，如轰炸、毁伤评估等，这时需要无人机在目标上空盘旋等待，直到满足时间要求方可执行，在这过程中，无人机由于盘旋等待而没有离开目标点去执行其他任务，但是其航程仍在增加。考虑到这种情形，在任务规划过程中计算无人机的航程时，仅仅根据无人机的路径序列，对航路点间的距离进行计算是不够的。

在定义4的前提下，以匀速运动规律计算无人机的航程，则第i架无人机的航程为：

式(2)中，是定义12中表示任务taskn_i的完成时刻，v_i表示无人机U_i的巡航速度，本发明假设无人机的巡航速度为固定值，dis(taskn_i，BP)为任务taskn_i与基地BP的欧式距离，计算公式为

式(3)中，x_BP、y_BP、分别为基地BP与任务taskn_i的横纵坐标；

2.任务约束

本发明任务分配问题中的约束条件如下：

(1)每个任务都必须被执行：

(2)每个任务只能被执行一次：

(3)每架无人机至少被分配一个任务，即：

(4)时序约束

公式(8)中是任务task_j(h+1)的开始被执行时刻；

(5)航程约束

Voy_i≤Voy>i(9)

(6)武器载荷资源约束

(7)打击任务和毁伤评估任务的时间间隔约束

eT_taskj2+Inter_min≤sT_taskj3>

eT_taskj2+Inter_max≥sT_taskj3>

步骤二：基于遗传算子的引力搜索算法设计

步骤2.1：个体离散化编码

在求解多无人机协同SEAD任务分配问题的引力搜索算法中，一个个体代表着一种分配方案，这里有两个方面的因素需要考虑：(1)选择哪些无人机执行哪些任务，即任务的分配情况；(2)各无人机以怎样的顺序去执行分配到自身的任务，即任务的排序情况。

本发明采用分段编码方式对引力搜索算法中的个体进行编码，以一个1×4N维向量表示引力搜索算法的个体；

个体编码分为两部分：任务分配(Task Allocation，TA)部分和任务排序(TaskSequencing，TS)部分，如图1所示。

定义18：设TG＝[TA TS]为一个1×4N维向量，表示一个引力搜索个体，TG分为两部分，其中TA表示任务分配部分，为2N维数组，TS表示任务排序部分，为2N维数组；

(1)任务分配部分：该部分表示N个目标共有2N个任务的分配情况，即N个目标的2N个任务如何分配给无人机i，共有2N个元素，分别代表着2N个任务，2N个元素从左往右，依次对应任务t₁₁、t₁₂、t₂₁、...、t_N1、t_N2，例如t₂₁表示无人机完成第二个目标的打击任务，t₂₂表示无人机完成第二个目标的毁伤评估任务；每个元素的取值为当前元素对应任务的可执行无人机集合中的元素，这保证了各任务被分配给能够执行该任务的无人机，如图2所示。

(2)任务排序部分：该部分表示所有任务的排序情况，该部分2N个元素，每个元素都有目标的编号编码，分别代表着2N个任务，2N个元素从左往右依次对应目标任务t₁₁、t₁₂、t₂₁、...、t_N1、t_N2，每个目标第一次出现即为打击任务，第二次出现即为毁伤评估任务；

例如在定义3中t₂₂即表示第二个目标的第二个任务(毁伤评估任务)，为目标的编号编码，假设每个目标需要完成2次任务即第一次是打击任务第二次是毁伤评估任务，在本发明中为了使问题适当简化，故简化假设每个目标只需完成两次任务；如此编码可保证攻击任务和毁伤评估任务时序耦合约束，如图3所示。

结合任务分配(TA)和任务排序(TS)两个部分，得到个体的完整编码，如图4所示。

步骤2.2：种群初始化

本发明采用随机产生的方式对个体种群进行初始化，具体方法是使用MATLAB仿真软件将一组自己设定的种群在任务约束条件下循环得出一组满足任务约束条件的初始种群，以随机初始化的方法对每个个体进行初始化编码，对于任务分配部分，每一位任务分配元素代表一个具体的任务t_jh，随机从能够执行任务t_jh的无人机集合U^jh中选取一个元素作为该位的取值，对于任务排序部分，以两组目标序号的随机排序表示该部分的位置，个体的速度初始化为0；

步骤2.3：个体解码

个体解码运算是在编码的基础上，采用和编码相反的思维，将编码得到的数据通过一定的方式转换成所研究问题的解决方案，进而可以通过解码得到的数据计算出当前方案的适应度值，即适应度函数值，并通过适应度函数的数值大小评判当前解决方案的优劣。

在任务分配部分，依次读取每一位元素的值VA_jh，其中j＝1，2，…，N，h＝1，2，VA_jh∈U，表示第VA_jh架无人机，并将任务t_jh添加到第VA_jh架无人机的任务集中，最终得到各无人机的任务分配集合；

在任务排序部分，每一个元素的值VS_d∈T，d＝1，2，…，2N，表示第VS_d个目标，每个目标有两种任务，因而每个目标会出现2次，第一次表示该目标的攻击任务，即代表任务第二次表示该目标的毁伤评估任务，即代表任务任务排序部分对所有任务进行顺序执行，对各无人机的任务分配集合中的元素进行排序，从而得到各无人机的任务执行序列；

综上，个体解码的具体步骤如下：

Step1：对任务分配部分进行解码

(1)初始化各无人机的任务集合为空集，即

(2)VA_k1＝TAL(2k-1)，其中TAL为目标数量，i＝VA_k1，将任务t_k1加入TaskSequence_i中；

(3)VA_k2＝TAL(2k)，i＝VA_k2，将任务t_k2加入TaskSequence_i中；

(4)k＝k+1，若k≤N，转到步骤(2)；否则结束；

Step2：对任务排序部分进行解码

(a)从左至右依次读取任务排序部分的第k位上的目标j的值，k＝1，2，…，2N，每个j代表目标T_j上的一个任务，若j是第h次出现，则表示Task_jm，当k＝2N得到所有任务的排列顺序TaskS；

(b)将TaskSequence_i根据TaskS重新排列任务顺序：当Task_jh和Task_kl都在TaskSequence_i中时，则以从左到右的顺序来比较；

至此，解码结束，得到各无人机的任务执行新序列TaskSequence_j；

步骤2.4：适应度函数计算适应度

依据步骤一中的适应度函数进行计算，即

F为本发明构造的适应度函数；

步骤2.5：更新种群的全局最优、局部最优和局部最差

根据步骤2.4中求得的种群中各个粒子的适应度函数值，更新种群的全局最优、局部最优和局部最差；

步骤2.6：个体更新

当个体受到其它个体的引力作用后会产生相应的加速度，个体i在第l维获得的加速度等于其受到合力与其自身惯性质量的比值，计算公式为：

式(13)中M_ii(t)为个体i在t时刻的惯性质量；F_i^l(t)表示个体i在t时刻万有引力的大小，表示个体i在t时刻在万有引力F_i^l(t)作用下的加速度，l表示个体i的第l维；

每一次更新过程中，个体i根据引力产生的加速度更新自身的速度和位置，更新方式如公式(14)所示：

表示粒子i在t+1时刻的速度，表示粒子i在t时刻的速度，表示粒子i在t+1时刻的位置，表示粒子i在t时刻的位置，rand_i表示粒子i在MATLAB仿真下的一个随机数；

对更新后的个体位置进行修正：首先对每一个个体位置)采用对于小数点后的一位四舍五入进行取整，其次，对个体位置取整后的每一位进行合法判断：若该位的值不在该位表示任务的可执行无人机集合内，则将离该位最近的一位，以集合的离该位元素最近的元素代替。

判断整个种群的迭代次数是否达到已经设定的最大迭代次数，若是，则结束流程；否则返回步骤2.3的step1，继续循环求解。

对于步骤2.6的更新，本发明引入遗传算法的交叉和变异操作对该部分进行更新，所述的更新步骤为：

a)交叉：交叉操作是利用父代个体经过一定的操作组合后产生新个体，从而达到在不破坏有效模式的前提下对解空间进行高效搜索的目的。本发明利用POX交叉方法，对个体的任务排序部分进行交叉操作，进而达到更新的目的，本发明所述的交叉操作每一次只产生一个新个体，具体步骤如下：

Step1：从目标集{T1，T2，…，Tn}随机抽取一个目标子集T_set；

Step2：选择需要进行交叉操作的个体X1和X2，若X1的适应度函数值大于X2的适应度函数值，则将X1中包含在目标子集T_set中的目标复制到新的个体C中，X1保持位置和顺序不变；

Setp3：将X2中不包含在T_set中的目标同样复制到新的个体C中，保持个体X1和X2顺序不变；

Step4：若新个体C的适应度函数值大于X2，则保存新个体C，并替代原来的个体X2；

如图5所示，如含有4个目标，随机抽取的目标集T_set＝{2，3}，X1的适应度函数要优于X2的适应度函数，将X1中包含目标2、3的位复制到新个体C中，然后将X2中去掉目标2、3后，剩下的部分按照原来的次序依次复制到C的除去2、3所在位的其他位，从而产生新个体C；

b)变异：变异操作是通过随机改变个体的某些位，从而产生较小扰动生成新个体，增加种群多样性，并在一定程度上影响着引力搜索算法的局部搜索能力。本文选择基于邻域搜索变异操作，在个体的任务分配部分不变的情况下，采用基于邻域搜索的变异方法，能够更好地通过局部范围内的搜索找到适合任务分配部分的任务排序，从而改善子代性能。本发明采用基于邻域搜索的变异方法，其操作步骤如下：

Step1：在个体的任务排序部分随机选择r个位，并生成个体排序的所有邻域；

Step2：计算任务元素所有邻域的适应度函数值，选出适应度函数值最大的个体作为子代，并代替原来的个体。

改进的混合离散引力遗传搜索算法(GSA-GA)的流程如图6所示。

本发明在以上定义、适应度函数和任务约束基础上，给出多无人机协同任务分配模型，其时间耦合约束下多无人机协同SEAD任务分配问题的数学模型如下：

已知参数：假设有5架UAV和9个待摧毁目标，UAV相关信息如表1所示，目标及着陆基地信息如表2所示。同样地，假设UAV执行打击任务的时间均为0.05h，执行毁伤评估任务的时间均为0.1h，且毁伤评估任务和打击任务的最小时间间隔为0.1h，最大时间间隔为0.5h。

表1 无人机相关信息

表2 目标及基地位置信息

战场态势如附图说明图7所示，方案实施过程如下：

1.基于以上作战想定，采用本发明改进的引力搜索算法进行仿真，种群规模设为30，最大迭代次数为100次，仿真得到最优任务分配结果如表3所示，以及各任务被执行时刻如表4所示，如图8所示为任务分配结构的甘特图，如图9所示为GSA-GA算法求解的收敛曲线。

表3 最优分配结果

表4 任务执行时刻表

由表3看出，分配结果中各UAV的资源约束和航程约束是完全满足的，由表3看出，各目标的打击与评估任务是满足任务间的时间耦合约束的。

2.针对上述问题，采用离散粒子群算法(DPSO)进行仿真验证，具体的参数设置为：ω＝0.5，c1＝0.3，c2＝0.2，如图10所示为两种算法求解下的收敛曲线，由图10可以看出，相对于离散粒子群算法，混合离散引力遗传搜索算法能够较快地收敛，但是由于两种算法均属于启发式优化算法，求得的结果往往不一定是最优解，而是可行解，因而单一的仿真结果并不能准确地比较出两种算法在求解任务分配问题上的优劣，现针对以上问题分别采用两种算法进行50次蒙特卡罗法仿真实验，统计结果如表5所示：

表5 GSA-GA与DPSO算法比较

3.如表5所示，经过50次随机求解，改进的GSA-GA得到的最佳适应度为2577.8km，最差适应度为2886.3km，平均适应度为2621.4km，平均收敛代数为21代，相比于DPSO，在最差适应度和平均适应度两项稍弱于DPSO，但是在最佳适应度和平均收敛代数上有更好的表现。实验数据表明，改进的GSA-GA算法能够有效并较快地对多UAV协同任务分配问题进行求解。