陳峰　劉孝忠　徐建華　姚頔

摘 要：多星測控調(diào)度是一個具有大搜索空間的多峰問題。針對簡單遺傳算法求解易陷入局部最優(yōu)和不穩(wěn)定的缺陷，借鑒分散搜索多樣化采樣、局部尋優(yōu)的特點，提出一種基于分散搜索的混合遺傳算法，在全局的隨機搜索中嵌入全局的定向搜索。在描述問題的基礎(chǔ)上，提出可進行細粒度搜索的可行解表示方式，構(gòu)建算法的整體流程，并設(shè)計由輸入?yún)?shù)控制的多樣化初始集產(chǎn)生方法、基于質(zhì)量和多樣性原則的參考集生成和更新方法、吸取被組合個體優(yōu)良成份的解組合方法及基于啟發(fā)式局部搜索的解提高方法等算法要素。仿真表明新算法在求解質(zhì)量上比簡單遺傳算法有明顯提高。

關(guān)鍵詞：調(diào)度；分散搜索；遺傳算法；測控

中圖分類號：TP18 文獻標(biāo)識碼：A

Abstract：MultiSatellite TT&C scheduling is a multipeak problem with huge search space.The simple genetic algorithm solving is prone to get into local optimization and instability.Because Scatter Search can sample diversifiedly and optimize locally， a hybridized genetic algorithm based on scatter search was proposed， which embeds the global directed search in the global stochastic search. After the problem was described，the representation of feasible solution was designed，which was convenient for searching roundly， then the process of the algorithm was construced， and the main elements of the algorithm were presented， which includes diversification generator controled by input parameters ， reference set generating and updating method based on quality and diversification principle， the combination method drawning on the good components of combinated solutions， and the improvement method based on heuristic local searching. Simulation result shows the new algorithm can improve the quality of the solutions，compared with the simple genetic algorithm.

Key words：scheduling；scatter search；genetic algorithm； TT&C

1 引 言

多星測控調(diào)度問題是指在多星測控需求和測控資源一定的背景下，研究如何合理分配測控資源，以更好滿足所有測控需求的問題[1]，是一個NP完全問題[2]。對于該類問題，主要有針對規(guī)劃模型的確定性解法[ 3]、基于規(guī)則和約束滿足的啟發(fā)式算法[4]以及智能搜索算法（以遺傳算法為主）[5-7]。從研究結(jié)果來看，遺傳算法（Genetic Algorithm，GA）的求解效果較好[6]。

雖然理論上GA的全局收斂性能夠保證算法對初值的魯棒性，但在解決一些實際問題時，求解搜索過程中某些低階模式可能難以重組為期望的高階模式，這會使其搜索效率大大降低[8]，而此時種群的質(zhì)量就將對算法的性能產(chǎn)生很大的影響。在用簡單遺傳算法（Simple Genetic Algorithm，SGA）求解多星測控調(diào)度問題時，編碼長，搜索空間大且多峰效應(yīng)嚴重，若進行細粒度的搜索，則搜索效率較低，而且獲得的往往是局部最優(yōu)解，若進行粗粒度的搜索，則隨機搜索特性較強，解的質(zhì)量和穩(wěn)定性無法保證。如果在進化過程中啟發(fā)式地往種群中加入一些搜索空間中適應(yīng)度高且離散分布的個體，可以確保搜索的遍歷性和重點性。分散搜索（Scatter Search，SS）是一種基于整數(shù)編碼的具有保優(yōu)思想的元啟發(fā)式算法，它蘊含了記憶搜索的功能，通過在整個搜索空間中采取離散的多點采樣、系統(tǒng)性組合[9]、局部提高等舉措，來獲得一組兼顧質(zhì)量和多樣性的解[10]，已成功應(yīng)用于車間任務(wù)調(diào)度[11，12]、項目調(diào)度[13]等問題。

本文針對多星測控調(diào)度問題的特點，將SS系統(tǒng)地的局部搜索與GA的全局隨機搜索結(jié)合起來，提出一種基于分散搜索的遺傳算法（Genetic Algorithm Based on Scatter Search，GASS），以期更有效地對問題進行求解。

