基于改进遗传算法的舰载机出库调度优化方法*

刘亚杰，李忠猛，谢 君

（海军工程大学，武汉 430033）

基于改进遗传算法的舰载机出库调度优化方法*

刘亚杰，李忠猛，谢 君

（海军工程大学，武汉 430033）

舰载机出库最优调度方案是合理编排一批次舰载机出库顺序，使目标舰载机在最短的时间内调出机库。提出舰载机出库调度方案4步单目标优化方法。第1步实现舰载机数量分配功能；第2步依靠遗传算法，实现舰载机选择功能，寻找最优出库组合方案；第3步根据优先级规则对舰载机出库作业进行排序，从而得到最优出库方案的舰载机调度序列；第4步找出需要倒机的舰载机并根据一定规则进行整理后，得到出库作业序列。最后，建立模拟机库验证调度方案的优化方法可行、高效。

舰载机，调度方案，遗传算法

0 引言

舰载机的出库调度效率，对于提高航母的作战效能具有极其重要作用。调度效率的高低与调度方案的制定有着密切关系。事实上，由于机库布满舰载机，安全路径可能并不存在。在安全路径不存在的情况下，需要不断将该批次目标飞机附近的舰载机移出机库（为了描述方便，本文将这种现象称之为倒机），这将触发了一个新的调运问题，直到机库有足够的空间使目标飞机能安全通行为止。因此，舰载机出库调度方案是一批次舰载机出库顺序的编排，最优调度方案则是合理的编排飞机出库顺序，使目标舰载机在最短的时间内调出机库。

国外过去对于舰载机调度的做法一般是通过摆放模型，以指导舰载机的调度活动，如在美军航母上使用的“占卜板”［1］。近年来，随着计算机技术的发展，国外开始将计算机应用于舰载机调度方面。为解决甲板操作人员视线阻挡等问题，造成飞机刮擦碰撞甚至人员的伤亡事故发生，通过设计航母舰载机甲板持续监控系统，结合舰载机GPS定位，碰撞事故检测等功能，为提高舰载机甲板作业效率和减少事故起到了一定的积极作用［2］。无论是模型摆放还是电子显示的方式，其优点是操作简单灵活，考虑人的经验因素比较多，适用于少数舰载机的调度；缺点是缺乏足够科学依据，在需要调度舰载机数量较多时，无法考虑到各种因素，从而可能得出的调度结果并不是最优［3］。近年来，国内学者也开始注重舰载机调度方面的研究［3-6］，但关于机库舰载机调度方案的文献资料仍较少。

舰载机出库调度方案制定的先决条件是机库舰载机调运作业环境建模［7］以及对舰载机在机库内的调运作业进行路径规划［8］。文献［7-8］中已对调运问题环境建模和路径规划问题进行了详述，本文不再赘述。

在环境建模和路径规划的基础上，本文从实际应用的角度出发，将舰载机出库方案制定分解为4个优化决策问题——数量分配优化、选机优化、排序优化和倒机优化，通过4个算法的顺序协作来完成出库作业调度方案的制定。

1 批次舰载机出库调度方案优化方法设计

舰载机出库作业调度方案制定问题是4步组合优化问题。舰载机出库调度方案优化问题与机场飞机调度优化问题和物流仓储系统的货物出入库问题都是典型的NP组合优化问题［9-11］，舰载机出库问题的解空间非常庞大，问题解空间随机库内舰载机规模和需求舰载机数量的增大呈指数级增长。由于机库中舰载机数量众多，即使现代智能计算方法，遍历问题解空间的时间开销也难以承受。依靠单一的算法难以实现全局寻优。对应于实际问题，舰载机出库优化算法设计分4步进行优化。第1步利用相关决策知识理论实现舰载机数量分配功能。第2步实现舰载机选择功能，本文采用遗传算法作为该优化问题的核心算法。依靠遗传算法对机库中出库舰载机可行解空间的遍历，寻找最优出库组合方案V。第3步实现排序决策功能，根据优先级规则对V中舰载机出库作业进行排序，从而得到最优出库方案舰载机调度序列Y。第4步实现舰载机倒机决策功能，根据舰载机之间的逻辑关系及其机库基本作业规则，基于Petri网的可达性，找出需要倒机的舰载机并根据一定规则进行整理后，得到出库作业序列Z。批次舰载机出库作业计划优化算法流程图如图1所示。

1.1 舰载机数量分配方案择优算法

已知调运需求信息Q，机库每个部分的机型、数量及其之间的逻辑关系等信息，求舰载机机型及出库数量在机库I和机库II的优化分配方案（本文设定有两部升降机，考虑升降机资源利用的均衡性，以防火分隔门为界，将机库分为两部分，分别记作机库I部和机库II部）。表1为各型舰载机需求及库存信息。

