基于次梯度优化算法的航天测控调度

基于次梯度优化算法的航天测控调度

1航天测控调度0-1优化问题航空航天探测调度的问题是，在有限的观测设备的情况下，利用合理的模型和算法，管理和规划各种卫星的跟踪、跟踪、测量和跟踪需求，以充分反映卫星探测的需要。卫星探测的需求必须通过卫星探测天线和地面站测量装置在几何可见时间窗口中建立一条循环路径来完成。由于测量设备数量不足，无法充分满足越来越多的卫星探测需求。因此，测量部门需要组织航空测量，以尽可能多地满足卫星测量的需要。航天测控调度问题是NP完全问题,目前解决这种问题的常用方法是构造启发式算法,求解尽量接近最优解的可行解.作为实际应用问题,航天测控调度问题具有领域知识复杂,解空间庞大的特点,给该问题的建模和求解带来了一定的困难.很多文献如何评价上述启发式算法可行解的优劣及当前场景配置的合理性是一个值得研究的问题,对于极大化目标函数问题,一个有效的方法是通过计算目标函数上界,利用上界和下界(可行解目标函数值)的差来评价启发式算法可行解的次优性,利用上界和完全满足需求收益值的差来评价当前场景配置的合理性.拉格朗日松弛算法就是求解上界的一种有效方法,其基本思想是:使用拉格朗日乘子向量,将造成问题难于求解的复杂约束本文将构建航天测控调度0-1整数规划模型,该模型充分地利用了任务可用时间窗口与任务要求持续时间之间的冗余,考虑了更多的任务可能开始时刻.设计了拉格朗日松弛(LR)算法对该问题的上界进行求解,用综合优先度(TSP)算法和遗传算法(GA)分别获得该问题的一个可行解目标值,用来与所求上界进行比较.最后,通过仿真算例对模型和算法进行了验证.2任务响应面特征为准确地描述航天测控调度问题,需要确定问题的优化目标,分析问题的约束条件,建立航天测控调度0-1整数规划模型.调度场景包括卫星及其测控需求、测控设备以及卫星与设备间的几何可见时间窗口,为方便调度,将测控需求转换为测控任务,将几何可见时间窗口转换为任务可能开始时刻.文中卫星测控需求指抽象测控需求,简称“需求”,定义卫星及其需求集合为SAT={sat定义设备集合为RES={res用1分钟为单位对调度周期内的时间进行离散化,将一个周期(一天)分成T=1440个时刻,定义时刻集合为TIME={1,2,…,T}.定义式(1)是目标函数:最大化成功调度任务收益值;式(2)是任务约束:每个任务最多只能执行一次;式(3)是设备约束:每个设备某一时刻最多只能为一个任务服务.其中,G3按z次梯度优化算法如果将IP中的任务约束(2)和设备约束(3)去掉,问题则变为集合配置问题(Set-packingproblem),简称“SP”,已知SP可在多项式时间内求得最优解式(7)和式(8)中,当task可以证明,对SP(λ,μ)可以分解成S个子问题SP定义SP由于为此,需要按Z次梯度优化算法就是利用s(λStep1初始化:Step2对给定的(λStep3判断停止准则:若Step4根据(s(λ本文中,(λ,μ)的步长(θ(λ),Φ(μ))设置为:式(19)中,上标k代表第k次迭代,乘子(λ通过上述次梯度优化算法可以得到一个最接近Z4模拟计算示例4.1系统基本信息利用STK软件设计两个场景:场景1有3个设备8颗卫星,场景2有3个设备18颗卫星.设计了两种卫星测控需求,需求1为:收益值30、跟踪时间8分钟、升降轨任务数各3次、最小测控间隔时间为0.需求2为:收益值20、跟踪时间10分钟、升降轨任务数各2次、最小测控间隔时间为1.场景1和场景2的前一半卫星的测控需求设置为需求1,后一半卫星的测控需求设置为需求2.限于篇幅,本文只给出场景1的基本参数.设备和卫星基本参数见表1和表2,卫星对应的测控需求设置见表3,调度周期设为1天:2009-12-200:00:00至2009-12-210:00:00.为验证拉格朗日松弛算法得到的上界性能,用文献4.2tsp可行性解与最优目标函数值的比较本文得到了场景1和场景2的调度结果,其中TSP表示综合优先度算法、GA表示遗传算法、LR表示拉格朗日松弛方法;TSP和GA用来求解目标函数的下界,LR用来求解目标函数的上界.调度结果如表4所示.由表4可以看出,LR得到的目标函数上界可以评价可行解的优劣和场景配置的合理性.首先,场景1和场景2的TSP可行解目标函数值与上界分别相差15.000015和30.000087,说明TSP可行解目标函数值与最优目标函数值还有一定差距,还应进一步优化.场景1和场景2的GA可行解目标函数值与上界分别相差0.000015和5.000087,说明GA可行解目标函数值与最优目标函数值已非常接近,是个较优的可行解.同时也说明LR算法得到的上界与最优目标函数值非常接近,是性能较优的上界.从运算时间上来看,GA算法的运算时间要远远大于TSP算法的运算时间,说明GA算法得到较优可行解的同时,增大了时间开销.其次,可以