面向成像衛(wèi)星組網(wǎng)的群任務(wù)規(guī)劃方法探討

中國(guó)電子科技集團(tuán)公司第五十四研究所 尚希杰 馮陽(yáng) 林曉勇 張超 趙超

針對(duì)面向成像衛(wèi)星組網(wǎng)的群任務(wù)規(guī)劃問題，本文提出一種基于遺傳算法和貪心算法相結(jié)合的任務(wù)規(guī)劃方法。首先，通過(guò)分析衛(wèi)星組網(wǎng)中的成像任務(wù)特點(diǎn)，將任務(wù)劃分為多個(gè)子任務(wù)，并考慮到任務(wù)之間的時(shí)空約束關(guān)系。然后，利用貪心算法對(duì)子任務(wù)進(jìn)行初步規(guī)劃，以獲得一個(gè)較好的初始解。接著，采用遺傳算法對(duì)初步規(guī)劃結(jié)果進(jìn)行優(yōu)化，以獲得更優(yōu)的任務(wù)規(guī)劃方案。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了所提方法的有效性和可行性。

1 問題分析

1.1 成像衛(wèi)星組網(wǎng)中的群任務(wù)規(guī)劃問題

隨著成像衛(wèi)星的數(shù)量逐漸增加，成像衛(wèi)星組網(wǎng)的任務(wù)規(guī)劃問題變得更加復(fù)雜。傳統(tǒng)的貪心算法在任務(wù)規(guī)劃方面表現(xiàn)出了較好的效果，但是由于其缺乏全局搜索能力，容易陷入局部最優(yōu)解。因此，需要一種能夠充分利用全局搜索能力，同時(shí)又能夠保持高效性的任務(wù)規(guī)劃算法[1]。為此，在本研究中提出了一種基于遺傳算法和貪心算法相結(jié)合的群任務(wù)規(guī)劃方法。在該方法中，首先利用遺傳算法對(duì)初始種群進(jìn)行選擇、交叉和變異等操作，以得到新的個(gè)體；然后，對(duì)于新生成的個(gè)體，采用貪心算法進(jìn)行局部搜索，以進(jìn)一步優(yōu)化個(gè)體的適應(yīng)度；最后，選擇適應(yīng)度最高的個(gè)體作為最優(yōu)解。該方法既能夠在全局范圍內(nèi)搜索任務(wù)規(guī)劃方案，同時(shí)又能夠保持高效性，避免陷入局部最優(yōu)解。

1.2 成像任務(wù)的特點(diǎn)和約束條件

成像任務(wù)具有以下幾個(gè)特點(diǎn)和約束條件：

（1）多源任務(wù)協(xié)同執(zhí)行：在多源任務(wù)協(xié)同執(zhí)行的情況下，成像衛(wèi)星需要對(duì)多個(gè)目標(biāo)進(jìn)行同時(shí)觀測(cè)，以提高任務(wù)效率。這意味著需要設(shè)計(jì)一種群任務(wù)規(guī)劃方案，對(duì)所有的任務(wù)進(jìn)行合理的分配和調(diào)度，以達(dá)到最佳的任務(wù)執(zhí)行效果。

（2）多級(jí)任務(wù)優(yōu)先級(jí)約束：成像任務(wù)一般是分為多級(jí)優(yōu)先級(jí)的，例如，在地震預(yù)警任務(wù)中，對(duì)于即將到來(lái)的地震事件，需要對(duì)不同區(qū)域進(jìn)行不同級(jí)別的觀測(cè)，因此，需要對(duì)任務(wù)進(jìn)行優(yōu)先級(jí)排序和分配。

（3）任務(wù)執(zhí)行時(shí)間約束：成像任務(wù)在執(zhí)行時(shí)，需要考慮任務(wù)執(zhí)行時(shí)間的限制。這是因?yàn)槿蝿?wù)執(zhí)行時(shí)間長(zhǎng)短直接影響著成像衛(wèi)星資源的利用效率和任務(wù)執(zhí)行效果。如果任務(wù)執(zhí)行時(shí)間過(guò)長(zhǎng)，將會(huì)影響其他任務(wù)的執(zhí)行時(shí)間。

