基于可視化HPSO的無人機裝備維修任務調度*

沈延安，葉 霖

（陸軍炮兵防空兵學院，合肥 230031）

0 引言

軍用無人機是信息化高技術條件下具有高效費比、攻防兼備的新概念裝備，可用于目標指示、偵查校射、電子干擾、火力打擊等多種用途，目前已在各軍種得到廣泛應用。由于無人機系統［1］裝備組成復雜，備件類型多，且維修地點隨無人機分隊的任務機動實時變化，導致其裝備維修任務的路徑選擇［2-4］由時間、距離、地形、任務類別等諸條件決定，并視戰場環境適時調整，容易形成復雜的NP（Non-deterministic Polynomial，NP）問題，加大了無人機裝備維修保障任務的工作難度。

快速、準確的維修任務調度不僅能夠節省維修費用及時間，更能夠提高裝備的作戰效能，具有重要的研究意義。文獻［5］提出維修點重要度和資源保障度的概念，研究了戰時裝備維修資源的優化調度；文獻［6］采用并行過程的二階段非均勻緊急任務列表，解決了非均勻環境下的任務調度問題；文獻［7］采用混合內核仿真解決了非專用計算環境下的任務調配問題，雖然能夠解決特定環境下的任務規劃，但不能滿足軍用無人機裝備維修的特殊需求，且算法過程不夠自動化、智能化。

混合粒子群優化算法（Hybrid Particle Swarm Optimization，HPSO）是粒子群算法［8］的改進，具有參數設置靈活、收斂速度快、魯棒性好等特點，目前已被廣泛應用于各類工程實踐。董穎［9］較早進行了HPSO 方面的研究；陳漢武［10］、陳喜陽［11］分別將粒子群算法與遺傳算法、神經網絡相結合，拓展了HPSO 的應用領域；田軍［12］、葉文［13］、武善玉［14］等進一步采用離散化HPSO簡化編/解碼過程，解決了復雜條件下的任務調度問題，但對迭代過程的粒子的分布及運動特點不夠關注，使計算過程易陷入局部最優，限制進化速度。本文在離散化HPSO的基礎上，建立了以粒子鄰接距離為依據的濃度監控機制，結合動態圖像展示函數，實現可視的種群進化調控，利用改進的HPSO算法對無人機維修任務調度進行科學的決策支持。

1 無人機裝備維修任務調度問題系統分析

無人機裝備維修任務調度主要通過對維修任務進行計劃、協調和控制，實現維修資源的合理調配和使用，提高裝備保障的響應效率，力求以最短的時間，最少的消耗，獲得滿意的保障效果。

統觀目前軍用無人機系統，其維修保障任務從功能組成上講基本相同，相關維修任務具有以下普遍特征：1）裝備組成復雜，部件精密，維修技術需求較高；2）機動性強，為保證偵查校射和目標打擊的精度要求，需要實施大量的戰術機動，導致裝備維修任務在不同時間、不同任務階段實時動態變化。結合霍爾三維結構分析，明確無人機裝備維修任務調度問題的組成要素，如表1所示。

表1 無人機維修任務調度組成要素

因此，無人機維修任務調度需要隨時根據故障類型、任務分布及庫存情況，制定優化方案，其規劃空間維數較高、約束條件多、指標模糊性大，隨著維修站點及任務數量的增加，調度方案數量將急劇增長。針對這一典型的NP問題，傳統的枚舉法、圖論、線性規劃等方法已不再適用。本文通過改進的HPSO算法，針對該問題進行具體研究。

2 維修任務調度問題的數學描述

假設每一個特定規模的作戰區域中各有一個無人機維修保障中心，擁有K個維修保障分隊，將各維修保障分隊的備件儲備最大任務載荷定義為綜合服務能力，記為Qk（k=1，2，…，K）；同時有L個維修任務點的維修任務需要完成，各維修任務點的備件需求量為Ni（i=1，2，…，L），且max{Ni}＜max{Qk}；將各維修站點編號為0，1，…，L，其中，以M0為無人機維修保障中心，M1，M2，…，ML為維修任務點。另定義變量如下：

設cij為任務點i到任務點j的任務成本，其可用的含義包括運輸費用、機動距離和行駛時間等。由于軍隊裝備保障的特殊需求，首先應保證響應維修任務的時效性，考慮到維修站點位置實時動態變化、且裝備保障分隊的最大機動速度相對固定，因此，本文將cij定義為任務行駛時間。rk為目標函數的固有成本，這里定義為固有維修時間。

對維修任務實施過程提出以下基本假設與約束條件：

1）各維修分隊負責站點的維修資源需求總和小于維修分隊的任務最大載荷，即一次任務調度路線中不存在中途返回；

2）各維修站點有且僅有一個維修分隊負責，即不存在維修站點接受多方服務；

3）各維修分隊的任務調度路線中途經的維修站點均為其負責對象，即維修分隊在任務響應過程中僅途經其任務站點。

