卞大鵬，欒添添，宋曄

1.海軍駐武漢701所軍事代表室，湖北武漢430064 2.哈爾濱工程大學(xué)自動化學(xué)院，黑龍江哈爾濱150001

基于模擬退火算法的艦載機(jī)布列方法研究

卞大鵬1，欒添添2，宋曄2

1.海軍駐武漢701所軍事代表室，湖北武漢430064 2.哈爾濱工程大學(xué)自動化學(xué)院，黑龍江哈爾濱150001

為提高航母飛行甲板的利用率，增加其最大載機(jī)量，采用模擬退火算法對艦載機(jī)布列方案進(jìn)行了優(yōu)化。首先對艦載機(jī)在航母上布列問題進(jìn)行了分析，著重分析了艦載機(jī)在甲板上二維不規(guī)則布列的各種約束;然后基于臨界多邊形法對艦載機(jī)包絡(luò)圖形間的靠接關(guān)系及其在甲板輪廓圖形內(nèi)定位方法進(jìn)行了研究;最后應(yīng)用模擬退火算法對艦載機(jī)在飛行甲板內(nèi)布列的方案進(jìn)行了優(yōu)化計算，得到了一種較優(yōu)的艦載機(jī)布列方案，提高了航母飛行甲板的利用率，有利于增加航母的常規(guī)載機(jī)量并提高其作戰(zhàn)能力。

艦載機(jī);布列;遞歸算法;模擬退火算法;艦載機(jī)甲板

網(wǎng)絡(luò)出版地址: http://www.cnki.net/kcms/detail/23.1191.U.20150727.0857.002.html

自從20世紀(jì)開始，人類對海洋資源的爭奪越發(fā)激烈，海洋工程技術(shù)及艦船制造技術(shù)發(fā)展勢頭迅猛。在當(dāng)今世界，航母甚至可以作為一個國家海上力量的具體體現(xiàn)。航空母艦主要靠艦載機(jī)作戰(zhàn)，艦載機(jī)的數(shù)量可以決定航母的戰(zhàn)斗力。航母的飛行甲板上有時會有幾十架艦載機(jī)，同時還有保障設(shè)備及大量工作人員，飛行甲板會顯得十分擁擠，因此，艦載機(jī)在甲板上的調(diào)度布列研究中，甲板上艦載機(jī)數(shù)量的確定尤為重要。一般來說，在可以正常調(diào)度的情況下，飛行甲板上可搭載的艦載機(jī)數(shù)量約為飛行甲板的最大載機(jī)量的80%。研究飛行甲板上可布列的艦載機(jī)的最大數(shù)量可以作為設(shè)計艦載機(jī)尺寸的重要參考。綜上所述，航母飛行甲板上最大載機(jī)量的研究在航母甲板上艦載機(jī)的布列及調(diào)度研究中十分重要［1-4］。

文中以“Nimitz”級航空母艦為研究對象，通過對艦載機(jī)在飛行甲板上布列的問題進(jìn)行分析并建立數(shù)學(xué)模型，將問題轉(zhuǎn)化為組合優(yōu)化問題，使用模擬退火算法對艦載機(jī)的布列方案進(jìn)行優(yōu)化。

1　艦載機(jī)布列問題概述

1.1甲板和艦載機(jī)

航空母艦有上下2層甲板:飛行甲板及機(jī)庫甲板，它們都可以停放艦載機(jī)。文中主要研究艦載機(jī)在飛行甲板上的布列問題。

“Nimitz”級航母飛行甲板長為332.9 m，寬為76.8 m。航母的艦島很小，“Nimitz”級航母的艦島占地面積僅有141 m2左右，被設(shè)置在右舷后部兩個升降機(jī)之間。

航母上搭載的艦載機(jī)種類很多，在高潮演習(xí)時，“Nimitz”甲板上有以下幾種艦載機(jī):戰(zhàn)斗機(jī)F-14A、F/A-18C，電子戰(zhàn)機(jī)EA-6B，反潛/加油機(jī)S-3B，電子偵察機(jī)ES-3A，預(yù)警機(jī)E-2C和直升機(jī)SH-60。

1.2艦載機(jī)布列約束