（4）資源約束：成像任務(wù)需要考慮衛(wèi)星資源的限制，如天線、電源等方面的約束。因此，對(duì)于任務(wù)的調(diào)度和分配需要考慮衛(wèi)星資源的利用率，以確保衛(wèi)星資源的充分利用。

（5）能耗控制約束：在衛(wèi)星的能耗控制方面，也需要對(duì)任務(wù)的執(zhí)行時(shí)間和頻率進(jìn)行合理的安排。如果衛(wèi)星的能耗控制不當(dāng)，將會(huì)影響衛(wèi)星的壽命和任務(wù)執(zhí)行效果。

總之，成像任務(wù)的特點(diǎn)和約束條件是復(fù)雜多樣的。因此，在成像任務(wù)中，如何設(shè)計(jì)一種合理的群任務(wù)規(guī)劃方案，對(duì)任務(wù)進(jìn)行合理的分配和調(diào)度，以達(dá)到最佳的任務(wù)執(zhí)行效果，是一個(gè)具有挑戰(zhàn)性的問題[2]。在實(shí)際應(yīng)用中，需要綜合考慮各種因素，并根據(jù)具體情況進(jìn)行相應(yīng)的任務(wù)調(diào)度和分配，以保證成像衛(wèi)星的最優(yōu)利用和任務(wù)執(zhí)行效率的最大化。

1.3 群任務(wù)規(guī)劃中存在的挑戰(zhàn)和難點(diǎn)

群任務(wù)規(guī)劃在成像衛(wèi)星組網(wǎng)中具有廣泛的應(yīng)用前景，但也存在著一些挑戰(zhàn)和難點(diǎn)，主要體現(xiàn)在如下幾點(diǎn)：

（1）群任務(wù)規(guī)劃中面臨的主要挑戰(zhàn)之一是任務(wù)之間的關(guān)聯(lián)性。在成像衛(wèi)星組網(wǎng)中，各個(gè)衛(wèi)星需要協(xié)同完成任務(wù)，而不同任務(wù)之間可能存在著復(fù)雜的依賴關(guān)系，如任務(wù)之間的時(shí)序限制、空間約束、資源共享等。因此，如何考慮任務(wù)之間的關(guān)聯(lián)性，合理分配任務(wù)執(zhí)行順序和資源，是群任務(wù)規(guī)劃中必須解決的問題。

（2）群任務(wù)規(guī)劃中還面臨著資源分配和能耗控制的問題。在成像衛(wèi)星組網(wǎng)中，衛(wèi)星資源受限，如何在有限的資源下合理分配任務(wù)，并保證任務(wù)的質(zhì)量和效率，是一個(gè)具有挑戰(zhàn)性的問題。此外，成像衛(wèi)星組網(wǎng)中的衛(wèi)星數(shù)量較多，同時(shí)衛(wèi)星之間需要相互通信和協(xié)調(diào)，衛(wèi)星的通信和數(shù)據(jù)傳輸也將消耗大量能量。因此，如何控制衛(wèi)星的能耗，以保證衛(wèi)星系統(tǒng)的長(zhǎng)期穩(wěn)定運(yùn)行，也是一個(gè)需要解決的難點(diǎn)。

（3）群任務(wù)規(guī)劃中需要兼顧任務(wù)執(zhí)行效率和成像質(zhì)量?jī)蓚€(gè)指標(biāo)。在成像衛(wèi)星組網(wǎng)中，任務(wù)執(zhí)行效率和成像質(zhì)量往往是相互矛盾的。例如，在某些情況下，為了獲得更高的成像質(zhì)量，需要增加任務(wù)執(zhí)行時(shí)間或增加衛(wèi)星之間的通信次數(shù)，這將導(dǎo)致任務(wù)執(zhí)行效率的降低。因此，如何在任務(wù)執(zhí)行效率和成像質(zhì)量之間取得平衡，是群任務(wù)規(guī)劃中需要解決的另一個(gè)難點(diǎn)。

