应用禁忌遗传算法的空间目标协同监视资源调度方法

庄海孝 潘腾 何宗波 李怀锋 贺冬雷

(北京空间飞行器总体设计部，北京 100094)

空间态势感知主要是指通过天地基空间态势感知手段、数据处理系统和地面支持系统等协同完成对在轨卫星、其他飞行器和空间碎片等空间目标的探测跟踪、观测识别，给出其空间分布、运行特征、行为动向、活动事件等信息，为空间系统在轨安全运行和空间资源有效利用提供重要的技术支撑[1]。空间动态感知不局限于跟踪空间碎片和发布撞击预警，对空间目标进行探测、跟踪、识别和编目，更为重要的是探测空间威胁，发布告警信息。

空间目标监视作为空间动态感知的支撑技术，近些年呈现快速发展态势。由于空间目标的高速运动、数量庞大、观测条件复杂等因素，对其有效监视一直是难点问题。为了提高监视精度、时效性，我国先后发展了各种监视手段，包括地基、天基等多种设备。但这些手段都存在一定的局限性[2]。地基系统可以不受体积和功率的限制，具有很高的观测精度。但是，部署位置受限，观测区域存在死角，还有天气条件、观测高度和观测时间等方面限制，导致对空间目标尤其是高轨空间目标监视能力受到制约。天基系统具有全天时、全天候、全天域的优势，可在地球大气层外的空间轨道上运行，不受空域的限制，能够对地基系统进行有效的补充和完善。目前，我国空间目标态势感知地基监视系统及天基系统的建设均是基于特定任务展开的，缺乏顶层设计，导致已有天地空间目标监视系统各自运行，难以发挥系统资源在联合观测、数据处理等方面的协同效应。为此，有必要发展天地一体空间目标监视系统，突破数据处理、自主任务规划等关键技术，实现天基、地基互补，以最大化利用已有资源高效完成各类复杂任务。本文通过对天基、地基资源统一建模，将地基资源按实际能力等效为天基资源，进而可将天基、地基资源一体化处理。调度决定着监视资源业务效能，面向空间目标监视的资源协同调度技术能用来解决天基、地基监视系统多个任务管理过程中的资源争用和任务冲突问题，优化天基、地基资源的综合使用效益。未来，全天时、全天候、全天域、广尺度、多手段的监视能力需求使天基、地基目标监视系统面临的任务日益精细化和复杂化[3]，这使得传统的单设备执行模式难以应对此类任务，亟需向自主化、协同化方向发展，即资源协同调度、自主决策、自主多星协同成为空间态势协同监视系统任务模式发展的新趋势。

本文讨论的天地一体空间目标协同监视资源调度问题，是保障天基、地基设备协同配合、高效运行，提高监视体系综合性能的关键。研究空间目标协同监视的天基、地基资源调度技术，对充分发挥天地监视资源的优势特点、有效调配资源，以及提升空间目标监视整体效能乃至空间动态感知能力具有参考价值。

1 空间目标协同监视资源调度方法

空间目标协同监视资源调度问题约束条件(资源约束和任务约束)比较复杂，监视任务包含点目标和区域目标，区域目标监视任务在资源调度前需要进行任务分解，因此在任务建模前要进行观测任务的预处理。任务预处理阶段主要分析用户任务需求，并对任务进行规范化处理及任务分解，在任务分解过程中处理任务约束，为建模过程准备数据。天基、地基空间目标协同监视资源调度问题的求解过程，可划分为如图1所示的任务预处理、建模、求解3个主要阶段。

图1 资源调度问题求解过程Fig.1 Problem-solving processes of resource scheduling

基于上述阶段划分，本文提出一种面向空间目标协同监视任务需求的资源调度方法，该方法具体实施步骤如图2所示，其中的约束满足优化问题模型构建、资源调度算法求解及仿真分析，是该方法的核心部分，同时也是本文讨论的重点内容。

图2 资源调度方法实施步骤Fig.2 Implementation steps of resource scheduling method

1.1 天地协同监视资源调度问题建模

综合考虑多星监视任务规划调度问题的特点，并结合工程实际，按约束的对象将协同监视资源调度问题的约束分为资源约束、时间约束、状态约束、关系约束4类。资源约束表示资源使用时应满足的约束关系。这里的资源并不仅指提供服务的监视资源，而是指调度过程中涉及到的所有对象，包括监视资源可用性约束、资源偏好约束、卫星对资源配置方式约束、应急监视约束、有效载荷工作能力约束、卫星存储容量约束、有效监视距离约束等。时间约束是指测控服务过程中需要满足的时间要求，也是多星测控调度问题中广泛存在的一种约束类型。状态约束主要是根据监视任务要求对资源状态提出的约束，仅当设备准备就绪才能进行监视，一个资源在任何时刻只能为一个任务提供服务。关系约束是指多个监视服务之间的相互要求对监视调度过程产生的影响，包括时间关系约束和逻辑关系约束。

天基、地基多设备协同监视资源调度问题，可通过系统分析联合监视中的各种约束和调度目标，对监视需求、调度目标、监视资源等基本要素进行抽象[4]，建立多目标优化的有色面向服务网结构(CSOP)模型。

1)总体功能分析及设计

总体功能分析及设计是指分析多设备协同监视建模任务需求，明确模型功能，确定适当的应用场景，主要包括3种模式。①排班模式：普通状态下的任务方案，基本需求是在最小能耗的前提下对目标进行尽量多的观测；②持续跟踪模式：发现重点观察对象后的任务方案，需求是在尽量小的能耗下实现对目标尽量长时间的累计观测；③应急模式：在突发情况下的方案，需求不计能耗地尽快捕获目标，并对目标进行尽量多的观测。

2)输入输出规范定义与描述

对输入输出规范进行定义与描述。其中：输入信息包括天基监视资源、地基监视资源、测控资源和数传接收资源；输出信息包括天基系统运行场景、观测任务规划甘特图、观测任务规划进化曲线、观测指向变化图。

3)目标函数分析与确定

如表1所示，根据排班模式、持续跟踪模式、应急模式需求，确立相应的优化目标，进而构建具体的目标函数。

表1 典型场景下的目标函数Table 1 Objective function in typical scenarios

在排班模式中，多个观测设备对大量的空间目标进行合作观测。可以选择的规划目标有观测目标数量最多、平均单目标观测次数最多、各星任务均衡3类。相应的目标函数分别为

max∑xi

(1)

max∑(xi·Ti)/∑xi

(2)

minD(xi·Ti)

(3)

式中：xi由观测目标i是否被选择观测确定，若被选择，xi=1，否则xi=0，i∈I，I为观测目标集合；Ti为目标i被观测的次数；D(·)为方差运算。

在持续跟踪模式中，多个观测设备对于重点目标进行接力持续观测。可以选择的规划目标有目标累计观测时长最长、观测条件最佳、各星任务均衡3类。前面2类相应的目标函数分别见式(4)和式(5)，第3类的目标函数同式(3)。

max∑r(∑kdr,k)

(4)

max∑r(∑kfr,k)

(5)

式中：dr，k为观测设备r执行第k个观测任务的持续时间，r∈R,k∈Or，R为观测主体集合，Or为观测主体r的观测任务集合；fr，k为观测设备r执行第k个观测任务的收益值。

在应急模式下，多个观测设备需要进行快速响应，协同完成对目标群的快速捕获。可以选择的规划目标有全部目标最快捕获、平均单目标观测次数最多2种类型，相应的目标函数分别为

min∑i(minn(si，n))

(6)

max∑(xi·Ti)/∑xi

(7)

式中：si，n为观测目标i在进行观测任务Oi，n时的初始时间，n∈Oi，Oi为观测目标i的观测任务集合。

4)天地协同监视任务资源调度CSOP模型

目标函数模型包括最大化观测数量、平均单目标观测次数最多、卫星电量消耗最小、各星任务方差最小。

最大化观测数量为

Q1=max(∑Vixi)

(8)

式中：Vi为观测目标i的观测次数。

平均单目标观测次数最多为

Q2=max(∑Vixi-∑eixi)

(9)

式中：ei为观测目标i的观测任务代价。

卫星电量消耗最小为

Q3=min(∑Vixiyi+∑Vixizi)

(10)

式中：yi为观测目标i的观测安排是否与原有任务相同，若相同，yi=1，若不同，yi=β，β∈(0,1)；zi为观测目标i是否为突发目标，若是突发目标，zi=1，否则，zi=0。

各卫星任务方差最小为

Q4=min((∑(Vixi-u)2)/N)

(11)

式中：u为目标的平均观测次数；N为可用的卫星及地面站总数。

1.2 天地协同监视资源调度算法设计

在多资源监视调度问题中，场景和监视需求是问题的输入，在考虑各种约束的情况下尽可能地满足监视需求是资源调度的目的，同时需要考虑优先保证高优先级任务需求得到服务的原则。依据需求的等级和紧迫性，可以选择不同的求解方法[5]，在时间要求比较高、调度精度要求不高的情况下，可以采用面向需求的启发式算法快速生成可用的调度方案；在时间充足且对调度精度要求较高时，可利用遗传算法。在为数众多的进化算法中，遗传算法是寻求组合优化问题满意解的最佳工具之一，已有研究将遗传算法应用于求解观测资源调度相关问题[6]。遗传算法具有并行搜索、搜索效率较高的优点，但也存在局部搜索能力较弱、容易早熟等缺点。

