基于優先排序與粒子群優化的裝備保障任務規劃方法

彭鵬菲，于錢，李啟元（海軍工程大學電子工程學院，湖北武漢430033）

?

基于優先排序與粒子群優化的裝備保障任務規劃方法

彭鵬菲，于錢，李啟元
（海軍工程大學電子工程學院，湖北武漢430033）

摘要：針對裝備保障任務規劃過程中保障資源占用沖突及保障任務邏輯關系約束的實際問題，構建基于任務優先排序的解空間模型，并進一步提出基于優先排序與改進粒子群優化的裝備保障任務規劃方法。該方法將分解后的保障任務按照其重要性和邏輯順序進行優先排序，并根據排序結果對粒子群優化算法得到的任務與資源匹配解空間進行調整，以解決資源占用沖突和邏輯順序問題。為保證每次迭代后的粒子為可行解，提出不可行粒子的多維異步處理機制，提高了粒子群優化算法的搜索效率。通過實例應用仿真分析，驗證了該方法在裝備保障任務規劃中的有效性和優越性。

關鍵詞：兵器科學與技術；裝備保障；任務規劃；優先排序；粒子群優化；異步處理

0　引言

裝備保障方案是指依據裝備使用特點和上級保障決心，以完成保障任務及實施相應措施的基本設想［1-2］。其中，裝備保障力量的編成及部署是裝備保障方案的核心內容，關鍵問題是裝備保障任務的規劃，即保障任務與保障資源間的匹配。裝備保障任務由裝備保障部門根據保障需求來確定，裝備保障資源是指保障作戰行動所需要的彈藥、裝備、人員等［3］。信息化條件下，保障任務屬性、保障資源屬性、保障時限和保障環境等多種因素均會影響到裝備保障任務規劃。因此，運用更加有效的保障任務規劃方法能夠進一步優化裝備保障方案，縮短響應時間，對實現裝備保障的精確化、信息化及智能化具有重要意義。

對于任務規劃問題的解決通常有兩類方法：第一類方法是致力于尋找最優解的精確求解方法，通常包括整數規劃、分支定界法以及枚舉法［4］，這類方法求解中占用大量計算機內存，并且求解時間較長［5］，不適用于問題規模較大、約束復雜、實時性強的任務規劃問題。第二類方法是啟發式方法，包括各類規劃表算法［6-7］以及蟻群算法、遺傳算法［8-9］等。啟發式方法基于直觀以及經驗構造，在可以接受的時間與空間開銷范圍內求解出約束之下問題的可行解。其中，粒子群優化算法具有編碼簡單、易于實現等特點，而且具有更強的全局搜索及快速收斂能力。

當前面臨的裝備保障任務規劃是一個典型的多約束離散優化問題，其任務間存在一定的邏輯關系，資源存在占用沖突。而傳統的粒子群優化算法只能完成任務與資源的匹配，但無法對資源占用沖突問題以及任務邏輯關系的約束進行很好處理。因此，本文提出采用任務優先排序的方法對粒子群優化算法求解的解空間進行規劃，以解決考慮資源占用沖突及任務邏輯關系的任務規劃問題；同時，引入了多維異步［10］的粒子調整處理機制，從而給出了基于優先排序與改進粒子群優化的裝備保障任務規劃方法，真正實現了裝備保障任務規劃與調配的科學性和有效性。

1　問題描述

裝備保障輔助決策中的關鍵問題是裝備保障任務的最優規劃［11］，而裝備保障任務規劃問題實質上是保障任務、保障資源和保障時間三者之間的匹配問題，而保障任務、保障資源及保障任務和保障資源之間通常存在著復雜的約束關系。在任務與資源的匹配過程中，通常須嚴格按照邏輯順序的先后進行資源分配；對于沒有嚴格邏輯關系的任務，則需要對任務進行優先排序，排序在前的優先占用資源，以解決資源占用沖突。

1.1保障任務、保障資源與保障時間

