一种基于分散搜索的多星测控调度遗传算法

陈峰　刘孝忠　徐建华　姚頔

摘 要：多星测控调度是一个具有大搜索空间的多峰问题。针对简单遗传算法求解易陷入局部最优和不稳定的缺陷，借鉴分散搜索多样化采样、局部寻优的特点，提出一种基于分散搜索的混合遗传算法，在全局的随机搜索中嵌入全局的定向搜索。在描述问题的基础上，提出可进行细粒度搜索的可行解表示方式，构建算法的整体流程，并设计由输入参数控制的多样化初始集产生方法、基于质量和多样性原则的参考集生成和更新方法、吸取被组合个体优良成份的解组合方法及基于启发式局部搜索的解提高方法等算法要素。仿真表明新算法在求解质量上比简单遗传算法有明显提高。

关键词：调度；分散搜索；遗传算法；测控

中图分类号：TP18 文献标识码：A

Abstract：MultiSatellite TT&C scheduling is a multipeak problem with huge search space.The simple genetic algorithm solving is prone to get into local optimization and instability.Because Scatter Search can sample diversifiedly and optimize locally， a hybridized genetic algorithm based on scatter search was proposed， which embeds the global directed search in the global stochastic search. After the problem was described，the representation of feasible solution was designed，which was convenient for searching roundly， then the process of the algorithm was construced， and the main elements of the algorithm were presented， which includes diversification generator controled by input parameters ， reference set generating and updating method based on quality and diversification principle， the combination method drawning on the good components of combinated solutions， and the improvement method based on heuristic local searching. Simulation result shows the new algorithm can improve the quality of the solutions，compared with the simple genetic algorithm.

Key words：scheduling；scatter search；genetic algorithm； TT&C

1 引 言

多星测控调度问题是指在多星测控需求和测控资源一定的背景下，研究如何合理分配测控资源，以更好满足所有测控需求的问题[1]，是一个NP完全问题[2]。对于该类问题，主要有针对规划模型的确定性解法[ 3]、基于规则和约束满足的启发式算法[4]以及智能搜索算法（以遗传算法为主）[5-7]。从研究结果来看，遗传算法（Genetic Algorithm，GA）的求解效果较好[6]。

虽然理论上GA的全局收敛性能够保证算法对初值的鲁棒性，但在解决一些实际问题时，求解搜索过程中某些低阶模式可能难以重组为期望的高阶模式，这会使其搜索效率大大降低[8]，而此时种群的质量就将对算法的性能产生很大的影响。在用简单遗传算法（Simple Genetic Algorithm，SGA）求解多星测控调度问题时，编码长，搜索空间大且多峰效应严重，若进行细粒度的搜索，则搜索效率较低，而且获得的往往是局部最优解，若进行粗粒度的搜索，则随机搜索特性较强，解的质量和稳定性无法保证。如果在进化过程中启发式地往种群中加入一些搜索空间中适应度高且离散分布的个体，可以确保搜索的遍历性和重点性。分散搜索（Scatter Search，SS）是一种基于整数编码的具有保优思想的元启发式算法，它蕴含了记忆搜索的功能，通过在整个搜索空间中采取离散的多点采样、系统性组合[9]、局部提高等举措，来获得一组兼顾质量和多样性的解[10]，已成功应用于车间任务调度[11，12]、项目调度[13]等问题。

本文针对多星测控调度问题的特点，将SS系统地的局部搜索与GA的全局随机搜索结合起来，提出一种基于分散搜索的遗传算法（Genetic Algorithm Based on Scatter Search，GASS），以期更有效地对问题进行求解。

2 问题描述

设有若干低轨卫星、地面测控站；对每颗卫星，需在一段时间内完成若干测控需求，这些需求的允许执行时间相互不重叠；所有卫星的测控需求总数记为CReq；对于每个测控任务需求，包含：卫星名称、卫星天线名称、需求类型、最早开始时间、最晚结束时间、需求优先级、每次测控最短持续时间等固有属性及构成调度目标的每天跟踪站数、每天升轨跟踪次数和每天降轨跟踪次数（其和构成需求要求的每天测控次数，记为Rj）、最小测控间隔时间、最大测控间隔时间五个具体要素。

