[發明專利]一種復雜約束條件下多星多任務觀測調度優化方法

在審

• 申請號: 201410650731.0
• 申請日: 2014-11-15
• 公開（公告）號: CN104361234A
• 公開（公告）日: 2015-02-18
• 發明（設計）人: 徐瑞;趙凡宇;崔平遠;李朝玉;朱圣英
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種復雜約束條件下多星多任務觀測調度優化方法，其特征在于：包括如下步驟：

步驟1，對多任務多資源調度問題模型的時序參數、優先級參數、存儲器容量參數、電量參數進行初始化，產生待選觀測任務集合，并在環繞地球的所有軌道圈次中隨機放置多個衛星初始運行位置；

步驟2，進行約束分析，綜合考慮各類約束，建立問題模型和約束模型；

將多任務多資源問題描述為六元組的形式，建立問題模型如下：

MTRS＝{S,T,P,G,R,W}???(1)

其中，S表示衛星集合，設能執行觀測任務的衛星數量為N_S，有其中分別表示第1顆衛星，第2顆衛星，…，第N_s顆衛星；T表示所有任務集合，設候選觀測任務數量為N_T，則候選觀測任務集數據下傳任務數量為N_D，則數據下傳任務集P表示觀測任務優先級的集合，為任務t_i在各衛星上的優先級，p₁為任務t_i在第1顆衛星上的優先級，p₂為任務t_i在第2顆衛星上的優先級，為任務t_i在第N_S顆衛星上的優先級；G表示地面站集合，地面站數量為N_G，分別表示第1，2,…,N_G個地面站；R表示調度過程中資源約束的集合，R＝{E,C}，其中E表示能量，C表示數據存儲容量；W表示可見窗口集合；為衛星s_i的可用觀測軌道圈次集，其中N_O為s_i可用觀測軌道數量；

建立多任務多資源問題的約束模型為：

①調度的目標函數：

P=Σi=1NTΣm=1NOΣp=1NSwicmiPci---(2)]]>

②約束條件：

觀測任務執行唯一性約束：

Σi=1NTΣm=1NOΣp=1NSctijpm=Σr=1NTΣm=1NOΣp=1NSctjrpm=Σm=1NOΣp=1NScmjp---(3)]]>

同軌道圈次任務執行時間約束：

cijPm=1,obtmjp≥obtmip+di+tacij---(4)]]>

衛星單一軌道圈次內電量約束：

Σtpi∈Teicmip+Σtdj∈DejdrmjP+Σti∈(T∪D)(emtacij+es)ctijpm≤Esp---(5)]]>

當前衛星(衛星資源)的存儲器容量約束：

總量約束：Σm=1NOΣi=1NTcicmip+Σm=1NOΣj=1NDcjrmjPm≤Csp---(6)]]>

下傳活動可行性的存儲器容量約束：

上述約束模型中：

時序參數：d_i為候選任務ti的觀測持續時長；tac_i,j為任務t_i到任務t_j的姿態調整時間長度；

優先級參數：w_i為任務t_i的優先級，對包括觀測任務及數據下傳任務在內的所有任務的優先級進行隨機賦值；

存儲器容量參數：為衛星s_p總的可用存儲容量；c_i為任務t_i所需占用的存儲容量；c_max＝max(c_i)為所有觀測任務中占用存儲器容量的最大值；

電量參數：為衛星s_p單個軌道圈次內可用的電量總量；e_i為任務t_i觀測所需消耗電量；為數據下傳任務td_i所需消耗電量；e_M為姿態機動單位角度所需能量；e_S為姿態穩定所需消耗電量，常數值；

調度過程中的決策變量為：

步驟3，對一個軌道圈次內的任意一顆衛星，根據公式(4)計算滿足時間約束的任務集合，并判斷集合是否為空；篩選出該衛星在該圈次內能夠執行的且滿足時序約束的任務集合；

步驟4，在步驟3得到的滿足時間約束的任務集合中，根據公式(5)—(7)選取能夠同時滿足能量和存儲容量約束的任務；在滿足所有約束的任務集合中，對當前衛星進行狀態轉移，并逐步得到滿足約束的可行任務序列；具體方法為：

采用的狀態轉移規則為

式中，allowedk(ti)=T-Σi=1NONStabui-t_violatek]]>為衛星k允許執行任務的集合，其中：為所有衛星已經探索過的任務目標，此集合為全局變量；t_violate_k為當前衛星k的位置時間參數不能滿足時間約束的目標任務集合；

q₀為控制轉移規則的參數，在[0,1]區間內取值；q為[0,1]區間上均勻分布的隨機變量；

τ_ij為任務t_i與任務t_j間的信息素強度；ξ_ij＝tac_i,j+e_j為任務t_i與任務t_j間能量需求影響；ω_j為任務t_j優先級的影響；

θj=infΣm=1NOΣi=1NTcicmip-Σm=1NOΣj=1NDcjrmjp≤cmax1else---(13)]]>

θ_j為存儲器容量需求的影響；

步驟5，經過步驟4的狀態轉移后，輸出當前衛星在該圈次內需要探索的可行任務序列，更新信息素；信息素更新策略采用所有衛星同步迭代的轉移方式，具體方法如下：

步驟5.1，為所有衛星隨機分配初始目標，然后所有衛星根據狀態轉移規則依次選擇下一任務，當所有的衛星完成可行任務序列構造，得到所有衛星的可行任務序列集合為：

TF=∪i=1NONSt_fi---(14)]]>

若無法找到任務，則返回該衛星的可行任務序列t_fi，執行步驟5.2；

步驟5.2，將TF收益與當前最優任務執行序列集TF_Best作比較；

若TF的總收益P_TF不大于TF_Best的總收益P_Best，則TF所有邊上的信息素揮發；

步驟5.3，經過揮發更新之后，任務t_i與任務t_j間的信息素濃度為：其中ρ為信息素揮發度，為任務t_i與任務t_j間的原信息素強度；若當前迭代步驟產生任務序列的總收益P_TF大于P_Best，則更新全局最優任務執行序列集TF_Best＝TF；

每次循環僅在當前迭代步數達到N_max時，對當前全局最優任務執行序列集中的信息素濃度進行更新：

τijnew=(1-ρ)τijold+Δτij---(15)]]>

式中其中Q為預設參數，L_Best為任務執行時資源參數的影響：

LBest=Σti,tj∈TFBestξij---(16)]]>

步驟6，設置蟻群算法最大遺傳代數為N_max，若迭代步數未達到N_max，則重新執行步驟3-步驟5，每個迭代步驟中，所有衛星都完成自己的尋找過程；當迭代步數等于N_max時，對當前全局最優任務執行序列集中的信息素濃度進行更新，完成一次循環，并輸出結果TF_best。