基于遗传和粒子群算法的天基资源调度策略

郭 磊 ,雪 晴 ,董彦磊 ,耿纪昭,尹 展∗

(1.军事科学院系统工程研究院,北京 100141;2.中国电子科技集团公司第五十四研究所,河北 石家庄 050081)

0 引言

天基信息网络[1](Space-Based Information Network,SBIN)是以卫星为通信手段,采用星地一体技术构成的空间通信网络[2]。 天基资源特指天基信息网络中分布的各型高、中、低轨卫星资源。 由于频率协调和星载平台技术限制,目前卫星频率和功率资源受限,如何在有限卫星资源前提下实现资源快速高效调度,最大限度满足地面通信任务对星上资源的需求是天基信息网络面临的关键技术之一。 使用传统遗传算法进行基于任务的卫星资源调度能够得到全局最优解,但存在收敛速度慢、计算过程耗时等问题;使用传统粒子群算法进行任务资源调度能够快速计算结果,但易陷入局部最优解[3]。 针对以上问题,本文提出了一种基于遗传和粒子群算法的天基资源调度改进方法,将天基资源调度问题抽象为数学上的装箱问题[4],通过重新定义遗传算法中选择、交叉和变异算子的进化行为以及粒子群算法的速度方向,结合遗传算法全局最优搜索、粒子群算法局部快速收敛优点,避免传统方法的局部最优、无法快速收敛等缺陷,提升天基资源规划调度效能。

天基资源调度问题是指在限定约束条件下,通过对任务、资源进行快速合理调度,实现卫星资源使用效能最大化。 多约束条件下资源调度问题已经被证明是NP 完全问题[5],近年来资源调度成为众多学者的热门研究。 文献[6]在卫星资源调度问题中应用简单启发式算法、局部搜索算法和遗传算法进行求解,结果表明遗传算法总体效果最好。 文献[7]以此为基础提出了一种遗传模拟退火算法,提高了算法的寻优能力。 文献[8]从调度任务特点出发建立了改进粒子群调度模型,但同传统粒子群算法相比,改进效果不明显。 本文针对卫星资源调度问题重新设计进化策略,将遗传算法和粒子群算法相结合,克服了传统遗传算法收敛速度慢,在实际工程应用中相对耗时,传统二进制编码方式不适合解决所有问题,而十进制编码方式又受到进化策略的制约,同时结合了传统粒子群算法快速收敛的优点,因此,本文所提算法能在保证全局最优搜索的同时具备快速收敛能力。

1 资源调度问题模型抽象

针对多约束条件下天基资源调度问题,采用基于任务驱动的资源调度模式,将问题抽象成待解模型。 假设一组任务(Task List,TL)总是和一组卫星转发器资源(Transponder Resource,TR)相关联,TL的任务只能使用TR 的资源,且所有使用TR 的任务都在TL 中,TR 和TL 都带有时间属性,资源调度问题数学模型如图1 所示。

图1 任务资源调度问题示意图Fig.1 Schematic diagram of task resour ce scheduling problem

图1(a)中,一组任务TL = {tl1,tl2,…,tln} ,以n = 10 为例阐述问题模型,假设n 个任务的资源需求如表1 所示。

表1 任务所需资源Tab.1 Resources required for the task

表1 中,t 为任务所需时间,f 为任务所需频率资源。 假设要求在0 ≤t ≤8、0 ≤f ≤8 范围内,尽可能多地满足任务资源需求,即追求时间、频率资源利用率最高。 将问题抽象在图1(b)所示的蓝色透明区域D 内,尽可能多地摆放任务块,使D 内的剩余面积最小。 为便于描述,将任务k 的占用资源范围表示为(mk,nk,pk,qk) ,如图2 所示。 其中,(mk,nk) 为任务k 占用资源左下角坐标,(pk,qk) 为任务k 占用资源右上角坐标。

图2 任务k 占用资源描述坐标示意图Fig.2 Schematic diagram of task k occupation resource description coordinate