图1 舰载机出库优化算法流程图

表1 舰载机需求及库存信息表

满足Q需求的机库I部与机库II部的舰载机机型及数量分配组合的集合元素数量为，其中Mi指每种机型的组合数。由于分配组合数量大，因此，需要对数量分配方案进行优化。优化方法为通过设定一些规则，去掉不合理的组合解，从而达到优化目的。设定的数量分配方案规则如下：

（1）机库两部分分配的调运数量不宜相差太大

为了保持升降机资源利用均衡，这里设定机库两部分舰载机分配的数量之差不大于2为宜。如以表1所示的信息为例，机库I与机库II舰载机的合理分配数量分别为6和5或者为5和6。

（2）根据优先级的级别，设定优先级的权重

设优先级的级别为n级，则依优先级级别的高低，设定该机型数量分配所占权重分别为n，n-1，…，1。即优先级别越高，所占的权重越大。通过对每个级别的舰载机权重进行求和，所求和的大小与该机型舰载机分配数量成正比。

（3）机库内该型舰载机的数量与舰载机分配数量成正比

舰载机的数量与分配数量成正比，符合实际情况。

根据上述规则，某机型在机库I部、II部的数量分配公式：

1.2 舰载机出库选择算法

当机库内两个部分的舰载机数量分配方案确定后，接下来就要分别对机库每部分具体调运需求进行调运方案求解，采用改进的遗传算法对调运方案进行优化。本文以机库I部的舰载机选择为例。

1.2.1 编码策略

每架舰载机都拥有相应的编号，每个编号对应着舰载机的位置。首先对机库中舰载机进行编号，选机算法编码对象为相应的舰载机编号。这里为了简化起见，舰载机的编号用英文大写字母表示。这样每个大写英文字母便与舰载机编号一一对应，即每个大写字母对应着不同架次的舰载机。

1.2.2 适应度函数设计

本文所求的目标函数值为调运所用时间最短，采用设定最大值Cmax的方法计算适应度值。遗传算法适应度函数值Fit（Zi）可通过式（2）计算求出。

其中，Cmax指进化到当前代为止的最大目标函数值。

1.2.3 选择算子设计

本文采用改进的排序法（又称赌盘选择）选择下一代个体。排序选择方法的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个体被选中的概率。概率计算如式（3）所示。

为保持种群多样性，避免过早收敛，本文借鉴期望值选择策略的应用经验，对染色体适应度值Fit（Z）进行调整，如式（4），式（5）所示，以替代值Fit'（X）参与轮盘赌选择。

排序后的种群中的第i个个体被选中概率由式（6）求得。

1.2.4 交叉算子设计

考虑到染色体个体中每个基因组编码值域不同，本文采用单点同位交叉的方式，在保证个体差异化的基础上，降低无效子个体产生几率。对于交叉操作之后仍然不满足编码约束的个体，采用随机数校正地方式，对无效个体进行修正。随机数生成域为该位基因的编码值域。

1.2.5 变异算子设计

遗传算法中的所谓变异运算，是指将个体染色体编码串中某些基因座上基因值用该基因座其他等位基因来替换，从而形成一个新的个体。对于符号编码个体，变异操作就是用这个字符集中一个随机指定且与原基因值不相同的字符去替换变异点上的原有符号。

1.3 舰载机出库排序及倒机决策算法

第3层排序优化算法对上一层传入的出库集合X中的舰载机，根据解码后舰载机的具体属性信息，按照优先级从高到低进行排序，同级者随机排列，得到出库作业次序Y。

对于排序后的舰载机，根据构造关联矩阵，可以计算每架舰载机的出库序列。舰载机倒机具体算法流程如图2所示。

图2 舰载机倒机决策算法流程图

2 应用案例

设定舰载机在机库中的一种布列方式，对舰载机出库方案优化算法进行验证。

2.1 问题描述

该机库配备两部升降机，一道防火分隔门将机库分为两部分，记作机库I部，机库II部，机库I部、机库II部分别与升降机1，升降机2对应，即机库I部的舰载机通过升降机1调运至甲板，机库II部的舰载机通过升降机II调运至甲板。机库内拥有舰载机的机型为4种，共计26架。

试验过程中设计4张不同的舰载机需求批量表Q1，Q2，Q3，Q4，每张批量表中包含4种机型的需求舰载机，舰载机数量分别为6，8，11，12。批量表中舰载机需求情况和各机型舰载机的在库数量如表2所示。

表2 舰载机库存及批量需求表

2.2 遗传算法参数设定

