基于遗传算法的机载武器调度优化

陈　涛，王　栋

（1.海军048工程综合办公室，北京100071；2.海军航空工程学院飞行器工程系，山东烟台264001）

基于遗传算法的机载武器调度优化

陈涛1，王栋2

（1.海军048工程综合办公室，北京100071；2.海军航空工程学院飞行器工程系，山东烟台264001）

针对航母机载武器弹药调度存在的过程复杂、不确定性强、涉及因素多等特点，建立了现阶段机载武器弹药调度模型。通过设计编码方案，选择适应度函数，设定交叉、变异操作建立了基于遗传算法的调度优化模型，并通过Matlab软件进行了仿真验证。结果表明，该优化过程可在一定程度上缩短调度总时间，提高调度效率。

遗传算法；机载武器；调度优化

航母机载武器从弹库到飞行甲板的调度过程，是通过武器升降机平台和飞机升降机平台，将所需的武器运至甲板不同战位，之后加挂在飞机挂架上，涉及到多个升降机使用和挂弹位的选择。对于不同的作战任务，所需的武器类型及数量也有所区别。且出动飞机的停放位置、使用的升降机位置对于武器的调度也有影响，这一影响主要体现在调度时间的长短上。建立调度模型的目的也正是对某个调度计划进行优化，合理分配各升降机的使用，将任务耗时降至最低。

航母机载武器的弹药调度属于资源优化调度问题，具有典型的复杂性、随机性、多约束性和多目标性特点。解决此类问题的方法主要有启发式方法、数学规划方法、规则调度方法、基于人工智能和仿真的方法以及控制理论方法等[1-2]，通过计算机应用现代优化算法解决此类问题已成主流趋势。马登武[3]等采用改进的蚁群算法对舰载机弹药调度问题进行了研究，建立调度方案求解模型，克服了基本蚁群算法搜索时间长、易陷入局部最优解等缺陷。

现代优化算法中，基于人工智能的遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。遗传算法在资源分配[4-7]、系统优化[8-12]、生产调度[13-14]等领域的应用已日渐成熟，并与诸多算法混合应用，取得了很好的效果。本文通过分析各项约束条件，运用遗传算法对机载武器的调度进行建模分析，力求通过设置合理的遗传因子和算法，优化调度过程。

1　遗传算法介绍

遗传算法（Genetic Algorithm，GA）是一种基于自然选择原理和自然遗传机制的并行全局搜索算法，能够较快地对解空间进行搜索，寻找满意解，并且通过采用实数编码的方式对调度方案进行编码迭代计算，能够解决难以具体表达的变量。它是通过借鉴自然界中生命体的遗传和进化机制，在人工系统中实现特定目标的优化。其实质是采用群体搜索技术，按照适者生存的规则进行进化和演变，得到最终的最优解或准最优解。遗传算法主要包括以下操作过程：产生初始群体、求出每个个体的适应度、根据适者生存的原则筛选出优良个体、将选出的优良个体进行两两配对、通过随机交叉其染色体的基因并随机变异某些染色体的基因来生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。

遗传算法的基本操作是选择、交叉和变异。选择的作用是使父代的优良特性得以保持并传递到下一代种群中。交叉使得种群中的个体以一定的概率随机交换部分染色体，发生一定的性状改变，从而产生新的特性。变异也是实现群体多样性的一种手段，是某个个体自身一个或多个染色体以一定概率发生变化，从而产生新性状。

使用遗传算法进行优化计算的步骤如下[15-16]。

1）根据优化对象，确定一种编码方法，并随机生成个体数一定的初始种群。用一个编码串来表示种群中的一个个体。

2）确定适应度函数。通过得到的种群中个体适应度值来判断与优化目标的相符性。若符合，则输出结果，终止计算；否则进入下一步。

3）根据适应度值选择需要进入下一代的个体。高适应度的个体有较大可能进入下一代，而低适应度的个体进入下一代的可能性较低甚至不会被选中进入下一代。

4）进行交叉和变异操作，得到新个体。

5）由上一步得到新的种群，返回步骤2）。基本遗传算法的求解过程如图1所示。

图1　基本遗传法的求解过程Fig.1 Solving process of Basic GA

2　航空弹药贮运系统工作流程