（4）群任務(wù)規(guī)劃中的算法設(shè)計(jì)也是一個(gè)需要解決的難點(diǎn)。在成像衛(wèi)星組網(wǎng)中，任務(wù)數(shù)量較大，而且任務(wù)之間的關(guān)聯(lián)性較強(qiáng)，因此如何設(shè)計(jì)高效、可擴(kuò)展的算法，以求得最優(yōu)的任務(wù)規(guī)劃方案，是群任務(wù)規(guī)劃中需要克服的另一個(gè)難點(diǎn)。目前，遺傳算法、貪心算法、模擬退火算法等已被廣泛應(yīng)用于群任務(wù)規(guī)劃中，但如何針對(duì)具體問題選擇合適的算法，還需要進(jìn)一步的研究和探索。

2 解決方案

面向成像衛(wèi)星組網(wǎng)的群任務(wù)規(guī)劃方法研究是一個(gè)復(fù)雜的問題，需要建立多個(gè)模型來(lái)描述和解決。

2.1 任務(wù)模型

任務(wù)模型主要用于描述50 個(gè)成像任務(wù)的類型和性質(zhì)，是任務(wù)規(guī)劃的基礎(chǔ)。具體而言，可以將50 個(gè)任務(wù)分為若干類別，如對(duì)地面上的某些點(diǎn)或區(qū)域進(jìn)行成像、對(duì)某些目標(biāo)的跟蹤和觀測(cè)等。每個(gè)任務(wù)可以用一個(gè)三元組(x,y,z)來(lái)表示，其中x表示任務(wù)類型，y表示任務(wù)位置，z表示任務(wù)執(zhí)行時(shí)間。任務(wù)模型還需要考慮一些約束條件，如任務(wù)之間的優(yōu)先級(jí)關(guān)系、任務(wù)執(zhí)行的時(shí)序關(guān)系等。這些約束條件可以用一個(gè)任務(wù)圖G=(V,E)來(lái)描述，其中V表示任務(wù)集合，E表示任務(wù)之間的優(yōu)先級(jí)和時(shí)序關(guān)系。例如，如果任務(wù)i必須在任務(wù)j之前執(zhí)行，可以用一個(gè)有向邊(i,j)來(lái)表示。

成像衛(wèi)星拍攝任務(wù)規(guī)劃問題中的優(yōu)化模型，即線性規(guī)劃模型如式（1）所示：

其中，x是決策變量向量，c是目標(biāo)函數(shù)系數(shù)向量，A是約束系數(shù)矩陣，b是約束條件向量。該模型可以通過(guò)優(yōu)化算法得到最優(yōu)的衛(wèi)星拍攝任務(wù)規(guī)劃方案。

2.2 資源模型

資源模型主要用于描述10 顆衛(wèi)星的類型、載荷和性能參數(shù)，是任務(wù)規(guī)劃的另一個(gè)基礎(chǔ)。具體而言，可以將10 顆衛(wèi)星分為若干類別，如低軌衛(wèi)星和高軌衛(wèi)星。每個(gè)衛(wèi)星可以用一個(gè)四元組(t,h,p,c)來(lái)表示，其中t表示衛(wèi)星類型，h表示衛(wèi)星軌道高度，p表示衛(wèi)星載荷，c表示衛(wèi)星能耗和資源限制。資源模型還需要考慮一些約束條件，如衛(wèi)星之間的通信和協(xié)作關(guān)系、衛(wèi)星載荷的重疊和沖突等。這些約束條件可以用一個(gè)資源圖G'=(V',E')來(lái)描述，其中V'表示衛(wèi)星集合，E'表示衛(wèi)星之間的通信和協(xié)作關(guān)系。例如，如果衛(wèi)星i需要和衛(wèi)星j進(jìn)行通信或協(xié)作，可以用一個(gè)無(wú)向邊(i,j)來(lái)表示。