2 問題描述

設(shè)有若干低軌衛(wèi)星、地面測控站；對每顆衛(wèi)星，需在一段時間內(nèi)完成若干測控需求，這些需求的允許執(zhí)行時間相互不重疊；所有衛(wèi)星的測控需求總數(shù)記為CReq；對于每個測控任務(wù)需求，包含：衛(wèi)星名稱、衛(wèi)星天線名稱、需求類型、最早開始時間、最晚結(jié)束時間、需求優(yōu)先級、每次測控最短持續(xù)時間等固有屬性及構(gòu)成調(diào)度目標(biāo)的每天跟蹤站數(shù)、每天升軌跟蹤次數(shù)和每天降軌跟蹤次數(shù)（其和構(gòu)成需求要求的每天測控次數(shù)，記為Rj）、最小測控間隔時間、最大測控間隔時間五個具體要素。

調(diào)度以天為時間單位進行，首先把測控需求的衛(wèi)星名稱、需求最早開始時間和最晚結(jié)束時間、每次測控最短持續(xù)時間等信息與通過可見性分析軟件獲得的衛(wèi)星可見弧段進行結(jié)合，得到各需求的每天可用可見弧段集合，每個弧段包含起止時間、衛(wèi)星及天線、地面站及設(shè)備、升降軌等信息，然后從弧段集合中抽取Rj個弧段分配給需求，分配過程考慮沖突消解，最終形成調(diào)度方案。

2.2 解的表示

將問題的可行解（調(diào)度方案）表示成被調(diào)度弧段ID號的整數(shù)排列形式，這種表示方法對SGA和SS都適用，為表述方便，統(tǒng)稱為染色體（個體）。

把調(diào)度周期內(nèi)的所有需求對應(yīng)的可用可見弧段存入某一集合，將該集合中所有弧段所對應(yīng)的位置序號序列作為一個標(biāo)準(zhǔn)參照序列。

編碼設(shè)計如圖1所示：依據(jù)一定規(guī)則不重復(fù)地從標(biāo)準(zhǔn)參照序列中選出序號，依次排列，形成染色體，染色體的長度為所有弧段的總數(shù)，記為NTotal。解碼時依次將染色體每個基因值對應(yīng)的可用可見弧段分配給相應(yīng)的需求，在此過程中，每對一個弧段進行分配后（表明該時間段內(nèi)弧段對應(yīng)的測控站

天線對弧段對應(yīng)的衛(wèi)星服務(wù)），要對染色體剩下所有基因?qū)?yīng)弧段進行一次資源沖突消解。此處的沖突是指在某一個調(diào)度方案中，由于地面資源的限制，當(dāng)某一弧段分配給某一測控需求時，導(dǎo)致分配給另一測控任務(wù)需求的弧段無法執(zhí)行。當(dāng)某需求要求的弧段數(shù)滿足時，染色體中與該需求對應(yīng)的可用可見弧段將不再參與分配。

3 分散搜索算法基本框架

SS最早在1977年由Glover Fred為解決整數(shù)規(guī)劃問題而提出[14]，但一直沒有得到重視，直到1998年Glover[15]給出了算法的通用框架和具體實現(xiàn)技術(shù)，才被廣泛地關(guān)注與應(yīng)用[16]。分散搜索的思想源于使用系統(tǒng)的方法對多個解進行組合以滿足需要的特征或約束[16]，即通過預(yù)先設(shè)定的規(guī)則來提取若干個解的“好”的部分以組合成“更好”的解。它在對搜索空間分散采樣的基礎(chǔ)上，基于高質(zhì)量和多樣性的原則從采樣點中選擇一部分“好”解構(gòu)成參考集，然后通過各種方法對參考集中的解進行要素提取和組合，以形成更“好”的解，并對參考集進行更新，當(dāng)參考集中解的質(zhì)量不能再提高時，也就標(biāo)志著這一次分散采樣點可能的組合效應(yīng)都已經(jīng)表現(xiàn)出來，需重新進行下一輪的多樣化采樣及后續(xù)操作。具體框架如下：

