基于拉格朗日松弛與最大分支算法的衛(wèi)星成像調(diào)度算法

《基于拉格朗日松弛與最大分支算法的衛(wèi)星成像調(diào)度算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第29卷第2期宇航學(xué)報(bào)Vol.29No.22008年3月JournalofAstronauticsMarch2008基于拉格朗日松弛與最大分支算法的衛(wèi)星成像調(diào)度算法靳肖閃,李軍,劉湘輝,郭玉華,景寧(國防科技大學(xué)電子科學(xué)與工程學(xué)院,長(zhǎng)沙410073)摘要:成像調(diào)度算法是衛(wèi)星成像規(guī)劃中的關(guān)鍵部分之一。建立了衛(wèi)星成像調(diào)度問題的0-1整數(shù)規(guī)劃模型,該問題具有NP完全特性。提出了一種基于拉格朗日松弛與最大分支算法的多項(xiàng)式時(shí)間復(fù)雜度的優(yōu)化算法。該算法可以計(jì)算出接近最優(yōu)解的上界及可行解,并給出可行解的優(yōu)化度。基于該算法提出了一種先驗(yàn)可行解條件下改進(jìn)上界及可行解的

2、二次優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明,該算法在時(shí)間性、優(yōu)化度等方面取得滿意的結(jié)果。關(guān)鍵詞:衛(wèi)星成像調(diào)度;0-1整數(shù)規(guī)劃;拉格朗日松弛;次梯度優(yōu)化;最大分支算法中圖分類號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1000-1328(2008)02-0694-06時(shí),由于現(xiàn)有的衛(wèi)星成像調(diào)度技術(shù)仍主要采取/離0引言線0方式,即在地面生成優(yōu)化調(diào)度方案,轉(zhuǎn)化為衛(wèi)星成像衛(wèi)星是利用所攜帶的光學(xué)成像儀、合成孔載荷控制指令后,上行注入星上控制系統(tǒng),控制衛(wèi)星徑雷達(dá)或高光譜成像儀等拍攝地面一定范圍內(nèi)的物完成指定任務(wù),這對(duì)成像調(diào)度算法的性能提出了更體來產(chǎn)生圖像的衛(wèi)星,一般都具有一定的側(cè)視成

3、像高的要求。能力,可對(duì)星下點(diǎn)軌跡兩側(cè)超過成像幅寬的區(qū)域內(nèi)目前國內(nèi)外已有不少關(guān)于衛(wèi)星成像調(diào)度問題的[1]的目標(biāo)成像。但除非側(cè)視角相同,否則衛(wèi)星對(duì)一個(gè)研究。Gabrel等把衛(wèi)星成像調(diào)度問題歸結(jié)為帶權(quán)目標(biāo)成像后,需要一定的動(dòng)作時(shí)間改變側(cè)視角度,以值無圈有向圖,提出了一種帶標(biāo)記的最優(yōu)路徑算法;[2]對(duì)下一個(gè)目標(biāo)成像。如圖1示,欲安排衛(wèi)星對(duì)目標(biāo)但該算法只能處理二元約束。Vasquez等把衛(wèi)星A、B、C、D成像,由于側(cè)視動(dòng)作時(shí)間限制,成像路徑成像調(diào)度問題歸結(jié)為背包問題,并采用禁忌搜索算只能選擇/AyC0或/AyByD0之一。對(duì)于數(shù)字傳法求解;該算法在二元及三元約