衛(wèi)星群任務(wù)分配問題中的任務(wù)分配模型，即整數(shù)線性規(guī)劃模型如式（2）所示：

其中，xi,j表示第i個(gè)衛(wèi)星執(zhí)行第j個(gè)任務(wù)的二元變量，fi,j是第i個(gè)衛(wèi)星執(zhí)行第j個(gè)任務(wù)所獲得的收益。該模型可以通過(guò)整數(shù)規(guī)劃算法得到衛(wèi)星群任務(wù)的最優(yōu)分配方案。

2.3 算法模型

算法模型主要用于描述遺傳算法和貪心算法的實(shí)現(xiàn)細(xì)節(jié)和參數(shù)設(shè)置。具體而言，遺傳算法包括選擇、交叉和變異等操作，需要設(shè)置適當(dāng)?shù)膮?shù)如種群大小、交叉概率和變異概率等。貪心算法包括局部搜索和全局搜索兩個(gè)階段，需要設(shè)置適當(dāng)?shù)乃阉鞑呗院蛦l(fā)式函數(shù)。

為了提高算法的效率和準(zhǔn)確性，可以將算法模型、任務(wù)模型和資源模型相結(jié)合，構(gòu)建一個(gè)任務(wù)-資源-算法模型。具體而言，該模型可以將任務(wù)和衛(wèi)星分配到不同的種群中，通過(guò)遺傳算法進(jìn)行優(yōu)化求解，得到最優(yōu)的任務(wù)分配方案。同時(shí)，也可以使用貪心算法進(jìn)行局部搜索和全局搜索，以進(jìn)一步優(yōu)化任務(wù)分配方案。

2.4 約束模型

約束模型主要用于描述任務(wù)和資源之間的約束關(guān)系。具體而言，約束模型可以包括以下幾個(gè)方面：（1）時(shí)間窗口約束：對(duì)于每個(gè)任務(wù)，都有一個(gè)時(shí)間窗口，表示任務(wù)必須在該時(shí)間窗口內(nèi)完成。這些時(shí)間窗口可以用一個(gè)時(shí)間表來(lái)描述，每個(gè)時(shí)間表包含多個(gè)時(shí)間段，表示任務(wù)可以在這些時(shí)間段內(nèi)完成。（2）衛(wèi)星載荷約束：每個(gè)衛(wèi)星只能同時(shí)執(zhí)行有限的載荷，因此需要對(duì)衛(wèi)星的載荷進(jìn)行限制和管理。具體而言，可以設(shè)置每個(gè)衛(wèi)星的載荷數(shù)量和類型，以保證衛(wèi)星的資源得到最優(yōu)利用。（3）任務(wù)執(zhí)行順序約束：對(duì)于一些任務(wù)，必須按照特定的順序執(zhí)行，否則可能會(huì)出現(xiàn)沖突或誤差。因此，需要設(shè)置任務(wù)執(zhí)行的順序和優(yōu)先級(jí)，以保證任務(wù)的準(zhǔn)確性和效率。（4）衛(wèi)星通信約束：衛(wèi)星之間需要進(jìn)行通信和協(xié)作，因此需要設(shè)置衛(wèi)星之間的通信頻率和協(xié)作方式，以保證衛(wèi)星之間的信息交流和資源共享。

成像衛(wèi)星調(diào)度問題中的排隊(duì)論模型，即M/M/1 排隊(duì)模型如式（3）所示：

其中，λ是任務(wù)到達(dá)率，μ是處理速率，ρ是系統(tǒng)繁忙因子，Pn是系統(tǒng)中有n個(gè)任務(wù)時(shí)的平穩(wěn)狀態(tài)概率。該模型可以用來(lái)分析成像衛(wèi)星調(diào)度系統(tǒng)的性能指標(biāo)，如平均等待時(shí)間和平均系統(tǒng)時(shí)間。