一般艦載機(jī)停在飛行甲板上時有3個停放特點(diǎn)，分別為:

1)停在甲板上待出動或正在被維護(hù)的艦載機(jī)對將要進(jìn)行起飛操作的飛機(jī)和在空中準(zhǔn)備著艦操作的飛機(jī)不可以造成影響，因此艦面上艦載機(jī)布列方案要根據(jù)有操作作業(yè)的艦載機(jī)在艦面上的移動路徑進(jìn)行設(shè)計。

2)由于艦載機(jī)一波出動的過程中需要不同種類的艦載機(jī)完成不同的任務(wù)，因此航母上不同艦載機(jī)停放的位置也需要一定的安排規(guī)劃。

3)一般在飛行甲板上停放的應(yīng)為沒有故障的艦載機(jī)，它們需要隨時待命準(zhǔn)備出動。

1.3艦載機(jī)的數(shù)學(xué)表達(dá)

艦載機(jī)的實(shí)際幾何形狀是十分復(fù)雜的，這里以F/A-18C型戰(zhàn)斗機(jī)為例，為了盡量減少在布列過程中的工作量，但又能保證艦載機(jī)的基本形狀而不影響其在甲板上的布列方法，為此將艦載機(jī)簡化為較簡單的幾何形狀。文中將艦載機(jī)簡化為一個五邊形，這個五邊形可以將F/A-18C戰(zhàn)機(jī)的輪廓完全包圍。

這個F/A-18C戰(zhàn)機(jī)輪廓多邊形P可以表示為P=P0，P1，P2，P3，P4{}，選取點(diǎn)P0作為參考點(diǎn)，如圖1所示。

圖1　艦載機(jī)的包絡(luò)多邊形

2　臨界多邊形的艦載機(jī)布列問題

在飛行甲板這個多邊形中，若干架艦載機(jī)之間的靠接關(guān)系、艦載機(jī)在甲板上的定位方式是它們在甲板上布列的前提。以上提出的問題都是二維不規(guī)則圖形布列問題中要討論的，在解決這些問題時就需要研究臨界多邊形算法(no fit polygon，NFP)這一在二維布列問題中極為關(guān)鍵的算法。

對于多個多邊形的靠接，臨界多邊形法能夠迅速的計算出它們之間的靠接關(guān)系并判斷它們是否相交［5-10］。完成這些工作之后才可將問題的數(shù)學(xué)模型總結(jié)出來，并使用智能優(yōu)化算法進(jìn)行優(yōu)化。

2.1臨界多邊形

臨界多邊形的定義:保持多邊形A不動，令多邊形B圍繞多邊形A做自身不轉(zhuǎn)動的剛體旋轉(zhuǎn)，在整個運(yùn)動過程中的參考點(diǎn)的軌跡就是B對于A的臨界多邊形，記做NFPAB。當(dāng)多邊形B包含在多邊形A內(nèi)部時，它們之間的臨界多邊形則屬于內(nèi)靠接臨界多邊形。圖2展示了內(nèi)靠接臨界多邊形的產(chǎn)生過程。

圖2　臨界多邊形的產(chǎn)生

2.2艦載機(jī)圖形相對甲板輪廓的NFP的生成

分析艦載機(jī)布放問題知艦載機(jī)停放于飛行甲板內(nèi)部，且只被允許停泊在安全停機(jī)區(qū)之內(nèi)，則該布列問題屬于典型的內(nèi)靠接問題。故在求解時要按照內(nèi)靠接NFP求法進(jìn)行計算。

根據(jù)內(nèi)靠接NFP原理得到艦載機(jī)圖形和甲板輪廓的內(nèi)靠接NFP，利用定位策略獲取臨界多邊形上比較有優(yōu)勢的布放點(diǎn)，將艦載機(jī)圖形放置于該點(diǎn)，于是完成單個艦載機(jī)的確定位置及擺放。單個艦載機(jī)擺放完成后，其與甲板內(nèi)邊界靠接位置形成的邊界與其余甲板邊界融合成為新的內(nèi)邊界。這樣，每擺放一個艦載機(jī)圖形就形成新的內(nèi)邊界，再計算下一個艦載機(jī)圖形與其的臨界多邊形。以此類推，直至甲板輪廓內(nèi)部無法再容納一個艦載機(jī)圖形為止，完成整個布列過程。算法過程如圖3所示。

