基于Memetic算法的舰载机舰面一站式保障调度

苏析超, 韩　维, 萧　卫, 蒋婷婷

(1. 海军航空工程学院飞行器工程系, 山东 烟台 264001; 2. 中国船舶工业系统工程研究院,北京 100094; 3. 海军航空工程学院研究生管理大队, 山东 烟台 264001)



基于Memetic算法的舰载机舰面一站式保障调度

苏析超1, 韩维1, 萧卫2, 蒋婷婷3

(1. 海军航空工程学院飞行器工程系, 山东 烟台 264001; 2. 中国船舶工业系统工程研究院,北京 100094; 3. 海军航空工程学院研究生管理大队, 山东 烟台 264001)

面向舰载机舰面保障效率和资源利用率等效能指标,系统分析了一站式保障流程约束和资源约束条件,建立了舰载机多机舰面一站式保障调度的数学优化模型。针对传统优化算法难以求解大规模调度问题,提出了一种Memetic算法。首先,为了使可更新类资源负载均衡化,采用一种嵌入资源分配策略的串行调度方案;其次,设计了一种基于子拓扑结构的自适应变异策略以提升算法的探索能力,并引入基于模拟退火机制的局部搜索方法;最后，基于不同调度规模案例的仿真结果验证了模型和算法的可行性和有效性。

舰载机; 舰面一站式保障;Memetic算法; 优化

0　引　言

作为航母作战编队攻防体系的核心,舰载机承担了航母全系统和航母战斗群的绝大多数作战使命,其舰面保障是影响出动架次率乃至航母编队作战效能的关键因素。舰载机舰面保障涉及复杂的流程约束、资源约束和环境约束,随着舰载机机群规模的增加,传统的人工调度已难以满足其实时性、鲁棒性和优化性能。因此,对舰载机多机舰面保障流程安排和资源分配进行科学的规划和决策具有重要意义[1]。

近年来,舰载机调度已成为国内外研究的一个新兴的热点。针对舰载机舰面调运规划,文献[2]提出了基于改进A*算法的甲板滑行路径规划方法;文献[3]在舰载机运动约束模型的基础上,引入了“凸壳模型”和碰撞检测以实现调运的安全性。美国的麻省理工学院通过对一款名为DCAP(deckoperationcourseofactionplanner)[4]的飞行甲板辅助决策平台的开发,建立了甲板周期内舰载机调度的线性整数规划模型,并研究了基于分支定界的精确算法[5]、基于逆向强化学习的机器学习方法[6]和基于差分进化算法的智能优化[7]等方法在舰载机机群全流程调度问题中的应用。文献[8]引入Multi-agent技术并基于舰载机作业流程建立了3层混合控制模型架构,研究了考虑故障扰动等因素的舰载机动态调度问题。文献[9]针对单机机组保障模式的不足,建立了多机一体化机务保障调度模型,可有效提升保障人员的利用率。

但是,由于目前航母资源设置的局限性,无法满足各停机位均能供给各类资源,使得舰载机在航空保障过程中需要频繁的调运作业,从而降低了保障作业效率和舰载机的出动架次率。

为此,本文针对舰载机一站式保障的发展趋势和其技术特征[10],建立了舰载机机群的舰面一站式保障调度模型,并设计了一种基于子拓扑网局部灾变策略的Memetic算法,以提升针对中、大规模调度问题的求解性能。

1　舰载机舰面一站式保障问题建模

1.1一站式保障流程分析与问题描述

舰载机舰面一站式保障是指舰载机在航空保障流程约束和资源配置约束条件下,不需要往返地调运即可在甲板同一个停机站位集中完成各项出动前保障作业,从而提升机群的快速出动能力。一站式保障实现的前提和关键在于各类保障资源的优化配置。根据资源的性质和作用,可将其分解为:可更新资源、消耗类资源、空间资源。

(1) 可更新资源,主要包括保障人员和保障设备/设施。其中保障人员按照保障作业的性质可划分为机械、军械、航电、特设等专业类型,每一类保障人员均包含若干组保障人员;保障设备则包括提供电燃气液等消耗类资源的固定站点和移动保障车。与移动保障车的甲板机动保障不同,固定资源站仅可对以管线长度为半径的圆域内的舰载机提供保障,图1为库兹涅佐夫号航母某类资源站覆盖的停机位示意图。

(2) 消耗类资源,指保障过程中不断消耗的电燃气液和弹药等物资资源。这类资源不仅总量有限制,而且由于航母技术和空间布局制约,存在任意时刻供应量的限制,如额定燃油压力仅能满足一定数量的舰载机同时进行加油作业。

