馬冬青，王蔚

1.華北計算技術研究所，北京 100083

2.太極計算機股份有限公司，北京 100083

基于改進遺傳算法的星地任務優(yōu)化調(diào)度研究

馬冬青1，王蔚2

1.華北計算技術研究所，北京 100083

2.太極計算機股份有限公司，北京 100083

星地任務優(yōu)化調(diào)度是利用特定的星地資源合理地安排星地任務。由于星地任務眾多而資源有限，而且星地任務受星地可見性以及多方面約束，星地任務調(diào)度問題十分復雜。針對星地任務的特點，建立了星地任務調(diào)度問題模型，提出了基于改進遺傳算法的星地任務優(yōu)化調(diào)度算法。算法采用按適應度排名輪盤賭選擇、順序交叉、隨機對換變異的算法要素。針對遺傳算法局部搜索能力弱的特點，提出了利用爬山算法優(yōu)化新一代個體的方法，以增強遺傳算法的局部搜索能力，給出了基于改進遺傳算法的星地任務調(diào)度算法。

星地任務調(diào)度；遺傳算法；爬山算法

1 引言

星地任務指在星地系統(tǒng)中由衛(wèi)星與地面設備共同完成的任務。星地系統(tǒng)由空間部分和地面部分組成，空間部分由多顆衛(wèi)星組成星座，地面部分由分布在不同位置的多個地面站組成。為了實現(xiàn)星地系統(tǒng)的特定功能，地面設備與星上的有效載荷設備需要協(xié)調(diào)配合完成指定任務。在星地系統(tǒng)中，星地任務的執(zhí)行受多種約束的影響。首先是星地可見約束。星地系統(tǒng)中衛(wèi)星按照各自的軌道運行，它們經(jīng)過各地面站的時間不同，執(zhí)行星地任務需要滿足星地可見條件。另外衛(wèi)星和地面設備具有一定的能力，星地任務需要符合各設備的限制，如天線的仰角限制等。在由多顆衛(wèi)星多個地面站組成的星地系統(tǒng)中，星地任務存在任務沖突及資源沖突。星地任務優(yōu)化調(diào)度目標是合理安排資源與任務執(zhí)行時間，從而在多種約束條件下完成系統(tǒng)業(yè)務，并使任務調(diào)度性能取得優(yōu)化。星地任務調(diào)度問題十分復雜，不僅包含任務和資源約束等通常的約束條件還包含時間窗約束，可歸類為有約束的組合優(yōu)化問題。

國內(nèi)外對衛(wèi)星相關調(diào)度問題開展了許多研究，從20世紀90年代美國空軍技術學院、美國國家航空和宇宙航行局、歐空局、印度空間研究機構等組織就展開對衛(wèi)星偵察、數(shù)傳和測控等調(diào)度問題的研究，并取得了一系列成果。例如，Gooley采用混合整數(shù)規(guī)劃算法解決美國空軍衛(wèi)星控制網(wǎng)的低、中高軌衛(wèi)星調(diào)度問題[1]。Parish提出了采用遺傳算法解決多星測控調(diào)度問題的方法[2]。目前國內(nèi)在建模方面對多種衛(wèi)星調(diào)度問題模型進行細分，融入多種約束，針對各種不同限制及優(yōu)化目標的衛(wèi)星任務調(diào)度問題提出了多種解決方法。

本文針對星地任務的特點，建立了星地任務調(diào)度問題模型，并提出了基于改進遺傳算法的星地任務優(yōu)化調(diào)度算法。

2 星地任務調(diào)度模型分析