调度以天为时间单位进行，首先把测控需求的卫星名称、需求最早开始时间和最晚结束时间、每次测控最短持续时间等信息与通过可见性分析软件获得的卫星可见弧段进行结合，得到各需求的每天可用可见弧段集合，每个弧段包含起止时间、卫星及天线、地面站及设备、升降轨等信息，然后从弧段集合中抽取Rj个弧段分配给需求，分配过程考虑冲突消解，最终形成调度方案。

2.2 解的表示

将问题的可行解（调度方案）表示成被调度弧段ID号的整数排列形式，这种表示方法对SGA和SS都适用，为表述方便，统称为染色体（个体）。

把调度周期内的所有需求对应的可用可见弧段存入某一集合，将该集合中所有弧段所对应的位置序号序列作为一个标准参照序列。

编码设计如图1所示：依据一定规则不重复地从标准参照序列中选出序号，依次排列，形成染色体，染色体的长度为所有弧段的总数，记为NTotal。解码时依次将染色体每个基因值对应的可用可见弧段分配给相应的需求，在此过程中，每对一个弧段进行分配后（表明该时间段内弧段对应的测控站

天线对弧段对应的卫星服务），要对染色体剩下所有基因对应弧段进行一次资源冲突消解。此处的冲突是指在某一个调度方案中，由于地面资源的限制，当某一弧段分配给某一测控需求时，导致分配给另一测控任务需求的弧段无法执行。当某需求要求的弧段数满足时，染色体中与该需求对应的可用可见弧段将不再参与分配。

3 分散搜索算法基本框架

SS最早在1977年由Glover Fred为解决整数规划问题而提出[14]，但一直没有得到重视，直到1998年Glover[15]给出了算法的通用框架和具体实现技术，才被广泛地关注与应用[16]。分散搜索的思想源于使用系统的方法对多个解进行组合以满足需要的特征或约束[16]，即通过预先设定的规则来提取若干个解的“好”的部分以组合成“更好”的解。它在对搜索空间分散采样的基础上，基于高质量和多样性的原则从采样点中选择一部分“好”解构成参考集，然后通过各种方法对参考集中的解进行要素提取和组合，以形成更“好”的解，并对参考集进行更新，当参考集中解的质量不能再提高时，也就标志着这一次分散采样点可能的组合效应都已经表现出来，需重新进行下一轮的多样化采样及后续操作。具体框架如下：

1）在问题的可行解空间中抽样一系列多样性的初始解，构成初始集P；其生成主要有系统方法和启发式方法[17]。系统的方法即是根据可行解空间中解的分布位置分散采样，而启发式方法则是根据解在目标值空间中的分布位置分散采样。

2）运用参考集生成方法，从初始集中选出兼顾质量和多样性的解构成参考集RefSet，SS主要通过对参考集中的解进行各种方式的组合和局部提高来获取问题的最优解或满意解。

3）运用子集产生方法，对RefSet构建子集。为了对参考集中的解进行各种可能的组合，先将要组合的解配对存储，也就是从RefSet中抽取各种规模的子集；出于运算时间和组合效果的考虑，常用的子集类型有[18]：二元素子集、三元素子集、最优若干元素子集等。为确保求解效率，产生的子集互不相同。

4）运用解组合方法，对每个子集中的解进行合并组合以产生一个或多个新解，所有子集的合并应遵循尽可能使新解中包含多样性解和高质量解的原则。

5）对新解运用解改进方法，提高解的质量，该过程一般是对新解进行一个局部的搜索。

6）运用参考集更新方法从所有经过提高的解中选择“好”解来更新参考集，更新的原则仍然是选用高质量解和多样性解。如果参考集能够被更新，则重新运用子集产生方法，产生子集，进入下一轮的组合提高，如果参考集不能被更新，则结束此次抽样的寻优，根据需要确定是否进行下一次抽样寻优。

4 基于分散搜索的混合遗传算法

4.1 GASS整体流程