圖3　艦載機(jī)被放置于甲板內(nèi)部過程

2.3艦載機(jī)圖形在甲板圖形內(nèi)部位置的確定方法

文中遵循“最低重心”原則確定艦載機(jī)在甲板內(nèi)部的位置，即尋找一條最低點(diǎn)縱坐標(biāo)最小的重心NFP。該原則的原理如圖4所示。

圖4　“最低重心”位置確定法原理

根據(jù)“最低重心”原則可得艦載機(jī)在甲板內(nèi)部定位算法的過程為:首先求出艦載機(jī)包絡(luò)圖形的重心;然后以其重心為參考點(diǎn)求出內(nèi)靠接重心NFP。由于在研究內(nèi)靠接布列問題時，待排列多邊形在保持與外部多邊形接觸的同時，若變換其角度且保持接觸狀態(tài)，那么其重心位置就會發(fā)生變化，因而需要在確定其位置時考慮在哪一角度其重心位置最低。采用分段式搜索法尋找艦載機(jī)圖形重心最低的位置及對應(yīng)角度值。

3　使用遞歸排列法對艦載機(jī)進(jìn)行布列

根據(jù)前面的研究，艦載機(jī)的布列方案可視為多個艦載機(jī)包絡(luò)多邊形定位變量的組合，定位一個艦載機(jī)包絡(luò)多邊形可以用其重心最低點(diǎn)的重心坐標(biāo)(xi，yi)和其旋轉(zhuǎn)的角度θi來確定，即艦載機(jī)包絡(luò)多邊形Pi的位置變量可表示為(xi，yi，θi)，由此多個艦載機(jī)包絡(luò)多邊形的位置變量組合可以表示為((x1，y1，θ1)，(x2，y2，θ2)，…，(xn，yn，θn))。

工程中常采用啟發(fā)式算法和智能優(yōu)化算法來進(jìn)行排列順序的確定。為與使用智能優(yōu)化算法得到的結(jié)果進(jìn)行對比，首先使用啟發(fā)式算法對艦載機(jī)包絡(luò)圖形進(jìn)行排布。文中由于參與布列的艦載機(jī)包絡(luò)圖形的面積大小是一致的，所以選取一個隨機(jī)的布列順序?qū)ε炤d機(jī)包絡(luò)圖形進(jìn)行布列，具體的布列算法為:

1)為全部艦載機(jī)包絡(luò)圖形(這里假設(shè)有90架艦載機(jī)參與布列)確定一個布列次序，將其儲存在一個數(shù)組中;

2)將甲板輪廓多邊形設(shè)為順時針方向變化以方便計算內(nèi)靠接NFP;

3)開始搜索布列艦載機(jī)的循環(huán)，循環(huán)計數(shù)變量i=0，得到當(dāng)前布列艦載機(jī)序號和艦載機(jī)包絡(luò)圖形，去掉不在當(dāng)前布列區(qū)域內(nèi)的孔洞，多角度旋轉(zhuǎn)艦載機(jī)包絡(luò)圖形并計算重心NFP，得到最低重心點(diǎn)和角度，并根據(jù)這兩個數(shù)據(jù)對艦載機(jī)包絡(luò)圖形進(jìn)行定位;

4)扣除已布列部分，在允許的誤差范圍內(nèi)簡化甲板輪廓圖形;

5)隨著i的遞增，重復(fù)上述步驟，依次將艦載機(jī)包絡(luò)圖形排布在甲板輪廓圖形中。

遞歸排列法流程如圖5所示，最終得到布列仿真結(jié)果如圖6所示。采用遞歸算法得到的仿真結(jié)果顯示，在甲板輪廓圖形中共排布了80個艦載機(jī)包絡(luò)圖形，即飛行甲板最多可容納80架艦載機(jī)。仿真過程中，在甲板上可以布列艦載機(jī)的區(qū)域為飛行甲板上不包括斜角甲板的所有位置，其面積大小約為13 809.3 m2，一架F/A-18C占地面積約為132.4 m2，則甲板的面積利用率為76.7%。

圖5　遞歸排列法流程

圖6　遞歸算法求得艦載機(jī)最大布列方式

4　艦載機(jī)布列方案的模擬退火優(yōu)化

4.1模擬退火算法

模擬退火算法是一種可以尋找到全局最優(yōu)的算法，若在搜索過程中陷入局部最優(yōu)，它可以根據(jù)概率突跳性逃出局部最優(yōu)并繼續(xù)搜索全局最優(yōu)解［8］。

Metropolis接受準(zhǔn)則是該算法的一個重要的準(zhǔn)則，宗旨是用概率接納新狀態(tài)。設(shè)此時溫度為t，狀態(tài)為i，系統(tǒng)的能量是f(i)，當(dāng)細(xì)微波動致新狀態(tài)j時，系統(tǒng)能量變?yōu)閒(j)。若Δf=f(j)－f(i)＜0，則接受狀態(tài)j為當(dāng)下狀態(tài);若Δf=f(j)－f(i)＞0，則要計算exp(－Δf/t)以確定是否接受新狀態(tài)，如果它大于random(0，1)，則接受，否則保留原狀態(tài)i。綜上，狀態(tài)接受概率可表示為

4.2問題的數(shù)學(xué)模型

令盡量多的艦載機(jī)以一定的規(guī)則排布在航母的飛行甲板上，使飛行甲板的面積利用率達(dá)到最高屬于組合優(yōu)化問題，布列方案是問題的解空間，每種方案都是由被排布的艦載機(jī)的位置變量構(gòu)成的，最優(yōu)解即是使甲板面積利用率最高的方案。已經(jīng)提到，定位一架艦載機(jī)Pi可以由艦載機(jī)的簡化多邊形的重心坐標(biāo)(xi，yi)和旋轉(zhuǎn)角度θi確定，于是有(xi，yi，θi)為艦載機(jī)Pi的位置變量，參與布列的艦載機(jī)位置變量組合是問題的解空間。這里可采用智能優(yōu)化算法對問題進(jìn)行優(yōu)化得到最優(yōu)的艦載機(jī)位置變量組合。

在采用定位算法后，艦載機(jī)重心坐標(biāo)及旋轉(zhuǎn)角度都是確定的，布列問題的求解只與布列順序有關(guān)，這樣解空間可表示為艦載機(jī)布列序號組合，即{ P1，P2，…，Pi，…，Pn}。

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

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

約束條件為

式中: S={ P1，P2，…，Pn}表示一種布列方案，S表示甲板面積，sp表示單架艦載機(jī)的面積(以F/A-18C型戰(zhàn)斗機(jī)為例)。則目標(biāo)函數(shù)的含義為目標(biāo)值=剩余甲板面積=甲板面積－全部布列艦載機(jī)面積的和。模擬退火算法基本流程如圖7所示。

圖7　模擬退火算法流程

4.3仿真結(jié)果分析

在進(jìn)行仿真時，算法的參數(shù)選擇為:接受概率P0=0.7;初溫t0=51.5;終止溫度t=5%t0。仿真過程中，在甲板上可以布列艦載機(jī)的區(qū)域為飛行甲板上不包括斜角甲板的所有位置，其面積大小約為13 809.3 m2，簡化輪廓后一架F/A-18C占地面積約為132.4 m2。經(jīng)過優(yōu)化仿真計算，目標(biāo)值變化曲線如圖8所示，從圖中可以看出，模擬退火算法的目標(biāo)值在逐漸減小，并穩(wěn)定于2 158.2 m2，說明模擬退火算法是收斂的。

圖8　目標(biāo)值變化曲線

最終得到的布列結(jié)果如圖9所示，在布列過程中艦載機(jī)完全布列在飛行甲板安全停機(jī)區(qū)內(nèi)部并避開艦島和4個彈射器，使用該算法共在“Nimitz”級航母的飛行甲板上布列了88架F/A-18C型艦載機(jī)，甲板面積利用率為84.4%。

圖9　模擬退火算法優(yōu)化得艦載機(jī)布列方案