算法中设最大遗传代数Genmax=200，种群空间Popmax=50，变异率pm=0.02，交叉率pc=0.6。算法执行过程中，往往会在没有达到最大遗传代数情况下得到最优解。为降低算法执行时间，GA算法中设置一个阈值flag，flag表示每代种群个体平均适应度值与当前最优适应度值比值，如式（7）所示。

设定flag=0.9，如果flag值超过0.9，就可以认为截止到当前己经取得问题的全局最优解。

2.3 试验结果及分析

在算法运行过程中，优化算法表现出较好的收敛性，需求Q1，Q2，Q3，Q4的求解时间分别为12 s，13 s，15 s和16 s，满足实时性要求。图3为需求Q1的求解结果。

下面将本文提出的改进遗传算法和标准遗传算法执行过程中的收敛情况进行比较。以需求Q4的求解为例，GA在每一代取得的最优目标函数值F（Z）随遗传代数的变化曲线如图4所示。由图中可以看出，与采用标准轮盘赌选择算子的优化算法相比，采用改进轮盘赌选择算子的优化算法运行得到最优目标函数值在整体上具有更好的收敛性。在算法运行前期，采用标准轮盘赌选择算子的优化算法具有更快的收敛速度。但是随着算法运行，采用改进轮盘赌选择算子的优化算法搜索效率更高，最终得到的优化结果也明显优于前者。

图3 舰载机出库优化方案结果区界面

图4 GA最优目标函数值变化曲线

3 小结

针对舰载机出库调度方案优化问题，提出了4步单目标优化算法设计方案并实现优化算法的开发。第1步利用相关决策知识理论，确定舰载机数量分配方案；第2步，以遗传算法作为优化核心算法，进行选机操作；第3步，利用优先级关系，对舰载机出库顺序进行排序。第4步，利用构造关联矩阵算法，构建倒机决策优化算法。最后通过模拟机库验证了优化算法的可行性和高效性。

［1］渔翁.美国航母航空部门的组织管理［J］.舰船知识，2006（9）:36-37.

［2］Jerrrey S.Feasibility Study of Global-positioning-System-Based Aircraft-Carrier Flight-Deck Persistent Moni-toring System［C］//Journal of Aircraft，2010.

［3］司维超，韩维，史玮韦.基于PSO算法的舰载机舰面布放调度方法研究［J］.航空学报，2012，33（11）:2048-2056.

［4］杨炳恒，毕玉泉，徐伟勤.一种舰载机调运作业流程优化模型［J］.舰船科学技术，2011，33（1）:118-121.

［5］冯强，曾声奎，康锐.基于MAS的舰载机动态调度模型［J］.航空学报，2009，30（11）:2109-2125.

［6］刘钦辉，邱长华，王能健.考虑空间约束的舰载机作业调度模型研究［J］.哈尔滨工程大学学报，2012，33（11）: 1435-1439.

［7］刘亚杰，翁辉，陈晓山.一种基于“矢栅结合”的机库舰载机调运作业环境建模方法［J］.装甲兵工程学院学报，2014，28（2）:75-78.

［8］刘亚杰，李忠猛，陈晓山.考虑空间约束的机库舰载机调运路径规划方法［J］.海军工程大学学报，2014，26（3）: 100-103.

［9］Abela J，Abranmson D.Computing Optional Scheduling for Landing Aircraft［C］//Proceedings 12th National ASOR Conference，Adelaide Australia，2006.

［10］冯心玲，龚月姣，林映霞.用遗传算法优化航班规划问题［J］.计算机工程与设计，2009，30（19）:468-471.

［11］王广民.造船厂钢板堆场出库作业计划建模及优化研究［D］.大连:大连理工大学，2009.

Optimized Method of Carrier-borne Aircrafts Exporting Scheduling Based on Improved Genetic Algorithm

LIU Ya-jie LI Zhong-meng XIE Jun
（Naval University of Engineering，Wuhan 430033，China）

The optimized exporting scheduling programme of carrier-borne aircrafts is to arrange exporting order of aircrafts，which makes the total time shortest.Four-stage decision-making course of exporting operation is put forward.The first step is to realize the amount allocation of the aircrafts.The second step is aircrafts chosen based on genetic algorithm.The third step is to sort order based on the rule of priority.The last step is to find out the aircrafts which need be rehandled.Finally，a simulated hangar is built to test the optimized algorithm reasonable and efficient.

carrier-borne aircraft，operation scheduling programme，genetic algorithm

TP208

A

1002-0640（2015）06-0057-04

2014-05-08

2014-06-19

军队科研计划基金资助项目

刘亚杰（1975- ），女，辽宁朝阳人，博士。研究方向：复杂系统建模与仿真。