1）在問題的可行解空間中抽樣一系列多樣性的初始解，構(gòu)成初始集P；其生成主要有系統(tǒng)方法和啟發(fā)式方法[17]。系統(tǒng)的方法即是根據(jù)可行解空間中解的分布位置分散采樣，而啟發(fā)式方法則是根據(jù)解在目標(biāo)值空間中的分布位置分散采樣。

2）運用參考集生成方法，從初始集中選出兼顧質(zhì)量和多樣性的解構(gòu)成參考集RefSet，SS主要通過對參考集中的解進行各種方式的組合和局部提高來獲取問題的最優(yōu)解或滿意解。

3）運用子集產(chǎn)生方法，對RefSet構(gòu)建子集。為了對參考集中的解進行各種可能的組合，先將要組合的解配對存儲，也就是從RefSet中抽取各種規(guī)模的子集；出于運算時間和組合效果的考慮，常用的子集類型有[18]：二元素子集、三元素子集、最優(yōu)若干元素子集等。為確保求解效率，產(chǎn)生的子集互不相同。

4）運用解組合方法，對每個子集中的解進行合并組合以產(chǎn)生一個或多個新解，所有子集的合并應(yīng)遵循盡可能使新解中包含多樣性解和高質(zhì)量解的原則。

5）對新解運用解改進方法，提高解的質(zhì)量，該過程一般是對新解進行一個局部的搜索。

6）運用參考集更新方法從所有經(jīng)過提高的解中選擇“好”解來更新參考集，更新的原則仍然是選用高質(zhì)量解和多樣性解。如果參考集能夠被更新，則重新運用子集產(chǎn)生方法，產(chǎn)生子集，進入下一輪的組合提高，如果參考集不能被更新，則結(jié)束此次抽樣的尋優(yōu)，根據(jù)需要確定是否進行下一次抽樣尋優(yōu)。

4 基于分散搜索的混合遺傳算法

4.1 GASS整體流程

從模型可以知道，雖然資源沖突是影響每個需求被滿足和所有需求被滿足的一個重要因素，但是，目標(biāo)函數(shù)仍然存在一定的可加性，即目標(biāo)值是所有需求被滿足程度的加權(quán)和，這一特點與SS提出者的初衷正好吻合，即SS具有在巨大的搜索空間中搜索到一些分布分散且質(zhì)量較優(yōu)的解的能力，而此性能正好能夠提高SGA的搜索起點，使其一些進化操作剛好作用于解的薄弱部分，從而有助于SGA克服全局搜索時被多峰效應(yīng)干擾的困境。鑒于此，考慮在SGA的隨機搜索過程中嵌入SS，利用SS獲得的解來改進SGA的種群質(zhì)量，以此來提高SGA求解的質(zhì)量和穩(wěn)定性。總體思想是：在SGA的每代進化中，當(dāng)前初始集ISetO中的解分別被SGA（作為其種群的一部分）和SS操作，后者獲得參考集RefSetN，種群更新時，由SS的多樣化生成方法重新生成一個新初始集ISetN，將其中的解和由SS剛獲得的參考集RefSetN中的解加入新種群中。新加入種群的參考集RefSetN中的解可以看作是SGA對ISetO采取一定的方法進化得來的。算法的整體步驟如表下：

基于分散搜索的遺傳算法

1）生成初始種群，其中δ·popsize（0.7≤δ≤0.85）個個體隨機生成，（1-δ）·popsize個個體由多樣化生成方法生成，該部分個體同時作為SS的初始集；

2）計算種群中各個體適應(yīng)度；令進化代數(shù)generation= 0；遺傳操作計數(shù)變量m=popsize；

3）判斷算法終止條件是否滿足？若是，則輸出結(jié)果，否則，轉(zhuǎn)步驟4；

4）若m>0，從種群中隨機選擇兩個個體進行交叉、變異運算，并轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟6；

5）m=m-2，轉(zhuǎn)步驟4；

6）計算經(jīng)交叉、變異后的個體適應(yīng)度，排序（精英）選擇確定進入下一代種群的δ·popsize-RefSet

個個體；

7）對初始集中的個體，用參考集生成方法生成RefSet；

8）若RefSet沒有變化，則轉(zhuǎn)步驟10，否則轉(zhuǎn)步驟9；

9）對RefSet采用子集產(chǎn)生方法產(chǎn)生Subsets；依次對每個子集采用解組合方法產(chǎn)生一個新解，應(yīng)用解提高方法對其進行提高，并用參考集更新方法對RefSet進行更新；轉(zhuǎn)步驟8；

10）由多樣化生成方法生成（1-δ）·popsize個個體，替換初始集中的個體，并與RefSet中個體一起加入下一代種群；

11）generation =generation +1，轉(zhuǎn)步驟3。

4.2 多星測控調(diào)度的GASS要素設(shè)計

4.2.1 遺傳操作算子

采用與本文類似編碼進行求解的相關(guān)研究表明，Syswerda的基于位置的交叉算子[2， 6]和排序選擇算子[2， 6， 19]性能較好；為確保求解質(zhì)量，采用精英保留策略；另外，為與Syswerda的序列交叉算子主要繼承父個體中某些基因相對順序的特點互補，采用兩點交換變異算子對染色體基因間的絕對順序進行變換，即隨機確定若干對位置，然后交換位置上的基因。

4.2.2 分散搜索子方法設(shè)計

雖然Glover在文獻[15]中給出了針對整數(shù)規(guī)劃問題的SS求解框架，其初始集生成方法、子集生成方法也具有一定的通用性，但在求解各種實際問題時，其它各子方法仍需要結(jié)合問題的特點進行設(shè)計。根據(jù)多星測控調(diào)度問題解的表示方法和目標(biāo)函數(shù)的特點，設(shè)計如下求解子方法。

5）解提高方法

采用局部搜索提高方法時，如果對不滿足的需求進行隨機的鄰域搜索，則時間開銷太大，且效果也不理想，考慮到時間間隔約束是模型中最強的約束，此處采用一種首先對弧段間隔時間進行預(yù)處理的半啟發(fā)式局部隨機搜索提高方法。

局部提高方法

1）對某未滿足需求的所有可用弧段按照起始時間從低到高進行排列；

2）對每個弧段i，將與其時間間隔滿足最小和最大測控時間間隔的左側(cè)弧段集合和右側(cè)弧段集合分別稱為該弧段的左鄰弧段集和右鄰弧段集，統(tǒng)稱為相鄰弧段集；3）首先隨機確定一個弧段，若其具有兩個方向的相鄰弧段集，則隨機確定一個集合，同時也就獲得了一個選擇方向，并從中隨機確定一個弧段，然后根據(jù)選擇方向，在該弧段的選擇方向弧段中選擇弧段，依此法選擇下去，當(dāng)進行到某個弧段在選擇方向上沒有相鄰弧段且需求還沒有被分配要求的弧段數(shù)時，則從被分配的第一個弧段的另外一個方向上開始搜索，直到被分配要求的弧段數(shù)，該過程中，若某弧段無相鄰弧段集，則重新選擇第一個弧段；

4）對該需求的滿足情況進行計算，若需求被滿足，則轉(zhuǎn)入步驟1；若需求沒滿足，則重新轉(zhuǎn)入步驟3，直到滿足停止規(guī)則。

5 實驗及分析

5.1 實驗設(shè)計

