基于改进遗传算法的星地任务优化调度研究

马冬青，王蔚

1.华北计算技术研究所，北京 100083

2.太极计算机股份有限公司，北京 100083

基于改进遗传算法的星地任务优化调度研究

马冬青1，王蔚2

1.华北计算技术研究所，北京 100083

2.太极计算机股份有限公司，北京 100083

星地任务优化调度是利用特定的星地资源合理地安排星地任务。由于星地任务众多而资源有限，而且星地任务受星地可见性以及多方面约束，星地任务调度问题十分复杂。针对星地任务的特点，建立了星地任务调度问题模型，提出了基于改进遗传算法的星地任务优化调度算法。算法采用按适应度排名轮盘赌选择、顺序交叉、随机对换变异的算法要素。针对遗传算法局部搜索能力弱的特点，提出了利用爬山算法优化新一代个体的方法，以增强遗传算法的局部搜索能力，给出了基于改进遗传算法的星地任务调度算法。

星地任务调度；遗传算法；爬山算法

1 引言

星地任务指在星地系统中由卫星与地面设备共同完成的任务。星地系统由空间部分和地面部分组成，空间部分由多颗卫星组成星座，地面部分由分布在不同位置的多个地面站组成。为了实现星地系统的特定功能，地面设备与星上的有效载荷设备需要协调配合完成指定任务。在星地系统中，星地任务的执行受多种约束的影响。首先是星地可见约束。星地系统中卫星按照各自的轨道运行，它们经过各地面站的时间不同，执行星地任务需要满足星地可见条件。另外卫星和地面设备具有一定的能力，星地任务需要符合各设备的限制，如天线的仰角限制等。在由多颗卫星多个地面站组成的星地系统中，星地任务存在任务冲突及资源冲突。星地任务优化调度目标是合理安排资源与任务执行时间，从而在多种约束条件下完成系统业务，并使任务调度性能取得优化。星地任务调度问题十分复杂，不仅包含任务和资源约束等通常的约束条件还包含时间窗约束，可归类为有约束的组合优化问题。

国内外对卫星相关调度问题开展了许多研究，从20世纪90年代美国空军技术学院、美国国家航空和宇宙航行局、欧空局、印度空间研究机构等组织就展开对卫星侦察、数传和测控等调度问题的研究，并取得了一系列成果。例如，Gooley采用混合整数规划算法解决美国空军卫星控制网的低、中高轨卫星调度问题[1]。Parish提出了采用遗传算法解决多星测控调度问题的方法[2]。目前国内在建模方面对多种卫星调度问题模型进行细分，融入多种约束，针对各种不同限制及优化目标的卫星任务调度问题提出了多种解决方法。

本文针对星地任务的特点，建立了星地任务调度问题模型，并提出了基于改进遗传算法的星地任务优化调度算法。

2 星地任务调度模型分析

星地任务调度问题是有约束的任务资源优化调度问题。调度研究的问题是将有限的资源分配给在一定时间内的不同任务。它是一个决策过程，其目的是优化一个或多个目标。调度问题可以用活动、资源、调度目标三要素来描述。活动指需要调度的任务和活动，完成活动需要一定的资源，并且持续一定时间。资源指完成活动所需的人力和资源。每个资源都有特定的能力。在任何时间，活动对资源的需求都必须满足资源能力的限制。调度目标指在满足时间和约束的条件下，为每个活动确定执行时间并分配资源，以使得调度问题的目标函数值最优。

星地任务调度是安排有限的星地资源协调完成系统的任务，以达到调度性能的最优。本文研究的星地任务调度问题，同样可以用活动、资源、调度目标三要素来描述。

（1）活动

活动指地面站设备与卫星协调执行的系统任务。活动需要持续一定的时间，要求持续时间大于指定的最少执行时间。活动根据重要性和时效性要求等，设置不同的优先级。

（2）资源

资源指完成星地任务所需的卫星有效载荷和各地面站的设备等。地面站分布在不同地理位置，位置固定，各站配备一定数量的设备用于执行星地任务。卫星与各地面站之间的可见时间由卫星的轨道决定。卫星配备一定的有效载荷。

（3）调度目标

在星地任务调度问题中，一般来讲，优化目标可以细化为多种优化目标，如：任务执行有效时间最长；任务安排的成功率最高；设备使用均衡等。在本文研究的星地任务调度问题中，调度目标是任务执行有效时间最长。

依据上述目标建立的数学模型是：其中，sj表示卫星j，dk表示设备k，t(sj，dk，i)表示星j设备k执行任务i的时间长度；ts表示开始时间，te表示结束时间，A(sj，dk)表示星j与设备k的可见时间窗口的集合。

在上述模型中，各式的含义是：

