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

卞大鵬，欒添添，宋曄

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

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

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

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

為提高航母飛行甲板的利用率，增加其最大載機(jī)量，采用模擬退火算法對(duì)艦載機(jī)布列方案進(jìn)行了優(yōu)化。首先對(duì)艦載機(jī)在航母上布列問(wèn)題進(jìn)行了分析，著重分析了艦載機(jī)在甲板上二維不規(guī)則布列的各種約束;然后基于臨界多邊形法對(duì)艦載機(jī)包絡(luò)圖形間的靠接關(guān)系及其在甲板輪廓圖形內(nèi)定位方法進(jìn)行了研究;最后應(yīng)用模擬退火算法對(duì)艦載機(jī)在飛行甲板內(nèi)布列的方案進(jìn)行了優(yōu)化計(jì)算，得到了一種較優(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ì)開始，人類對(duì)海洋資源的爭(zhēng)奪越發(fā)激烈，海洋工程技術(shù)及艦船制造技術(shù)發(fā)展勢(shì)頭迅猛。在當(dāng)今世界，航母甚至可以作為一個(gè)國(guó)家海上力量的具體體現(xiàn)。航空母艦主要靠艦載機(jī)作戰(zhàn)，艦載機(jī)的數(shù)量可以決定航母的戰(zhàn)斗力。航母的飛行甲板上有時(shí)會(huì)有幾十架艦載機(jī)，同時(shí)還有保障設(shè)備及大量工作人員，飛行甲板會(huì)顯得十分擁擠，因此，艦載機(jī)在甲板上的調(diào)度布列研究中，甲板上艦載機(jī)數(shù)量的確定尤為重要。一般來(lái)說(shuō)，在可以正常調(diào)度的情況下，飛行甲板上可搭載的艦載機(jī)數(shù)量約為飛行甲板的最大載機(jī)量的80%。研究飛行甲板上可布列的艦載機(jī)的最大數(shù)量可以作為設(shè)計(jì)艦載機(jī)尺寸的重要參考。綜上所述，航母飛行甲板上最大載機(jī)量的研究在航母甲板上艦載機(jī)的布列及調(diào)度研究中十分重要［1-4］。

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

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

1.1甲板和艦載機(jī)

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

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

航母上搭載的艦載機(jī)種類很多，在高潮演習(xí)時(shí)，“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ī)停在飛行甲板上時(shí)有3個(gè)停放特點(diǎn)，分別為:

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

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

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

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

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

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

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

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

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

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

2.1臨界多邊形

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2)將甲板輪廓多邊形設(shè)為順時(shí)針?lè)较蜃兓苑奖阌?jì)算內(nèi)靠接NFP;

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

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

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

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

圖5　遞歸排列法流程

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

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

4.1模擬退火算法

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

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

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

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

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

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

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

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

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

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

5　結(jié)束語(yǔ)

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

［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é)報(bào)，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］劉胡瑤，何援軍.基于軌跡計(jì)算的NFP求解算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18(8) : 1123-1129.

［6］楊衛(wèi)波，王萬(wàn)良.改進(jìn)臨界多邊形生成算法［J］.計(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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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.