基于EDA算法的航母彈藥調度優化研究

陶俊權，蘇析超，韓 維，李亞飛

(1.海軍航空大學， 山東 煙臺 264001； 2.海軍研究院， 北京 100072)

1 引言

艦載機作為航母這個現代戰爭中最重要作戰平臺的基本作戰力量，其出動架次率是衡量航母作戰能力的關鍵指標。而航空彈藥轉運作業能力則是影響艦載機出動架次率的重要因素。作為航空保障作業諸多作業之一，航空彈藥保障作業需要完成彈藥的貯存、轉運、裝配、掛載，所需要的安全性高、作業流程復雜、花費時間長。彈藥從出庫到掛載，環節多，需要從彈藥庫取出，通過下層武器升降機運送，依據武器類型判斷裝配地點，裝配好的彈藥再通過上層武器升降機或飛機升降機送達飛行甲板，最終在飛行甲板完成艦載機彈藥的掛載。因此優化航母彈藥轉運調度，對提高艦載機保障效率，增強航母作戰能力有重要意義。

航母航空彈藥轉運作業問題復雜程度高，約束條件眾多，且求解難度隨單批次轉運彈藥數量增加呈指數性增長。對于此問題的求解，國內學者已進行了很多研究。首先是對美軍航母彈藥轉運流程的分析，文獻[5-6]介紹了美尼米茲級航母的航空彈藥組成及彈藥轉運基本流程，并通過分析美航母轉運作業過程中遇到的問題并提出相應的改進建議，其次是對航母彈藥轉運作業問題的智能算法求解。文獻[7-11]應用遺傳算法及蟻群算法，對艦載機彈藥調度問題依據不同的假設條件進行了優化。除此之外，文獻[12]基于PERT網絡，對航空彈藥保障人員配置方案進行分析，優選出有限保障人員的配置方案。文獻[13]應用基于T-S的模糊非線性優化方法，實現了對彈藥組裝和轉運速率的控制。文獻[14]考慮航空彈藥保障系統的動態特征，借鑒Multi-Agent方法，建立了航空彈藥動態調運優化模型。文獻[15]將航母彈藥轉運問題抽象為2階段多目標規劃問題，深入分析轉運約束條件，采用彈藥轉運優先級的方法建立了轉運模型。

本文在對航空彈藥轉運流程及其約束條件進行分析的基礎上，將問題抽象為資源受限項目調度問題，構建了基于模塊化運輸單元的彈藥轉運優化模型，并使用EDA算法進行了求解。該模型通用性強，可適應不同航母的不同彈藥轉運流程，模型精細程度高，可實現對每一輛彈藥轉運車的獨立調度，最后用實驗表明，該算法及模型可有效求解航空彈藥轉運問題，對作業效率進行優化。

2 彈藥調度問題模型描述

彈藥轉運作業時間長、工作量大，涉及包括各類武器彈藥、彈藥轉運車、武器升降機、彈藥裝配區等在內的眾多因素，其保障效率是制約艦載機出動架次率主要因素之一，本節對彈藥保障轉運過程中的運輸流程及約束進行具體分析，構建彈藥調度問題的總體框架。

2.1 彈藥轉運處理流程分析

參照美“福特”級航母的航空彈藥轉運作業流程，艦載機彈藥轉運基本環節如圖1所示。彈藥管理人員依據該出動批次飛機所需彈藥，確定彈藥總需求量、種類，并將運彈任務分配至各彈庫。運彈人員則因彈藥儲存方式不同采取不同手段取出彈藥并考慮是否進行簡單裝配。完成上述步驟的彈藥將等待下層升降機空閑，若空閑則將下層升降機調至該彈庫實施升降機轉運。若彈藥需要裝配臺進行裝配，將彈藥轉運至彈藥裝配區進行裝配作業，否則轉運至機庫甲板。待上層升降機或多用途升降機空閑后，彈藥繼續轉運至飛行甲板及各停機位處進行掛載作業。最后彈藥轉運車及運彈人員待升降機空閑后原路返回，彈藥轉運結束。

圖1 彈藥轉運流程框圖

2.2 彈藥運輸約束分析

一個批次的彈藥轉運任務需要許多彈藥轉運車，當最后一輛彈藥轉運車在停機位完成彈藥裝載作業并成功返回原位后，該批次的彈藥轉運任務成功完成。視一輛彈藥轉運車為一個獨立運輸單元，其完成轉運任務并回到原位的時間花費設為，時間從該批次彈藥開始轉運任務起計算。若有個運輸單元，則其時間花費分別為,,…,，因該問題存在多個可行解，為完成整個轉運任務時間花費最小的任務目標，目標函數可設為最后完成任務的運輸單元所處時刻距任務開始時間最短。即：

=min{}

=max{,,…,}

(1)

彈藥轉運最優任務目標的完成仍需滿足以下約束條件。