天地协同监视资源调度问题作为一个带有时间窗约束的复杂组合优化问题，决策变量数量多，与之相应的解空间也自然巨大，相比之下，遗传算法能够获取质量更高的解，但是遗传算法是一种随机性的搜索算法，需要逐步在整个解空间中搜索，因此算法时间开销会较大。根据上述分析，本文综合考虑卫星资源、地基资源、任务需求等因素，将禁忌搜索与遗传算法相结合，提出基于禁忌遗传算法的协同监视资源调度优化求解方法[7]，探索以较小的时间开销求解天地多资源联合监视任务规划问题。禁忌遗传算法基本思想是：利用遗传算法的进化功能使得搜索迅速集中在较优解周围，然后利用禁忌搜索方法在小范围内进一步搜索最优解。结合遗传算法思想和禁忌搜索方法的优点[8]，能有效地利用全局信息及搜索过程中获得的信息，在邻域中重复搜索[9]，快速地向最优解的方向移动，从而有效地克服局部最优，达到提高求解效果和搜索效率的目的[10]。具体实现过程如图3所示，主要分为以下3个阶段。

图3 禁忌遗传算法实现过程Fig.3 Implementation process of tabu genetic algorithm

(1)初步优化。输入原始数据及所需参数，形成初始化的种群，设置种群迭代次数N的初始值为1，计算得到适应值并进行初步优化。

(2)禁忌处理。基于精英选择法进行选择，基于禁忌搜索进行交叉、变异，并更新禁忌表。

(3)终止判断。判断是否满足禁忌算法终止条件。若满足，则跳出禁忌优化，并进行遗传优化操作；若不满足，则继续进行禁忌操作，直至找到生存概率最大的染色体。

2 仿真验证

2.1 系统功能验证

依据前述协同监视资源调度算法，采用模块化思想，以3颗卫星(Sat1，Sat2，Sat3)、5个地面站、200个目标为典型约束条件，开展仿真验证。为了减小偶然性影响，在进行求解时，每种应用模式进行多次计算，并优化目标平均值和最优解次数，优化结果如表2所示。可以看出：在给定的资源条件和目标数量要求下，基于本文所介绍资源调度方法的系统可有效支持对广域探测、持续跟踪、应急响应及自定义4种任务模式的资源调度优化，任务方案优化时间在6.6 min以内。

表2 目标函数求解优化结果Table 2 Optimization results for objective function

图4给出了某监视任务资源调度的初步优化方案，根据优化方案实施天基、地基资源调配计划，可快速响应任务需求。图4(a)是根据优化方案生成的协同监视任务甘特图，纵坐标是可被调度的天基、地基监视资源，横坐标是监视任务周期。图4(b)是被调度的天基监视资源在监视任务周期内不同时刻相应的在轨姿态角度，横坐标是执行监视任务的具体时刻。图4(c)反映了在监视任务周期内不同时段的天基卫星被调用情况，横坐标同样是是执行监视任务的具体时刻。

图4 资源调度初步方案Fig.4 Preliminary scheme of resource scheduling

2.2 效能分析

为检验本文方法的效能，以天地联合监视任务为应用背景，以获得最大任务收益为目标函数，进行分析。目标函数累计收益最大为式(5)，以卫星、地面站联合监视任务规划为背景，进行观测任务调度仿真计算。应用禁忌遗传算法基于目标函数进行优化求解。为了减小偶然性影响，在进行求解时，独立运行30次，记录其找到的解、找到最优解的次数、找到最优解的轮数及平均运行时间，结果统计如表3所示。 从表3结果可以看出：在复合型优化目标函数下，本文方法优化收敛速度可以满足实际需求，并且具有更强的发现最优解的能力。该方法在寻优质量和寻优速度上表现优越，且对复杂的目标函数适应良好。

表3 计算结果Table 3 Calculation results

进一步验证卫星调度能力和监视跟踪目标容量。基于卫星参数，分别管控3,5,10，20颗卫星，依次进行广域探测模式、持续跟踪模式、应急模式和自定义模式下的仿真测试，并记录仿真时长，见表4。由表4可知，可支持管控20颗卫星。基于目标参数，导入100,200,300,500，1000个目标，分别进行广域探测模式、持续跟踪模式、应急模式和自定义模式下的仿真测试，并记录仿真时长，见表5。由表5可知，监视跟踪目标容量不少于1000个。仿真结果表明，本文方法在目标监视容量、资源管控数量及任务优化时效性方面均具有明显优势。

表4 管控卫星数量测试Table 4 Test of satellite number in management and control

表5 监视跟踪目标容量测试Table 5 Volume test for detecting and tracking space objects

3 结束语

本文系统分析了空间目标协同监视资源调度方法的需求背景、当前问题及应对措施，面向实际任务需求提出了应用禁忌遗传算法的天基、地基协同监视资源调度方法。以任务收益作为具体的衡量值，证实了基于禁忌遗传算法的资源调度方法在调度优化求解速度、算法收敛速度、求解精度等方面的明显优势，对于解决空间目标监视本身的复杂性，以及天基、地基手段多样差异性等问题，更好地发挥天基、地基监视手段各自的优势，提升空间目标监视能力和空间动态感知整体效能具有参考价值。