以上約束模型可以用數(shù)學(xué)形式來(lái)表示，并與任務(wù)模型、資源模型和算法模型相結(jié)合，構(gòu)建一個(gè)完整的任務(wù)規(guī)劃模型。該模型可以通過(guò)遺傳算法、貪心算法等多種優(yōu)化方法進(jìn)行求解，得到最優(yōu)的任務(wù)分配方案，從而實(shí)現(xiàn)成像衛(wèi)星組網(wǎng)的群任務(wù)規(guī)劃[3]。

3 實(shí)驗(yàn)仿真

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)設(shè)置

本文采用Python 語(yǔ)言實(shí)現(xiàn)群任務(wù)規(guī)劃方法，并在Windows 10 操作系統(tǒng)上進(jìn)行實(shí)驗(yàn)仿真。實(shí)驗(yàn)所需數(shù)據(jù)主要包括成像衛(wèi)星的任務(wù)需求和資源信息，以及衛(wèi)星之間的通信和協(xié)作約束條件等[4]。在實(shí)驗(yàn)中，設(shè)置了50 個(gè)成像任務(wù)和10 顆衛(wèi)星，其中每個(gè)衛(wèi)星可以執(zhí)行5 個(gè)任務(wù)。同時(shí)，考慮了衛(wèi)星之間的通信和協(xié)作約束條件，以確保任務(wù)的正確執(zhí)行和協(xié)調(diào)。

3.2 實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)中，采用遺傳算法和貪心算法相結(jié)合的方法來(lái)進(jìn)行群任務(wù)規(guī)劃和優(yōu)化求解。首先采用遺傳算法對(duì)初始種群進(jìn)行選擇、交叉和變異等操作，以得到新的個(gè)體；然后，對(duì)新生成的個(gè)體，采用貪心算法進(jìn)行局部搜索，以進(jìn)一步優(yōu)化個(gè)體的適應(yīng)度；最后，選擇適應(yīng)度最高的個(gè)體作為最優(yōu)解。在實(shí)驗(yàn)中，將任務(wù)執(zhí)行效率和成像質(zhì)量的平衡作為評(píng)價(jià)指標(biāo)，用于衡量任務(wù)規(guī)劃方案的優(yōu)劣。同時(shí)，還考慮了資源分配和能耗控制等因素，以確保任務(wù)規(guī)劃的可行性和有效性。

圖1 實(shí)驗(yàn)仿真模擬圖Fig.1 Simulation diagram of experimental simulation

基于以上參數(shù)和概念，可以嘗試建立一個(gè)簡(jiǎn)單的模型來(lái)解釋實(shí)驗(yàn)結(jié)果。假設(shè)所有50 個(gè)成像任務(wù)都是對(duì)地面上的某些點(diǎn)進(jìn)行成像，并且所有10 顆衛(wèi)星都是低軌衛(wèi)星，軌道高度在1000 公里左右，同時(shí)假設(shè)每個(gè)衛(wèi)星搭載了一個(gè)光學(xué)相機(jī)，可以計(jì)算每個(gè)任務(wù)的成像質(zhì)量和執(zhí)行時(shí)間。通過(guò)遺傳算法和貪心算法的組合，可以找到一組最佳的任務(wù)規(guī)劃方案，使得總的成像質(zhì)量和執(zhí)行時(shí)間達(dá)到一個(gè)最優(yōu)的平衡。最終得到的最優(yōu)方案是，在10 顆衛(wèi)星上分別安排5 個(gè)任務(wù)，每個(gè)衛(wèi)星上的任務(wù)執(zhí)行時(shí)間和成像質(zhì)量均衡，任務(wù)間的調(diào)度和資源分配也得到了優(yōu)化，從而實(shí)現(xiàn)了最佳的任務(wù)執(zhí)行效率和成像質(zhì)量的平衡。需要注意的是，在實(shí)際應(yīng)用中，成像任務(wù)的類型、衛(wèi)星的類型和載荷類型等參數(shù)都可能發(fā)生變化，因此需要根據(jù)具體情況調(diào)整模型和算法。另外，任務(wù)規(guī)劃涉及到的因素很多，如任務(wù)調(diào)度、資源分配、能耗控制等，需要綜合考慮和優(yōu)化，才能得到最佳的任務(wù)規(guī)劃方案[5]。