式（1）是目标函数，要求任务执行有效时间最长。

式（2）是卫星资源，各卫星有各自的轨道参数。

式（3）是地面设备，地面设备有一定的能力限制，各设备位于地理分布不同的地面站。

式（4）是任务执行时间的计算公式。

式（5）是星地约束，表示任务需安排在设备对卫星的可见时间窗口。

3 基于改进遗传算法的星地任务调度算法

遗传算法是受生物进化思想启发而得到的一种全局优化算法，是一种通过模拟自然进化过程来搜索最优解的方法。遗传算法是由美国的Holland教授于1975年提出的。遗传算法首先构造出初始种群，然后按一定的规则进行逐步迭代以产生新的个体，按照适者生存和优胜劣汰的原理，逐代演化生成越来越好的近似解。在每一代，根据个体适应度来选择个体，并借助于遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程模拟了自然进化，使后代种群比前代具备更优的适应性。通过多次迭代，最后生成的种群中的最优个体，就可作为问题的满意解。

本文参照多路旅行商问题的遗传算法，构建星地任务调度的基本框架，分析比较影响遗传算法性能的各方面因素，经过多种尝试，设计了采用按适应度排名轮盘赌选择、顺序交叉、随机对换变异的算法要素，并针对遗传算法局部搜索能力弱的特点，提出了利用爬山算法优化新一代个体的方法，以增强遗传算法的局部搜索能力，最终给出了基于改进遗传算法的星地任务调度算法。

3.1 个体染色体

采用遗传算法解决问题时，首先要规定一种编码方法，使得调度问题的任何一个潜在可行解都能表示成为一个数字染色体。在本文中，个体染色体用来表示星地任务的调度序列。在改进遗传算法的星地任务调度中，采用任务与任务分隔符联合编排的染色体编码方式，将可行的潜在解表示为1至T+K-1（T是任务数，K是资源数）的不重复的自然数编码。在这种编码中，1至T表示各星地任务，T+1至T+K-1表示各任务分割符。这种自然数编码表示的星地任务的调度序列中，利用T-1个任务分隔符，可以将任务划分为K组，每组中的任务由一个资源来完成。由于星地任务与卫星绑定，资源可转化为地面设备资源。在编码序列中，第一个资源的任务是从编码头开始，逐一按编码顺序安排，遇到任务分隔符时结束，接下来由第二个资源按编码继续执行后续任务，以此类推。

个体染色体编码通过解码过程转化为实际的调度方案。由于染色体编码序列中的各项任务必须满足星地可见约束及任务资源约束，因此解码过程对资源与任务、资源与资源、任务与任务之间的冲突进行化解，将个体染色体编码转化为满足各类约束条件的调度方案。

3.2 种群

种群由一定数量的个体组成。在本文中，种群中的每个个体都代表一个星地任务调度序列，种群中包含多个调度序列。这些调度序列经过遗传操作逐代演化，生成越来越好的调度序列。种群的大小指种群中的个体数目。种群的大小对算法的性能有一定的影响。种群较大时，更容易找到全局最优解，但是每次迭代的时间也有所增加。本算法采用固定大小种群，即在算法的逐步迭代中，种群大小不变。

初始种群的产生采用随机法。由于初始种群的优劣直接影响算法的性能，因而构造初始种群时首先保证种群中个体的可行性。本算法随机产生调度序列，根据星地任务检查调度序列中是否包含各任务且每个任务只包含一次，如果是则将该调度序列作为初始种群的个体，如果不是则重新产生调度序列。这种随机产生可行个体的操作不断重复，直到种群中包含指定数目的个体。

在种群的世代繁衍中，新种群由父代的个体经过选择、交叉、变异等遗传操作产生。在本算法的逐次迭代中，新种群的确定采用保留最优个体、引入新个体的方法。通过保留最优个体，可以避免遗传操作的随机性破坏掉已有的最优个体。引入遗传操作产生的新个体，可以不断获得适应度改进的可能性。

3.3 适应度

在遗传算法中，个体的优劣由适应度来决定。在本文研究的星地任务调度问题中，采用任务执行有效时间（目标函数值）作为调度序列的适应度，用于评判个体的优劣，任务执行有效时间长的调度序列优于任务执行有效时间短的调度序列。对应于调度序列的每个个体的适应度就是调度序列解码后的调度方案中，实际安排的各项任务的持续时间之和，如式（6）所示。

在选择及评价个体时，均用到适应度的计算。

3.4 选择操作

选择操作是从种群中选出优良个体的操作。在本文中，选择操作用于从种群的多个调度序列中选出优良的调度序列。本算法采用按适应度排名的轮盘赌选择方法。在种群中，每个个体具有各自的选择概率，这个概率取决于种群中个体的适应度及分布。选择概率的确定一般有两种方法：一种方法是按适应度比例确定选择概率；另一种方法是按适应度排名确定选择概率。

按适应度比例确定选择概率时，可以保证优势个体具有更高的选择概率，但有一些缺点。当种群中出现超常优势个体时，种群的选择压力大，若采用按比例选择法，则这些超常优势个体有可能由于竞争力过强而控制选择，影响全局优化能力。当种群中个体差异较小时，种群的选择压力小，有可能造成继续优化潜能的降低，可能获得某个局部的最优解。

按适应度排名确定选择概率时，任务执行有效时间最长的调度序列排在最前，即排名靠前的个体具有更高的选择概率。按适应度排名的选择方法比按适应度比例的选择方法具有更好的鲁棒性。在按适应度排名的选择中，种群的个体按目标函数值排序，选择概率仅取决于个体在种群种中序位，而不是实际的目标值。这种方法引入了种群均匀尺度，有效地控制了种群的选择压力，避免了由于选择压力过大或过小时出现的过早收敛或停滞现象。

按排名确定选择个体选择概率的方法见式（7）。

其中，i为个体排名。

本算法中采用按适应度排名的轮盘赌选择策略。具体步骤是：

（1）根据适应度对个体进行排序，适应度最好的排在最先。

（2）根据种群大小，计算各排名的选择概率和累积概率。

（3）产生0～1之间的随机数，采用轮盘赌的方式，确定选出的个体。

累积概率见式（8）和式（9）。

其中，POPSIZE表示种群大小，i表示排名。PSi表示排名为i的个体的选择概率。PsumSi表示排名为i的个体的累积概率。

轮盘赌的选择方式是随机产生0～1之间的随机数，模拟轮盘旋转，将随机数与个体的累积概率比较。用i来表示某个体的排名，当随机数大于排名i的累积概率且小于排名i+1的累积概率时，排名为i的个体被选中。

3.5 交叉操作

交叉操作也称基因重组，是结合来自父代交配种群中的信息产生新个体的操作。交叉操作将选定个体按一定的交叉概率把两个父代个体染色体的部分结构加以替换重组，生成新个体。在本文中，交叉操作对选定的两个调度序列中的部分任务序列进行替换重组，生成新的调度序列。交叉是遗传算法获取新的优良个体的最重要的手段。交叉操作有多种形式，包括单点交叉、部分交叉（PMX）、顺序交叉（OX）、循环交叉（CX）等。

在本文的改进遗传算法中采用顺序交叉操作。1985年，Davis等人针对TSP问题提出了基于路径表示的顺序交叉法。两个父代染色体进行顺序交叉操作时有两个关键点，一是子代染色体保存其中一个父代染色体的一部分，二是保存另一父代染色体基因编码中的相对顺序。这种顺序交叉法避免了染色体中出现重复基因编码的情况。本文参照该方法设计了算法的交叉操作。

交叉操作的具体步骤是：

（1）随机生成编码范围内的两个随机数，将两个随机数之间的部分作为匹配区域。

（2）生成子代个体1。方法是用父代个体1中匹配区域内的基因编码，复制到子代个体1的相应区域；其余部分从匹配区域后由父代个体2中的基因顺序补充，补充过程中，剔除掉子代个体中已经拥有的基因编码。

（3）采用类似方法，构造子代个体2。

交叉概率决定交叉操作的频率，概率越高，可以越快地收敛到最有希望的最优解区域，因此一般选择较大的交叉概率。但交叉概率太高会导致过早收敛。本算法中缺省将交叉概率设置为0.8。

3.6 变异操作

变异操作是按一定的概率对个体染色体进行改变的操作。变异使遗传算法保持种群的多样性，防止出现未成熟收敛。交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化。在本文中，变异操作对交叉后生成的调度序列进行微调，提高种群中调度序列的多样性。

变异操作具体步骤是：

（1）随机抽取染色体中的两个基因位置。

（2）将这两个位置的基因进行对换，形成新的个体。

在变异操作中，变异概率一般取较小值。当变异概率过大时，遗传算法就规划为随机搜索，这样就破坏了遗传算法的重要数学特性和搜索能力。本算法缺省将变异概率设置为0.1。

3.7 爬山操作

遗传算法是一种全局优化算法，但是局部搜索能力较弱。针对遗传算法局部搜索能力弱的特点，本文在遗传算法中增加爬山操作，采用爬山算法优化新一代个体的方法，以增强遗传算法的局部搜索能力，提高遗传算法的运行效率和求解质量。

