基于次梯度優(yōu)化算法的航天測控調(diào)度

1航天測控調(diào)度0-1優(yōu)化問題航空航天探測調(diào)度的問題是，在有限的觀測設(shè)備的情況下，利用合理的模型和算法，管理和規(guī)劃各種衛(wèi)星的跟蹤、跟蹤、測量和跟蹤需求，以充分反映衛(wèi)星探測的需要。衛(wèi)星探測的需求必須通過衛(wèi)星探測天線和地面站測量裝置在幾何可見時(shí)間窗口中建立一條循環(huán)路徑來完成。由于測量設(shè)備數(shù)量不足，無法充分滿足越來越多的衛(wèi)星探測需求。因此，測量部門需要組織航空測量，以盡可能多地滿足衛(wèi)星測量的需要。航天測控調(diào)度問題是NP完全問題,目前解決這種問題的常用方法是構(gòu)造啟發(fā)式算法,求解盡量接近最優(yōu)解的可行解.作為實(shí)際應(yīng)用問題,航天測控調(diào)度問題具有領(lǐng)域知識復(fù)雜,解空間龐大的特點(diǎn),給該問題的建模和求解帶來了一定的困難.很多文獻(xiàn)如何評價(jià)上述啟發(fā)式算法可行解的優(yōu)劣及當(dāng)前場景配置的合理性是一個(gè)值得研究的問題,對于極大化目標(biāo)函數(shù)問題,一個(gè)有效的方法是通過計(jì)算目標(biāo)函數(shù)上界,利用上界和下界(可行解目標(biāo)函數(shù)值)的差來評價(jià)啟發(fā)式算法可行解的次優(yōu)性,利用上界和完全滿足需求收益值的差來評價(jià)當(dāng)前場景配置的合理性.拉格朗日松弛算法就是求解上界的一種有效方法,其基本思想是:使用拉格朗日乘子向量,將造成問題難于求解的復(fù)雜約束本文將構(gòu)建航天測控調(diào)度0-1整數(shù)規(guī)劃模型,該模型充分地利用了任務(wù)可用時(shí)間窗口與任務(wù)要求持續(xù)時(shí)間之間的冗余,考慮了更多的任務(wù)可能開始時(shí)刻.設(shè)計(jì)了拉格朗日松弛(LR)算法對該問題的上界進(jìn)行求解,用綜合優(yōu)先度(TSP)算法和遺傳算法(GA)分別獲得該問題的一個(gè)可行解目標(biāo)值,用來與所求上界進(jìn)行比較.最后,通過仿真算例對模型和算法進(jìn)行了驗(yàn)證.2任務(wù)響應(yīng)面特征為準(zhǔn)確地描述航天測控調(diào)度問題,需要確定問題的優(yōu)化目標(biāo),分析問題的約束條件,建立航天測控調(diào)度0-1整數(shù)規(guī)劃模型.調(diào)度場景包括衛(wèi)星及其測控需求、測控設(shè)備以及衛(wèi)星與設(shè)備間的幾何可見時(shí)間窗口,為方便調(diào)度,將測控需求轉(zhuǎn)換為測控任務(wù),將幾何可見時(shí)間窗口轉(zhuǎn)換為任務(wù)可能開始時(shí)刻.文中衛(wèi)星測控需求指抽象測控需求,簡稱“需求”,定義衛(wèi)星及其需求集合為SAT={sat定義設(shè)備集合為RES={res用1分鐘為單位對調(diào)度周期內(nèi)的時(shí)間進(jìn)行離散化,將一個(gè)周期(一天)分成T=1440個(gè)時(shí)刻,定義時(shí)刻集合為TIME={1,2,…,T}.定義式(1)是目標(biāo)函數(shù):最大化成功調(diào)度任務(wù)收益值;式(2)是任務(wù)約束:每個(gè)任務(wù)最多只能執(zhí)行一次;式(3)是設(shè)備約束:每個(gè)設(shè)備某一時(shí)刻最多只能為一個(gè)任務(wù)服務(wù).其中,G3按z次梯度優(yōu)化算法如果將IP中的任務(wù)約束(2)和設(shè)備約束(3)去掉,問題則變?yōu)榧吓渲脝栴}(Set-packingproblem),簡稱“SP”,已知SP可在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解式(7)和式(8)中,當(dāng)task可以證明,對SP(λ,μ)可以分解成S個(gè)子問題SP定義SP由于為此,需要按Z次梯度優(yōu)化算法就是利用s(λStep1初始化:Step2對給定的(λStep3判斷停止準(zhǔn)則:若Step4根據(jù)(s(λ本文中,(λ,μ)的步長(θ(λ),Φ(μ))設(shè)置為:式(19)中,上標(biāo)k代表第k次迭代,乘子(λ通過上述次梯度優(yōu)化算法可以得到一個(gè)最接近Z4模擬計(jì)算示例4.1系統(tǒng)基本信息利用STK軟件設(shè)計(jì)兩個(gè)場景:場景1有3個(gè)設(shè)備8顆衛(wèi)星,場景2有3個(gè)設(shè)備18顆衛(wèi)星.設(shè)計(jì)了兩種衛(wèi)星測控需求,需求1為:收益值30、跟蹤時(shí)間8分鐘、升降軌任務(wù)數(shù)各3次、最小測控間隔時(shí)間為0.需求2為:收益值20、跟蹤時(shí)間10分鐘、升降軌任務(wù)數(shù)各2次、最小測控間隔時(shí)間為1.場景1和場景2的前一半衛(wèi)星的測控需求設(shè)置為需求1,后一半衛(wèi)星的測控需求設(shè)置為需求2.限于篇幅,本文只給出場景1的基本參數(shù).設(shè)備和衛(wèi)星基本參數(shù)見表1和表2,衛(wèi)星對應(yīng)的測控需求設(shè)置見表3,調(diào)度周期設(shè)為1天:2009-12-200:00:00至2009-12-210:00:00.為驗(yàn)證拉格朗日松弛算法得到的上界性能,用文獻(xiàn)4.2tsp可行性解與最優(yōu)目標(biāo)函數(shù)值的比較本文得到了場景1和場景2的調(diào)度結(jié)果,其中TSP表示綜合優(yōu)先度算法、GA表示遺傳算法、LR表示拉格朗日松弛方法;TSP和GA用來求解目標(biāo)函數(shù)的下界,LR用來求解目標(biāo)函數(shù)的上界.調(diào)度結(jié)果如表4所示.由表4可以看出,LR得到的目標(biāo)函數(shù)上界可以評價(jià)可行解的優(yōu)劣和場景配置的合理性.首先,場景1和場景2的TSP可行解目標(biāo)函數(shù)值與上界分別相差15.000015和30.000087,說明TSP可行解目標(biāo)函數(shù)值與最優(yōu)目標(biāo)函數(shù)值還有一定差距,還應(yīng)進(jìn)一步優(yōu)化.場景1和場景2的GA可行解目標(biāo)函數(shù)值與上界分別相差0.000015和5.000087,說明GA可行解目標(biāo)函數(shù)值與最優(yōu)目標(biāo)函數(shù)值已非常接近,是個(gè)較優(yōu)的可行解.同時(shí)也說明LR算法得到的上界與最優(yōu)目標(biāo)函數(shù)值非常接近,是性能較優(yōu)的上界.從運(yùn)算時(shí)間上來看,GA算法的運(yùn)算時(shí)間要遠(yuǎn)遠(yuǎn)大于TSP算法的運(yùn)算時(shí)間,說明GA算法得到較優(yōu)可行解的同時(shí),增大了時(shí)間開銷.其次,可以