3.3 仿真實(shí)驗(yàn)的可行性和有效性驗(yàn)證

本文所提出的群任務(wù)規(guī)劃方法在實(shí)驗(yàn)中得到了較好的效果，說(shuō)明該方法具有較好的可行性和有效性。具體來(lái)說(shuō)，該方法能夠充分考慮任務(wù)之間的相關(guān)性和約束條件，以及資源分配和能耗控制等實(shí)際問題，從而得到更優(yōu)的任務(wù)規(guī)劃方案。另外，本文所采用的實(shí)驗(yàn)環(huán)境和數(shù)據(jù)設(shè)置也能夠滿足實(shí)際應(yīng)用的需求。在實(shí)際應(yīng)用中，可以根據(jù)具體情況進(jìn)行調(diào)整和優(yōu)化，以進(jìn)一步提高任務(wù)規(guī)劃的效率和精度。

總之，本文所提出的群任務(wù)規(guī)劃方法具有較好的可行性和有效性，能夠?yàn)槌上裥l(wèi)星等多任務(wù)系統(tǒng)的規(guī)劃和優(yōu)化提供參考。在未來(lái)的研究中，還可以進(jìn)一步探究群任務(wù)規(guī)劃方法在不同情境下的表現(xiàn)，并結(jié)合機(jī)器學(xué)習(xí)等技術(shù)，實(shí)現(xiàn)更智能化的任務(wù)規(guī)劃和優(yōu)化。

4 實(shí)驗(yàn)結(jié)果分析

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

平衡指標(biāo)表示任務(wù)執(zhí)行效率和成像質(zhì)量的綜合指標(biāo)。在該實(shí)驗(yàn)中，綜合指標(biāo)為0.92，說(shuō)明該方法在任務(wù)規(guī)劃方面具有較好的表現(xiàn)，同時(shí)，資源分配和能耗控制也能夠得到有效的控制和管理。與傳統(tǒng)的貪心算法相比，該方法具有更優(yōu)的任務(wù)規(guī)劃方案，如表1 所示。

表1 實(shí)驗(yàn)結(jié)果分析Tab.1 Analysis of experimental results

4.2 研究局限性和不足之處

本研究雖然取得了一定的成果，但仍然存在一些局限性和不足之處：（1）本研究?jī)H采用了50 個(gè)任務(wù)和10顆衛(wèi)星的情況進(jìn)行實(shí)驗(yàn)測(cè)試，對(duì)于規(guī)模更大的任務(wù)規(guī)劃問題，該方法是否仍然有效尚需進(jìn)一步探究；（2）本研究的評(píng)價(jià)指標(biāo)僅考慮了任務(wù)執(zhí)行效率和成像質(zhì)量的平衡，而沒有考慮其他因素對(duì)任務(wù)規(guī)劃的影響，例如，時(shí)間成本、經(jīng)濟(jì)成本等；（3）在本研究中，貪心算法只用于對(duì)新生成的個(gè)體進(jìn)行局部搜索，對(duì)于遺傳算法生成的初始種群是否存在更好的優(yōu)化方法需要進(jìn)一步研究；（4）本研究中采用的遺傳算法和貪心算法并不是唯一可行的方法，也許存在其他更有效的方法，需要進(jìn)一步研究[6]。

5 結(jié)語(yǔ)

通過(guò)本研究，提出了一種基于遺傳算法和貪心算法相結(jié)合的群任務(wù)規(guī)劃方法，用于優(yōu)化衛(wèi)星任務(wù)執(zhí)行的效率和成像質(zhì)量。實(shí)驗(yàn)結(jié)果表明，該方法可以有效地提高任務(wù)規(guī)劃的效率和精度，達(dá)到了預(yù)期的效果，同時(shí)，在資源分配和能耗控制等方面也具有較好的表現(xiàn)。然而，本研究也存在一些局限性和不足之處，需要進(jìn)一步探索與完善。