从模型可以知道，虽然资源冲突是影响每个需求被满足和所有需求被满足的一个重要因素，但是，目标函数仍然存在一定的可加性，即目标值是所有需求被满足程度的加权和，这一特点与SS提出者的初衷正好吻合，即SS具有在巨大的搜索空间中搜索到一些分布分散且质量较优的解的能力，而此性能正好能够提高SGA的搜索起点，使其一些进化操作刚好作用于解的薄弱部分，从而有助于SGA克服全局搜索时被多峰效应干扰的困境。鉴于此，考虑在SGA的随机搜索过程中嵌入SS，利用SS获得的解来改进SGA的种群质量，以此来提高SGA求解的质量和稳定性。总体思想是：在SGA的每代进化中，当前初始集ISetO中的解分别被SGA（作为其种群的一部分）和SS操作，后者获得参考集RefSetN，种群更新时，由SS的多样化生成方法重新生成一个新初始集ISetN，将其中的解和由SS刚获得的参考集RefSetN中的解加入新种群中。新加入种群的参考集RefSetN中的解可以看作是SGA对ISetO采取一定的方法进化得来的。算法的整体步骤如表下：

基于分散搜索的遗传算法

1）生成初始种群，其中δ·popsize（0.7≤δ≤0.85）个个体随机生成，（1-δ）·popsize个个体由多样化生成方法生成，该部分个体同时作为SS的初始集；

2）计算种群中各个体适应度；令进化代数generation= 0；遗传操作计数变量m=popsize；

3）判断算法终止条件是否满足？若是，则输出结果，否则，转步骤4；

4）若m>0，从种群中随机选择两个个体进行交叉、变异运算，并转步骤5；否则转步骤6；

5）m=m-2，转步骤4；

6）计算经交叉、变异后的个体适应度，排序（精英）选择确定进入下一代种群的δ·popsize-RefSet

个个体；

7）对初始集中的个体，用参考集生成方法生成RefSet；

8）若RefSet没有变化，则转步骤10，否则转步骤9；

9）对RefSet采用子集产生方法产生Subsets；依次对每个子集采用解组合方法产生一个新解，应用解提高方法对其进行提高，并用参考集更新方法对RefSet进行更新；转步骤8；

10）由多样化生成方法生成（1-δ）·popsize个个体，替换初始集中的个体，并与RefSet中个体一起加入下一代种群；

11）generation =generation +1，转步骤3。

4.2 多星测控调度的GASS要素设计

4.2.1 遗传操作算子

采用与本文类似编码进行求解的相关研究表明，Syswerda的基于位置的交叉算子[2， 6]和排序选择算子[2， 6， 19]性能较好；为确保求解质量，采用精英保留策略；另外，为与Syswerda的序列交叉算子主要继承父个体中某些基因相对顺序的特点互补，采用两点交换变异算子对染色体基因间的绝对顺序进行变换，即随机确定若干对位置，然后交换位置上的基因。

4.2.2 分散搜索子方法设计

虽然Glover在文献[15]中给出了针对整数规划问题的SS求解框架，其初始集生成方法、子集生成方法也具有一定的通用性，但在求解各种实际问题时，其它各子方法仍需要结合问题的特点进行设计。根据多星测控调度问题解的表示方法和目标函数的特点，设计如下求解子方法。

5）解提高方法

采用局部搜索提高方法时，如果对不满足的需求进行随机的邻域搜索，则时间开销太大，且效果也不理想，考虑到时间间隔约束是模型中最强的约束，此处采用一种首先对弧段间隔时间进行预处理的半启发式局部随机搜索提高方法。

局部提高方法

1）对某未满足需求的所有可用弧段按照起始时间从低到高进行排列；