1) 從某一彈庫獲得某種彈數量不超過該彈庫儲存的該種類彈數量上限。

(2)

式(2)中，代表第個運輸單元從第個彈庫所取的第種彈的數量。共有個彈庫，種彈藥。

2) 每個運輸單元只從一個彈庫取彈。

(3)

式(3)中，為狀態變量。若第個運輸單元從任務規定的第個彈庫取彈，則值為1，否則為0。

3) 每個運輸單元只取一種類型的彈藥。

(4)

式(4)中，為狀態變量。若第個運輸單元取任務規定的第種彈藥，則值為1，否則為0。

4) 每個運輸單元彈藥量不超過該運輸單元容納彈藥上限。

(5)

式(5)中，代表第個運輸單元承載彈藥數上限。

5) 升降機承載的運輸單元數量不能超過最大載運量。

(6)

式(6)中：為狀態變量，代表所處的升降機，共有個升降機；代表第個升降機能承載的彈藥轉運車數量。

6) 單個彈庫內轉運設備同時轉運彈藥數量不超過設計上限。

(7)

式(7)中：代表第個彈庫內正在轉運的第種彈藥數量；代表第個彈庫可同時轉運彈藥數量上限。

7) 彈藥裝配區同時進行裝配數量不超過容納上限。

(8)

式(8)中，代表彈藥裝配區裝配臺的數量。

8) 一個運輸單元只能前往一個停機位。

(9)

3 改進分布估計算法設計及其實現

3.1 分布估計算法的基本原理

分布估計算法(estimation distribution algorithm,EDA)是一種基于統計學習理論的群體進化算法,通過建立起概率模型來描述候選解在搜索空間的分布信息并以此解決問題，利用統計分析的工具，EDA從群體宏觀角度建立一個描述解分布的概率模型，估計精英個體所在編碼變量的潛在概率分布。在生成初始種群和初始化概率矩陣后，采用迭代方法估計最優解的分布。EDA總體流程如圖2所示。

圖2 EDA算法總體流程框圖

3.2 調度模型的改進分布估計算法實現

本節中，航母的彈藥調度問題，將通過建立針對彈藥調度問題的特殊概率模型、基于EDA搜索機制的概率更新機制以及進行深度優化的局部搜索機制來進行求解。

3.2.1 編碼方案

參考多模式資源受限項目調度問題，采用調度順序+雙重模式的編碼方式。一個批次彈藥所對應的所有運輸單元按先后順序進行調度，起始彈庫及停機位作為每個運輸單元所對應的雙重模式，如圖3所示。

圖3 編碼方案示意圖

第1行代表各個運輸單元的調度順序，數字代表運輸單元編號。第2行則代表按運輸單元編號排列的各運輸單元所屬彈庫。第3行代表按運輸單元編號排列的各運輸單元將要運輸到達的停機位。

各個運輸單元序號及其所包含的彈種與彈藥數量由各停機位所需彈藥的運輸任務分配情況決定。如圖4所示，一輛轉運車可轉運彈藥a數量為2，則轉運5枚彈藥a的任務被分配給了3個彈藥車運輸單元，所有運輸單元編號順序按停機位及彈藥需求任務依次排列，而每輛彈藥所需運載彈藥也由此確定。

圖4 停機位彈藥分配過程框圖

3.2.2 多彈庫多通道并行調度時序生成方案

航母彈藥轉運，彈藥從不同的彈庫出發，經由固定的轉運通道轉運至飛行甲板及停機位。由于各轉運通道的運輸路徑之間可能存在交叉，全艦的單批次彈藥轉運任務無法轉化為各通道的單獨彈藥運輸子任務，因此需要建立多彈庫多通道聯合調度方案。具體流程如圖5所示。

3.2.3 概率模型及概率生成機制

相較于其他智能算法(如遺傳算法等)采用交叉及變異方式產生新的解來求解彈藥調度問題，分布估計算法采用更簡便的概率模型來解決這一問題，如何產生概率模型是設計一個EDA算法的關鍵問題。

本文所建立的概率模型包含2個概率矩陣，一個是×的調度順序概率矩陣()，為運輸單元總數。另一個是×的彈庫選擇概率矩陣()，為彈庫總數。

1)()：該概率矩陣被用來預測每個運輸單元在總調度過程中的順序。

(10)

式(10)中，象征編號為的運輸單元位于第個被調度位置上的概率，其大小表示運輸單元在位置上的優劣性。初始概率如式(11)所示，以此保證概率估計及采樣的公正性。

(11)

圖5 多彈庫多通道轉運任務求解流程框圖

2)()：該概率矩陣被用來預測每個運輸單元選擇不同彈庫的概率，即：

(12)

式(12)中，象征運輸單元選擇彈庫的概率，其大小表示運輸單元從彈庫出發的優劣性。同調度概率矩陣一樣，該矩陣也用保證公平的初始矩陣來確定平等選擇各彈庫。表達式為：

