基于可視化HPSO的無人機(jī)裝備維修任務(wù)調(diào)度*

沈延安，葉 霖

（陸軍炮兵防空兵學(xué)院，合肥 230031）

0 引言

軍用無人機(jī)是信息化高技術(shù)條件下具有高效費比、攻防兼?zhèn)涞男赂拍钛b備，可用于目標(biāo)指示、偵查校射、電子干擾、火力打擊等多種用途，目前已在各軍種得到廣泛應(yīng)用。由于無人機(jī)系統(tǒng)［1］裝備組成復(fù)雜，備件類型多，且維修地點隨無人機(jī)分隊的任務(wù)機(jī)動實時變化，導(dǎo)致其裝備維修任務(wù)的路徑選擇［2-4］由時間、距離、地形、任務(wù)類別等諸條件決定，并視戰(zhàn)場環(huán)境適時調(diào)整，容易形成復(fù)雜的NP（Non-deterministic Polynomial，NP）問題，加大了無人機(jī)裝備維修保障任務(wù)的工作難度。

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

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

1 無人機(jī)裝備維修任務(wù)調(diào)度問題系統(tǒng)分析

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

統(tǒng)觀目前軍用無人機(jī)系統(tǒng)，其維修保障任務(wù)從功能組成上講基本相同，相關(guān)維修任務(wù)具有以下普遍特征：1）裝備組成復(fù)雜，部件精密，維修技術(shù)需求較高；2）機(jī)動性強(qiáng)，為保證偵查校射和目標(biāo)打擊的精度要求，需要實施大量的戰(zhàn)術(shù)機(jī)動，導(dǎo)致裝備維修任務(wù)在不同時間、不同任務(wù)階段實時動態(tài)變化。結(jié)合霍爾三維結(jié)構(gòu)分析，明確無人機(jī)裝備維修任務(wù)調(diào)度問題的組成要素，如表1所示。

表1 無人機(jī)維修任務(wù)調(diào)度組成要素

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

2 維修任務(wù)調(diào)度問題的數(shù)學(xué)描述

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

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

對維修任務(wù)實施過程提出以下基本假設(shè)與約束條件：

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

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

3）各維修分隊的任務(wù)調(diào)度路線中途經(jīng)的維修站點均為其負(fù)責(zé)對象，即維修分隊在任務(wù)響應(yīng)過程中僅途經(jīng)其任務(wù)站點。

若以Z為全體維修保障分隊的任務(wù)完成時間（Mission Finished Time，MFT），且以該時間最短作為維修任務(wù)優(yōu)化調(diào)度的系統(tǒng)目標(biāo)，則無人機(jī)裝備維修任務(wù)調(diào)度的數(shù)學(xué)模型為：

3 可視化HPSO算法設(shè)計

3.1 粒子群算法基本原理

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

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

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

3.2 粒子編碼/解碼方法

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

表2 粒子編碼形式

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

維修任務(wù)調(diào)度的粒子解碼過程為：

1）根據(jù)維修站點的責(zé)任劃分，歸納各維修分隊對應(yīng)的任務(wù)鏈集合 M1{}，M2{}，…，Mk{}；

2）讀取各任務(wù)鏈集合當(dāng)中粒子當(dāng)前站點Ti1，Ti2，…，Tik；

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

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

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

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

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

3.3 HPSO算法改進(jìn)

3.3.1 離散粒子群

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

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

設(shè)ρ為［0，1］區(qū)間內(nèi)的隨機(jī)數(shù)，則針對參數(shù)x2構(gòu)造的二進(jìn)制離散粒子群算法的粒子速度和位置的更新公式為：

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

3.3.2 粒子濃度監(jiān)控機(jī)制

傳統(tǒng)粒子群算法的迭代機(jī)制使得粒子在后期的相似度較高，易陷入局部最優(yōu)。本文引入粒子濃度監(jiān)控機(jī)制，綜合了粒子濃度和適應(yīng)度兩方面信息，對粒子群的進(jìn)化過程進(jìn)行調(diào)控。

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

濃度監(jiān)控機(jī)制主要根據(jù)粒子的分布情況，實時地對粒子適應(yīng)度進(jìn)行調(diào)整，具體通過構(gòu)造空間適應(yīng)度Z′來實現(xiàn)：

其中，Zk′為空間適應(yīng)度，Zk為原粒子適應(yīng)度。由于Zk′與Zk成正相關(guān)，與Ck成負(fù)相關(guān)，以空間適應(yīng)度表征粒子的質(zhì)量優(yōu)劣，即可實現(xiàn)對高濃度粒子進(jìn)行抑制，對濃度低、適應(yīng)度大的粒子促進(jìn)。

3.3.3 粒子定向交叉遺傳

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

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

遺傳過程采用實數(shù)交叉操作來實現(xiàn)信息交換，交叉過程如下：

粒子的變異過程通過隨機(jī)選擇變異粒子中的第d維為變異點，隨機(jī)產(chǎn)生初始速度：

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

3.3.4 可視化處理

針對傳統(tǒng)粒子群算法仿真動態(tài)過程反映不直觀的問題［15］，本文基于Matlab粒子群工具箱PSOt，通過GUI模塊優(yōu)化了用戶界面，改進(jìn)了圖形展示函數(shù)goplotpso.m，能夠?qū)崟r展現(xiàn)粒子在迭代過程中的空間分布與參數(shù)狀態(tài)，其基本調(diào)用方式為：

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

4 實例分析

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

圖1 維修中心與任務(wù)點空間分布

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

表3 維修任務(wù)點位置坐標(biāo)

在Matlab 2015b環(huán)境下運行混合粒子群程序，相關(guān)參數(shù)設(shè)置為：畫面展示步長為1，學(xué)習(xí)因子c1=c2=2，慣性因子 wmax=0.9、wmin=0.4，種群規(guī)模、進(jìn)化代數(shù)均為30，迭代終止精度要求為1e-25，粒子速度設(shè)置vmax=5、vmax=-5，以MFT最短作為尋優(yōu)目標(biāo)，迭代過程如圖2所示。

連續(xù)進(jìn)行40次仿真計算，對結(jié)果進(jìn)行統(tǒng)計，并與普通粒子群算法進(jìn)行對比，將兩種算法得到最優(yōu)結(jié)果展示，如圖3、圖4所示。

根據(jù)實驗統(tǒng)計，進(jìn)一步對兩種算法的達(dá)優(yōu)次數(shù)、達(dá)優(yōu)率、平均計算時間等性能指標(biāo)進(jìn)行列舉，如表4所示。

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

圖2 改進(jìn)的HPSO算法流程

圖3 普通粒子群算法最優(yōu)結(jié)果

圖4 改進(jìn)的HPSO最優(yōu)結(jié)果

表4 主要性能參數(shù)比較

綜上，采用混合粒子群算法得出最優(yōu)結(jié)果，查詢相應(yīng)維修保障分隊的任務(wù)點分配、調(diào)度次序、機(jī)動距離、任務(wù)時間等信息，得出該任務(wù)背景下的最優(yōu)調(diào)度方案。

各維修保障分隊同時從保障中心出發(fā)，K1分隊經(jīng)L9到達(dá)L6，K2分隊經(jīng) L1到達(dá) L2，K3分隊經(jīng)L4、L5、L7 到達(dá) L3，K4 分隊經(jīng) L10 到達(dá) L8，維修任務(wù)展開1.617 h后，作戰(zhàn)區(qū)域中所有無人機(jī)分隊的維修需求得到滿足，即最優(yōu)任務(wù)完成時間為1.617 h。

表5 最優(yōu)調(diào)度方案

5 結(jié)論

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