創(chuàng)建兩個仿真場景：場景一包含20顆衛(wèi)星（表1中的前20顆）和5個地面測站，場景二包含35顆低軌衛(wèi)星，5個地面測站，衛(wèi)星各配一架天線，測站各配一套設(shè)備，頻段匹配，具體參數(shù)見表1（軌道用Semimajor Axis（S）/km、Eccentricity（E）、Inclination（I）/deg、Argument of Perigee（A）/deg、RAAN（R）/deg、TraeAnomaly（T）/deg表示。）和表2。仿真時間：2009＼＼06＼＼14 00：00：00～ 2009＼＼06＼＼1500∶00∶00。各衛(wèi)星任務(wù)需求優(yōu)先級相同，各具體要求統(tǒng)一設(shè)置為：每天跟蹤站數(shù)為2，每天升、降軌測控次數(shù)分別為2，最小測控間隔時間、最大測控間隔時間分別為1小時和8小時，每次測控最短持續(xù)時間為8分鐘。兩種進化策略下種群規(guī)模都為44，交叉概率為0.8，變異概率為0.1，終止條件為進化20代。初選集規(guī)模設(shè)為11，參考集規(guī)模設(shè)為6。局部提高算法的終止規(guī)則為搜索4次。

5.2 結(jié)果分析

從圖3、圖4和表3可以看出，無論對于需調(diào)度弧段數(shù)（編碼長度）達256的場景1還是588的場景2，GASS的求解質(zhì)量都要遠遠好于SGA。如果不在SGA的搜索過程中加入SS的搜索結(jié)果，則SGA的搜索效果很大程度上取決于初始種群的性能，在絕大多數(shù)情況下，其搜索到的最優(yōu)解只能在初始最優(yōu)解的基礎(chǔ)上略有提高。相比而言，加入SS解后（SS算法在整個搜索過程中能獲得的最優(yōu)值分別為0.3和0.2857），GASS能在其基礎(chǔ)上搜索到更好的解，從而使得算法搜索優(yōu)良解的能力和求解穩(wěn)定性得到進一步加強。

作為對比，兩個場景及對應(yīng)的任務(wù)需求使用衛(wèi)星調(diào)度中經(jīng)典的FIFO（First In First Out， FIFO）算法進行求解，該算法將所有可用可見弧段按起始時間升序排序后，依次將弧段分配給對應(yīng)需求。效果如圖所示。需要指出的是，測控任務(wù)加權(quán)滿足率是一個面向全部任務(wù)需求的指標(biāo)，場景1的20個任務(wù)需求使用FIFO算法調(diào)度的加權(quán)滿足率是0，而場景2的35個任務(wù)需求使用FIFO調(diào)度的結(jié)果是0.1429，原因在于雖然場景2的前20個需求也都沒有得到滿足，但后面15個需求中有5個需求得到了滿足。

由于SS算法本身在Refset更新過程中需要反復(fù)評估個體的目標(biāo)值，會占用較多時間，且在SGA的每次迭代中都有SS進行，所以導(dǎo)致GASS整體時間開銷較大，具體數(shù)據(jù)如表3所示。在一些大規(guī)模問題的求解中，可以通過適當(dāng)控制SS的使用時機和次數(shù)來減小時間開銷。

從算法運行情況來看，初始種群中個體適應(yīng)度整體上比Refset中解的目標(biāo)值要小，而SS在搜索過程中除搜索到的最優(yōu)解可能發(fā)生變化外，Refset中個體的目標(biāo)值整體變化不大，進化一定代數(shù)后，種群中的個體的適應(yīng)度將與Refset中個體適應(yīng)度接近，此時，Refset的作用更大地體現(xiàn)于為種群提供多樣化的個體。

需要說明的是算法求得的測控任務(wù)加權(quán)滿足率整體較低，原因在于模型的約束較強，尤其是最小最大測控間隔時間的要求，受地面測站位置的限制，衛(wèi)星的實際可用時間窗口本身就無法滿足其要求，因此，滿足情況較差。如果所有需求沒有此約束，則目標(biāo)值可達92%。這說明現(xiàn)有測控資源的配置與衛(wèi)星需求的滿足之間還存在較大差距。

6 結(jié) 論

實驗結(jié)果表明，本文提出的基于分散搜索的混合遺傳算法在求解的質(zhì)量上要優(yōu)于簡單的遺傳算法和經(jīng)典的啟發(fā)式算法，但是，由于在每代進化中增加了分散搜索的工作，導(dǎo)致其計算時間要長于簡單遺傳算法。雖然本文僅在所建模型上對算法性能進行了試驗，但從算法的設(shè)計理念可以看出，算法也具有普遍的適用性，尤其對多峰和欺騙性強的問題，具有相對優(yōu)勢，可作進一步研究。