航母航空弹药贮运系统与机载武器调度直接相关，下有航空弹药综合调度设施、航空弹药贮存装置和航空弹药转运装置3个子系统。航空弹药综合调度设施负责对航空弹药贮运系统的机载武器、设备、人员、任务等进行智能化管理调度；航空弹药贮存装置负责为机载武器在航母上安全、可靠、合理的贮存提供保障；航空弹药转运装置主要用于转运所装载的各种机载武器，并具有部分对机顶升能力[17-19]。

综合调度设施包括指挥管理设备、调度监控设备和信息采集处理设备。

航空弹药贮存装置可分为航空弹药贮存设备、可拆军械贮存设备、保障器材贮存设备。按照结构，航空弹药贮存装置可分为存放架、存放笼、存放柜、通用基座等结构形式。

航空弹药转运装置主要由垂直转运设备、库内转运设备和甲板转运设备等组成。其中，垂直转运设备包括武器升降机，库内转运设备包括库内转运机、轨道转运车和库内转运吊车等，甲板转运设备包括甲板转运车、顶升装置和转运设备等。

在接到调度任务后，由综合调度设施制定并下发调度计划。相应的舱室根据调度计划，从贮存装置上取出并转运弹药、附属设备至指定位置，组装检测完成后最终运至甲板，加挂至作战飞机上。综合调度设施在调度的同时对人员设备进行监控，根据反馈和现场状况调整调度计划，完成后，修改数据库中相应内容。

3　弹药调度模型的建立

设在航母上，参与一次运输弹药任务的升降机共有m个，挂弹位共有n个。第i个升降机到第 j个挂弹位所需的时间为tij。则升降机到挂弹位调度时间矩阵为：

相应的，设有升降机调度任务矩阵S。其中，元素amn表示第m台升降机向第n个挂弹位提供的弹药数量，则供弹任务矩阵为

记第i个升降机完成自身任务的时间行向量为Fi，矩阵T中对应的第i个行向量为Ti，S中第i个行向量为Si。先对Si中的元素进行逻辑判断，当Si中的某个元素Six不为0时，令其在新的对应行向量Ri中对应元素的值Rix为1，反之为0。那么有

而一次调度任务的完成时间Tf为所有升降机中最晚完成任务的时间，则有

对任务的评价标准即为完成时间的长短。当完成任务时间最短时，说明调度方案最优，即要求Tf的最小值。所以目标函数应为[20-22]：

相应的约束条件为：

3.1编码方案

由于在调度过程中，任务矩阵S中元素均为非负实数，且有具体含义，故采用实数编码。一条染色体共有n段，每一段由m个基因值组成，基因值pji的数值表示第 j挂弹位由第i个升降机提供的弹药数量，如图2所示。

图2　编码方案Fig.2 Coding scheme

可以看出，该编码能够符合约束条件。优化问题的实质就是从这一编码构成的种群中选择最合适的解作为调度方案。

3.2适应度函数

适应度函数是进行自然选择的依据，常由目标函数变形而来。在该问题中，目标函数是求最小值，可将函数值取倒数作为适应度函数，那么当函数值变小时适应度变大，说明更优。适应度函数为

3.3选择操作

本模型中采用轮盘赌法进行选择操作。该方法对染色体的选择基于适应度函数值的大小，当适应程度越高，时被选择进入下一代种群的概率越高。染色体i被选中概率为

式（8）中：fi为染色体i的适应值；Z表示种群中个体总数。

3.4交叉操作

由于交叉过程在算法的迭代过程中是随机发生的，这样可能会导致已经产生的优良染色体又被破坏。因此，需要一种机制防止出现这种现象，使优良个体能够顺利进入下一代种群中。在交叉过程中，采取精英选择法对适应度高于某个值Em的染色体进行保留进行交叉，剩下的染色体进行两点交叉操作。关于Em的取值可以根据如下方法：

式中，k、c均为系数且0＜k＜1。

3.5变异操作

同上，在变异操作过程中也采用精英选择法保护适应度高的染色体。当适应值高于某个值Ea时，该染色体直接进入下一代种群，而当染色体的适应值低于某个值Si时，将其淘汰并在这一代种群中随机生成一个染色体代替。中间值部分，根据变异概率Pm进行变异操作。其中：

4　模型验证

设在一次调度过程中，有5台升降机和4个挂弹位参与，对应的调度时间矩阵和各挂弹位弹药需求分别为：

设置算法相关初始参数为：初始种群个体数70，交叉概率0.25，变异概率0.01，迭代代数200。通过Matlab软件进行仿真，得到结果见表1。

