中國電子科技集團公司第五十四研究所 尚希杰 馮陽 林曉勇 張超 趙超

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

1 問題分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 解決方案

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

2.1 任務(wù)模型

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

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

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

2.2 資源模型

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

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

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

2.3 算法模型

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

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

2.4 約束模型

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

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

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

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

3 實驗仿真

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

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

3.2 實驗結(jié)果分析

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

圖1 實驗仿真模擬圖Fig.1 Simulation diagram of experimental simulation

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

3.3 仿真實驗的可行性和有效性驗證

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

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

4 實驗結(jié)果分析

4.1 實驗結(jié)果

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

表1 實驗結(jié)果分析Tab.1 Analysis of experimental results

4.2 研究局限性和不足之處

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

5 結(jié)語

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