若以Z為全體維修保障分隊的任務完成時間（Mission Finished Time，MFT），且以該時間最短作為維修任務優化調度的系統目標，則無人機裝備維修任務調度的數學模型為：

3 可視化HPSO算法設計

3.1 粒子群算法基本原理

粒子群算法是 Eberhart和 Kennedy［4］于 1995年提出一種基于集群智能的進化類算法，其基本思想是基于生物的集群信息共享機制，以每個粒子的位置代表一個解的狀態，以適應度函數作為解的優劣的評價標準，由粒子的個體歷史最優位置Pi和集群全局最優位置Pg共同決定粒子的運動方向，并通過迭代計算對粒子群進行更新，直到獲得滿意的計算結果。

設指標空間為D維，總粒子數為n。第i個粒子位置表示為向量 Xi=（ xi1，xi2，…，xiD）；第 i個粒子運動歷史中的最優位置為 Pi=（ pi1，pi2，…，piD），其中第g個粒子的過去最優位置Pg為所有Pi（i=1，…，n）中的最優；第 i個粒子的速度為向量 Vi=（vi1，vi2，…，viD）。每個粒子的位置和速度按迭代公式如下：

其中，c1，c2為學習因子；w稱慣性因子，定義為粒子的動態慣性步長，用于實現迭代過程自適應步長調節，wmax和wmin是w的最大、最小值；iter和itermax分別是當前迭代次數和最大迭代次數；rand（）為[0，1]之間的隨機數；粒子第 d（1≤d≤D）維的位置變化范圍為［-XMAX-d，XMAX-d］，速度變化范圍為［-VMAX-d，VMAX-d］，若迭代過程中粒子運動狀態超出邊界，則以邊界賦值。

3.2 粒子編碼/解碼方法

本文以四維粒子結構對維修任務進行描述，粒子的第1維度x1采用自然碼編碼方式來表征L個維修任務站點；第2維度x2以隨機數的形式映射各維修任務站點分配的維修分隊；第3維度x3代表對應任務站點的維修資源需求量Ni；第4維度x4為維修站點的空間坐標Wi。由此得出模型中一個完整的粒子編碼形式為：

表2 粒子編碼形式

按照編碼格式對粒子x2進行取整，得到1～K的隨機序列，實現將各站點的維修任務映射到K個維修分隊中，完成粒子的初始化。

維修任務調度的粒子解碼過程為：

1）根據維修站點的責任劃分，歸納各維修分隊對應的任務鏈集合 M1{}，M2{}，…，Mk{}；

2）讀取各任務鏈集合當中粒子當前站點Ti1，Ti2，…，Tik；

3）由第4維度x4計算粒子當前站點到集合內剩余維修站點的運輸成本cij（任務行駛時間），并按由小到大順利排序；

4）選取各任務鏈集合中cij數值最小的維修站點 Ti1′，Ti2′，…，Tik′，計算響應后累計消耗備件數量Ni′；

5）若 Ni′＜Qi（累計備件消耗未超過最大載荷），則執行步驟6），否則跳轉步驟2）；

6）更新粒子當前站點 Ti1′，Ti2′，…，Tik′，計算粒子適應度Z，確定維修分隊的機動方向；

7）逐次計算，始終保證維修分隊按照最小運輸成本原則進行機動，直到遍歷集合內責任站點，完成初始化粒子的解碼。

3.3 HPSO算法改進

3.3.1 離散粒子群

由于粒子的編解碼過程中，x1，x3，x4均為輔助變量，而決定粒子優劣的主要因素為維修任務點的分配情況，即x2。為了構造初始化整數序列，粒子在迭代過程中針對隨機變量x2涉及大量的取整運算，影響計算效率，因此，可對粒子參數x2進行離散處理，使之更適合解決本文的研究問題。

本文采用Sigmoid函數來映射參數s，通過s（t）將迭代過程中每一個粒子中xi2的值編碼為1～K以內的整數序列，即：

設ρ為［0，1］區間內的隨機數，則針對參數x2構造的二進制離散粒子群算法的粒子速度和位置的更新公式為：

式（5）中，ceil［］和round［］分別代表向上取整運算與就近取整運算，考慮映射算子s（t）與vi2（t）為正相關關系，且粒子進化差距越大，對移動步長需求越大，可根據粒子位置，通過合理選擇取整方向控制移動距離，實現任務序列的粒子離散化處理。

3.3.2 粒子濃度監控機制

傳統粒子群算法的迭代機制使得粒子在后期的相似度較高，易陷入局部最優。本文引入粒子濃度監控機制，綜合了粒子濃度和適應度兩方面信息，對粒子群的進化過程進行調控。

定義粒子濃度Ck為種群中在當前粒子鄰接分布的粒子個數與種群規模之比，即Ck=Nk/N。鄰接分布的數學意義為兩粒子間的平均距離小于一個VMAX-d，本文通過歐式距離對粒子的距離進行計算，將兩粒子間的平均距離表示為：