1）保障任務的分解及描述。根據保障任務的性質、保障裝備的類型以及保障地點，對保障任務進行分解，得到子任務。對保障任務分解的目的是保證分解后的子任務能夠由某個資源獨立完成，不需要其他資源參與。保障任務的數學模型為

式中：T表示整個裝備保障任務；Tj表示子任務，｛Tj｝表示子任務集合；n表示子任務的總數；GT= ｛G_S，G_B｝表示各個子任務之間的關系，G_S表示順序關系，G_B表示并發關系；ATj表示對應子任務的屬性，ATj=｛EqTj，MountTj，LocTj，StartTj，EndTj｝，EqTj表示裝備，MountTj表示裝備數量，LocTj表示保障任務的部署位置，StartTj表示任務的開始時間，EndTj表示任務的結束時間；（2）式表示原任務TOj分解后對應的子任務集為｛Tp，Tp+1，…，Tq｝，是子任務集｛Tj｝的子集；p、q為子任務的編號。

2）保障資源的分解及描述。將保障資源按照保障裝備類型、保障單位及保障性質進行分解，得到子資源。分解后的子資源均具有單獨承擔某項或某幾項子任務的能力，且均能同時被占用。保障資源的數學模型為

式中：Ci表示子資源；YCi表示子資源間的約束；ACi= ｛EqCi，UnitCi，LocCi，TimeCi，vCi，StateCi｝表示保障資源的屬性，屬性包括可保障裝備、保障單位、所在位置、單枚保障時間、機動速度和空閑狀態；（4）式表示原資源COi分解后對應的子資源集為｛Cp，Cp+1，…，Cq｝，是子資源集的子集。

3）保障時間的描述。子任務占用不同子資源，其執行時間是不同的。將子任務與子資源匹配的相應執行時間用矩陣表示為

式中：tcij表示任務Tj與資源 Ci匹配的執行時間，“tcij=—”表示對應的任務與資源不可匹配。

1.2基于優先排序的解空間構建

而對于一系列的任務，通過任務的優先排序可以對任務-資源的解空間在時間上進行規劃，為各任務分配執行時間，以解決裝備保障任務規劃的資源占用沖突問題。

1）解空間模型裝備保障任務規劃是求保障任務與保障資源匹配可行解的離散問題，其匹配結果可用一個0-1矩陣表示。n個任務與m個資源匹配的可行解矩陣為

式中：sij表示任務Tj和資源Ci之間的匹配結果，其取值為1表示任務Tj占用資源Ci，0表示任務Tj未占用資源Ci.S矩陣的各列表示任務被執行情況，即表示任務被執行。S矩陣的各行表示資源被占用的情況，在某一時刻：，表示資源空閑；，表示資源被占用；，表示資源占用發生沖突。可行解矩陣中每個任務與資源的匹配是可行的，即資源可以滿足任務的執行。在（6）式中，對于每一個具體的可行解矩陣，各子任務的執行時間timeTj是確定的，但子任務的開始時間和結束時間是未知的。在可行解矩陣已知的情況下，為了求解任務的開始時間和結束時間，還需要對任務與資源匹配的解空間在時序上進行調整。約束條件為

式中：ΩCd表示在資源Cd上發生占用沖突的任務集合，d為資源編號；StartTa和 EndTa分別為子任務 Ta的開始時間和結束時間，其執行的起止時間表示為［StartTa，EndTa］（其中EndTa=StartTa+timeTa），其他子任務起止時間的表示方式與Ta相同；a、b為子任務的編號。（6）式的意義是：同一時刻不存在多個子任務占用一個資源；另外，對于帶有順序關系的子任務Ta和Tb，其邏輯順序為Ta→Tb.根據其順序關系，解空間按照（8）式約束進行規劃：

通過調整任務執行的起止時間對解空間進行規劃，直至滿足（7）式和（8）式的約束條件，最終解空間模型為

（9）式意義為：任務Ta在時間段［StartTa，EndTa］被資源Cd執行。

2）優先排序。要滿足（7）式和（8）式的約束條件，需要對子任務進行優先排序，排序包括兩個方面：1）資源占用沖突時子任務的優先順序；2）子任務執行先后的邏輯順序。根據子任務的排序對解空間進行時序規劃，即排序在前的子任務優先占用沖突資源，且具有邏輯順序的子任務要嚴格按照時序關系占用資源。由于任意子任務間都有可能出現資源占用沖突的情況，因此需要對所有子任務進行優先排序，各子任務優先排序表為

式中：aj表示任務的序號，序號越靠前表示該任務的優先級越高。對于帶有順序關系的子任務，必須嚴格按照其邏輯先后的順序執行，具有強制性。為了計算和表示方便，對于（10）式的任務優先排序需要根據子任務的邏輯順序進行調整，使其優先順序與邏輯順序相一致。調整后得到的優先排序表為

式中：pj表示任務的序號，意義同aj.對于所有的子任務在發生資源占用沖突的情況下，對其時間分配進行調整。對于具有邏輯順序關系的子任務，在時間分配上還應強制其符合邏輯順序要求，如（8）式。

2　基于優先排序與改進粒子群優化的裝備保障任務規劃

裝備保障任務規劃的目的是針對現有保障任務對保障資源進行編成和部署［11］。結合裝備保障任務規劃的數學模型，對傳統離散粒子群優化算法進行了適應性改進：1）采用多維異步的處理機制調整粒子的位置，保證每一次迭代粒子的可行性，即資源與任務之間可匹配；2）對于解矩陣中的資源占用沖突情況和子任務邏輯順序關系約束，則通過優先排序的方法使各子任務按照一定的順序占用資源。經過改進的粒子群優化算法能夠實現保障任務和保障資源在時間上的最優規劃，具體步驟如下：

1）粒子編碼。每個粒子表示任務與資源匹配的一個解，根據（6）式中的解矩陣S構建粒子：用矩陣各列的行標作為粒子的各個維，粒子各維表示的意義為各個子任務所占用的資源序號。粒子k的位置和速度數學表示為

式中：xkj（t）∈［1，2，…，m］表示t時刻第k個粒子、第j個子任務在資源序列（共m個資源）中的位置；vkj（t）表示相應粒子的速度。

2）初始化。粒子群的初始化實際上是對每個粒子的位置和速度的初始化［12］。對粒子k位置的初始化實質上是給各個子任務選定一個資源，需要注意的是粒子的初始位置必須是可行的（任務與資源可匹配）；對粒子速度的初始化就是對進行第一次迭代的粒子各維移動距離的初始化；根據問題規模設置種群大小N；計算各粒子適應函數值，初始個體最優位置pBest和全局最優位置gBest.

3）粒子移動。移動速度的調整根據（14）式：

式中：ω是慣量權值；c1和c2為加速因子；r1和r2為［0，1］區間上的隨機數［13］。通過向量的計算對粒子速度的各維進行改變，為防止粒子過快地從搜索空間的一個區域飛向另一個區域，將粒子各維速度限制在［-vmax，vmax］范圍之內，即

式中：vmax應小于粒子活動范圍，這里活動范圍指可用子資源的個數。

4）位置的更新與越界修正。

式中：對粒子的位置坐標值進行四舍五入取整處理，對于越界的粒子，其越界的維取靠近的邊界值。

5）解空間異步處理。粒子的某個維不可行時，如果按照迭代速度繼續更新位置，將改變所有維，既降低了搜索效率，又容易錯過最優位置。針對這種情況，對粒子進行異步處理，只對不可匹配的粒子維進行改變，其他維保持不變。處理方法為：將速度矢量中將匹配可行的維置為0，將其他各維置為原值，按照重置的速度繼續更新粒子位置，直到粒子所有維的匹配均為可行。

6）基于優先排序的解空間規劃。

①對各子任務進行排序，并結合子任務邏輯順序生成子任務優先排序表，如（11）式。

