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

卞大鵬，欒添添，宋曄

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

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

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

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

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

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

網絡出版地址: http://www.cnki.net/kcms/detail/23.1191.U.20150727.0857.002.html

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

文中以“Nimitz”級航空母艦為研究對象，通過對艦載機在飛行甲板上布列的問題進行分析并建立數學模型，將問題轉化為組合優化問題，使用模擬退火算法對艦載機的布列方案進行優化。

1　艦載機布列問題概述

1.1甲板和艦載機

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

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

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

1.2艦載機布列約束

一般艦載機停在飛行甲板上時有3個停放特點，分別為:

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

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

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

1.3艦載機的數學表達

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

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

圖1　艦載機的包絡多邊形

2　臨界多邊形的艦載機布列問題

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

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

2.1臨界多邊形

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

圖2　臨界多邊形的產生

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

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

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

圖3　艦載機被放置于甲板內部過程

2.3艦載機圖形在甲板圖形內部位置的確定方法

文中遵循“最低重心”原則確定艦載機在甲板內部的位置，即尋找一條最低點縱坐標最小的重心NFP。該原則的原理如圖4所示。

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

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

3　使用遞歸排列法對艦載機進行布列

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

工程中常采用啟發式算法和智能優化算法來進行排列順序的確定。為與使用智能優化算法得到的結果進行對比，首先使用啟發式算法對艦載機包絡圖形進行排布。文中由于參與布列的艦載機包絡圖形的面積大小是一致的，所以選取一個隨機的布列順序對艦載機包絡圖形進行布列，具體的布列算法為:

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

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

3)開始搜索布列艦載機的循環，循環計數變量i=0，得到當前布列艦載機序號和艦載機包絡圖形，去掉不在當前布列區域內的孔洞，多角度旋轉艦載機包絡圖形并計算重心NFP，得到最低重心點和角度，并根據這兩個數據對艦載機包絡圖形進行定位;

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

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

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

圖5　遞歸排列法流程

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

4　艦載機布列方案的模擬退火優化

4.1模擬退火算法

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

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

4.2問題的數學模型

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

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

根據優化目標以及布列中的約束條件可得待優化問題的數學模型。

目標函數為

約束條件為

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

圖7　模擬退火算法流程

4.3仿真結果分析

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

圖8　目標值變化曲線

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

圖9　模擬退火算法優化得艦載機布列方案

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

5　結束語

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

［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］.指揮控制與仿真，2013，35(2) : 125-131.

［3］司維超，韓維，史瑋韋.基于PSO算法的艦載機艦面布放調度方法研究［J］.航空學報，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］.計算機輔助設計與圖形學學報，2006，18(8) : 1123-1129.

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

［7］盧齊飛.二維不規則圖形下料排樣優化算法研究［D］.廣州:廣東工業大學，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］陳勇.基于遺傳模擬退火算法的不規則多邊形排樣［J］.計算機輔助設計與圖形學學報，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.網絡出版日期: 2015-07-27.

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

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