资源描述：
《基于拉格朗日松弛与最大分支算法的卫星成像调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第29卷第2期宇航学报Vol.29No.22008年3月JournalofAstronauticsMarch2008基于拉格朗日松弛与最大分支算法的卫星成像调度算法靳肖闪,李军,刘湘辉,郭玉华,景宁(国防科技大学电子科学与工程学院,长沙410073)摘要:成像调度算法是卫星成像规划中的关键部分之一。建立了卫星成像调度问题的0-1整数规划模型,该问题具有NP完全特性。提出了一种基于拉格朗日松弛与最大分支算法的多项式时间复杂度的优化算法。该算法可以计算出接近最优解的上界及可行解,并给出可行解的优化度。基于该算法提出了一种先验可行解条件下改进上界及可行解的
2、二次优化算法。实验结果表明,该算法在时间性、优化度等方面取得满意的结果。关键词:卫星成像调度;0-1整数规划;拉格朗日松弛;次梯度优化;最大分支算法中图分类号:TP391文献标识码:A文章编号:1000-1328(2008)02-0694-06时,由于现有的卫星成像调度技术仍主要采取/离0引言线0方式,即在地面生成优化调度方案,转化为卫星成像卫星是利用所携带的光学成像仪、合成孔载荷控制指令后,上行注入星上控制系统,控制卫星径雷达或高光谱成像仪等拍摄地面一定范围内的物完成指定任务,这对成像调度算法的性能提出了更体来产生图像的卫星,一般都具有一定的侧视成
3、像高的要求。能力,可对星下点轨迹两侧超过成像幅宽的区域内目前国内外已有不少关于卫星成像调度问题的[1]的目标成像。但除非侧视角相同,否则卫星对一个研究。Gabrel等把卫星成像调度问题归结为带权目标成像后,需要一定的动作时间改变侧视角度,以值无圈有向图,提出了一种带标记的最优路径算法;[2]对下一个目标成像。如图1示,欲安排卫星对目标但该算法只能处理二元约束。Vasquez等把卫星A、B、C、D成像,由于侧视动作时间限制,成像路径成像调度问题归结为背包问题,并采用禁忌搜索算只能选择/AyC0或/AyByD0之一。对于数字传法求解;该算法在二元及三元约
4、束空间中搜索邻域,输型成像卫星,成像后的图像存储在星载存储器上,并对存储器约束进行松弛,以求得可行解;但是该算规划的卫星成像任务不能超过存储器容量的限制。法仅适用于只有一个多元(>3)约束的情况。[3]Vasquez等在去掉整数性限制,对卫星成像调度背包问题进行松弛后,用单纯形方法计算目标函数的上界;但是获得的上界比较差,并且这种方法不能直[4]接求解出原问题的最优解。LinWC等针对卫星成像调度问题,建立了整数规划模型,用拉格朗日松弛方法将原问题分解为多个子问题,并基于贪婪思想及线性搜索技术求解,其结果略优于文献[2],但[8]图1卫星成像示意图该
5、文缺少对其产生解的近似程度的分析。王钧等Fig.1Illustratingofsatelliteimaging采用遗传算法解决多目标的多卫星成像调度问题,其结果优于贪婪算法,但缺乏对产生解的评价机制。卫星成像调度问题就是在满足各类成像约束本文从整数规划角度建立了成像调度问题的数下,尽可能多的安排成像任务,是约束优化问题。同学模型,基于拉格朗日松弛方法给出了成像调度问收稿日期:2007-03-28;修回日期:2007-06-23基金项目:国家自然科学基金(60604035);国家863重点项目(2007AA120202);国家863高技术研究发展项目(
6、2007AA12Z229)第2期靳肖闪等:基于拉格朗日松弛与最大分支算法的卫星成像调度算法695题的求解算法。算法具有多项式时间复杂度,并可1.2卫星成像调度的0-1整数规划模型给出比较/紧致0的上下界。二次优化算法提高了优根据前文,卫星成像调度问题可以建模为:N化的结果。ZIP=max6Xixi本文第1节建立了0-1整数规划模型。第2i=1节给出了卫星成像调度问题可行解及上界的求解方xi+xj[1,PIFN法。第3节给出了求解调度问题的单次优化及二次6Nixi[F优化算法。第4节是相关实验及结果分析。最后是i=1s.t.(1-1)结论与展
7、望。N6xi[Gi=11卫星成像调度问题的数学模型NxI{0,1}1.1卫星成像调度问题的数学描述NN为了建立卫星成像调度问题的数学模型,首先max6Xixi为待优化的目标函数,xI{0,1}i=1给出以下几个形式化描述:为整数性约束,xi+xj[1,PIF为二NNN:待成像目标总数;s:待成像目标集合,s={s元约束,6Nixi[F与6xi[G为多元约束。1,s2,,,sN};i=1i=1+Xi:待成像目标si的权重,XiIZ;式(1-1)的可行解域为:Nti:卫星对目标si成像的起始时刻;DIP={x
8、6Nixi[F;i=1Ti:卫星对
9、目标si成像的时长;NTij:卫星对si和sj成像所需侧视动作时间;6xi[G;xi+xj[1,i=1Ni:
