基于基本空間組合關(guān)系的艦載機(jī)機(jī)庫布列算法

徐柱國(guó)，余明暉*，吳靳，戴明強(qiáng)

1 華中科技大學(xué) 人工智能與自動(dòng)化學(xué)院，湖北 武漢 430074

2 海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033

3 海軍工程大學(xué) 基礎(chǔ)部, 湖北 武漢 430033

0 引 言

艦載機(jī)作為航空母艦（以下稱“航母”）的核心作戰(zhàn)裝備，其數(shù)量以及調(diào)運(yùn)效率與航母綜合作戰(zhàn)能力緊密相關(guān)[1]。作為航母停放艦載機(jī)的主要地點(diǎn)，機(jī)庫不僅需要盡可能布列更多數(shù)量的艦載機(jī)，同時(shí)布列方案還需合理滿足艦載機(jī)出庫調(diào)運(yùn)需求。因此，需對(duì)艦載機(jī)機(jī)庫的停放布列問題，即在二維機(jī)庫平面內(nèi)對(duì)不同種類艦載機(jī)（如戰(zhàn)斗機(jī)、直升機(jī)、預(yù)警機(jī)等）進(jìn)行站位劃分，以提高機(jī)庫停放的艦載機(jī)數(shù)量并保證艦載機(jī)調(diào)運(yùn)效率。

國(guó)內(nèi)外學(xué)者針對(duì)機(jī)庫布列問題開展了較多研究。美國(guó)海軍開發(fā)了航空數(shù)據(jù)管理與控制系統(tǒng)（aviation data management and control system，ADMACS）[2]以及艦船綜合信息系統(tǒng)（integrated shipboard information system，ISIS），通過在艦載機(jī)上安裝具有標(biāo)識(shí)的GPS，可實(shí)時(shí)顯示其位置狀態(tài)信息，進(jìn)而供相關(guān)人員手動(dòng)調(diào)控站位，實(shí)現(xiàn)艦載機(jī)的布列；李耀宇等[3]對(duì)艦載機(jī)甲板布列調(diào)運(yùn)業(yè)務(wù)進(jìn)行分析，總結(jié)了國(guó)內(nèi)外相應(yīng)的研究情況；胡玉龍等[4]對(duì)機(jī)庫進(jìn)行了模糊建模以求解機(jī)庫結(jié)構(gòu)設(shè)計(jì)方案，其機(jī)庫分段思想對(duì)布列問題很有幫助；張思[5]基于臨界多邊形（no-fit polygon，NFP）與遺傳算法（GA），以艦載機(jī)數(shù)量為目標(biāo)對(duì)該問題進(jìn)行了求解；田大肥[6]將該問題轉(zhuǎn)化成二維矩形裝箱問題，以總調(diào)運(yùn)路程為目標(biāo)對(duì)問題進(jìn)行了優(yōu)化求解；Li等[7]通過對(duì)放置空間和飛機(jī)二維幾何模型進(jìn)行建模，開發(fā)了一種用于解決飛機(jī)布列問題的新型遺傳算法。