表1　仿真结果Tab.1 Simulation results

仿真结果图如图3所示。通过优化，可以得到改进后的调度方案为333352213255211411444，任务总时间为31min。新方案的甘特图如图4所示。

图3　仿真结果图Fig.3 Simulation results

图4　调度方案甘特图Fig.4 Gantt chart of dispatching scheme

5　结论

相较传统的数学和运筹方法既耗时又不便计算机实现，本文通过遗传算法对航母机载武器从弹库到飞行甲板的过程进行建模，方便计算机程序处理且步骤相对简单，容易理解。采用实数编码对调度过程进行描述，分段表示各挂弹位的补给方案，减少了迭代计算的次数，耗时较少，效率较高。在交叉变异操作中，使用精英保留策略对适应度值高的函数进行保护，能够有效避免优良个体被淘汰，并自动调整选取保留的范围，防止出现算法陷入局部最优的状况。仿真结果可以看出，该算法在机载武器弹药调度保障中具有一定的适用性和实用价值。

[1]王万良，吴启迪.生产调度智能算法及其应用[M].北京：科学出版社，2007：43-44. WANG WANLIANG，WU QIDI.Intelligent algorithm and its application in production scheduling[M].Beijing：Science Press，2007：43-44.（in Chenese）

[2]李敏强，寇纪淞，林丹，等.遗传算法的基本理论与应用[M].北京：科学出版社，2003：56-58. LI MINQIANG，KOU JISONG，LIN DAN，et al.Basic theory and application of genetic algorithm[M].Beijing：Science Press，2003：56-58.（in Chenese）

[3]马登武，郭小威，邓力.基于改进蚁群算法的舰载机弹药调度[J].系统仿真学报，2012，24（6）：1207-1211. MA DENGWU，GUO XIAOWEI，DENG LI.Ammunition scheduling of carrier-based aircraft based on improved ant colony algorithm[J].Journal of System Simulation，2012，24（6）：1207-1211.（in Chenese）

[4]王为新，李原，张开富.基于遗传算法的多模式资源约束项目调度问题研究[J].计算机应用研究，2007，24（1）：72-74. WANG WEIXIN，LI YUAN，ZHANG KAIFU.Research of multi-Model resource constrained project scheduling problem based on genetic algorithm[J].Application Research of Computers，2007，24（1）：72-74.（in Chenese）

[5]熊辉.基于遗传算法的公路养护资源最优分配[J].北京理工大学学报，2007，27（1）：21-24. XIONG HUI.Optimal allocation of highway maintenance resources based on genetic algorithms[J].Beijing Institute of Technology，2007，27（1）：21-24.（in Chenese）

[6]王波，刘小利，胡亮，等.基于改进遗传算法的反舰导弹火力分配研究[J].火力与指挥控制，2015，40（8）：90-93．WANG BO，LIU XIAOLI，HU LIANG，et al.Antiship missile fire distribution based on improved genetic algorithm[J].Fire Control&Command Control，2015，40（8）：90-93.（in Chenese）

[7]杨童.基于遗传算法的SOFDM信道资源动态分配策略[J].中国空间科学技术，2010，30（4）：23-30．YANG TONG.Genetic arithmetic based dynamic channel allocation algorithm for SOFDM system in satellite multimedia broadcastings[J].Chinese Space Science and Technology，2010，30（4）：23-30.（in Chenese）

[8]张宗华，张伟，赵霖.利用遗传算法实现交通控制系统优化的方法[J].计算机工程，2003，29（12）：53-54，155. ZHANG ZONGHUA，ZHANG WEI，ZHAO LIN.Method of optimizing the traffic control system using genetic algorithm[J].Computer Engineering，2003，29（12）：53-54，155.（in Chenese）

[9]童树鸿，沈毅，刘志言.遗传算法在模糊系统优化设计中的应用研究[J].系统工程与电子技术，2001，23（1）：73-76. TONG SHUHONG，SHEN YI，LIU ZHIYAN.Simultaneous optimal design of membership functions and rule sets for fuzzy systems using genetic algorithm[J].Systems Engineering and Electronics，2001，23（1）：73-76.（in Chenese）

[10]段芳，余培兵，朱卫锋.舰船补给物料搬运顺序优化问题的改进遗传算法[J].计算机系统应用，2015，24（9）：105-111．DUAN FANG，YU PEIBING，ZHU WEIFENG.Improved genetic algorithm of material handling sequence optimization problem for ship material supply[J].Computer Systems&Applications，2015，24（9）：105-111.（in Chenese）