濃度監控機制主要根據粒子的分布情況，實時地對粒子適應度進行調整，具體通過構造空間適應度Z′來實現：

其中，Zk′為空間適應度，Zk為原粒子適應度。由于Zk′與Zk成正相關，與Ck成負相關，以空間適應度表征粒子的質量優劣，即可實現對高濃度粒子進行抑制，對濃度低、適應度大的粒子促進。

3.3.3 粒子定向交叉遺傳

引入遺傳算法的思想，當粒子陷入集中分布，且解質量較低時，根據粒子濃度選擇種群中適應度高而濃度較低的粒子進行交叉、變異，使粒子跳出局部極值，加快進化過程。

根據粒子空間適應度，采用輪盤賭的方式選擇參與子代遺傳的粒子，選擇概率為：

遺傳過程采用實數交叉操作來實現信息交換，交叉過程如下：

粒子的變異過程通過隨機選擇變異粒子中的第d維為變異點，隨機產生初始速度：

為了確保變異粒子的局部的隨機搜索能力，避免粒子接近最優解的趨勢因變異遭到破壞，變異概率應取小值，因此，本文中變異概率取0.1。

3.3.4 可視化處理

針對傳統粒子群算法仿真動態過程反映不直觀的問題［15］，本文基于Matlab粒子群工具箱PSOt，通過GUI模塊優化了用戶界面，改進了圖形展示函數goplotpso.m，能夠實時展現粒子在迭代過程中的空間分布與參數狀態，其基本調用方式為：

pso_Trelea_vectorized （′main_func′，n，Max_V，range，minmax，Pdef）。其中，Pdef=［me，ps，ac1，ac2，iw1，iw2，iwe，ergrd，ergrde，errgoa，trelea，PSOseed］，代表算法的參數設置，主要包括畫面記錄步長、進化代數、群體規模、學習因子、慣性因子、約束條件、中止迭代條件、初始化狀態等參數信息。

4 實例分析

以某次無人機［16］分隊山地作戰維修保障任務為例，作戰區域內含有一個維修保障中心L0，坐標為（11.62，5.23，0），以 km 為單位；另有 10 個維修任務點L1～L10，各無人機分隊根據任務需要實時機動，某時刻各維修任務點的空間分布如圖1所示。

圖1 維修中心與任務點空間分布

設維修保障中心擁有4個維修保障分隊，各維修保障分隊的綜合服務能力均為40，最大機動速度為90 km/h，固有維修時間計0.56 h，各維修任務點的資源需求量依次為 {7，5，3，6，6，8，2，7，11，9}，且位置坐標為已知，如表3所示。

表3 維修任務點位置坐標

在Matlab 2015b環境下運行混合粒子群程序，相關參數設置為：畫面展示步長為1，學習因子c1=c2=2，慣性因子 wmax=0.9、wmin=0.4，種群規模、進化代數均為30，迭代終止精度要求為1e-25，粒子速度設置vmax=5、vmax=-5，以MFT最短作為尋優目標，迭代過程如圖2所示。

連續進行40次仿真計算，對結果進行統計，并與普通粒子群算法進行對比，將兩種算法得到最優結果展示，如圖3、圖4所示。

根據實驗統計，進一步對兩種算法的達優次數、達優率、平均計算時間等性能指標進行列舉，如表4所示。

通過對比可知，在40次模擬實驗中，混合粒子群算法的尋優能力明顯高于普通粒子群算法，且具有解質量高、迭代速度快等優點，而普通粒子群算法易陷入局部最優解、計算結果不夠穩定。

圖2 改進的HPSO算法流程

圖3 普通粒子群算法最優結果

圖4 改進的HPSO最優結果

表4 主要性能參數比較

綜上，采用混合粒子群算法得出最優結果，查詢相應維修保障分隊的任務點分配、調度次序、機動距離、任務時間等信息，得出該任務背景下的最優調度方案。

各維修保障分隊同時從保障中心出發，K1分隊經L9到達L6，K2分隊經 L1到達 L2，K3分隊經L4、L5、L7 到達 L3，K4 分隊經 L10 到達 L8，維修任務展開1.617 h后，作戰區域中所有無人機分隊的維修需求得到滿足，即最優任務完成時間為1.617 h。

表5 最優調度方案

5 結論

本文針對軍用無人機裝備維修任務調度的特殊需求，對傳統粒子群算法進行了改進，采用離散化粒子群簡化粒子論域，加快計算速度，引入濃度監控機制對粒子的分布及運動過程進行調控，并通過粒子交叉遺傳加快進化速度，防止陷入局部最優。通過實例分析表明，改進的混合粒子群算法能夠進行高效仿真計算，快速得出維修任務最佳調度方案，且解質量更高、迭代速度更快，進化過程更加直觀，證明了混合粒子群算法在裝備資源調度問題中的有效應用，為軍隊維修保障的決策工作提供了新的思路。