调度模型为寻找TL 最优调度序列SEQ ={seq1,seq2,…seqn}(n = 10) ,按SEQ 中的顺序对任务块进行摆放,摆放范围限制在图1(b)中的蓝色透明区域D 内,摆放规则为从坐标(0,0) 处开始,沿横坐标找到能放下seqk(即任务占用资源不越界)的最小时间点tmin,再沿纵坐标在tmin时间线上找到最小可用频点ftmin,将(mk,nk) 摆放在(tmin,ftmin)处,然后将seqk从队列SEQ 中删除,若当前任务已不存在可用空间,则将其视为不可摆放任务,将其从SEQ 删除并加入不可摆放队列NSEQ,进行下一个任务的摆放,直至所有任务遍历完成,具体算法如下。

调度算法(Algorithm①)

输入：SEQ = {seq1,seq2,…,seqn} (n = 10),NSEQ=Ø。

① k=1;

② 判断k≤n,若为真,转③,否则转⑥;

③ seqk存在摆放空间,找到当前任务摆放点(tmin,ftmin),并将其从SEQ 中删除;

④ seqk不存在摆放空间,则将其从SEQ 中删除并加入NSEQ;

⑤ k=k+1,转②;

⑥ 结束;

输出：SEQ=Ø,NSEQ={不可摆放任务},为当前序列任务调度结果。

2 基于遗传和粒子群的资源调度改进方法

遗传算法和粒子群算法是目前成熟的群体优化算法,通过初始化种群,设计进化策略,使种群向最优解方向进化[9]。 遗传算法的进化策略来源于自然界生物的进化规律,即父代通过选择、交叉和变异3 种遗传算子产生子代个体,子代具有优于父代的生物特性[10]。 粒子群算法的进化策略来源于自然界动物觅食,动物在觅食过程中,依据气味等信息向可能存在食物的方向移动[11]。 进化策略的合理性决定最终搜索结果的优劣,因此2 种算法进行应用的关键是对具体问题设计合理的编码方案和进化策略。

2.1 编码方案选择

传统的遗传算法和粒子群算法一般采用二进制编码方案,本文将天基资源调度问题抽象成任务排序摆放问题,故传统编码方案不再适用。 针对任务排序问题,设计十进制编码方案,对于一组待调度任务TL = {tl1,tl2,…,tln} ,用十进制编码集合SEQ ={seq1,seq2,…,seqn} 表示该组任务的一种调度顺序,其中seqi与tlseqi一一对应,代表一个待调度任务编号,且seqi∈{1,2,…,n - 1,n} 。SEQ 对应一组待调度任务的执行顺序,同时对应一个资源分配方案和相应的资源利用率,资源利用率越高,表明编码方案越优。

2.2 进化策略设计

群体优化算法进化的基本思想是依据进化策略产生的子代群体总体上应优于父代群体,进化后群体向着越来越优的方向发展[12]。 进化策略的设计原则是子代在继承父代优秀基因基础上保留产生新优秀基因的可能性,同时摒弃父代中的非优秀基因。

对于资源调度问题,优秀基因定义是进化策略设计的核心[13]。 本文用待分配任务序列表示一个资源调度方案,即优秀的任务序列具有更高的资源利用率。 在此将基因定义为任务调度的相对顺序,优秀基因代表队列中任务的相对顺序能产生更高的资源利用率。 例如,有2 个待分配任务A 和B ,若有序集合{A,B} 的资源利用率高于有序集合{B,A} ,则认为基因{A,B} 优于基因{B,A} 。 依此原则,分别设计遗传算法和粒子群算法的进化策略。

2.2.1 遗传算法进化策略

遗传算法进化策略包含3 个算子：选择、交叉和变异。 选择算子将父代群体中的优秀基因保留下来;交叉算子将父代群体基因进行杂交,产生新的更优秀基因;变异算子保留子代产生新优秀基因的可能性,使进化不受父代群体限制,能够在全局范围内搜索问题最优解[14]。 本文以优秀基因定义为原则,设计了3 种进化算子。

(1) 选择算子

假设父代种群有r 个个体{SEQ1,SEQ2,…,SEQr} ,设定参数θ ∈(0,1) ,保留r 个个体中最优的r × θ 个个体作为子代群体的一部分,即选择算子。

(2) 交叉算子

以n = 10 为例,假设有2 个父代个体,如式(1)和式(2)所示。

其中,右上角的数字代表进化代数,定义交叉点为2 个数字间的位置,对于具有n = 10 个任务的队列来说,有9 个不同的交叉点,如图3 所示。

图3 n=10 任务队列交叉点示意图Fig.3 Schematic diagram of task queue intersection when n=10