[11]刘洋.基于遗传算法的水下无人潜器结构特性优化分析[J].舰船科学技术，2015，37（9）：145-148．LIU YANG.Optimization analysis of structure of UUV based on genetic algorithm[J].Ship Science and Technology，2015，37（9）：145-148.（in Chenese）

[12]徐昕，耿清华.基于实数型遗传算法的水轮机调节系统设计优化[J].人民长江，2015，46（17）：83-86．XU XIN，GENG QINGHUA.Design optimization of turbine regulating system based on real coded genetic algorithm[J].Yangtze River，2015，46（17）：83-86.（in Chenese）

[13]KIM M，JUNG J H，LEE I B.Intelligent scheduling and moni-toring for multi-product networked bath processes [J].Computers and Chemical Engineering，1996（20）：1149-1154.

[14]KIM M，JUNG J H，LEE I B.Optimal scheduling of multi-product batch processes for various intermediate storagepolicies[J].Industrial and Engineering Chemistry Re-search，1996，35（11）：4058-4066.

[15]曲晓燕，温德宏，谢勇.遗传算法在舰载机弹药转运任务优化配置中的应用[J].计算机与现代化，2012（3）：23-26. QU XIAOYAN，WEN DEHONG，XIE YONG.Genetic algorithm for ammunition transfer assignment optimization collocation of carrier-based aircraft[J].Computer and Modernization，2012（3）：23-26.（in Chenese）

[16]夏惠诚，申战胜，伊柏栋.基于遗传算法的舰载机对海导弹攻击任务分配模型研究[J].舰船科学技术，2012，34（5）：117-121. XIA HUICHENG，SHEN ZHANSHENG，YI BAIDONG. Research on the mission assignment model of missile attacking on the sea by carrier aircraft on genetic algorithms[J].Ship Science and Technology，2012，34（5）：117-121.（in Chenese）

[17]史文强，李彦庆，陈练.航母的航空弹药贮运作业解析[J].舰船科学技术，2013，35（6）：136-141. SHI WENQIANG，LI YANQING，CHEN LIAN.Analysis for the ordnance handling process aboard aircraft carrier [J].Ship Science and Technology，2013，35（6）：136-141.（in Chenese）

[18]XIAO HE，LIU YUNHUI，YU ZHENRONG.Combination of eco-profile and least-cost model for eco-network planning[J].China Geography Science，2014，24（1）：113-125.

[19]玄光男，程润伟.遗传算法与工程优化[M].北京：清华大学出版社，2012：1-3. XUAN GUANGNAN，CHENG RUNWEI.Genetic algorithm and engineering scheduling[M].Beijing：Tsinghua University Press，2012：1-3.（in Chenese）

[20]BU QUANMIN，WANG ZHANJUN，TONG XING.An improved genetic algorithm for searching for pollution sources[J].Water Science and Engineering，2013，6（4）：392-401.

[21]JIANG RUI，LUO YUPIN，HU DONGCHENG.Coordinating exploration and exploitation to construct genetic algorithms[J].Tsinghua Science and Technology，2002，7（6）：608-618.

[22]BU QUANMIN，WANG ZHANJUN，TONG XING.An improved genetic algorithm for searching for pollution sources[J].Water Science and Engineering，2013，6（4）：392-401.

Scheduling Optimization of Aircraft Weapons Based on Genetic Algorithm

CHEN Tao1,WANG Dong2
（1.Naval General Office of 048 Project,Beijing 100071,China; 2.Department of Airborne Vehicle Engineering,NAAU,Yantai Shandong 264001,China）

Aiming at the characteristics of complex course,strong uncertainty and many involved factors in scheduling of aircraft weapons,the scheduling optimization model based on genetic algorithm was built through coding scheme design⁃ing,adaption function selecting,across and aberrance sizing.The simulation validating was also carried through Matlab. The result showed that the optimization was effective to shorten scheduling time and to elevate scheduling efficiency in a certain extent.

genetic algorithm;aircraft weapons;scheduling optimization

V271.4；E926.392

A

1673-1522（2016）01-0058-05

10.7682/j.issn.1673-1522.2016.01.011

2015-11-21；

2015-12-25

陈涛（1964-），男，高工，大学。