②對于每一次迭代得到的任務與資源匹配的解矩陣，按照子任務的優先排序表依次對各子任務進行時間分配，每次分配后相應資源被占用的時間段將會被標記，后續的任務將不能在該時間段內占用此資源。為了減少資源處于空閑狀態的時間，對于資源占用沖突的子任務Ta和Tb（Ta優于Tb），做如下處理：

③對于帶有邏輯順序的子任務時間分配，首先按照②處理。然后判斷其是否滿足（8）式，對于不滿足的情況，對邏輯順序的子任務（Ta→Tb）按照（17）式進行處理，如果處理后發生資源占用沖突，則將該子任務排至該資源當前被占用時間段的最后，使其強制滿足時序要求，并避免資源占用沖突。

7）保障任務的時限約束。任務完成的時間必須小于給定的時限，總時限約束為mtot，單個時限約束表示為

式中：timeTa表示任務Ta的執行時間；mTa為任務Ta完成的時限約束。

8）計算適應值。考慮以最短保障時間為目標，通過計算所有子任務的最長結束時間來得到保障任務完成的最終時間。其適應度函數為

9）算法結束。通過迭代次數E判斷算法是否終止。經過E次迭代之后，獲取當前全局最優粒子，即為裝備保障任務規劃的最佳方案。

算法流程如圖1所示。

3　應用實例及對比分析

3.1應用實例

某個裝備保障任務描述為：在大規模聯合火力打擊海上作戰的背景下，我方出動多艘艦艇執行某海上作戰任務，需完成相應的各類技術準備、臨搶修等裝備保障任務，該任務可進一步分解為10個子任務：｛T1，T2，T3，T4，T5，T6，T7，T8，T9，T10｝，保障任務完成的總時限為mtot=18，單個子任務完成時限約束為mT8=5.其中的帶有順序關系的任務及其順序為T3→T4→T5.子任務的優先排序為P=（1，3，7，4，9，2，5，8，6，10）（數值為子任務的序號），可用保障資源分為12個子資源：｛C1，C2，C3，C4，C5，C6，C7，C8，C9，C10，C11，C12｝.分別使用粒子群優化和遺傳算法對實例進行對比仿真，各子任務對應各子資源的執行時間矩陣T_C（單位：h）為

圖1　算法流程圖Fig.1 Flow chart of algorithm

3.2算法初始化

1）改進粒子群優化算法初始化。各參數初始賦值如表1所示。粒子初始種群和初始速度由隨機方式產生，并滿足任務與資源的匹配限制。

表1　改進粒子群優化算法參數初始值表Tab.1 Initial value table of PSO algorithm parameters

2）遺傳算法初始化。實例中共有10個子任務和12個子資源，因此遺傳編碼的染色體有種基因。染色體編碼為0-1編碼［9］，對染色體進行隨機初始化，并將不合法的基因（任務與資源不能匹配）置為“0”。其余初始參數與粒子群優化算法相同。

3.3仿真結果與分析

1）對比仿真。對實例的應用求解過程進行數值仿真。圖2為本文中提出的粒子群優化算法得到的仿真結果，粒子群體經過85次迭代后收斂至最優適應值，為14.5 h；圖3為由遺傳算法得到的仿真結果，算法進化至150次獲得最優適應值為14.7 h.

由圖2和圖3對比可知，改進的粒子群優化算法收斂速度明顯快于遺傳算法，且優化效果更好（14.5 h＜14.7 h）。另外，在裝備保障任務規劃問題中，遺傳算法存在編碼復雜、計算速度慢等特點。仿真結果對比如表2所示。

圖2　改進粒子群優化算法最優適應值變化曲線Fig.2 Changing curve of PSO adaptive value

圖3　遺傳算法最優適應值變化曲線Fig.3 Changing curve of GA adaptive value

表2　仿真結果對比表Tab.2 Comparison of simulated results