4、束空間中搜索鄰域,輸型成像衛(wèi)星,成像后的圖像存儲(chǔ)在星載存儲(chǔ)器上,并對(duì)存儲(chǔ)器約束進(jìn)行松弛,以求得可行解;但是該算規(guī)劃的衛(wèi)星成像任務(wù)不能超過存儲(chǔ)器容量的限制。法僅適用于只有一個(gè)多元(>3)約束的情況。[3]Vasquez等在去掉整數(shù)性限制,對(duì)衛(wèi)星成像調(diào)度背包問題進(jìn)行松弛后,用單純形方法計(jì)算目標(biāo)函數(shù)的上界;但是獲得的上界比較差,并且這種方法不能直[4]接求解出原問題的最優(yōu)解。LinWC等針對(duì)衛(wèi)星成像調(diào)度問題,建立了整數(shù)規(guī)劃模型,用拉格朗日松弛方法將原問題分解為多個(gè)子問題,并基于貪婪思想及線性搜索技術(shù)求解,其結(jié)果略優(yōu)于文獻(xiàn)[2],但[8]圖1衛(wèi)星成像示意圖該

5、文缺少對(duì)其產(chǎn)生解的近似程度的分析。王鈞等Fig.1Illustratingofsatelliteimaging采用遺傳算法解決多目標(biāo)的多衛(wèi)星成像調(diào)度問題,其結(jié)果優(yōu)于貪婪算法,但缺乏對(duì)產(chǎn)生解的評(píng)價(jià)機(jī)制。衛(wèi)星成像調(diào)度問題就是在滿足各類成像約束本文從整數(shù)規(guī)劃角度建立了成像調(diào)度問題的數(shù)下,盡可能多的安排成像任務(wù),是約束優(yōu)化問題。同學(xué)模型,基于拉格朗日松弛方法給出了成像調(diào)度問收稿日期:2007-03-28;修回日期:2007-06-23基金項(xiàng)目:國家自然科學(xué)基金(60604035);國家863重點(diǎn)項(xiàng)目(2007AA120202);國家863高技術(shù)研究發(fā)展項(xiàng)目(

6、2007AA12Z229)第2期靳肖閃等:基于拉格朗日松弛與最大分支算法的衛(wèi)星成像調(diào)度算法695題的求解算法。算法具有多項(xiàng)式時(shí)間復(fù)雜度,并可1.2衛(wèi)星成像調(diào)度的0-1整數(shù)規(guī)劃模型給出比較/緊致0的上下界。二次優(yōu)化算法提高了優(yōu)根據(jù)前文,衛(wèi)星成像調(diào)度問題可以建模為:N化的結(jié)果。ZIP=max6Xixi本文第1節(jié)建立了0-1整數(shù)規(guī)劃模型。第2i=1節(jié)給出了衛(wèi)星成像調(diào)度問題可行解及上界的求解方xi+xj[1,PIFN法。第3節(jié)給出了求解調(diào)度問題的單次優(yōu)化及二次6Nixi[F優(yōu)化算法。第4節(jié)是相關(guān)實(shí)驗(yàn)及結(jié)果分析。最后是i=1s.t.(1-1)結(jié)論與展

7、望。N6xi[Gi=11衛(wèi)星成像調(diào)度問題的數(shù)學(xué)模型NxI{0,1}1.1衛(wèi)星成像調(diào)度問題的數(shù)學(xué)描述NN為了建立衛(wèi)星成像調(diào)度問題的數(shù)學(xué)模型,首先max6Xixi為待優(yōu)化的目標(biāo)函數(shù),xI{0,1}i=1給出以下幾個(gè)形式化描述:為整數(shù)性約束,xi+xj[1,PIF為二NNN:待成像目標(biāo)總數(shù);s:待成像目標(biāo)集合,s={s元約束,6Nixi[F與6xi[G為多元約束。1,s2,,,sN};i=1i=1+Xi:待成像目標(biāo)si的權(quán)重,XiIZ;式(1-1)的可行解域?yàn)?Nti:衛(wèi)星對(duì)目標(biāo)si成像的起始時(shí)刻;DIP={x

8、6Nixi[F;i=1Ti:衛(wèi)星對(duì)

9、目標(biāo)si成像的時(shí)長(zhǎng);NTij:衛(wèi)星對(duì)si和sj成像所需側(cè)視動(dòng)作時(shí)間;6xi[G;xi+xj[1,i=1Ni: