基于改进遗传算法的相控阵雷达任务调度方法

明 乐，周 峰

(空军工程大学防空反导学院，陕西 西安 710051)

0 引言

相控阵雷达具有灵活、快速的波束捷变和自适应能力，它可以同时执行多个任务，如搜索和跟踪[1-4]。近年来，相控阵雷达资源调度方法层出不穷，而遗传算法作为一种模拟生物进化“优胜劣汰”的搜索方法，是一种高效、并行、全局优化的搜索方法，可以实现资源的最佳调度。

文献[5]将相控阵雷达任务的调度过程与车间作业的调度流程进行了类比分析。算法根据雷达任务的优先级和时间窗对调度性能的影响，定义了最优调度的目标函数，同时考虑了时间、能量和计算机资源约束条件。文献[6]在文献[5]的基础上分析了雷达任务的编码规则，详细介绍了算法求解过程中初始种群生成、选择、交叉和变异算子的设计，并且通过仿真验证了基于遗传算法的相控阵雷达任务自适应调度算法的可行性和有效性。然而，早期的遗传算法仍然存在早熟现象，针对这一缺陷，文献[7]提出动态的交叉和变异概率，该算法虽然在一定程度上能克服早熟现象，但是当种群较大时，在后期迭代中基因改动较小，导致系统全局能力变差。

上述遗传算法在任务调度过程中容易出现收敛速度慢以及早熟的问题，针对这一问题，本文提出了一种基于改进遗传算法的相控阵雷达任务调度方法。

1 任务调度模型

1.1 遗传算法调度的目标函数

本文采用文献[8]中的方法，把任务执行时间与期望执行时间的偏移量的和最小及所有类型任务调度成功率加权和最大作为调度的目标函数，具体表达式如下：

(1)

式(1)中，M、L、P和Q分别为搜索、验证、跟踪和失跟的子类数目，A(·)为代价函数，当ηi=1时，δ(·)=1，否则δ(·)=0，ρi为雷达任务的加权，ni表示第i类雷达任务调度安排的个数，Ni为待调度安排的数目，F(·)表示执行效益因子。

1.2 遗传算法调度的约束条件

限制相控阵雷达任务调度的重要因素有时间、计算机、能量和硬件资源[9-11]，每一个任务的执行都需要消耗时间、能量资源，并且还会占用计算机和硬件资源，所以在研究任务调度的过程中必须充分考虑这四种约束条件。

1) 时间资源约束

时间资源约束反映的是在一个调度间隔内能调度的事件数目，其约束条件如下所示：

(2)

式(2)中，Dj表示的是一个调度间隔中第j个雷达任务的波束驻留时间，N为调度间隔内任务总数。

2) 能量资源约束

能量资源约束指的是发射机占空比需要满足一定条件，遵从发射系统的平均功率容量。具体如下：

(3)

式(3)中，τ表示的是占空比，α为比率，Pjk为脉宽，Lj为第j个波束驻留中发射脉冲个数。

3) 计算机资源约束

计算机资源对信号处理的速度有一定的影响，从而对雷达的任务调度也会产生一定的影响，具体表达式如下：

(4)

式(4)中，g(·)表示事件产生数目，R2表示计算机总资源。

4) 硬件约束

其约束条件为：

(5)

式(5)中，h(·)表示事件对雷达硬件的需求，R3表示雷达硬件总资源。

2 改进的遗传算法及其任务调度流程

常见的遗传算子有交叉、变异和选择算子，其中交叉算子是重要组成部分。所谓交叉是交换两个染色体的局部结构，然后重组成新的个体，经过交叉步骤，能够把父代的优良基因遗传给子代，从而确保得到全局最优解。所以交叉是新个体产生的主要途径，是全局收敛性的重要保证[12]。传统的交叉操作具有一定的盲目性，父代染色体进行交叉后可能会导致其优良基因被破坏，无法遗传给下一代。因此本文提出了一种改进的交叉方案，来保证父代的优良基因尽可能的遗传给子代个体。

本文提出的编码相似度指的是种群内两个不同个体染色体对应位置编码的相似程度。假设现有两个父个体X和Y，我们定义其相似度为：

ξ=α/n

(6)

式(16)中，ξ表示的是编码相似度，α表示的是两个个体对应位置编码相同的数目，n表示的是个体染色体编码的长度。

假设个体X的代码为1010101010，个体Y的代码为1000011001，那么可以看出两个个体的相同位串数量为5，此时的α=5，n=10，因此ξ=5/10=0.5。

有了编码相似度并不能决定是否进行交叉操作，需要一个参照点，在这里提出标准交叉点的概念，所谓的标准交叉点指的是当前染色体种群进行交叉操作的门限，是一种临界值，其具体表示方法[13]如下：

(7)

式(7)中，k为标准交叉点，G为此群体事先设置的总进化代数，g为算法到目前为止已运行的代数。因为式中g是在随着种群进化而在不断增大的，所以k的值是处于一种动态变化的，是随着种群进化不断增大的。

当两个染色体的相似性ξ小于或者等于动态标准交叉点k时，才可以进行个体的交叉操作，反之，则不进行交叉操作，而是克隆其本身，直接将其基因遗传给下一代。在遗传算法的早期阶段，种群个体是随机产生的，编码相似度比较低，此时为了保留群体中的优良个体，所以k值应相对较小，降低其交叉几率；在后期阶段遗传算法趋于收敛时，个体之间的差别较小，它们的相似性较高，此时应增大k值，使得群体中的个体还能进行交叉操作，保障了群体的多样性，防止出现局部最优解以及早熟问题。

本文提出的对父代染色体标准交叉点的动态控制，从理论上分析能有效提高遗传算法的收敛速度，保障了群体的多样性，防止出现局部最优解，提高了其全局搜索能力。为了更好地评价本文提出的改进算法，下面会对基于改进遗传算法的相控阵雷达任务调度进行研究。

假设雷达在一个调度间隔SI=[t0,t1]内有N个任务请求[14]{q1,q2,q3，…，qn}。对于其中一个任务qi，其优先级是pi，最早可调度时间是tzi，最晚可调度时间是twi，期望调度时间是tqi，调度的时间长度是Δti。任务调度的具体步骤如下：

第一步 在一个调度间隔内的任务根据优先级进行排序，得到待调度任务序列Q。

第二步 从待调度任务序列Q中取出任务ql，并将ql的期望调度时间和Q中每个任务的调度时间进行比较，得出ql前后的两个任务，分别记作qs和qm。确定qs的最早调度时间为tzs，qm的最晚调度时间为twm。

第三步 当tzs+Δts>twm时，任务ql分配至删除队列；当tzs+Δts=twm时，任务ql分配至延迟队列；当tzs+Δts

第四步 本调度间隔内的任务结束，此时Q=∅；若不是，则l=l+1，返回第一步。

基于改进遗传算法调度结构框图如图1所示，其中综合优先级包括任务工作方式优先级和其截止期。结构框图中改进的遗传算法模块的具体流程图如图2所示。

图1 基于改进遗传算法任务调度结构框图Fig.1 Structure diagram of task scheduling based on improved genetic algorithm

图2 改进的遗传算法模块Fig.2 Improved genetic algorithm module

3 仿真试验及性能评估

3.1 性能评估指标

本文采用以下评估指标对改进的算法进行性能评估，从而验证其具有一定的优势。

1) 调度成功率[15](Schedule Sccess Ratio，SSR)：

(8)

式(8)中，Nsuc为成功调度任务总数；N为所有请求的任务总数。调度成功率用来描述调度任务的情况，调度成功率越高，性能越好。

2) 截止期错误率(Miss deadline Ratio，MDR)：

(9)

式(9)中，Ndef为在截止期内调度失败的任务数；N为所有请求的任务总数。截止期错误率反映的是在截止期内任务的调度情况，截止期错误率越低，方法性能越佳。

3.2 仿真分析

本文为了更好地对比新算法与传统算法在性能上的差异，采用了如下仿真参数对两种算法进行仿真，通过仿真结果来检验新算法的性能。

仿真参数：1)调度间隔为50 ms；2)综合优先级的设计均衡考虑工作方式优先级和截止期的影响；3)改进的遗传算法中，编码采取二进制的方式，其最大交叉概率pc=0.9，最大变异概率pm=0.1，最大进化代数1 000。

任务的参数设置如表1所示。

表1 任务参数设置

计算出两种方法10次独立实验结果的平均值。图3得到的是两种方法的调度成功率随目标数量的变化曲线；图4得到的是两种方法的截止期错失率随目标数量的变化曲线。

图3 任务调度成功率对比Fig.3 The contrast of schedule success ratio

图4 截止期错失率对比Fig.4 The contrast ofmiss deadline ratio

从图3中可以看出，当目标很少时，两种算法在调度成功率方面相差并不大，由于此时相控阵雷达资源充足，大部分任务基本都可以被成功安排。随着目标数目的增多，两种算法的调度成功率都有所下降，但是改进遗传算法相较于标准的遗传算法，其任务调度成功率更高。在目标数量160左右时，曲线已经降到很低，是由于相控阵雷达资源趋于饱和导致了两种调度方法的成功率很低。

从图4中可以看出，随着目标数目的增多，两种调度算法的截止期错误率都会上升，但是显然改进遗传算法的调度方法比传统的遗传算法上升的慢，在目标数量为200左右时，基于标准遗传算法的调度算法的截止期错误率已经达到了0.016 8，而基于改进遗传算法的调度方法达到了0.013，改进遗传算法的截止期错误率要小一些。

表2给出的是进行10次独立试验后，计算出的两种方法的SSR和MDR的均值以及标准差。由表2可以更直观地得到结论：基于改进遗传算法的相控阵雷达任务调度方法能提升任务调度的成功率，减少截止期错误率，并且其统计标准差较小，表明改进后的算法比传统的算法在任务调度方面表现的更加稳定。

表2 调度性能指标统计结果

4 结论

本文提出了一种改进遗传算法的相控阵雷达任务调度方法。该方法在现有遗传算法的基础上引入编码相似度以及动态标准交叉点的概念，通过比较两者的大小来决定是否进行交叉操作，避免了交叉过程的盲目性，保留了种群的优良基因，有效提升了遗传算法的收敛性能，提高了相应的收敛速度；通过动态控制父代染色体的标准交叉点，来维持算法推进过程中种群的多样性，提升系统全局搜索能力，避免了局部最优解的产生。仿真试验结果表明，与传统的遗传算法相比较，该算法提升了任务调度成功率，降低了截止期错失率，有效提高了相控阵雷达的整体调度性能，具有一定的优势。