(13)

另外，由于不同彈庫所儲存的彈藥種類有所不同，彈庫選擇概率初始矩陣，應根據不同運輸單元所搭載的彈藥種類將相應位置的概率歸零并重新分配每行的概率。

由于各運輸單元之間不存在前后序約束，因此各運輸單元可以按照編號順序依次經過調度順序概率矩陣，并最終生成一個完整的調度順序。運輸單元選擇位置的概率為：、

(14)

若位置已被選取，則對應的列概率全部歸零，即該位置不可再被選取，以保證位置的唯一性。

選取完各單元位置后，還需對各單元所屬彈庫進行選擇，運輸單元選擇彈庫的概率為：

(15)

由于運輸單元所屬停機位在分配運輸單元彈藥時已經固定，故無需進行選取。最終，經過調度順序概率矩陣及彈庫選擇概率矩陣的選取，可以確定一個完整的調度順序集。由于存在同一彈庫取彈量不得超過存彈量等約束條件，確定運輸單元所屬彈庫后，需進行檢驗，若不滿足約束，需重新進行選取。

將確定調度順序集的操作重復次，由此得到了一個擁有個個體的種群，為之后的操作做準備。

3.2.4 局部搜索

3.2.5 概率矩陣更新機制

為了更好地進行迭代，加速獲得更加優秀的解，需要依據計算所得的個優勝解對概率矩陣()及()進行更新，其更新規則為：

(16)

(17)

圖6 局部搜索流程框圖

3.3 EDA算法總結

經過上述設計，基于EDA算法的航母彈藥調度問題可以有總結表述如下：首先，初始化概率矩陣，以保證選擇公平性。其次，使用多彈庫多通道并行時序生成方案，生成個解，挑選其中個優異解并進行局部搜索以優化解的質量。最后，依據優化后的優異解對概率矩陣進行修改，并進行迭代運算，以求得最終的最優解。

4 仿真實驗

本節中，算法的實用性會通過一個具體實例來證明。由圖1可知，航母的彈藥轉運流程可根據彈藥種類及特點的不同分為2種：一種彈藥經彈藥裝配區裝配后轉移至飛行甲板停機位，另一種在彈庫簡單裝配后經機庫甲板到達飛行甲板停機位，具體轉運流程及編號如圖7所示。

圖7 2種彈藥轉運流程框圖

設某型航母共有11個彈庫，分為1-3號、4-7號、8-11號3個彈庫群。相對應的有10臺升降機，其中6臺下層升降機(3臺對應3個彈庫群執行任務類別1，另外3臺對應3個彈庫群執行任務類別2)；4臺上層升降機(3臺對應各個彈庫群執行任務類別1，另外1臺對應所有彈庫執行任務類別2)。

在彈藥轉運任務設置上，設該批次航母彈藥轉運涉及5個停機位，上層升降機位于飛行甲板上的4個出口與各停機位之間存在獨立的轉運時間。共需運輸3種類型彈藥，A型彈1車1枚，彈庫內3枚聯裝，經任務類別1進行運輸。B型彈一車2枚，彈庫內獨立包裝，經任務類別2進行運輸。C型彈1車1枚，彈庫內獨立包裝，經任務類別1進行運輸。共需運輸5枚A型彈、10枚B型彈、5枚C型彈且各停機位彈藥分配平均，均為1枚A型、2枚B型、1枚C型。共需調度15輛彈藥轉運車，即15個運輸單元。

EDA算法參數設置上，種群大小設定為200，局部搜索概率為0.05，學習速率為0.3，共迭代運行4 000次，對比未采用局部搜索的EDA算法及采用局部搜索的改進EDA算法，運行結果如圖8所示。

由圖8可以看出，采用局部搜索的改進EDA算法所獲得的最優解優于標準EDA算法，收斂速度也有所超出，這是對解空間進行深度搜索的結果。

各彈藥轉運車執行各個調度工序的甘特圖如圖9，橫軸為時間，縱軸代表各個運輸單元的編號，各甘特塊長度代表所耗工時，其內編號為工序編號。所得到的最優調度方案盡可能利用各升降機，以保證總調度時間最小，實現資源的有效利用。通過該甘特圖驗證模型滿足式(2)至式(9)中的各項約束，證明了模型的合理性。

圖8 2種EDA算法運行結果曲線

圖9 彈藥運輸單元工序甘特圖

5 結論

改進的EDA算法引入了雙概率矩陣的形式，對初始種群的生成進行了改進。并結合了局部搜索，相較于標準EDA算法，對于解空間的深度搜索效果有了很大的提高。充分結合了EDA算法種群正反饋機制下的全局搜索能力以及對精英個體深度搜索后的快速收斂能力。采用彈藥轉運車運輸單元為基本單位進行計算，優化了解的精細程度。通過實例仿真，驗證了其在航母彈藥調度方案設計中的實用價值。