星地任務調(diào)度問題是有約束的任務資源優(yōu)化調(diào)度問題。調(diào)度研究的問題是將有限的資源分配給在一定時間內(nèi)的不同任務。它是一個決策過程，其目的是優(yōu)化一個或多個目標。調(diào)度問題可以用活動、資源、調(diào)度目標三要素來描述?；顒又感枰{(diào)度的任務和活動，完成活動需要一定的資源，并且持續(xù)一定時間。資源指完成活動所需的人力和資源。每個資源都有特定的能力。在任何時間，活動對資源的需求都必須滿足資源能力的限制。調(diào)度目標指在滿足時間和約束的條件下，為每個活動確定執(zhí)行時間并分配資源，以使得調(diào)度問題的目標函數(shù)值最優(yōu)。

星地任務調(diào)度是安排有限的星地資源協(xié)調(diào)完成系統(tǒng)的任務，以達到調(diào)度性能的最優(yōu)。本文研究的星地任務調(diào)度問題，同樣可以用活動、資源、調(diào)度目標三要素來描述。

（1）活動

活動指地面站設備與衛(wèi)星協(xié)調(diào)執(zhí)行的系統(tǒng)任務?；顒有枰掷m(xù)一定的時間，要求持續(xù)時間大于指定的最少執(zhí)行時間。活動根據(jù)重要性和時效性要求等，設置不同的優(yōu)先級。

（2）資源

資源指完成星地任務所需的衛(wèi)星有效載荷和各地面站的設備等。地面站分布在不同地理位置，位置固定，各站配備一定數(shù)量的設備用于執(zhí)行星地任務。衛(wèi)星與各地面站之間的可見時間由衛(wèi)星的軌道決定。衛(wèi)星配備一定的有效載荷。

（3）調(diào)度目標

在星地任務調(diào)度問題中，一般來講，優(yōu)化目標可以細化為多種優(yōu)化目標，如：任務執(zhí)行有效時間最長；任務安排的成功率最高；設備使用均衡等。在本文研究的星地任務調(diào)度問題中，調(diào)度目標是任務執(zhí)行有效時間最長。

依據(jù)上述目標建立的數(shù)學模型是：其中，sj表示衛(wèi)星j，dk表示設備k，t(sj，dk，i)表示星j設備k執(zhí)行任務i的時間長度；ts表示開始時間，te表示結束時間，A(sj，dk)表示星j與設備k的可見時間窗口的集合。

在上述模型中，各式的含義是：

式（1）是目標函數(shù)，要求任務執(zhí)行有效時間最長。

式（2）是衛(wèi)星資源，各衛(wèi)星有各自的軌道參數(shù)。

式（3）是地面設備，地面設備有一定的能力限制，各設備位于地理分布不同的地面站。

式（4）是任務執(zhí)行時間的計算公式。

式（5）是星地約束，表示任務需安排在設備對衛(wèi)星的可見時間窗口。

3 基于改進遺傳算法的星地任務調(diào)度算法

遺傳算法是受生物進化思想啟發(fā)而得到的一種全局優(yōu)化算法，是一種通過模擬自然進化過程來搜索最優(yōu)解的方法。遺傳算法是由美國的Holland教授于1975年提出的。遺傳算法首先構造出初始種群，然后按一定的規(guī)則進行逐步迭代以產(chǎn)生新的個體，按照適者生存和優(yōu)勝劣汰的原理，逐代演化生成越來越好的近似解。在每一代，根據(jù)個體適應度來選擇個體，并借助于遺傳算子進行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個過程模擬了自然進化，使后代種群比前代具備更優(yōu)的適應性。通過多次迭代，最后生成的種群中的最優(yōu)個體，就可作為問題的滿意解。

本文參照多路旅行商問題的遺傳算法，構建星地任務調(diào)度的基本框架，分析比較影響遺傳算法性能的各方面因素，經(jīng)過多種嘗試，設計了采用按適應度排名輪盤賭選擇、順序交叉、隨機對換變異的算法要素，并針對遺傳算法局部搜索能力弱的特點，提出了利用爬山算法優(yōu)化新一代個體的方法，以增強遺傳算法的局部搜索能力，最終給出了基于改進遺傳算法的星地任務調(diào)度算法。

3.1 個體染色體

采用遺傳算法解決問題時，首先要規(guī)定一種編碼方法，使得調(diào)度問題的任何一個潛在可行解都能表示成為一個數(shù)字染色體。在本文中，個體染色體用來表示星地任務的調(diào)度序列。在改進遺傳算法的星地任務調(diào)度中，采用任務與任務分隔符聯(lián)合編排的染色體編碼方式，將可行的潛在解表示為1至T+K-1（T是任務數(shù)，K是資源數(shù)）的不重復的自然數(shù)編碼。在這種編碼中，1至T表示各星地任務，T+1至T+K-1表示各任務分割符。這種自然數(shù)編碼表示的星地任務的調(diào)度序列中，利用T-1個任務分隔符，可以將任務劃分為K組，每組中的任務由一個資源來完成。由于星地任務與衛(wèi)星綁定，資源可轉化為地面設備資源。在編碼序列中，第一個資源的任務是從編碼頭開始，逐一按編碼順序安排，遇到任務分隔符時結束，接下來由第二個資源按編碼繼續(xù)執(zhí)行后續(xù)任務，以此類推。

個體染色體編碼通過解碼過程轉化為實際的調(diào)度方案。由于染色體編碼序列中的各項任務必須滿足星地可見約束及任務資源約束，因此解碼過程對資源與任務、資源與資源、任務與任務之間的沖突進行化解，將個體染色體編碼轉化為滿足各類約束條件的調(diào)度方案。

3.2 種群

種群由一定數(shù)量的個體組成。在本文中，種群中的每個個體都代表一個星地任務調(diào)度序列，種群中包含多個調(diào)度序列。這些調(diào)度序列經(jīng)過遺傳操作逐代演化，生成越來越好的調(diào)度序列。種群的大小指種群中的個體數(shù)目。種群的大小對算法的性能有一定的影響。種群較大時，更容易找到全局最優(yōu)解，但是每次迭代的時間也有所增加。本算法采用固定大小種群，即在算法的逐步迭代中，種群大小不變。

初始種群的產(chǎn)生采用隨機法。由于初始種群的優(yōu)劣直接影響算法的性能，因而構造初始種群時首先保證種群中個體的可行性。本算法隨機產(chǎn)生調(diào)度序列，根據(jù)星地任務檢查調(diào)度序列中是否包含各任務且每個任務只包含一次，如果是則將該調(diào)度序列作為初始種群的個體，如果不是則重新產(chǎn)生調(diào)度序列。這種隨機產(chǎn)生可行個體的操作不斷重復，直到種群中包含指定數(shù)目的個體。

在種群的世代繁衍中，新種群由父代的個體經(jīng)過選擇、交叉、變異等遺傳操作產(chǎn)生。在本算法的逐次迭代中，新種群的確定采用保留最優(yōu)個體、引入新個體的方法。通過保留最優(yōu)個體，可以避免遺傳操作的隨機性破壞掉已有的最優(yōu)個體。引入遺傳操作產(chǎn)生的新個體，可以不斷獲得適應度改進的可能性。

3.3 適應度

在遺傳算法中，個體的優(yōu)劣由適應度來決定。在本文研究的星地任務調(diào)度問題中，采用任務執(zhí)行有效時間（目標函數(shù)值）作為調(diào)度序列的適應度，用于評判個體的優(yōu)劣，任務執(zhí)行有效時間長的調(diào)度序列優(yōu)于任務執(zhí)行有效時間短的調(diào)度序列。對應于調(diào)度序列的每個個體的適應度就是調(diào)度序列解碼后的調(diào)度方案中，實際安排的各項任務的持續(xù)時間之和，如式（6）所示。

在選擇及評價個體時，均用到適應度的計算。

3.4 選擇操作

選擇操作是從種群中選出優(yōu)良個體的操作。在本文中，選擇操作用于從種群的多個調(diào)度序列中選出優(yōu)良的調(diào)度序列。本算法采用按適應度排名的輪盤賭選擇方法。在種群中，每個個體具有各自的選擇概率，這個概率取決于種群中個體的適應度及分布。選擇概率的確定一般有兩種方法：一種方法是按適應度比例確定選擇概率；另一種方法是按適應度排名確定選擇概率。

按適應度比例確定選擇概率時，可以保證優(yōu)勢個體具有更高的選擇概率，但有一些缺點。當種群中出現(xiàn)超常優(yōu)勢個體時，種群的選擇壓力大，若采用按比例選擇法，則這些超常優(yōu)勢個體有可能由于競爭力過強而控制選擇，影響全局優(yōu)化能力。當種群中個體差異較小時，種群的選擇壓力小，有可能造成繼續(xù)優(yōu)化潛能的降低，可能獲得某個局部的最優(yōu)解。

按適應度排名確定選擇概率時，任務執(zhí)行有效時間最長的調(diào)度序列排在最前，即排名靠前的個體具有更高的選擇概率。按適應度排名的選擇方法比按適應度比例的選擇方法具有更好的魯棒性。在按適應度排名的選擇中，種群的個體按目標函數(shù)值排序，選擇概率僅取決于個體在種群種中序位，而不是實際的目標值。這種方法引入了種群均勻尺度，有效地控制了種群的選擇壓力，避免了由于選擇壓力過大或過小時出現(xiàn)的過早收斂或停滯現(xiàn)象。

按排名確定選擇個體選擇概率的方法見式（7）。

其中，i為個體排名。

本算法中采用按適應度排名的輪盤賭選擇策略。具體步驟是：

（1）根據(jù)適應度對個體進行排序，適應度最好的排在最先。

（2）根據(jù)種群大小，計算各排名的選擇概率和累積概率。

（3）產(chǎn)生0～1之間的隨機數(shù)，采用輪盤賭的方式，確定選出的個體。

累積概率見式（8）和式（9）。

其中，POPSIZE表示種群大小，i表示排名。PSi表示排名為i的個體的選擇概率。PsumSi表示排名為i的個體的累積概率。

輪盤賭的選擇方式是隨機產(chǎn)生0～1之間的隨機數(shù)，模擬輪盤旋轉，將隨機數(shù)與個體的累積概率比較。用i來表示某個體的排名，當隨機數(shù)大于排名i的累積概率且小于排名i+1的累積概率時，排名為i的個體被選中。

3.5 交叉操作

交叉操作也稱基因重組，是結合來自父代交配種群中的信息產(chǎn)生新個體的操作。交叉操作將選定個體按一定的交叉概率把兩個父代個體染色體的部分結構加以替換重組，生成新個體。在本文中，交叉操作對選定的兩個調(diào)度序列中的部分任務序列進行替換重組，生成新的調(diào)度序列。交叉是遺傳算法獲取新的優(yōu)良個體的最重要的手段。交叉操作有多種形式，包括單點交叉、部分交叉（PMX）、順序交叉（OX）、循環(huán)交叉（CX）等。

在本文的改進遺傳算法中采用順序交叉操作。1985年，Davis等人針對TSP問題提出了基于路徑表示的順序交叉法。兩個父代染色體進行順序交叉操作時有兩個關鍵點，一是子代染色體保存其中一個父代染色體的一部分，二是保存另一父代染色體基因編碼中的相對順序。這種順序交叉法避免了染色體中出現(xiàn)重復基因編碼的情況。本文參照該方法設計了算法的交叉操作。

交叉操作的具體步驟是：

（1）隨機生成編碼范圍內(nèi)的兩個隨機數(shù)，將兩個隨機數(shù)之間的部分作為匹配區(qū)域。

（2）生成子代個體1。方法是用父代個體1中匹配區(qū)域內(nèi)的基因編碼，復制到子代個體1的相應區(qū)域；其余部分從匹配區(qū)域后由父代個體2中的基因順序補充，補充過程中，剔除掉子代個體中已經(jīng)擁有的基因編碼。

（3）采用類似方法，構造子代個體2。

交叉概率決定交叉操作的頻率，概率越高，可以越快地收斂到最有希望的最優(yōu)解區(qū)域，因此一般選擇較大的交叉概率。但交叉概率太高會導致過早收斂。本算法中缺省將交叉概率設置為0.8。

3.6 變異操作

變異操作是按一定的概率對個體染色體進行改變的操作。變異使遺傳算法保持種群的多樣性，防止出現(xiàn)未成熟收斂。交叉之后子代經(jīng)歷的變異，實際上是子代基因按小概率擾動產(chǎn)生的變化。在本文中，變異操作對交叉后生成的調(diào)度序列進行微調(diào)，提高種群中調(diào)度序列的多樣性。

變異操作具體步驟是：

（1）隨機抽取染色體中的兩個基因位置。

（2）將這兩個位置的基因進行對換，形成新的個體。

在變異操作中，變異概率一般取較小值。當變異概率過大時，遺傳算法就規(guī)劃為隨機搜索，這樣就破壞了遺傳算法的重要數(shù)學特性和搜索能力。本算法缺省將變異概率設置為0.1。

3.7 爬山操作

遺傳算法是一種全局優(yōu)化算法，但是局部搜索能力較弱。針對遺傳算法局部搜索能力弱的特點，本文在遺傳算法中增加爬山操作，采用爬山算法優(yōu)化新一代個體的方法，以增強遺傳算法的局部搜索能力，提高遺傳算法的運行效率和求解質(zhì)量。

本算法對經(jīng)過選擇、交叉、變異操作后產(chǎn)生的新一代個體逐個進行爬山操作，利用爬山算法局部搜索力強的特點，提高新一代個體的適應度。爬山操作采用逆序法構造新個體作為候選個體，并進行適應度計算，如果候選個體優(yōu)于原個體則接受候選個體，否則拒絕候選個體。

4 實驗驗證

為驗證本算法的調(diào)度能力，本文采用模擬生成的實驗樣本進行解算。在實驗樣本中，星座部分包括9顆衛(wèi)星，參數(shù)見表1，地面部分由分布在不同位置的3個地面站組成，參數(shù)見表2，每個地面站有3個設備用于執(zhí)行星地任務，設備的設置時間為5 min，設備的工作仰角為10°至90°。星地任務調(diào)度時間范圍為2012年3月20日12時至2012年3月22日12時，根據(jù)衛(wèi)星與地面站的可見關系生成91個任務。每個任務最少執(zhí)行時間為10 min，各任務優(yōu)先級相同。

表1 實驗樣本衛(wèi)星參數(shù)

表2 實驗樣本地面站參數(shù)

實驗中遺傳算法和改進遺傳算法各運行20次，計算平均值。實驗中設置遺傳算法的種群規(guī)模為20，交叉概率為0.8，變異概率為0.1，迭代次數(shù)為100。本文另外選用先到先服務算法FCFS，沒有引入爬山操作的遺傳算法和動態(tài)規(guī)劃法對實驗樣本進行計算。實驗的結果如表3所示。

表3 實驗結果

從數(shù)據(jù)中可以看出，在改進遺傳算法生成的優(yōu)化調(diào)度方案中，任務執(zhí)行有效時間為710 801 s，任務調(diào)度率達到90.4%，計算結果明顯優(yōu)于FCFS算法和遺傳算法。在計算時間上，遺傳算法和改進遺傳算法由于處理的復雜性，使得計算較為耗時，但計算時間屬于實際應用可接受的范圍內(nèi)。采用動態(tài)規(guī)劃法解決實驗樣本問題時，經(jīng)6 h的計算沒有生成最優(yōu)化調(diào)度序列。實驗證明動態(tài)規(guī)劃法不適用于解決較大規(guī)模的星地任務規(guī)劃問題。

5 結束語

通過分析和實驗驗證，得出如下結論：

本文的改進遺傳算法可以有效解決星地任務優(yōu)化調(diào)度問題。算法通過對星地任務調(diào)度序列的編碼和解碼，將任務的執(zhí)行安排在星地可見的范圍內(nèi)，并且化解了資源以及任務之間的沖突。在資源有限的情況下，通過統(tǒng)籌安排，協(xié)調(diào)了眾多星地任務的執(zhí)行，使星地任務的調(diào)度得到優(yōu)化。采用爬山增強的遺傳算法生成的調(diào)度方案優(yōu)于FCFS算法和沒有爬山操作的遺傳算法。

采用爬山增強的遺傳算法優(yōu)于改進前的遺傳算法，通過引入爬山操作增強遺傳算法的局部搜索能力，是算法改進的一項有效途徑。

[1]Gooley T D.Automating the satellite range scheduling process[D].Ohio：Air Force Institute of Technology，1993.

[2]Parish S A.A genetic algorithm approach to automating satellite range scheduling[D].Ohio：Air Force Institute of Technology，1994.

[3]Pinedo M.調(diào)度：原理、算法和系統(tǒng)[M].張智海，譯.2版.北京：清華大學出版社，2007.

[4]王小平，曹立明.遺傳算法——理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002：7-9.

[5]玄光南，程潤偉.遺傳算法與工程優(yōu)化[M].北京：清華大學出版社，2004.

[6]Laporte G.Fifty years of vehicle routing[J].Transportation Science，2009，43（4）.

[7]Bodin B G.Planning for truck fleet size in the presence of a common-carrier option[J].Decision Sci，1983，14：103-120.

[8]Frank J.Planning and scheduling for fleets of earth observing satellites[C]//Proceedings of the Sixth International Symposium on Artificial Intelligence，Robotics，Automation and Space，2001.

MA Dongqing1,WANG Wei2

1.North China Institute of Computing Technology,Beijing 100083,China
2.TAIJI Computer Corporation Limited,Beijing 100083,China

The scheduling of satellite-ground cooperating missions is to arrange the missions scientifically,which uses the limited satellites and ground resources to fulfill.The scheduling is complex not only because of the access conditions between satellites and ground stations,but also because of the conflict between the large numbers of tasks and the limited resources.In this paper,a mathematical model of the satellite-ground cooperating scheduling problem is established considering the features of the missions.And an improved genetic algorithm is presented to solve the scheduling problem. The algorithm includes rank-based fitness assignment and roulette wheel selection,ordered crossover,and random change mutation.By using hill-climbing methods,the local searching ability of the genetic algorithm is improved.

satellite-ground cooperating scheduling;genetic algorithm;hill-climbing method

A

TP39

10.3778/j.issn.1002-8331.1204-0645

MA Dongqing,WANG Wei.Research on scheduling of satellite-ground cooperating missions based on improved genetic algorithm.Computer Engineering and Applications,2014,50（6）：246-249.

馬冬青（1972—），女，高工，研究領域為航天測控軟件，衛(wèi)星應用；王蔚（1973—），男，工程師，研究領域為工程優(yōu)化。E-mail：ma_dq@yahoo.com.cn

2012-05-04

2012-06-19

1002-8331（2014）06-0246-04