從機(jī)庫布列的2個(gè)優(yōu)化目標(biāo)（即艦載機(jī)數(shù)量更多與出動(dòng)效率更高）出發(fā)，該問題可拆分為兩個(gè)優(yōu)化問題，即空間利用率優(yōu)化與考慮調(diào)運(yùn)效率的空間布局優(yōu)化?？臻g利用率優(yōu)化也稱裝箱問題，屬于一種NP難度問題。機(jī)庫空間狹小，將艦載機(jī)輪廓凸化處理會(huì)導(dǎo)致艦載機(jī)間隙過大，機(jī)庫空間利用不充分，故若想布列結(jié)果有實(shí)際使用價(jià)值，需要將機(jī)庫布列問題轉(zhuǎn)化為連續(xù)空間下二維凹多面體的裝箱問題，面積利用率越高，則放置的艦載機(jī)數(shù)量越多。二維裝箱問題解決方法很多，但目前在艦載機(jī)布列問題上應(yīng)用不多。如Burke等[8]基于軌跡線建立臨界多邊形，可以為復(fù)雜二維圖形排樣提供多樣化的運(yùn)算；Alvarez-Valdes等[9]基于分支定界算法，實(shí)現(xiàn)了對(duì)二維不規(guī)則形狀圖形的排樣切割；這個(gè)問題與Kheirkhah等[10]在動(dòng)態(tài)設(shè)施布局問題上的研究類似。考慮調(diào)運(yùn)效率的空間布局優(yōu)化對(duì)應(yīng)于倉儲(chǔ)、車庫領(lǐng)域的車位排布問題。Abdelfatah等[11]采用線性規(guī)劃對(duì)車庫停車容量進(jìn)行了優(yōu)化；徐涵喆等[12]提出一種基于規(guī)則的車位排布啟發(fā)式算法，得到了車位數(shù)較多且實(shí)用的排布方案。

艦載機(jī)不僅具有空間輪廓屬性，還有轉(zhuǎn)運(yùn)的業(yè)務(wù)需求。從現(xiàn)有的研究結(jié)果來看，一方面是弱化艦載機(jī)調(diào)度需求，以艦載機(jī)數(shù)量為唯一優(yōu)化目標(biāo)的布列優(yōu)化研究已取得不錯(cuò)的成果，另一方面是簡(jiǎn)化艦載機(jī)輪廓和布列算法，以調(diào)運(yùn)總路程為唯一目標(biāo)的研究也成果頗豐，但這兩方面都因優(yōu)化目標(biāo)單一，算法結(jié)果與機(jī)庫實(shí)際布列方案還存在很大的差距。目前，同時(shí)考慮這2個(gè)優(yōu)化目標(biāo)的研究尚屬空白。本文擬通過分析機(jī)庫布列問題的特點(diǎn)和業(yè)務(wù)需求，建立基本空間組合關(guān)系庫，計(jì)算可能的空間組合，然后基于遺傳算法優(yōu)化布列順序，建立以最大化布列飛機(jī)數(shù)目與最大化緊急出動(dòng)艦載機(jī)數(shù)量為優(yōu)化目標(biāo)的多目標(biāo)智能算法，優(yōu)化機(jī)庫甲板艦載機(jī)布列方案。

1 機(jī)庫布列問題描述

1.1 機(jī)庫環(huán)境描述

與飛行甲板相比，在機(jī)庫甲板容納更多艦載機(jī)的優(yōu)化目標(biāo)顯得更為重要。機(jī)庫甲板作為航母上空間最大的艙室，無起降跑道與艦島等空間限制，布列自由度高、靈活性強(qiáng)、優(yōu)化空間大。本文將以“尼米茲”級(jí)航母作為參考對(duì)象，研究艦載機(jī)在機(jī)庫甲板的布列問題。

“尼米茲”級(jí)航母機(jī)庫甲板的形狀約為矩形，長(zhǎng)208.5 m，寬33 m。其右舷有3部升降機(jī)，左舷有1部。升降機(jī)是艦載機(jī)在機(jī)庫甲板與飛行甲板之間轉(zhuǎn)運(yùn)的唯一途徑，其數(shù)量與位置不僅影響甲板之間的轉(zhuǎn)運(yùn)效率，而且還會(huì)對(duì)機(jī)庫內(nèi)的布列方案產(chǎn)生影響。在設(shè)計(jì)自動(dòng)布列算法時(shí)，應(yīng)當(dāng)考慮升降機(jī)的因素，以提高布列方案的轉(zhuǎn)運(yùn)效率與業(yè)務(wù)合理性。本文以升降機(jī)數(shù)量多的一側(cè)-右舷的升降機(jī)為節(jié)點(diǎn)，以相鄰升降機(jī)間隔中線為界限，將機(jī)庫劃分為3個(gè)子艙室，分隔線同時(shí)也與航母機(jī)庫防火簾的位置大體一致[13]，如圖1所示。