(3) 空间资源,主要考虑对舰载机实施保障作业所需的诸如座舱、起落架仓等的站位空间。

图1　库兹涅佐夫号航母某类资源站覆盖停机位示意图Fig.1　Distribution map of some resource stations on the admiral Kuznetsov aircraft carrier

对任一舰载机i,其保障工序流程可表示为有向网络图Di=(Vi,Ai),其中,节点Vi表示保障工序集合,有向弧Ai表示各工序间的紧前紧后约束关系。本文研究的目的,即在保证流程约束条件下,对各类资源进行合理地分配和调度,以实现机群快速保障和保障资源均衡使用,进而提升舰载机多机的出动效能。

1.2一站式保障调度数学模型

首先定义模型参数如下:

I={1,2,…,n}为舰载机集合,其中n为舰载机数量；

Ji={1,2,…,|Ji|}为舰载机i的工序集,其中|Ji|为工序数；

Kp={1,2,…,|Kp|}为保障专业种类集合；

Ks={1,2,…,|Ks|}为站位空间种类集合；

Kr={1,2,…,|Kr|}为保障设备种类集合；

Kw={1,2,…,|Kw|}为消耗性资源种类集合；

Lpk={1,2,…,|Lpk|}为第k(k∈Kp)种专业保障人员集合；

Lsk={1,2,…,|Lsk|}为第k(k∈Ks)类空间集合；

Lrk={1,2,…,|Lrk|}为第k(k∈Kr)种保障设备集合；

Rkl为第k(k∈Kr)种第l个保障设备所覆盖到的舰载机集合；

rpijk为舰载机i的第j道保障工序对第k(k∈Kp)类专业保障人员的需求量；

rsijk为舰载机i的第j道保障工序对第k(k∈Ks)类空间站位的需求变量；

rijk为舰载机i的第j道保障工序对第k(k∈Kr)种保障设备的需求量；

rwijk为舰载机i的第j道保障工序对第k(k∈Kw)类消耗性资源的需求量；

Pij为工序Oij的紧前工序集合；

Tij为工序Oij的保障作业时间；

Sij、Eij分别为第i架舰载机第j道工序的开始保障时间和结束保障时间；

Eopk、Eork′分别为第k(k∈Kp)类专业保障人员和第k′(k′∈Kr)类保障设备的闲忙比方差；

Bpkl、Brk′l′分别为为第k(k∈Kp)类专业中第l个保障人员和第k′(k′∈Kr)类第l′个保障设备的工作时间。

决策变量定义为

根据舰载机调度的指标要求,优化的目标选取分层双目标,即在满足最小化最大保障完工时间的前提下,使得可更新资源的闲忙比方差和最小

(1)

式中,第k类专业的闲忙比方差

(2)

工作时间Bpkl可表示为

(3)

第k类设备的闲忙比方差Eork和其第l个设备的工作时间Brkl可分别参照式(2)和式(3)给出。

约束条件包括

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

表示舰载机i中同时进行保障的不同工序均对某类设备有需求时,仅需一个设备即可满足,如一个供电设备可满足若干并行通电作业工序;式(10)为消耗性资源约束,即任意时刻对某消耗性资源的需求不大于其供给量。

2　Memetic算法设计

由上述模型可以看出,舰载机多机一站式保障调度问题本质上属于一类具有非确定性多项式-难(non-deterministicpolynomial-hard,NP-hard)特性的资源受限多项目调度问题(resource-constrainedmulti-projectschedulingproblem,RCMPSP)[11-12]。若按照各类资源的选择和工序保障顺序逐一编码,不仅编码复杂度高,且求解效率随着舰载机保障数量规模增大而急剧下降,计算量耗费大。因此,本文借鉴RCMPSP的群智能优化求解方法,并嵌入可更新性资源选择的启发式规则,在确保求解精度的前提下提升了解算的效率。

Memetic算法是一种基于种群的全局搜索和基于个体的局部搜索的混合算法,自1989年由Moscato提出后,已经在诸多领域得到了广泛的应用[13],特别是在解决具有多极值特性的调度问题具有很强的寻优能力和普适性[14-15]。本文在求解RCMPSP问题的标准遗传算法(geneticalgorithm,GA)的基础上,设计了改进的Memetic算法如下。

2.1解的编码

