基于離散粒子群的艦載機彈藥調度?

張洪亮 劉建偉 馬 羚 楊東澤

（1.海裝駐上海地區第一軍事代表室 上海 200000）（2.中國船舶集團有限公司第七一三研究所 鄭州 450000）（3.海軍航空大學 煙臺 264000）

1 引言

艦載機作戰能力與機載彈藥保障效率密不可分，合理、高效的機載彈藥調度方案直接決定機載彈藥保障效率，從而影響艦載機作戰任務的實施。調度資源中彈藥艙群、武器升降機及艦載機停機位等數量多、分布廣，需要在短時間內給出最優或較優的調度方案［1］。

機載彈藥調度是一個資源的離散組合優化問題，屬于NP難題［2］。隨著需求彈藥批次的增加，可能的調度方案數量呈指數性增長，欲從中找尋較優的方案難度巨大。傳統的枚舉法和啟發式算法計算量大，且需要針對求解問題找尋特定的啟發途徑，不易實現［3］。

目前，基于模擬自然界生物行為的智能算法，諸如模擬退火、遺傳算法、蟻群算法等，在處理典型組合優化問題上取得了許多進展［4～6］。蟻群優化算法（Ant Colony Optimization，ACO）是由意大利學者Dorigo等于1991年提出的［7］。粒子群優化（Particle Swarm Optimization，PSO）算法是由Eberhart博士和Kennedy博士通過觀察模擬鳥類捕食的行為，于1995年提出的一種仿生學方法［8］，遺傳算法（Genet?ic Algorithm，GA）是J.Holland于1975年受生物進化論的啟發而提出的［9］。文獻［10］基于博弈模型首先對多目標問題進行度量，進而結合遺傳算法優化彈藥調度策略。文獻［11］通過蟻群算法將彈藥運輸路徑的問題轉化為多目標決策問題進行求解。其中粒子群具有搜索速度快、效率高、算法簡單的優點［12～13］。鑒于這些優點，本文運用粒子群算法求解艦載機彈藥調度模型，并將其參數整數化以用于解決離散問題。

2 建立艦載機彈藥調度模型

假設某次艦載機彈藥保障任務中，由A個彈藥艙群負責保障B架艦載機，彈藥調度任務要在盡可能短的時間內完成。

彈藥艙是機載彈藥調度的起點，上級部門下達調度任務后，彈藥艙負責將彈藥出庫，經由多級轉運最終達到艦載機機位；同一彈藥艙群中，各彈藥艙的彈藥轉運時間相差很小，且各彈藥艙群使用的升降機是固定的，如圖1所示。因此，單批次彈藥保障關系可以視為彈藥艙群與艦載機的關系，單批次彈藥從彈藥艙群a運送至艦載機b的時間為tab。

圖1 彈藥轉運流程示意圖

各艦載機彈藥需求總批次為

艦載機b需求的第r批次彈藥表示為p(b，r)，取值為彈藥艙群編號，即：

模型的目標是使得調度方案的執行時間Tf最小。執行時間Tf可轉化為所有批次彈藥調度完成時間，即最后一個彈藥艙群中負責任務完成時間。彈藥艙群a的任務執行時間：

則調度方案的執行時間：

3 離散粒子群算法設計

粒子群優化算法于1995年首次提出的一種隨機搜素算法，原理受到鳥群捕食行為的啟發。算法中粒子的位置坐標被看作問題的解，粒子根據粒子個體信息和種群社會信息進行位置更新，使得整個種群向最優解靠近。傳統粒子群通常用于處理連續函數的尋優問題，不適合直接用于處理離散問題。因此，需要對傳統粒子群的算法原理進行調整。

3.1 粒子坐標

粒子的坐標如式（5）所示：

坐標按艦載機編號順序，依次表示負責各機位需求彈藥批次的供給彈藥艙群。粒子的坐標應滿足式（2）。若在位置更新中，粒子的位置坐標值不為合法的取值，則將非法的坐標值賦值為離其最近的上限或下限。

3.2 粒子更新

粒子速度和坐標根據以下公式獲得：

為了保證粒子坐標為整數量，由速度更新公式得到速度值根據四舍五入化為整數。pbest和gbest為個體最優解和全局最優解；ω為慣性權值，c1，c2為個體最優與全局最優的權重值；rand()為分布在0和1之間的隨機數，反映了粒子運動的隨機性。

3.3 適應度函數

適應度函數如式（4）所示，適應度值越低代表方案執行時間越短，方案越優。

粒子群算法運行流程如圖2所示。

圖2 粒子群算法流程圖

4 仿真驗證

假設某次彈藥保障任務中，由5個彈藥艙群為4架艦載機提供彈藥保障。各機位需求彈藥分別為3、5、5、4批次。彈藥調度時間如表1所示。

表1 彈藥調度時間成本表

粒子群算法參數設定：種群規模80，最大迭代次數100代，慣性權值ω為0.8。個體最優權值c1和全局最優權值c2皆為1.4。

共計運行20次結果如表2所示。

表2 算法運行20次結果

使用離散粒子群對模型進行求解，運行20次最優個體適應度值變化如圖3所示。

圖3 算法運行20次適應度值變化曲線

從圖3可以看出20次運行中，算法在20代左右收斂，收斂速度較快，能夠快速找到最優解。算法得到的最優方案的概率為80%，方案為2 1 4 5 4 5 1 2 4 5 4 3 3 2 5 1 3，方案執行時間為11.2。方案執行甘特圖如圖4。

圖4 調度方案執行甘特圖

5 結語

通過對機載彈藥資源的分析，建立彈藥調度方案優化模型，并利用改進的粒子群算法進行求解。將粒子群算法的速度位置更新公式整數化，使其具備處理離散問題的能力。通過仿真驗證，可證明論文建立模型是合理的，離散后的粒子群得到優質方案的概率達到80%。