圖 1 “尼米茲”級(jí)機(jī)庫環(huán)境Fig.1 Hangar environment of USS Nimitz-class aircraft carrier

將機(jī)庫甲板劃分成3個(gè)子艙室后，每個(gè)子艙室僅將其相鄰的升降機(jī)作為調(diào)運(yùn)出口。設(shè)n個(gè)單位的布列問題為Gn(x)， 劃分成m個(gè)子艙室后，研究問題轉(zhuǎn)化為如式(1)所示的問題：

1.2 艦載機(jī)布列資源分配方法

航母攜帶的艦載機(jī)數(shù)量多，種類也多。在美軍進(jìn)行的“高強(qiáng)度演習(xí)”中，“尼米茲”級(jí)航母共裝載了F-14A戰(zhàn)斗機(jī)、F/A-18C戰(zhàn)斗/攻擊機(jī)、EA-6B電子戰(zhàn)機(jī)、S-3A反潛/加油機(jī)、E-2C預(yù)警機(jī)和SH-60B直升機(jī)等多種飛機(jī)，機(jī)庫內(nèi)還放置了少許小艇，這些統(tǒng)稱為布列單位。為保證每部升降機(jī)都能出動(dòng)特定類型的飛機(jī)，并保持升降機(jī)使用次數(shù)的均衡，本文將機(jī)庫總布列需求分配至子艙室。

分配的規(guī)則為：

1) 各子艙室布列的艦載機(jī)總數(shù)量不宜相差太大；

2) 同一種類飛機(jī)不應(yīng)過于集中。

根據(jù)上述規(guī)則，具體的分配算法流程如圖2所示。

圖 2 艙室需求分配算法流程圖Fig.2 The process of cabin requirement allocation algorithm

上述流程圖中，在對(duì)各類艦載機(jī)數(shù)量進(jìn)行判定后，先均勻分配布列需求，再將無法均勻分配的剩余部分與其他數(shù)量少的布列單位合并為新的需求，進(jìn)行二次分配。

1.3 艦載機(jī)幾何描述與布列原則

現(xiàn)有研究普遍采用以五邊形為主的凸多邊形，甚至以矩形來簡(jiǎn)化艦載機(jī)輪廓，這就導(dǎo)致艦載機(jī)間距空間、艦載機(jī)機(jī)翼與機(jī)身所夾空間等空間資源可能出現(xiàn)浪費(fèi)。本文設(shè)計(jì)的算法對(duì)艦載機(jī)幾何輪廓無要求，可以在同一方案內(nèi)采用多種簡(jiǎn)化或原輪廓的圖形來表示艦載機(jī)。如圖3所示，分別為簡(jiǎn)化輪廓戰(zhàn)斗機(jī)（折翼狀態(tài)）、原輪廓戰(zhàn)斗機(jī)（展翼狀態(tài)）、原輪廓預(yù)警機(jī)和原輪廓直升機(jī)（折翼狀態(tài)），這些輪廓均可通過2.1節(jié)中描述的布列算法進(jìn)行布列。

圖 3 部分艦載機(jī)輪廓圖Fig.3 Outline drawing of some carrier aircrafts

在本文研究工作中，圖形處理算法引用了Burke等[8]的研究成果：基于移動(dòng)碰撞算法，求解出NFP，從而實(shí)現(xiàn)二維排樣。NFP是二維排樣問題中關(guān)鍵的幾何工具，可以用于求解圖形間最優(yōu)靠接位置、重疊判斷、定位等。根據(jù)內(nèi)靠接NFP原理，基于最左最下原則（bottom left，BL）、最左最下填充原則（bottom left fill，BLF）、最合適位置原則（best fit，BF）及最低重心原則等多種定位策略，可以為布列單位選取比較有優(yōu)勢(shì)的布列位置。

1.4 艦載機(jī)機(jī)庫布列特點(diǎn)

艦載機(jī)在航母飛行甲板和機(jī)庫甲板上的約束有許多差異。通過分析機(jī)庫使用的特點(diǎn)，得出在機(jī)庫劃分艦載機(jī)站位時(shí)，需要考慮以下布列特點(diǎn)：

1) 機(jī)庫內(nèi)艦載機(jī)調(diào)運(yùn)全部靠牽引車實(shí)現(xiàn)，不需要考慮艦載機(jī)發(fā)動(dòng)機(jī)尾焰對(duì)機(jī)尾朝向的影響。

2) 單類型艦載機(jī)不應(yīng)全部依賴于特定的升降機(jī)轉(zhuǎn)運(yùn)，以防止在該升降機(jī)發(fā)生故障時(shí)無法出動(dòng)該類型艦載機(jī)。

3) 機(jī)庫的主要功能是存儲(chǔ)與維修，緊急出動(dòng)的艦載機(jī)是用來替換飛行甲板上發(fā)生故障的艦載機(jī)。不需要緊急出動(dòng)的艦載機(jī)無需考慮轉(zhuǎn)運(yùn)成本，這些飛機(jī)有足夠的時(shí)間在機(jī)庫內(nèi)完成運(yùn)動(dòng)姿態(tài)的轉(zhuǎn)換。

4) 緊急出動(dòng)艦載機(jī)的尾部應(yīng)朝向升降機(jī)，以便緊急出動(dòng)時(shí)由牽引車將其推入升降機(jī)，并牽引至飛行甲板指定保障站位進(jìn)行保障。

5) 緊急出動(dòng)艦載機(jī)的尾部不應(yīng)被任何障礙物阻攔，即無需移動(dòng)其他艦載機(jī)便可將其移動(dòng)至升降機(jī)，且應(yīng)盡可能避免正反向行駛多次切換。

6) 在不考慮飛行甲板使用的情況下，每部升降機(jī)都能用來緊急出動(dòng)艦載機(jī)。

7) 艦載機(jī)擺放在機(jī)庫甲板規(guī)定的區(qū)域內(nèi)。

8) 艦載機(jī)不可互相重疊。

9) 為方便管理與擺放美觀，艦載機(jī)劃分的站位需盡可能具有整齊劃一、朝向有規(guī)律等特點(diǎn)。

2 機(jī)庫布列問題建模

2.1 基于基本空間組合關(guān)系的艦載機(jī)組合生成算法

對(duì)于如航母機(jī)庫等自由空間下布列多類不規(guī)則輪廓物體的問題，巧妙利用艦載機(jī)等單位不規(guī)則輪廓間的鑲嵌，建立更緊密的組合關(guān)系是增加布列飛機(jī)數(shù)量、提高空間利用率的有效方法。艦載機(jī)的組合方式與業(yè)務(wù)強(qiáng)相關(guān)，涉及管理、安全、美觀等多個(gè)因素。本文依據(jù)實(shí)際業(yè)務(wù)，以提取艦載機(jī)等物體常用的、可靠的組合方式為規(guī)則來建立基本組合關(guān)系庫。

在基本組合關(guān)系庫中以類型為節(jié)點(diǎn)，記錄各類型間是否存在推薦的組合關(guān)系。將可以相互組合的布列單位放入集合中，再基于以整數(shù)拆分思想為基礎(chǔ)的搜索算法計(jì)算集合內(nèi)可能存在的組合分配方案。同時(shí)，基本組合關(guān)系庫可以支持新機(jī)型的布列設(shè)計(jì)，使算法具有一定的可擴(kuò)展性。

下面，以“尼米茲”級(jí)航母的主要固定翼艦載機(jī)機(jī)型為例來說明組合關(guān)系的建模。主要考慮F-14A，F(xiàn)/A-18C，EA-2C這3種機(jī)型，可能的組合關(guān)系包括對(duì)式和齊頭式，不同機(jī)型的組合關(guān)系如表1所示。

表 1 部分組合關(guān)系Table 1 Partial combination relationship of aircrafts

部分組合類型樣式如圖4所示。

圖 4 部分組合結(jié)果Fig.4 Partial combination results

以計(jì)算1架EA-2C和4架F-14A的組合方案結(jié)果集為例來介紹算法流程，流程圖如圖5所示。圖中，“*”后面的數(shù)字表示該機(jī)型的數(shù)量。

圖 5 組合算法流程圖Fig.5 The flow chart of combinatorial search

表 2 結(jié)果集Table 2 The result set

多個(gè)布列單位組合成布列模塊，各布列模塊中布列單位的數(shù)量如表2所示。表2中，“F-14A*4”表示4架F-14A組合擺放，為1個(gè)布列模塊，“F-14A*1+F-14A*1+F-14A*1+F-14A*1”表示4架F-14A單獨(dú)擺放，為4個(gè)布列模塊。兩者的區(qū)別在于布列模塊之間以最小包絡(luò)矩形的形式堆疊，沒有采用組合關(guān)系的4個(gè)布列模塊堆疊導(dǎo)致相鄰的“F-14A”的間隙空間不會(huì)被利用。提高面積利用率的唯一途徑在于建立布列模塊之間緊密的組合關(guān)系，即通過減少浪費(fèi)面積來實(shí)現(xiàn)。

由于組合關(guān)系固定，基于同種組合關(guān)系組合成的布列模塊內(nèi)停機(jī)密度一定相等。

原問題為有限空間內(nèi)多個(gè)不規(guī)則物體的二維連續(xù)排樣問題，上述算法將該問題通過基本組合關(guān)系庫離散化，將問題轉(zhuǎn)化為了組合優(yōu)化問題。在轉(zhuǎn)化過程中，嘗試從有限的合理組合關(guān)系來分析問題，將解空間由連續(xù)解空間離散化至可求解程度。被舍棄的解空間中不會(huì)存在滿足業(yè)務(wù)需求的最優(yōu)解。

2.2 組合布列優(yōu)化模型建立

根據(jù)前面的研究，艦載機(jī)布列方案有2個(gè)優(yōu)化目標(biāo)：布列數(shù)量更多與緊急出動(dòng)艦載機(jī)數(shù)量更多。通過對(duì)布列資源進(jìn)行分析，由搜索算法得出的結(jié)果集中包含了該布列資源下全部的組合方案。組合方案中的元素被命名為布列模塊，這在2.1節(jié)中已有介紹。通過為各模塊編號(hào)，基于LB（left bottom）策略，按編號(hào)順序迭代擺放至機(jī)庫空間即可實(shí)現(xiàn)一個(gè)完整的布列方案。LB策略意為將需要放置的模塊先向左移動(dòng)至邊界，再向下移動(dòng)至邊界。通過該策略實(shí)現(xiàn)擺放定位。通常LB策略會(huì)造成很明顯的元素分布不均勻問題，但在本文研究?jī)?nèi)容中，由于布列模塊內(nèi)部停機(jī)密度固定、布列模塊之間間隙基本相同，因此LB策略基本滿足此業(yè)務(wù)需求。

根據(jù)總體業(yè)務(wù)優(yōu)化目標(biāo)以及布列中的約束條件，可得到優(yōu)化問題的數(shù)學(xué)模型。

目標(biāo)函數(shù)為：

約束條件為：

式中：S為機(jī)庫甲板總空間；Si為編號(hào)為i的飛機(jī)所占空間，在機(jī)庫內(nèi)布列單位不僅不可互相重疊，也不可超出機(jī)庫空間；f1(x)為所有布列單位占用的面積，其只與布列資源中的布列單位數(shù)量有關(guān)；Bt為t類型布列單位經(jīng)路徑規(guī)劃模塊判斷后可直接出動(dòng)的數(shù)量。飛機(jī)是否能夠直接出動(dòng)的判斷邏輯是：?jiǎn)渭芘炤d機(jī)在將其他布列單位視為障礙物且不超過邊界的條件下，是否可以完成前往指定升降機(jī)的路徑規(guī)劃。

在這種情況下，路徑規(guī)劃只需要回答“可以”或“不可以”即可?！翱梢浴钡臄?shù)量與優(yōu)化目標(biāo)f2(x)密切相關(guān)，而路徑的長(zhǎng)度優(yōu)化從業(yè)務(wù)角度來看并無太大意義：機(jī)庫內(nèi)空間狹小，不同路徑間長(zhǎng)度差額的絕對(duì)值不大，不會(huì)對(duì)調(diào)運(yùn)效率產(chǎn)生明顯影響。本文基于Reed-Shepp算法實(shí)現(xiàn)路徑規(guī)劃進(jìn)而完成邏輯判斷。Reed-Shepp算法理論成熟，運(yùn)算速度快，且具有考慮運(yùn)動(dòng)學(xué)約束等特點(diǎn)。對(duì)升降機(jī)附近的布列模型進(jìn)行倒車路徑判定可迅速評(píng)估布列方案的緊急出動(dòng)能力。

當(dāng)布列資源確定時(shí)，機(jī)庫甲板內(nèi)面積利用率也可同時(shí)確定。兩目標(biāo)優(yōu)化問題此時(shí)成為單目標(biāo)優(yōu)化問題，即鎖定了布列資源后只需要對(duì)f2(x)求解即可。

此時(shí)，對(duì)于確定了布列資源后的模型，有

式中：C為機(jī)庫布列問題解集；D為組合方案集解集；E為布列順序解集。

3 機(jī)庫布列的多目標(biāo)啟發(fā)式算法設(shè)計(jì)

3.1 啟發(fā)式算法設(shè)計(jì)

基于搜索得出眾多組合方案后，需要對(duì)每個(gè)組合方案的最優(yōu)布列進(jìn)行優(yōu)化求解。同一組合方案下各模塊不同順序的擺放會(huì)得到不同的結(jié)果，模塊數(shù)決定了解空間大小。不同組合方案中模塊數(shù)量n并 不相同，解空間的大小為n!。本文基于遺傳算法來求解該模型。

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，其求解過程不受搜索空間的限制，也不要求解具有連續(xù)性，在組合優(yōu)化問題上具有很大優(yōu)勢(shì)。遺傳算法具有很強(qiáng)的魯棒性，能夠面對(duì)不同的解空間保持較穩(wěn)定的求解效率。

下面，具體說明為求解布列順序設(shè)計(jì)的遺傳算法內(nèi)容。

本文采用十進(jìn)制編碼方式，染色體長(zhǎng)度值為模塊數(shù)量m值的2倍。每個(gè)模塊具有2個(gè)變量：布列順序與布列角度。所有的模塊只考慮垂直與水平2種擺放形式。某含有9個(gè)模塊的組合方案的染色體編碼為[(2,0),(3,1),(4,0),(5,1),(1,0),(6,1),(7,0),(8,1),(0,0)]，其含義為布列順序(2,3,4,5,1,6,7,8,0)，布列角度編碼0代表水平擺放，1代表垂直擺放。基于Abdoun等[14]的研究成果，本文采用“順序交叉”（order crossover，OX）規(guī)則對(duì)染色體進(jìn)行交叉操作。第1步，隨機(jī)選擇一對(duì)染色體（父代）中幾個(gè)基因的起止位置（兩染色體被選位置相同）；第2步，生成一個(gè)子代，并保證子代中被選中基因的位置與父代相同；第3步，先找出第1步選中的基因在另一個(gè)父代中的位置，再將其余基因按順序放入上一步生成的子代中，如圖6所示。

圖 6 編碼流程Fig.6 Encoding process

變異選用單點(diǎn)突變，即隨機(jī)選取要突變的基因位點(diǎn)，然后突變成與剩余的其他基因不同的基因。

通過對(duì)布列方案中的每架艦載機(jī)（只計(jì)算F-14A，F(xiàn)/A-18C等戰(zhàn)斗機(jī)型，不計(jì)算預(yù)警機(jī)、救生艇、直升機(jī)等非戰(zhàn)斗機(jī)型）遍歷調(diào)用路徑規(guī)劃算法，計(jì)算可緊急出動(dòng)的艦載機(jī)數(shù)量，將其作為適應(yīng)度值。

遺傳算法流程圖如圖7所示。

圖 7 遺傳算法求解流程Fig.7 Solving process of GA

在算法運(yùn)行中，若某一編碼對(duì)應(yīng)的布列方案因機(jī)庫空間幾何約束導(dǎo)致空間不足而無法完成放置，則會(huì)放棄該編碼。通過將機(jī)庫幾何輪廓作為二維排樣中的約束不斷淘汰不合格的編碼。

3.2 迭代調(diào)用算法實(shí)現(xiàn)兩目標(biāo)優(yōu)化

當(dāng)機(jī)庫內(nèi)擺放一定數(shù)量的艦載機(jī)時(shí)，利用遺傳算法可以計(jì)算出最大緊急出動(dòng)飛機(jī)數(shù)量以及其對(duì)應(yīng)的布列方案。本文為遺傳算法設(shè)置適應(yīng)度閾值，當(dāng)達(dá)到閾值時(shí)提前終止遺傳算法，以使機(jī)庫完全能夠滿足該數(shù)量布列需求下對(duì)于緊急出動(dòng)的業(yè)務(wù)需求。終止算法后，在布列需求中添加一架默認(rèn)的戰(zhàn)斗機(jī)型，如F-14A或F/A-18C，繼續(xù)進(jìn)行布列方案探究。迭代多次后，混合算法能夠輸出布列數(shù)量與最大緊急出動(dòng)能力平衡的布列方案。m個(gè)子艙室的滿意解構(gòu)成總機(jī)庫的滿意解。

兩目標(biāo)迭代算法流程如圖8所示。

4 仿真實(shí)驗(yàn)

由文獻(xiàn)[13]，得到美海軍“尼米茲”級(jí)航母機(jī)庫的布列圖如圖9所示。

圖 8 迭代算法流程Fig.8 Solving process of iterative algorithm

圖 9 “尼米茲”級(jí)航母機(jī)庫布列方案Fig.9 The hangar layout scheme of Nimitz-class aircraft carrier

本文設(shè)計(jì)了“尼米茲”級(jí)航母在類似戰(zhàn)斗模式下機(jī)庫的布列需求，并對(duì)算法有效性進(jìn)行驗(yàn)證。算法采用C++編程實(shí)現(xiàn)，運(yùn)行在CPU為i5-6500(4核，3.2 GHz)、內(nèi)存8 GB的計(jì)算機(jī)上。該布列需求包括7種布列單位，初始布列需求與美軍方案保持一致，經(jīng)過任務(wù)分配后得到具體子艙室的布列需求如表3所示。

表 3 艦載機(jī)機(jī)庫基本布列需求表Table 3 Basic layout requirements of aircraft hangar

在本次算法運(yùn)行中，設(shè)最大遺傳代數(shù)Genmax=100，種群空間Popmax=50，變異率pm=0.02，交叉率pc=0.6，設(shè)置閾值為

式中：Ek為第k個(gè)艙室緊急出動(dòng)的艦載機(jī)數(shù)量；Fk為第k個(gè)艙室擁有的升降機(jī)數(shù)量。每個(gè)艙室單獨(dú)求解。

在算法運(yùn)行過程中，優(yōu)化算法表現(xiàn)出較好的收斂性，不同子艙室的求解時(shí)間接近，求解出的總布列方案如圖10所示。

圖 10 最終布列結(jié)果Fig.10 The final layout result

在計(jì)算美軍布列方案利用率時(shí)，需將各艦載機(jī)占用面積替換為本文布列算法中同類型艦載機(jī)采用的輪廓的占用面積，以保證結(jié)果不受輪廓因素的干擾。經(jīng)計(jì)算，得到美軍布列方案面積利用率為36.54%。

在本文得出的方案中，各布列單位長(zhǎng)、寬參數(shù)經(jīng)過核對(duì)，符合實(shí)際尺寸。在計(jì)算中，通過多次迭代加入F/A-18C來增加布列數(shù)量，使機(jī)庫總布列單位數(shù)量達(dá)到44架，其中F/A-18C為27架，面積利用率為53.46%，與美軍布列方案相比提高了16.92%。各升降機(jī)均保證了一定的緊急出動(dòng)能力?？紤]到可能會(huì)因擺放規(guī)則而出現(xiàn)右上方區(qū)域利用率不夠高的情況，可人工對(duì)生成的方案進(jìn)行艦載機(jī)間距調(diào)整，使之分布均勻。

5 結(jié) 論

本文通過對(duì)機(jī)庫環(huán)境進(jìn)行分析，對(duì)艦載機(jī)常用擺放形式進(jìn)行了歸納整理；通過對(duì)基本組合關(guān)系庫進(jìn)行組合關(guān)系搜索，實(shí)現(xiàn)布列資源預(yù)處理，得到了所有可能的布列區(qū)塊組合；以布列面積利用率最大化與艦載機(jī)可直接出動(dòng)數(shù)量最大化為目標(biāo)，通過遺傳算法對(duì)組合模塊進(jìn)行布列順序優(yōu)化，與美軍布列方案對(duì)比驗(yàn)證了算法的有效性。通過研究，得到如下結(jié)論：

1) 本文提出的布列算法能夠應(yīng)對(duì)不同類型機(jī)庫、不同布列需求下同類問題的計(jì)算與優(yōu)化；

2) 基于基本組合關(guān)系庫得到的組合方案使得布列結(jié)果具有較高的實(shí)用性、安全性與美觀性；

3) 啟發(fā)式算法不僅能夠盡可能提高機(jī)庫存放艦載機(jī)數(shù)量，同時(shí)能夠保證艦載機(jī)緊急出動(dòng)能力；

4) 可視化輸出的布列結(jié)果，可以為機(jī)庫管理員提供站位劃分的輔助決策依據(jù)。

由于艦載機(jī)組合關(guān)系十分復(fù)雜，本文多以同類機(jī)型組合為主進(jìn)行研究。基本組合關(guān)系庫需要在后續(xù)的工作中繼續(xù)豐富，同時(shí)組合的角度也可從離散化向連續(xù)化繼續(xù)深入研究。目前，基本組合關(guān)系庫需要用戶手動(dòng)輸入，若能依據(jù)外形輪廓智能生成則更方便、更全面，更豐富的組合關(guān)系可以得到更優(yōu)秀的布列方案。組合關(guān)系與艦載機(jī)實(shí)際業(yè)務(wù)密切相關(guān)，且不同戰(zhàn)斗模式下機(jī)庫對(duì)組合關(guān)系有不同的要求，特定區(qū)域?qū)ε艠咏嵌纫灿屑s束，需要建立更復(fù)雜的業(yè)務(wù)模型。此外，啟發(fā)式算法的設(shè)計(jì)與優(yōu)化空間巨大，與求解效率緊密相關(guān)，還需進(jìn)行大量的研究。