2）对每个弧段i，将与其时间间隔满足最小和最大测控时间间隔的左侧弧段集合和右侧弧段集合分别称为该弧段的左邻弧段集和右邻弧段集，统称为相邻弧段集；3）首先随机确定一个弧段，若其具有两个方向的相邻弧段集，则随机确定一个集合，同时也就获得了一个选择方向，并从中随机确定一个弧段，然后根据选择方向，在该弧段的选择方向弧段中选择弧段，依此法选择下去，当进行到某个弧段在选择方向上没有相邻弧段且需求还没有被分配要求的弧段数时，则从被分配的第一个弧段的另外一个方向上开始搜索，直到被分配要求的弧段数，该过程中，若某弧段无相邻弧段集，则重新选择第一个弧段；

4）对该需求的满足情况进行计算，若需求被满足，则转入步骤1；若需求没满足，则重新转入步骤3，直到满足停止规则。

5 实验及分析

5.1 实验设计

创建两个仿真场景：场景一包含20颗卫星（表1中的前20颗）和5个地面测站，场景二包含35颗低轨卫星，5个地面测站，卫星各配一架天线，测站各配一套设备，频段匹配，具体参数见表1（轨道用Semimajor Axis（S）/km、Eccentricity（E）、Inclination（I）/deg、Argument of Perigee（A）/deg、RAAN（R）/deg、TraeAnomaly（T）/deg表示。）和表2。仿真时间：2009＼＼06＼＼14 00：00：00～ 2009＼＼06＼＼1500∶00∶00。各卫星任务需求优先级相同，各具体要求统一设置为：每天跟踪站数为2，每天升、降轨测控次数分别为2，最小测控间隔时间、最大测控间隔时间分别为1小时和8小时，每次测控最短持续时间为8分钟。两种进化策略下种群规模都为44，交叉概率为0.8，变异概率为0.1，终止条件为进化20代。初选集规模设为11，参考集规模设为6。局部提高算法的终止规则为搜索4次。

5.2 结果分析

从图3、图4和表3可以看出，无论对于需调度弧段数（编码长度）达256的场景1还是588的场景2，GASS的求解质量都要远远好于SGA。如果不在SGA的搜索过程中加入SS的搜索结果，则SGA的搜索效果很大程度上取决于初始种群的性能，在绝大多数情况下，其搜索到的最优解只能在初始最优解的基础上略有提高。相比而言，加入SS解后（SS算法在整个搜索过程中能获得的最优值分别为0.3和0.2857），GASS能在其基础上搜索到更好的解，从而使得算法搜索优良解的能力和求解稳定性得到进一步加强。

作为对比，两个场景及对应的任务需求使用卫星调度中经典的FIFO（First In First Out， FIFO）算法进行求解，该算法将所有可用可见弧段按起始时间升序排序后，依次将弧段分配给对应需求。效果如图所示。需要指出的是，测控任务加权满足率是一个面向全部任务需求的指标，场景1的20个任务需求使用FIFO算法调度的加权满足率是0，而场景2的35个任务需求使用FIFO调度的结果是0.1429，原因在于虽然场景2的前20个需求也都没有得到满足，但后面15个需求中有5个需求得到了满足。

由于SS算法本身在Refset更新过程中需要反复评估个体的目标值，会占用较多时间，且在SGA的每次迭代中都有SS进行，所以导致GASS整体时间开销较大，具体数据如表3所示。在一些大规模问题的求解中，可以通过适当控制SS的使用时机和次数来减小时间开销。

从算法运行情况来看，初始种群中个体适应度整体上比Refset中解的目标值要小，而SS在搜索过程中除搜索到的最优解可能发生变化外，Refset中个体的目标值整体变化不大，进化一定代数后，种群中的个体的适应度将与Refset中个体适应度接近，此时，Refset的作用更大地体现于为种群提供多样化的个体。

需要说明的是算法求得的测控任务加权满足率整体较低，原因在于模型的约束较强，尤其是最小最大测控间隔时间的要求，受地面测站位置的限制，卫星的实际可用时间窗口本身就无法满足其要求，因此，满足情况较差。如果所有需求没有此约束，则目标值可达92%。这说明现有测控资源的配置与卫星需求的满足之间还存在较大差距。

6 结 论