參考文獻

[1] 陳峰， 武小悅. 基于正交設(shè)計的多星測控調(diào)度協(xié)同進化代表個體選擇[J]. 小型微型計算機系統(tǒng)， 2010，31（8）：1582-1586.

[2] BARBULESCU L，HOWE A E， WHITLEY L D. Understanding algorithm performance on an oversubscribed scheduling application[J]. Artificial Intelligence Research， 2006， 27（1）：577-615.

[3] BARBULESCU L. Scheduling space-ground communication for the air force satellite control network[J]. Journal of scheduling， 2004， 7（1）：7-34.

[4] 凌曉冬，武小悅. 一種求解多星測控調(diào)度問題的啟發(fā)式算法[J]. 兵工自動化， 2008， 27（1）：71-73.

[5] PARISH S A. A genetic algorithm approach to automating satellite range scheduling[D].USA： Air Force Institute of Technology， 1994.

[6] BARBULESCU L，HOWE A，WATSON J P. Satellite range scheduling： A comparison of genetic， heuristic and local search[C]. Proceedings of the 7th International Conference on Parallel ProblemSolving From Nature. Berlin：Springer， 2002：611-620.

[7] Zhang Na， Feng Zuren， Feng Yuanjing. An optimization model for multisatellite resources scheduling[C]. Proceedings of the 6th World Congress on Intelligent Control and Automation. Dalian， China， 2006：7400-7404.

[8] 李敏強，寇紀淞. 遺傳算法的模式欺騙性分析[J]. 中國科學(xué)（E輯），2002， 32（1）：95-102.

[9] NOORUL HAQ A，SARAVANAN M，VIVEKRAJ A R. A scatter search approach for general flowshop scheduling problem[J]. Int J Adv Manuf Technol， 2007， 31（7-8）：731-736.

[10]趙 強， 張鵬飛， 孫立鐫. 利用分散搜索算法實現(xiàn)受時延約束的多播路由[J]. 軟件， 2011，32（11）：13-16.

[11]NOWICHI E，SMUTNICHI C. Some aspects of scatter search in the flowshop problem[J]. European Journal of Operational Research， 2005， 169（2）：654-666.

[12]TONG Kena ， XU Kelin ， ZHENG Yongqian. Sequencing mixed-model flexible assembly lines with variable launching intervals[J]. Journal of Shanghai Jiaotong University（Science）， 2013， 18（4）： 460-467.

[13]AlvarezValdes R， CRESPO E， TAMARIT J M. A scatter search algorithm for project scheduling under partially renewable resources[J]. Journal of Heuristics 2006， 12（1-2）：95-113.

[14]GLOVER F. Heuristics for integer programming using surrogate constraints[J]. Decision Sciences， 1977， 8（1）：156-166.

[15]GLOVER F. A template for scatter search and path relinking， In Lecture Notes in Computer Science， Hao J K， Lutton E， and Ronald E， Editors. Berlin Springer， 1998：13-54.

[16]MARTI R. Scatter searchwellsprings and challenges[J]. European Journal of Operational Research， 2006， 169（2）：351-358.

[17]CAMPOS V， GLOVER F，LAGUNA M. An experimental evaluation of a scatter search for the linear ordering problem[J]. Journal of Global Optimization， 2001， 21（4）：397-414.

[18]MARTI R，LAGUNA M，GLOVER F. Principles of scatter search[J]. European Journal of Operational Research， 2006， 169（2）：359-372.

[19]BARBULESCU L，HOWE A E， WHITLEY L D. AFSCN scheduling： How the problem and solution have evolved[J]. Mathematical and Computer Modelling， 2006， 43（9-10）：1023-1037.

[20]SARAVANAN M，NOORUL HAQ A. Evaluation of scatter-search approach for scheduling optimization of flexible manufacturing systems[J]. Int J Adv Manuf Technol， 2008， 38（9-10）：978-986.