基于模拟退火算法的舰载机布列方法研究

卞大鹏，栾添添，宋晔

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.