基于改进粒子群算法的多无人机任务分配研究

　　1　引言

　　无人机由于具有重量轻、尺寸小、机动性高、隐蔽性好、适应性强和不必冒生命危险等特点,在民用和军用领域受到广泛关注。随着无人机技术的发展和军事需求的进一步提高,如果UAV孤立的作战,必然会由于其对战场态势认识的不足而降低攻击能力和规避能力;如果多架UAV只是简单地构成机群,而机群间没有相互的协调机制,那么只会增加机群的规模,并不能提高机群的战斗力,甚至给机群带来不利的影响。因此,由多UAV所组成的飞行编队中的协调与控制,成为UAV领域一个重要的研究课题[1]。任务分配是多无人机任务规划的一个重点问题,它解决的是多架无人机在协同执行多项任务时各无人机做什么和怎样做的问题。已有学者应用进化算法[2-3]、蚁群算法[4]、合同网[5]等方法对该问题进行了求解。本文将展开粒子群算法在该问题上。

　　2　协同任务分配模型的建立

　　2.1　决策变量的设计

　　二进制决策变量:

　　2.2　网络流示意图

　　为了形象直观地表达多无人机任务分配问题,将此问题描述为如下网络流模型,图中将无人机和任务进行统一编号,任务号为1…n,无人机号为n +1…n +w,图中虚线内的任务点可以彼此达到。

　　2.3　多无人机任务分配的混合整数线性规划模型

　　考虑最小化总飞行时间和最大化任务执行数量两项指标,指标之间采用加权相加形式,给出目标函数如下:

　　约束条件：

　　约束条件1-10分别表达了:

　　1)一项任务只能由一架无人机执行一次。

　　2)只有一架无人机飞离该任务。

　　3)K设定为一个较大的量若无人机未由任务i位置向任务j位置飞行,则此约束条件总能被满足。

　　4)当xki, j=1时本约束与3)合为一个等式约束,表示无人机在一个任务上的执行时间等于其前续任务执行的时间与两任务之间的飞行时间之和。

　　5)时间窗约束。

　　6)任务时序约束。

　　7)无人机不能在相同的任务之间航行。

　　8)无人机不能在基地之间航行。

　　9)无人机进入某个任务点也必须从该任务点离开,但不是原路返回。

　　10)无人机的最大航程限制。

　　3　粒子群算法的改进策略

　　多无人机任务分配问题属于多约束组合优化问题,由于变量维数高、约束条件复杂,搜索过程中的某些搜索区域是不可行的,导致整个搜索区域呈现出狭长的或不连续的状态。基本粒子群算法由于存在两个缺陷:1)容易陷入局部极值;2)精细搜索能力不强。在求解此类大规模多约束组合优化问题时找到全局最优解的效率非常低,为了使粒子群算法在尽可能少的时间代价下取得较高的探测和开发能力,本文提出了一种多子群多阶段粒子群算法。现有粒子群算法的离散策略很多,本文将遗传算法的交叉和变异操作与粒子群结合实现粒子群算法的离散化[6]。