编码方案是影响算法搜索效果和效率的重要因素,求解RCMPSP问题的主要编码策略包括任务列表编码、优先数编码和优先规则编码。其中,任务列表编码相对于后两者具有更有效的搜索空间,因此本文采用任务列表的编码策略。染色体个体可表示为满足流程约束关系的作业排列X=[x1,x2,…,xk,…,xnm],其中,xk为二元数组(i,j)分别表示舰载机编号及其工序号,nm为所有工序数总和。

2.2解码操作

解码是实现染色体编码向调度方案映射的关键步骤,通过解码确定各舰载机工序的保障开始/结束时间以及资源的分配。然而经典的串行调度生成机制和并行调度生成机制仅考虑任意时刻资源占用量,而不考虑资源的具体分配[16]。为了更均衡地利用各类资源,分别设计保障人员和保障设备的分配规则:

(2) 基于覆盖范围内剩余工序作业时间最少优先(minimumtotalprocessingtimeremainingincoveringarea,MTRCA)的保障设备分配规则,表示当工序Oij需要第k类设备进行保障,则对覆盖到舰载机i的所有k类设备,分别计算其覆盖范围内对应的舰载机待保障工序时间和

并选取最小值所对应的保障设备。其中令Sg表示已调度集合,则覆盖域内待分配工序集

通过MTRCA分配,一方面缓解覆盖较多舰载机工序的设备的使用冲突,使工作负载均衡;另一方面避免设备使用过度集中造成保障总时间的延迟。当存在待保障工序时间和相同的设备时,采用MATF规则进行分配。

Initialization:g=1,Sg=∅;

While|Sg|

(i*,j*)=xg;

ESi*j*=max{Eij+dij|(i,j)∈Pi*j*};

For∀k∈Kp∧rpi*j*k>0

Endfor

For∀k∈Kr∧ri*j*k>0

Endfor

Sg+1=Sg∪{(i*,j*)},g=g+1;

End

2.3适应度分配与选择算子

采用基于排序的适应度分配法,以避免适应度函数选取不当而降低求解的鲁棒性。对于规模为Np的种群,按照个体最大保障完成时间Cmax进行排序,即Cmax越小排序越高,设选择压力Π(Π∈[1,2]),表示最佳个体被选中的概率与平均选中概率的比值,pi种群中个体i的位序,则基于线性排序的适应度计算方法可表示为

(12)

根据式(12)所得适应度分配,按照轮盘赌策略选择个体进行种群更新。

2.4交叉算子

2.5基于子拓扑工序网的自适应变异策略

变异策略是增加种群多样性,避免陷入局部最优的重要手段,常规的基于Insertion或Inerchange的变异策略仅能产生较小的邻域变换范围,对于较大规模的调度问题则难以跳出局部最优。为此,本文针对大规模的RCMPSP问题特性,设计一种新的邻域结构如下:

(1) 针对染色体个体X根据概率Pm选择舰载机i,并从X中提取其工序排列πi;

(4) 将重排的序列随机插入至原染色体X的[dx1,dx2]位置区间,得到新的染色体Y。

该邻域结构一方面通过基于子拓扑工序网的重排实现舰载机内的工序排序的变动,另一方面通过重插入实现舰载机之间的工序变换,从未增大了搜索空间。此外,为了进一步增强变异策略在进化后期避免陷入局部极值的能力,对变异概率采用自适应变化策略

(13)

(14)

2.6基于模拟退火机制的局部搜索策略

通过引入局部搜索策略可进一步引导算法在多局部极值解空间中进行高效地深度搜索,增强算法的全局寻优能力。在执行了交叉和变异的全局搜索后,选取种群中100p%的最优个体,并采用基于Inerchange的邻域结构和模拟退火选择机制进行局部搜索:

步骤 1对选取的个体Spbest,令k=1。

步骤 2按概率Pl选取基因位xk=(i,j),找到其紧前工序集所在Spbest中的最大基因位xk′=(i,h),h∈Pij。

步骤 5令k=k+1,若k

基于上述各部分算法描述,求解舰载机一站式保障调度问题的Memetic算法基本流程图如图2所示。

图2　Memetic算法流程图Fig.2　Flow diagram of Memetic algorithm

3　仿真分析

以库兹涅佐夫号航母为实例分析对象,如图1所示，某出动任务想定需要对8架舰载机进行出动前的保障作业。任一舰载机i的单机保障工序流程如图3所示,其中除编号1和编号19为单机虚拟开始/结束工序,其余编号工序右上角括号内分别表示需要的保障人员专业类型和设备类型,且需求量均为1,虚线连接的工序表示因站位空间的限制而不能同时进行。通过添加整体保障任务的虚拟开始/结束节点可将各舰载机保障工序流程合并为多机保障网络流程。