2）裝備保障任務規劃方案。根據仿真計算結果，此時最優解粒子的位置gBest=［10 3 5 6 6 7 6 4 5 10］，gBest對應的最優解矩陣為

圖4是基于優先排序和粒子群優化算法得到的裝備保障任務規劃甘特圖，表示任務與資源在時序上的分配結果。

圖4　裝備保障任務規劃甘特圖Fig.4 Gantt chart of equipment support task planning

每次迭代后，都要基于優先排序對匹配結果進行規劃。根據優化結果（見圖4）可得到：①子任務的執行時間滿足T3→T4→T5的邏輯順序；②T3和T9均占用資源C5，根據子任務優先排序表P=（1，3，7，4，9，2，5，8，6，10）（T3在前，T9在后）對兩個任務的執行時間進行解空間規劃，得到兩個任務執行的起止時間按照優先排序表錯開的匹配結果，解決了資源占用沖突的問題；③對于T1和T10均占用資源C10以及T4、T5和T7均占用資源C6的情況，均按照優先排序原則進行了合理規劃。

4　結論

本文針對裝備保障任務規劃的求解問題，對傳統的粒子群優化算法進行了適應性改進，通過引入多維異步處理機制提高了粒子群優化算法的搜索效率；同時，將任務優先排序思想與粒子群優化算法相結合，提出了基于優先排序和改進粒子群優化的裝備保障任務規劃方法，從而有效解決了裝備保障任務規劃中保障資源占用沖突問題和保障任務邏輯順序關系處理問題。結合具體的應用實例，將該方法與遺傳算法的求解過程及應用效果進行了相應的對比仿真求解與分析，從而進一步驗證了方法的有效性和優越性。仿真分析表明：提出的方法充分考慮了任務規劃的時序關系，通過優先排序解決了資源占用沖突問題，并與改進的粒子群優化算法相結合，能夠很好地解決裝備保障任務規劃及保障方案擬制過程中的關鍵問題，與基于遺傳算法的求解相比，具有更好的快速收斂性，應用簡捷，易于實現。

參考文獻（References）

［1］ 高飛，徐英，張英，等.基于軍事概念模型的裝備保障方案生成研究［J］.價值工程，2010，29（28）：112-113. GAO Fei，XU Ying，ZHANG Ying，et al.Equipment support plan evaluation software designing based on the military conceptual mode［J］.Value Engineering，2010，29（28）：112-113.（in Chinese）

［2］ 楊英杰，張柳，聶成龍，等.使用階段裝備保障方案評價研究［J］.火力與指揮控制，2015，40（10）：5-7. YANG Ying-jie，ZHANG Liu，NIE Cheng-long，et al.The evaluation research summary of equipment support concept in operational phase［J］.Fire Control&Command Control，2015，40（10）：5-7.（in Chinese）

［3］ 朱石堅.艦船裝備保障資源需求半結構化預測方法［J］.海軍工程大學學報，2015，27（4）：54-59. ZHU Shi-jian.Semi-structural prediction method study on support resources demand of warship equipment［J］.Journal of Naval University of Engineering，2015，27（4）：54-59.（in Chinese）

［4］ 李敏.資源約束下多項目調度問題遺傳算法研究［D］.杭州：浙江大學，2008. LI Min.Research on genetic algorithm of resource constrained multi-project scheduling problem［D］.Hangzhou：Zhejiang University，2008.（in Chinese）

［5］ 黃敏鎂，江濤.資源約束項目調度問題研究綜述［J］.科協論壇，2007（2）：45-46. HUANG Min-mei，JIANG Tao.Comprehensive description of resource constrained project scheduling problem［J］.Science& Technology Association Forum，2007（2）：45-46.（in Chinese）

［6］ Levchuk Y N，Levchuk G M，Pattipati K R.A systematic approach to optimize organizations operating in uncertain environments：design methodology and applications［C］//7th International Command and Control Research and Technology Symposium.Quebec City，QC，Canada：IC2I，2002：170-230.