实验结果表明，本文提出的基于分散搜索的混合遗传算法在求解的质量上要优于简单的遗传算法和经典的启发式算法，但是，由于在每代进化中增加了分散搜索的工作，导致其计算时间要长于简单遗传算法。虽然本文仅在所建模型上对算法性能进行了试验，但从算法的设计理念可以看出，算法也具有普遍的适用性，尤其对多峰和欺骗性强的问题，具有相对优势，可作进一步研究。

参考文献

[1] 陈峰， 武小悦. 基于正交设计的多星测控调度协同进化代表个体选择[J]. 小型微型计算机系统， 2010，31（8）：1582-1586.

[2] BARBULESCU L，HOWE A E， WHITLEY L D. Understanding algorithm performance on an oversubscribed scheduling application[J]. Artificial Intelligence Research， 2006， 27（1）：577-615.

[3] BARBULESCU L. Scheduling space-ground communication for the air force satellite control network[J]. Journal of scheduling， 2004， 7（1）：7-34.

[4] 凌晓冬，武小悦. 一种求解多星测控调度问题的启发式算法[J]. 兵工自动化， 2008， 27（1）：71-73.

[5] PARISH S A. A genetic algorithm approach to automating satellite range scheduling[D].USA： Air Force Institute of Technology， 1994.

[6] BARBULESCU L，HOWE A，WATSON J P. Satellite range scheduling： A comparison of genetic， heuristic and local search[C]. Proceedings of the 7th International Conference on Parallel ProblemSolving From Nature. Berlin：Springer， 2002：611-620.

[7] Zhang Na， Feng Zuren， Feng Yuanjing. An optimization model for multisatellite resources scheduling[C]. Proceedings of the 6th World Congress on Intelligent Control and Automation. Dalian， China， 2006：7400-7404.

[8] 李敏强，寇纪淞. 遗传算法的模式欺骗性分析[J]. 中国科学（E辑），2002， 32（1）：95-102.

[9] NOORUL HAQ A，SARAVANAN M，VIVEKRAJ A R. A scatter search approach for general flowshop scheduling problem[J]. Int J Adv Manuf Technol， 2007， 31（7-8）：731-736.

[10]赵 强， 张鹏飞， 孙立镌. 利用分散搜索算法实现受时延约束的多播路由[J]. 软件， 2011，32（11）：13-16.

[11]NOWICHI E，SMUTNICHI C. Some aspects of scatter search in the flowshop problem[J]. European Journal of Operational Research， 2005， 169（2）：654-666.

[12]TONG Kena ， XU Kelin ， ZHENG Yongqian. Sequencing mixed-model flexible assembly lines with variable launching intervals[J]. Journal of Shanghai Jiaotong University（Science）， 2013， 18（4）： 460-467.

[13]AlvarezValdes R， CRESPO E， TAMARIT J M. A scatter search algorithm for project scheduling under partially renewable resources[J]. Journal of Heuristics 2006， 12（1-2）：95-113.

[14]GLOVER F. Heuristics for integer programming using surrogate constraints[J]. Decision Sciences， 1977， 8（1）：156-166.

[15]GLOVER F. A template for scatter search and path relinking， In Lecture Notes in Computer Science， Hao J K， Lutton E， and Ronald E， Editors. Berlin Springer， 1998：13-54.

[16]MARTI R. Scatter searchwellsprings and challenges[J]. European Journal of Operational Research， 2006， 169（2）：351-358.

[17]CAMPOS V， GLOVER F，LAGUNA M. An experimental evaluation of a scatter search for the linear ordering problem[J]. Journal of Global Optimization， 2001， 21（4）：397-414.

[18]MARTI R，LAGUNA M，GLOVER F. Principles of scatter search[J]. European Journal of Operational Research， 2006， 169（2）：359-372.

[19]BARBULESCU L，HOWE A E， WHITLEY L D. AFSCN scheduling： How the problem and solution have evolved[J]. Mathematical and Computer Modelling， 2006， 43（9-10）：1023-1037.

[20]SARAVANAN M，NOORUL HAQ A. Evaluation of scatter-search approach for scheduling optimization of flexible manufacturing systems[J]. Int J Adv Manuf Technol， 2008， 38（9-10）：978-986.