图4 交叉算子进化行为示意图Fig.4 Evolutionary behavior of Crossover operators

(3) 变异算子

一次变异行为发生在2 个基因之间,个体变异时随机选取2 个基因位,2 个基因位上的基因互相交换位置产生一个新个体,如图5 所示。 以第一代个体= {5,8,4,1,3,6,7,2,10,9} 为例,若此时随机产生的变异基因位为(3,9),则将3 号基因位的基因“4”与9 号基因位的基因“10”交换位置,得到子代个体= {5,8,10,1,3,6,7,2,4,9} 。

图5 变异算子进化行为示意图Fig.5 Schematic diagram of evolution behavior of mutation operators

以上3 种遗传算子既保留了父代群体中的优秀基因,也使子代具有产生新优秀基因的可能性。 每一次进化产生的子代群体在总体上都优于父代群体,随着进化代数增加,群体向最优解方向收敛。

2.2.2 粒子群算法进化策略

不同于遗传算法,粒子群算法不通过选择、交叉和变异产生子代个体,而是通过更新个体位置和速度的方式进行迭代[15]。

假设有r 个个体的第n 代群体SEQn= {} ,针对每个个体,要找到最佳速度vi,使+vi。 传统粒子群算法中,速度vi由历代最优个体和当代最优个体得到。集合{,} 为历代的最优个体,集合{,…} 为第n 代所有个体,为了得到当前进化速度,从{} ∪{,…} 中选取最优个体,即第g 代的第h 个个体,其中g ∈[1,n] ,h ∈[1,r] ,且均为整数。 定义vi=,由+ vi可得下一代个体,该设计思想可使当前个体每次进化时都向更优方向前进。

对于资源调度问题,由于每个个体是一组待调度任务序列,所以进化速度无法通过简单的数学运算得出[16],据此设计进化策略如图6 所示。 随机生成一个基因数β,在此取β=2 代表每次从最优个体中拷贝的连续基因数量上限,如图6 左侧的红色方框所示。 取父代个体中的第一个基因摆在子代个体基因位1 的位置,在当前最优个体中找到该基因,并顺位取包括该基因在内的连续β 个基因加入子代个体,然后将加入子代的基因分别从父代个体和当前最优个体中删除,完成一轮循环。 顺位取父代个体中的下一个基因,重复以上操作,直至所有基因全部取完,此时得到子代个体。 依此策略得到的子代个体既保留了父代的部分基因,也学习了当前最优个体中的部分基因。 在资源调度问题中,已将优秀基因定义为能得到高资源利用率的基因相对位置[17]。 在图6 中,学习到了当前最优个体中红框内的相对基因位置,即有序集合{2,10},{8,4},{6,7},{3,9},{1},{5} ,同时也保留了父代个体的部分相对基因,即黄色基因序列{2,8,6,3,1,5} ,因此子代个体是在父代个体的基础上向当前最优个体收敛。

图6 粒子群算法进化示意图Fig.6 Evolution of PSO

2.3 遗传-粒子群算法

首先定义个体适应度为特定任务调度序列下的资源利用率,资源利用率越高,个体适应度值越高,总结遗传算法流程、粒子群算法流程如下所示。

(1) 遗传算法(Algorithm②)

① 编码并生成初代种群;

② 利用Algorithm①计算种群中个体适应度;

③ 若适应度达到满意程度,转⑥,否则转④;

④ 对初代种群进行选择、交叉和变异,得到子代种群;

⑤ 转②;

⑥ 结束。

(2) 粒子群算法(Algorithm③)

① 编码并生成初代种群;

② 利用Algorithm①计算种群中个体适应度;

③ 若适应度达到满意程度,转⑥,否则转④;

④ 向当前最优个体进化,得到子代种群;

⑤ 转②;

⑥ 结束。

遗传-粒子群算法的整体流程与Algorithm②和Algorithm③一致,不同点是在进化过程中将父代个体按照适应度进行排序,取较优部分使用粒子群算法进行进化,其余部分使用遗传算法进行进化,完成后计算子代个体适应度并排序,将子代个体作为父代个体重新进行迭代计算直到获得最优值,算法示意如图7 所示,算法流程如下所示。

图7 遗传-粒子群算法示意图Fig.7 Schematic diagram of the genetic-PSO algorithm