［7］ Levchuk G M，Levchuk Y N，Luo J.Normative design of organizations-part I：mission planning［J］.IEEE Transactions on Systems，Man and Cybernetics，2002，32（3）：346-359.

［8］ 鄧向陽，張立民，黃曉冬.一種基于蟻群優化的裝備保障任務調度方法［J］.計算機工程，2013，39（2）：284-287. DENG Xiang-yang，ZHANG Li-min，HUANG Xiao-dong.An equipment support task scheduling method based on ant colony optimization［J］.Computer Engineering，2013，39（2）：284-287. （in Chinese）

［9］ 張杰勇，姚佩陽，周翔翔，等.基于DLS和GA的作戰任務-平臺資源匹配方法［J］.系統工程與電子技術，2012，34（5）：947-954. ZHANG Jie-yong，YAO Pei-yang，ZHOU Xiang-xiang，et al.Approach to operation task and platform resource matching based on DLS and GA［J］.System Engineering and Electronics，2012，34（5）：947-954.（in Chinese）

［10］ 陳君彥，齊二石，劉亮.多維異步隨機擾動的粒子群優化算法［J］.計算機應用，2009，29（12）：3267-3269. CHEN Jun-yan，QI Er-shi，LIU Liang.Particle swarm optimization algorithm with multi-dimensional asynchronism and stochastic disturbance［J］.Journal of Computer Applications，2009，29（12）：3267-3269.（in Chinese）

［11］ 張春潤，熊林偉，趙坤，等.裝備保障任務規劃系統體系結構研究［J］.中國管理信息化，2012，15（16）：55-57. ZHANG Chun-run，XIONG Lin-wei，ZHAO Kun，et al.Research on the system architecture of the equipment support task planning system［J］.China Management Informationization，2012，15（16）：55-57.（in Chinese）

［12］ 黃競偉，朱福喜，康立山.計算智能［M］.北京：科學出版社，2010. HUANG Jing-wei，ZHU Fu-xi，TANG Li-shan.Computational intelligence［M］.Beijing：Science Press，2010.（in Chinese）

［13］ 郭文忠，陳國龍.離散粒子群優化算法及其應用［M］.北京：清華大學出版社，2012. GUO Wen-zhong，CHEN Guo-long.Discrete particle swarm optimization algorithm and its application［M］.Beijing：Tsinghua U-niversity Press，2012.（in Chinese）

中圖分類號：TP301；E917

文獻標志碼：A

文章編號：1000-1093（2016）06-1082-07

DOI：10.3969/j.issn.1000-1093.2016.06.016

收稿日期：2015-10-14

基金項目：湖北省自然科學基金項目（2014EKB013）

作者簡介：彭鵬菲（1977—），男，副教授。E-mail：pengpengfei@126.com

A Planning Method of Equipment Support Task Based on Priority Ordering and Particle Swarm Optimization Algorithm

PENG Peng-fei，YU Qian，LI Qi-yuan
（College of Electronic Engineering，Naval University of Engineering，Wuhan 430033，Hubei，China）

Abstract：A solution space model based on task priority ordering is constructed according to the practical problem of support resource occupancy conflicts and logical relationship among support tasks in the process of equipment support task planning.A planning method of equipment support task based on priority ordering and improved particle swarm optimization is further proposed.In the proposed method，the decomposed support tasks are ordered by priority according to their importance and logical order.According to the sorted results，the task and the resource matching solution space obtained by the particle swarm optimization algorithm are adjusted for solving the problem of resource occupancy and logical sequence.A multi-dimensional asynchronous processing mechanism is proposed to ensure that the particles are feasible，so that the search efficiency of the particle swarm optimization algorithm is improved.The effectiveness and advantage of the method in the planning of equipment support tasks are verified by examples and contrastive simulation analysis.The method has broad application prospects in the field of equipment support assistant decision-making technology.

Key words：ordnance science and technology；equipment support；task planning；priority ordering；particle swarm optimization；asynchronous processing