基于離散粒子群的艦載機(jī)彈藥調(diào)度?

張洪亮 劉建偉 馬 羚 楊東澤

（1.海裝駐上海地區(qū)第一軍事代表室 上海 200000）（2.中國(guó)船舶集團(tuán)有限公司第七一三研究所 鄭州 450000）（3.海軍航空大學(xué) 煙臺(tái) 264000）

1 引言

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

機(jī)載彈藥調(diào)度是一個(gè)資源的離散組合優(yōu)化問(wèn)題，屬于NP難題［2］。隨著需求彈藥批次的增加，可能的調(diào)度方案數(shù)量呈指數(shù)性增長(zhǎng)，欲從中找尋較優(yōu)的方案難度巨大。傳統(tǒng)的枚舉法和啟發(fā)式算法計(jì)算量大，且需要針對(duì)求解問(wèn)題找尋特定的啟發(fā)途徑，不易實(shí)現(xiàn)［3］。

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

2 建立艦載機(jī)彈藥調(diào)度模型

假設(shè)某次艦載機(jī)彈藥保障任務(wù)中，由A個(gè)彈藥艙群負(fù)責(zé)保障B架艦載機(jī)，彈藥調(diào)度任務(wù)要在盡可能短的時(shí)間內(nèi)完成。

彈藥艙是機(jī)載彈藥調(diào)度的起點(diǎn)，上級(jí)部門(mén)下達(dá)調(diào)度任務(wù)后，彈藥艙負(fù)責(zé)將彈藥出庫(kù)，經(jīng)由多級(jí)轉(zhuǎn)運(yùn)最終達(dá)到艦載機(jī)機(jī)位；同一彈藥艙群中，各彈藥艙的彈藥轉(zhuǎn)運(yùn)時(shí)間相差很小，且各彈藥艙群使用的升降機(jī)是固定的，如圖1所示。因此，單批次彈藥保障關(guān)系可以視為彈藥艙群與艦載機(jī)的關(guān)系，單批次彈藥從彈藥艙群a運(yùn)送至艦載機(jī)b的時(shí)間為tab。

圖1 彈藥轉(zhuǎn)運(yùn)流程示意圖

各艦載機(jī)彈藥需求總批次為

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

模型的目標(biāo)是使得調(diào)度方案的執(zhí)行時(shí)間Tf最小。執(zhí)行時(shí)間Tf可轉(zhuǎn)化為所有批次彈藥調(diào)度完成時(shí)間，即最后一個(gè)彈藥艙群中負(fù)責(zé)任務(wù)完成時(shí)間。彈藥艙群a的任務(wù)執(zhí)行時(shí)間：

則調(diào)度方案的執(zhí)行時(shí)間：

3 離散粒子群算法設(shè)計(jì)

粒子群優(yōu)化算法于1995年首次提出的一種隨機(jī)搜素算法，原理受到鳥(niǎo)群捕食行為的啟發(fā)。算法中粒子的位置坐標(biāo)被看作問(wèn)題的解，粒子根據(jù)粒子個(gè)體信息和種群社會(huì)信息進(jìn)行位置更新，使得整個(gè)種群向最優(yōu)解靠近。傳統(tǒng)粒子群通常用于處理連續(xù)函數(shù)的尋優(yōu)問(wèn)題，不適合直接用于處理離散問(wèn)題。因此，需要對(duì)傳統(tǒng)粒子群的算法原理進(jìn)行調(diào)整。

3.1 粒子坐標(biāo)

粒子的坐標(biāo)如式（5）所示：

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

3.2 粒子更新

粒子速度和坐標(biāo)根據(jù)以下公式獲得：

為了保證粒子坐標(biāo)為整數(shù)量，由速度更新公式得到速度值根據(jù)四舍五入化為整數(shù)。pbest和gbest為個(gè)體最優(yōu)解和全局最優(yōu)解；ω為慣性權(quán)值，c1，c2為個(gè)體最優(yōu)與全局最優(yōu)的權(quán)重值；rand()為分布在0和1之間的隨機(jī)數(shù)，反映了粒子運(yùn)動(dòng)的隨機(jī)性。

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)如式（4）所示，適應(yīng)度值越低代表方案執(zhí)行時(shí)間越短，方案越優(yōu)。

粒子群算法運(yùn)行流程如圖2所示。

圖2 粒子群算法流程圖

4 仿真驗(yàn)證

假設(shè)某次彈藥保障任務(wù)中，由5個(gè)彈藥艙群為4架艦載機(jī)提供彈藥保障。各機(jī)位需求彈藥分別為3、5、5、4批次。彈藥調(diào)度時(shí)間如表1所示。

表1 彈藥調(diào)度時(shí)間成本表

粒子群算法參數(shù)設(shè)定：種群規(guī)模80，最大迭代次數(shù)100代，慣性權(quán)值ω為0.8。個(gè)體最優(yōu)權(quán)值c1和全局最優(yōu)權(quán)值c2皆為1.4。

共計(jì)運(yùn)行20次結(jié)果如表2所示。

表2 算法運(yùn)行20次結(jié)果

使用離散粒子群對(duì)模型進(jìn)行求解，運(yùn)行20次最優(yōu)個(gè)體適應(yīng)度值變化如圖3所示。

圖3 算法運(yùn)行20次適應(yīng)度值變化曲線

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

圖4 調(diào)度方案執(zhí)行甘特圖

5 結(jié)語(yǔ)

通過(guò)對(duì)機(jī)載彈藥資源的分析，建立彈藥調(diào)度方案優(yōu)化模型，并利用改進(jìn)的粒子群算法進(jìn)行求解。將粒子群算法的速度位置更新公式整數(shù)化，使其具備處理離散問(wèn)題的能力。通過(guò)仿真驗(yàn)證，可證明論文建立模型是合理的，離散后的粒子群得到優(yōu)質(zhì)方案的概率達(dá)到80%。