图3　舰载机单机保障工序流程图Fig.3　Support process flow chart of single aircraft

各舰载机工序保障的时间参数和设备对舰载机的保障覆盖情况分别如表1和表2所示。

表1 保障工序时间参数表

表2中单元格的数字集合表示该列设备类型可覆盖到该行的舰载机的设备集合。此外,参与保障的5类专业保障人员的数量分别为|Lp1|=4,|Lp2|=4,|Lp3|=6,|Lp4|=4,|Lp5|=4;5类设备资源分别对应5类可消耗性资源,例如工序Oij需要Kr1类设备保障的同时也需要Kw1类消耗性资源供给,且各类消耗性资源的供给限制可表示[Nw1,Nw2,…,Nw5]=[6,5,2,4,2],其中Nwk表示第k(k∈Kw)类消耗性资源能同时供给Nwk架舰载机进行保障作业。

表2　设备对舰载机保障覆盖关系

将GA、IGA和Memetic算法分别求得的最优解进化曲线进行对比,如图4所示,并结合表3的对比分析可以看出,本文所提出的Memetic算法不仅具有较强的全局搜索能力和收敛速度,且算法更稳定,鲁棒性更强;而通过比较基于本文所设计变异策略的IGA和标准GA算法,验证了

表3　算法性能对比

图4　最优解收敛对比曲线Fig.4　Comparison diagram of optimal convergence

图5　最优调度甘特图Fig.5　Gantt chart of optimal scheduling

为了检验Memetic算法求解中、大规模调度问题的优越性,另外分别在相同保障条件下进行4机和12机出动的仿真对比,算法设置相同,得到出动保障效率参数如表4所示。通过仿真可以看出,在保障规模较小的情况下,3种算法基本上均能以较大概率收敛至最优解或次优解,而随着舰载机规模的增加,3种算法的求解性能差距拉大,GA和IGA算法往往收敛不到最优解,而Memetic算法依然保持较好的收敛性和鲁棒性。

表4　不同出动规模下算法性能对比

4　结　论

本文针对舰载机舰面一站式保障调度问题,通过系统分析舰载机保障的流程约束和各类资源约束,以优化保障时间和可更新资源利用率方差为目标,建立了问题的数学模型。在此基础上,设计了一种基于子拓扑结构的变异策略和基于模拟退火机制局部搜索的Memetic算法求解该模型。通过以库兹涅佐夫号航母为背景的仿真实例验证了模型的可行性,以及算法对于中、大规模保障调度问题求解的有效性。在今后研究中,将着力研究算法在实际调度中的时效性问题。

[1]HanW,WangQG. Conspectus of aircraft carrier and carrier plane[M].Yantai:NavalAeronauticalandAstronauticalUniversityPress, 2009: 37-41. (韩维, 王庆官. 航母与舰载机概论[M].烟台: 海军航空工程学院出版社, 2009: 37-41.)

[2]WuY,QuXJ.Pathplanningfortaxiofcarrieraircraftlaunching[J].Science China Technological Sciences, 2013, 56(6): 1561-1570.

[3]HanW,SiWC,DingDC,etal.Multi-routesdynamicplanningondeckofcarrierplanebasedonclusteringPSO[J].Journal of Beijing University of Aeronautics and Astronautics, 2013, 39(5): 610-614. (韩维, 司维超, 丁大春, 等. 基于聚类PSO算法的舰载机舰面多路径动态规划[J].北京航空航天大学学报, 2013, 39(5): 610-614.)

[4]RyanJC,CummingsML,RoyN,etal.Designinganinteractivelocalandglobaldecisionsupportsystemforaircraftcarrierdeckscheduling[C]∥Proc.of the AIAA Infotech@ Aerospace Conference, 2011.

[5]RyanJC,BanerjeeAG,CummingsML,etal.Comparingtheperformanceofexpertuserheuristicsandanintegerlinearprograminaircraftcarrierdeckoperations[J].IEEE Trans. on Cybernetics, 2014, 44(6): 761-773.

[6]MichiniB,JonathanP.Ahuman-interactivecourseofactionplannerforaircraftcarrierdeckoperations[C]∥Proc.of the AIAA Infotech @ Aerospace Conference, 2011.

[7]DastidarRG,FrazzoliE.Aqueueingnetworkbasedapproachtodistributedaircraftcarrierdeckscheduling[C]∥Proc.of the AIAA Infotech @ Aerospace Conference, 2011.