本算法对经过选择、交叉、变异操作后产生的新一代个体逐个进行爬山操作，利用爬山算法局部搜索力强的特点，提高新一代个体的适应度。爬山操作采用逆序法构造新个体作为候选个体，并进行适应度计算，如果候选个体优于原个体则接受候选个体，否则拒绝候选个体。

4 实验验证

为验证本算法的调度能力，本文采用模拟生成的实验样本进行解算。在实验样本中，星座部分包括9颗卫星，参数见表1，地面部分由分布在不同位置的3个地面站组成，参数见表2，每个地面站有3个设备用于执行星地任务，设备的设置时间为5 min，设备的工作仰角为10°至90°。星地任务调度时间范围为2012年3月20日12时至2012年3月22日12时，根据卫星与地面站的可见关系生成91个任务。每个任务最少执行时间为10 min，各任务优先级相同。

表1 实验样本卫星参数

表2 实验样本地面站参数

实验中遗传算法和改进遗传算法各运行20次，计算平均值。实验中设置遗传算法的种群规模为20，交叉概率为0.8，变异概率为0.1，迭代次数为100。本文另外选用先到先服务算法FCFS，没有引入爬山操作的遗传算法和动态规划法对实验样本进行计算。实验的结果如表3所示。

表3 实验结果

从数据中可以看出，在改进遗传算法生成的优化调度方案中，任务执行有效时间为710 801 s，任务调度率达到90.4%，计算结果明显优于FCFS算法和遗传算法。在计算时间上，遗传算法和改进遗传算法由于处理的复杂性，使得计算较为耗时，但计算时间属于实际应用可接受的范围内。采用动态规划法解决实验样本问题时，经6 h的计算没有生成最优化调度序列。实验证明动态规划法不适用于解决较大规模的星地任务规划问题。

5 结束语

通过分析和实验验证，得出如下结论：

本文的改进遗传算法可以有效解决星地任务优化调度问题。算法通过对星地任务调度序列的编码和解码，将任务的执行安排在星地可见的范围内，并且化解了资源以及任务之间的冲突。在资源有限的情况下，通过统筹安排，协调了众多星地任务的执行，使星地任务的调度得到优化。采用爬山增强的遗传算法生成的调度方案优于FCFS算法和没有爬山操作的遗传算法。

采用爬山增强的遗传算法优于改进前的遗传算法，通过引入爬山操作增强遗传算法的局部搜索能力，是算法改进的一项有效途径。

[1]Gooley T D.Automating the satellite range scheduling process[D].Ohio：Air Force Institute of Technology，1993.

[2]Parish S A.A genetic algorithm approach to automating satellite range scheduling[D].Ohio：Air Force Institute of Technology，1994.

[3]Pinedo M.调度：原理、算法和系统[M].张智海，译.2版.北京：清华大学出版社，2007.

[4]王小平，曹立明.遗传算法——理论、应用与软件实现[M].西安：西安交通大学出版社，2002：7-9.

[5]玄光南，程润伟.遗传算法与工程优化[M].北京：清华大学出版社，2004.

[6]Laporte G.Fifty years of vehicle routing[J].Transportation Science，2009，43（4）.

[7]Bodin B G.Planning for truck fleet size in the presence of a common-carrier option[J].Decision Sci，1983，14：103-120.

[8]Frank J.Planning and scheduling for fleets of earth observing satellites[C]//Proceedings of the Sixth International Symposium on Artificial Intelligence，Robotics，Automation and Space，2001.

MA Dongqing1,WANG Wei2

1.North China Institute of Computing Technology,Beijing 100083,China
2.TAIJI Computer Corporation Limited,Beijing 100083,China

The scheduling of satellite-ground cooperating missions is to arrange the missions scientifically,which uses the limited satellites and ground resources to fulfill.The scheduling is complex not only because of the access conditions between satellites and ground stations,but also because of the conflict between the large numbers of tasks and the limited resources.In this paper,a mathematical model of the satellite-ground cooperating scheduling problem is established considering the features of the missions.And an improved genetic algorithm is presented to solve the scheduling problem. The algorithm includes rank-based fitness assignment and roulette wheel selection,ordered crossover,and random change mutation.By using hill-climbing methods,the local searching ability of the genetic algorithm is improved.

satellite-ground cooperating scheduling;genetic algorithm;hill-climbing method

A

TP39

10.3778/j.issn.1002-8331.1204-0645

MA Dongqing,WANG Wei.Research on scheduling of satellite-ground cooperating missions based on improved genetic algorithm.Computer Engineering and Applications,2014,50（6）：246-249.

马冬青（1972—），女，高工，研究领域为航天测控软件，卫星应用；王蔚（1973—），男，工程师，研究领域为工程优化。E-mail：ma_dq@yahoo.com.cn

2012-05-04

2012-06-19

1002-8331（2014）06-0246-04