模擬退火算法優(yōu)化出的布列方案與前文使用遞歸算法求得布列方案相比，在甲板上多布列了8架艦載機(jī)，甲板面積利用率提高了7.7%，這說明模擬優(yōu)化算法計算出的布列方案優(yōu)于普通啟發(fā)式算法計算出的方案，可以有效提高甲板面積的利用率。

5　結(jié)束語

文中以“Nimitz”級航母為研究對象，針對甲板面積利用率最高為目標(biāo)對艦載機(jī)進(jìn)行布列，該問題可以歸納為帶有約束的組合優(yōu)化問題，因此選擇模擬退火算法對問題進(jìn)行優(yōu)化。最終經(jīng)過優(yōu)化得到了一個較優(yōu)的艦載機(jī)布列方案，使甲板面積利用率有了一定的提高，這說明了模擬退火算法的優(yōu)越性，文中的研究成果可以為未來艦載機(jī)和航母飛行甲板的尺寸設(shè)計提供一定的理論參考價值。

［1］JOHNSTON J S.A feasibility study of a persistent monitoring system for the flight deck of US Navy aircraft carriers ［R］.Dayton: Air Force Inst of Tech Wright-Patterson AFB OH Graduate School of Engineering and Management，2009.

［2］李耀宇，朱一凡，齊鳴，等.艦載機(jī)甲板布列調(diào)運(yùn)優(yōu)化方法研究［J］.指揮控制與仿真，2013，35(2) : 125-131.

［3］司維超，韓維，史瑋韋.基于PSO算法的艦載機(jī)艦面布放調(diào)度方法研究［J］.航空學(xué)報，2012，33(11) : 2048-2056.

［4］RYAN J C，CUMMINGS M L，ROY N，et al.Designing an interactive local and global decision support system for aircraft carrier deck scheduling［J］.Proceedings AIAA Infotech，2011，10(6) : 217-231.

［5］劉胡瑤，何援軍.基于軌跡計算的NFP求解算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2006，18(8) : 1123-1129.

［6］楊衛(wèi)波，王萬良.改進(jìn)臨界多邊形生成算法［J］.計算機(jī)工程與應(yīng)用，2013(1) : 32-35.

［7］盧齊飛.二維不規(guī)則圖形下料排樣優(yōu)化算法研究［D］.廣州:廣東工業(yè)大學(xué)，2013: 15-36.

［8］IMAMICHI T，YAGIURA M，NAGAMOCHI H.An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem［J］.Discrete Optimization，2009，6(4) : 345-361.

［9］陳勇.基于遺傳模擬退火算法的不規(guī)則多邊形排樣［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2003(5) : 598-609.

［10］BURKE E，HELLIER R，KENDALL G，et al.A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem［J］.Operations Research，2006，54(3) : 587-601.

A layout method of carrier-based aircraft based on simulated annealing

BIAN Dapeng1，LUAN Tiantian2，SONG Ye2

1.The Navy in Wuhan 701 Military Representative Office，Wuhan 430064，China 2.College of Automation，Harbin Engineering University，Harbin 150001，China

This paper researches a class of aircraft layouts on the deck of a carrier.In order to improve the carrier flight deck area utilization and increase the maximum amount of aircrafts，the simulated annealing algorithm is used to optimize the layout scheme of aircrafts.At first，the problem of aircraft layout on the carrier is analyzed.The emphasis is put on the constraints of the two-dimensional irregular arrangement of the aircraft on the deck.Then this paper studies the location within the deck contour graphic and the inarching relationship between aircraft envelope graphics based on the no-fit polygon (NFP) method.The simulated annealing algorithm is used to optimize the aircraft envelope graphics layout scheme on the flight deck graphic.Finally an optimal aircraft layout scheme is obtained and the utilization rate of the carrier flight deck is increased.It is beneficial to increase the normal amount of aircrafts on the carrier and improve its operational capability.

carrier-based aircraft; layout; recursive algorithm; simulated annealing; decks

TP273.1

A

1009-671X(2015) 04-020-05

10.3969/j.issn.1009-671X.201411002

2014-11-07.網(wǎng)絡(luò)出版日期: 2015-07-27.

卞大鵬(1976-)，男，工程師，碩士.

欒添添，E-mail: luantiantian1988@126.com.