[8]FengQ,ZengSK,KangR.AMAS-basedmodelfordynamicschedulingofcarrieraircraft[J].Acta Aeronautica et Astronautica Sinica,2009,30(11):2119-2125.(冯强,曾声奎,康锐.基于MAS的舰载机动态调度模型[J].航空学报,2009,30(11):2119-2125.)

[9]HanW,SuXC,ChenJF.Integratedmaintenancesupportschedulingmethodofmulti-carrieraircrafts[J].Systems Engineering and Electronics,2015,37(4):809-816.(韩维,苏析超,陈俊锋.舰载机多机一体化机务保障调度方法[J].系统工程与电子技术,2015,37(4): 809-816.)

[10]LiuXC.Technicalfeaturesandcriticaltechnologiesforthe“pit-stop”aircraftservicingadoptedbyfordclassaircraftcarriers[J].Chinese Journal of Ship Research, 2013, 8(6): 1-5. (刘相春. 美国“福特”级航母“一站式保障”技术特征和关键技术分析[J].中国舰船研究, 2013, 8(6): 1-5.)

[11]HartmannS,BriskornD.Asurveyofvariantsandextensionsoftheresource-constrainedprojectschedulingproblem[J].European Journal of Operational Research, 2014, 207(1): 1-14.

[12]WangL,FangC.Ahybridestimationofdistributionalgorithmforsolvingtheresource-constrainedprojectschedulingproblem[J].Expert Systems with Application, 2012, 39(3): 2451-2460.

[13]NeriF,CottaC.MemeticalgorithmandMemeticcomputingoptimization:aliteraturereview[J].Swarm and Evolutionary Computation, 2012(2): 1-14

[14]GaoL,ZhangGH,ZhangLP,etal.AnefficientMemeticalgorithmforsolvingthejobshopschedulingproblem[J].Computers & Industrial Engineering, 2011, 60(4): 699-705.

[15]ChiangTC,ChengHC,FuLC.NNMA:aneffectiveMemeticalgorithmforsolvingmultiobjectivepermutationflowshopschedulingproblems[J].Expert Systems with Application, 2011, 38(5): 5986-5999.

[16]ShouYY. Resource-constrained multi-project scheduling models and methods[M].Hangzhou:ZhejiangUniversityPress, 2010: 74-80. (寿涌毅. 资源受限多项目调度的模型与方法[M].杭州:浙江大学出版社, 2010: 74-80.)

Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm

SU Xi-chao1, HAN Wei1, XIAO Wei2, JIANG Ting-ting3

(1. Department of Airborne Vehicle Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China;2. System Engineering Research Institute, China State Shipbuilding Corporation, Beijing 100094, China;3. Graduate Student’s Brigade, Naval Aeronautical and Astronautical University, Yantai 264001, China)

Forimprovingtheeffectivenessindexessuchassupportefficiencyandresourcesavailabilityondeckofcarrierplaneseffectively,thepit-stopsupportroutingconstraintsandresourcesconstraintsareanalyzedsystematically,andanoptimizedpit-stopsupportschedulingmathematicmodelondeckofcarrierplanesisestablished.Tosolvelarge-scaleschedulingproblemswhicharedifficultfortraditionaloptimizationmethods,aMemeticalgorithmisproposed.First,tomaketheloadofrenewableresourcesequalized,aserialschedulegenerationschemeembeddedbyresourcesallocationstrategiesisadopted.Second,anewadaptivemutationstrategybasedonthesub-topologystructureisdesignedtoimproveexplorationabilityofthealgorithm,andalocalsearchmethodbasedonsimulatedannealingisintroduced.Finally,thesimulationresultsshowthefeasibilityofthemodelandtheeffectivenessofthealgorithmunderdifferentdispatchscales.

carrierplane;pit-stopsupportschedulingondeck;Memeticalgorithm;optimization

2016-02-29；

2016-04-05；网络优先出版日期：2016-06-29。

国家自然科学基金(51375490)；航空科学基金(20145784010)资助课题

V271.4+92

ADOI:10.3969/j.issn.1001-506X.2016.10.12

苏析超(1989-),男,博士研究生,主要研究方向为舰载机技术研究及应用。

E-mail:suiting1012@163.com

韩维(1970-),男,通信作者,教授,博士研究生导师,博士，主要研究方向为航空保障工程和飞行动力学。

E-mail:Luckydevilhan@163.com

萧卫(1966-),男,研究员,硕士,主要研究方向为航空系统工程、流程优化。

E-mail:18911990663@189.cn

蒋婷婷(1995-),女,硕士研究生,主要研究方向为舰载机技术研究及应用。

E-mail:suiting1012@163.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160629.1132.002.html