(3) 遗传-粒子群算法(Algorithm④)

① 编码并生成初代种群;

② 用Algorithm①计算种群中个体适应度;

③ 适应度达到满意程度,转⑥,否则转④;

④ 较优个体使用粒子群算法进行进化,剩余个体使用遗传算法进行进化,完成后组合得到子代种群;

⑤ 转②;

⑥ 结束。

3 实验及结果分析

针对天基信息网络资源调度计算量大、无法快速收敛到最优解问题[18],利用传统遗传算法、粒子群算法和改进遗传-粒子群算法分别进行资源调度实验,通过对实验结果进行分析比较,验证本文提出的遗传-粒子群算法具有全局最优搜索、计算快速收敛等优点。

以表1 所示的任务模型为例,首先使用传统遗传算法进行任务调度,随机生成100 个任务调度序列作为初始种群,分三轮进化,每轮在上一轮基础上进化100 代。 第一轮进化后的最优个体为{1,2,3,4,5,6,7,8,9,10} ,剩余任务为{9,10} ,资源利用率为78.125%,如图8(a)、图8(d)和图8(g)所示;第二轮进化后的最优个体为{2,9,3,7,5,8,6,1,4,10} ,剩余任务为{4} ,资源利用率为81.25%,如图8(b),图8(e)和图8(h)所示;第三轮进化后得到全局最优个体{7,5,1,9,8,2,3,4,6,10} ,无剩余任务,资源利用率为96. 875%,如图8(c)和图8(f)所示。

图8 遗传算法进化结果Fig.8 Results of genetic algorithm evolution

任务模型保持不变,初始种群个体数量保持不变,但分别生成2 个不同的初始种群使用传统粒子群算法进行任务调度。 初始种群1 中初代最优个体为{3,4,10,7,1,5,8,9,6,2} ,剩余任务为{9,6,2} ,资源利用率为73.437 5%,使用粒子群算法进化,当进化到100 代时结果已经收敛,此时最优个体为{1,3,10,7,6,5,2,9,8,4} ,剩余任务为{4,9} ,资源利用率为76.562 5%,如图9 (a)、图9(c)和图9(e)所示。 初始种群2 中初代最优个体为{10,1,2,9,5,8,4,3,6,7} ,剩余任务为{7} ,资源利用率为81.25%,使用粒子群算法进化100 代时结果同样收敛,此时最优个体为{7,9,8,2,3,10,4,1,5,6} ,剩余任务为{6} ,资源利用率为87.5%,如图9 (b)、图9(d)和图9(f)所示。

任务模型保持不变,初始种群个体数量保持不变,使用改进后的遗传-粒子群算法进行任务调度,结果如图10(a)和图10 (b)所示。

种群在第83 代时收敛到最优解,到100 代时最优解不变,此时的资源利用率为96. 875%,对应任务调度序列为{7,5,1,9,8,2,3,4,6,10},所有任务均在规定的时间和频率范围内获得相应的资源。

图9 粒子群算法进化结果Fig.9 Results of PSO algorithm evolution

图10 遗传-粒子群算法进化结果Fig.10 Results of genetic-PSO algorithm evolution

综上比较,使用传统遗传算法虽然能够计算得到最优解,但受限于进化策略,收敛速度较慢,收敛所需时间至少是遗传-粒子群算法的3 倍。 粒子群算法虽然能够快速收敛,但局限于进化策略,整个进化过程受初始种群优劣限制,容易陷入局部最优解。遗传-粒子群算法不受初始种群优劣限制,具有全局最优搜索,高效快速收敛优点。

4 结束语

以天基信息网络资源调度问题为背景,针对传统遗传算法局部最优、无法快速收敛等局限性,提出了一种改进的遗传-粒子群天基资源调度算法,将资源调度问题抽象为任务排序问题,以传统遗传算法和粒子群算法为基础,设计新的十进制编码方案和种群进化策略以适应资源调度问题模型,重新定义遗传算法的选择、交叉、变异行为以及粒子群算法的进化速度。 通过实验仿真,将传统遗传算法、粒子群算法和改进遗传-粒子群算法进行对比,结果证明,改进后的遗传-粒子群算法具有全局最优搜索能力且具有较快的收敛速度,能够应用于天基资源调度领域。