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

馬冬青，王蔚

1.華北計(jì)算技術(shù)研究所，北京 100083

2.太極計(jì)算機(jī)股份有限公司，北京 100083

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

馬冬青1，王蔚2

1.華北計(jì)算技術(shù)研究所，北京 100083

2.太極計(jì)算機(jī)股份有限公司，北京 100083

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

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

1 引言

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

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

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

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

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

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

（1）活動(dòng)

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

（2）資源

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 個(gè)體染色體

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

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

3.2 種群

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

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

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

3.3 適應(yīng)度

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

在選擇及評(píng)價(jià)個(gè)體時(shí)，均用到適應(yīng)度的計(jì)算。

3.4 選擇操作

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

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

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

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

其中，i為個(gè)體排名。

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

（1）根據(jù)適應(yīng)度對(duì)個(gè)體進(jìn)行排序，適應(yīng)度最好的排在最先。

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

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

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

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

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

3.5 交叉操作

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

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

交叉操作的具體步驟是：

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

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

（3）采用類似方法，構(gòu)造子代個(gè)體2。

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

3.6 變異操作

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

變異操作具體步驟是：

（1）隨機(jī)抽取染色體中的兩個(gè)基因位置。

（2）將這兩個(gè)位置的基因進(jìn)行對(duì)換，形成新的個(gè)體。

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

3.7 爬山操作

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

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

4 實(shí)驗(yàn)驗(yàn)證

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

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

表2 實(shí)驗(yàn)樣本地面站參數(shù)

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

表3 實(shí)驗(yàn)結(jié)果

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

5 結(jié)束語(yǔ)

通過分析和實(shí)驗(yàn)驗(yàn)證，得出如下結(jié)論：

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

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

[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版.北京：清華大學(xué)出版社，2007.

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

[5]玄光南，程潤(rùn)偉.遺傳算法與工程優(yōu)化[M].北京：清華大學(xué)出版社，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—），女，高工，研究領(lǐng)域?yàn)楹教鞙y(cè)控軟件，衛(wèi)星應(yīng)用；王蔚（1973—），男，工程師，研究領(lǐng)域?yàn)楣こ虄?yōu)化。E-mail：ma_dq@yahoo.com.cn

2012-05-04

2012-06-19

1002-8331（2014）06-0246-04