基于遗传算法舰船装载码头配置方案优化

徐清华，季大琴，英戈

（海军陆战学院，广州510430）

基于遗传算法舰船装载码头配置方案优化

徐清华，季大琴，英戈

（海军陆战学院，广州510430）

两栖输送舰船码头装载过程中，如何科学配置装载码头，使得整个装载任务完成时间最短是部队制定装载方案需要解决的重要难题。依据码头装载配置特点和要求，运用军事运筹学多目标规划理论构建装载码头配置规划模型，并运用遗传算法理论和计算机编程工具实现码头配置规划模型的优化解算。从而提高了部队两栖输送舰船码头装载方案制定的科学性和时效性。

遗传算法，装载，码头配置，方案

0 引言

两栖输送舰船装载是两栖作战准备的关键环节，是完成两栖作战任务的首要。码头装载依靠其健全的港口装载设施成为两栖输送舰船装载方式的首选。两栖输送舰船码头装载过程中，如何科学配置装载码头，使得整个装载任务完成时间最短是部队制定装载方案需要解决的重要难题。

1 两栖输送舰船装载码头配置方案优化模型构建

在组织较大规模两栖作战装载任务时，通常涉及的两栖舰船类型、数量较多，选择的装载码头类型、数量较多，装载装备的类型、数量较多。而这些涉及因素都直接影响两栖作战装载任务完成的效率。通过构建码头配置方案优化模型，使得整个装载任务完成时间最短，是提高部队两栖作战装载任务效率的有力方法。

1.1 两栖输送舰船及装载码头分类

为了提高模型构建的通用性，现将两栖输送舰船和装载码头进行分类。两栖输送舰船按照排水量和功能特点可划分为大型登陆舰艇、中型登陆舰艇、小型登陆舰艇及特种两栖输送舰艇等4种类型；装载码头按照其使用功能划分为大、中、小型登陆码头（指能够为陆战装备通过斜坡、跳板直接机动上落舰的码头），大、中、小型普通码头（指能够提供吊装功能的普通民用码头）和大、中、小型可供两栖装备泛水装载码头［1］。

1.2 两栖输送舰船装载码头配置条件

两栖输送舰船配置装载码头时应遵循以下条件:大型登陆舰艇只能配置在大型码头装载，不适合在中、小型码头装载；中型登陆舰艇只能配置在大型码头或中型码头装载，不适合在小型码头装载；小型登陆舰艇可以配置在大、中、小型码头装载。另外，规定一座码头同一时间内只能容纳1艘舰船进行装载。

1.3 两栖输送舰船装载码头配置方案需求描述

设完成某两栖作战任务所需两栖输送舰艇的类型和数量如表1所示，所需两栖舰船总数为A= {A1，A2，A3}，其中A1，A2，A3分别为大型、中型、小型登陆舰艇数量，某港可用于两栖输送舰船装载的码头总数为X={X1，X2，X3，X4，X5，X6，X7，X8，X9}，如表2所示，其中X1，X2，X3分别为大、中、小型登陆码头（M1、M2、M3）的数量，X4，X5，X6分别为大、中、小型普通码头（M4、M5、M6）的数量，X7，X8，X9为大、中、小型可供两栖装备泛水装载码头（M1、M2、M3）的数量。各型登陆舰艇配置给相应码头数量为{X11，X12，X13，X21，X22，X23，X24，X25，X26，X31，X32，X33，X34，X35，X36，X37，X38，X39}，如图1所示，其中，大型登陆舰艇配置给大型码头数量分别为X11，X12，X13，中型登陆舰艇配置给大、中型码头数量分别为X21，X22，X23，X24，X25，X26，小型登陆舰艇配置给大、中、小型码头数量分别为X31，X32，X33，X34，X35，X36，X37，X38，X39。每艘舰艇分配相应码头装载时间为t11，t12，t13，t21，t22，t23，t24，t25，t26，t31，t32，t33，t34，t35，t36，t37，t38，t39，各型码头完成装载任务所需要的时间为TX1，TX2，TX3，TX4，TX5，TX6，TX7，TX8，TX9。合理规划码头配置方案{X11，X12，X13，X21，X22，X23，X24，X25，X26，X31，X32，X33，X34，X35，X36，X37，X38，X39}，并计算完成整个两栖输送舰船装载任务最短时间。

表1 两栖输送舰船兵力投送需求数量

1.4 装载码头配置方案模型构建

依据两栖输送舰船装载码头配置条件，运用军事运筹学多目标规划理论构建装载码头配置方案模型。

表2 某港装载码头建设配置情况

图1 舰艇装载码头配置方案示意图

①已知

2 基于遗传算法装载码头配置方案优化模型解算

两栖输送舰船装载码头配置优化所要解决的是配置方案能够实现整体装载时间最短问题，属于多目标规划问题。由于遗传算法（GA）在解算多目标规划问题过程中，不受问题求解空间的限制，不必对求解问题作出连续性、导数存在和单峰等假设，在装载码头配置方案搜索进化过程中基本上不需要外部信息，仅用评估函数即适应值函数来评价种群中个体的优劣，并作为优胜劣汰遗传操作的依据，加上遗传算法本身固有的并行性，使得遗传算法在装载码头配置方案优化求解方面具有较强的优越性［2-3］。因此，本文采用遗传算法求解装载码头配置方案优化问题。

2.1 问题编码（构造染色体）

根据装载码头配置方案规划约束条件，配置给各个码头的舰艇数量为正整数，且一种方案中的配置数为18种，因此，采用非负整数进行编码比较合适，一个个体代表一种配置方案，其个体编码为xijk（i=1，2，3，…，18，j=1，2，3，…，M）。xijk表示第k代种群第j个个体中的第i段基因编码值，M为种群数。

2.2 初始种群设定

在装载码头配置方案中，配置最少为0艘舰艇，最多A1，A2，A3为艘舰艇，因此，可初始化种群如图3所示。即，大中小型舰艇在编码过程是相对独立，每段染色体第1至n-2为0，第n-1个染色体为1，最后一个染色体为Ai-1。

图2 装载码头配置方案问题编码

图3 装载码头配置方案种群初始化

2.3 适应值函数设计

遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。评估函数又称适应值（fitness）。适应值函数是根据目标函数确定的，其值总是非负数，且越大越好［4］。

2.4 遗传操作设计

遗传算法的执行过程中，每一代有许多不同的染色体（个体）同时存在，这些染色体中哪个保留（生存），哪个淘汰（死亡）是根据它们对环境的适应能力决定的，适应性强的有更多的机会保留下来，主要的遗传操作有选择、交叉和变异。

2.4.1 选择操作

选择又称复制、繁殖。选择是从种群中选择生命力强的染色体产生新种群的过程。依据每个染色体的适应值大小，适应值越大，被选择的概率就越大，其子孙在下一代产生的个数就越多［5］。

根据装载码头配置方案规划的需要，采取排序选择方法比较适合研究的需要，排序选择方法是指在计算每个个体的适应值后，根据适应值的大小顺序对群体中个体排序，按线性排序计算个体的适应度，再采用轮盘赌选择方式选择复制个体，同时为了保存优良个体加快算法的收敛，采用精英保存策略，将当代种群中的最优个体直接复制至下一代。

设种群大小为M，个体j的适应值为fj，则j个体被选择的概率psj为:

2.4.2 交叉操作

交叉又称重组、配对。当许多染色体相同或者后代的染色体与上一代没有多大差别时，可通过染色体重组来产生新一代染色体。染色体重组分两步进行，首先在新复制的群体中随机选取两个个体，交叉算子采用扩展整体算术杂交算子。如对个体Xijk和Xγjk执行扩展整体算术杂交操作。课题中的个体要求同一段染色体总和为定值A1，A2，A3，因此，采用同一个体同一段染色体之间的编码值进行交叉，保证产生新染色体依然满足约束条件，如图4所示。

图4 装载码头配置方案基因交叉操作

2.4.3 变异操作

选择和交叉操作基本完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率，随机地改变基因值，变异发生的概率pm一般都取很小（一般在0.001～0.1之间）。当选定某个染色体变异操作时，即这个染色体基因加1操作，同时在同一段染色体中另一基因作减1操作，如果另一基因值小于1，则终止此次变异操作。对个体xijk执行变异操作，如图5所示。

图5 装载码头配置方案基因变异操作

2.5 控制参数的设定

控制参数的设定主要指群体的大小和使用遗传算法操作的概率，针对装载配置方案可取交叉概率为0.9，变异概率为0.1，种群规模为N=100。利用计算机编程即可实现解算最优结果。

2.6 遗传算法解算流程图

根据以上遗传算法求解步骤，可制定遗传算法解算流程图，如图6所示。

图6 遗传算法解算流程图

3 算例分析

3.1 基本想定

为实现某两栖作战任务需要两栖舰船数量为A型舰8艘、C型舰6艘、E型舰3艘。现要求最短时间内在某港2座M1登陆码头、2座M4普通码头、1座可供两栖装备泛水装载的M8码头完成以上装载任务，计算此次装载任务的码头配置方案。两栖舰艇装载数量及码头装载参数如表3、表4所示。

表3 两栖舰船装载数量

3.2 码头配置模型构建

如图7所示，实线表示可装载的码头和舰艇，虚线表示不存在装载的码头和舰艇。

表4 某港码头装载能力性能参数表

图7 舰艇装载码头配置方案图

3.2.1 已知

3.2.2 设定

即

3.2.3 求解

图8 装载码头配置方案种群初始化

3.3 运用遗传算法解优化模型

3.3.1 初始种群设定

3.3.2 适应值函数设计

3.3.3 遗传操作实现

①利用计算机编程将以上模型进行解算可得优化方案为:

图9 两栖舰船装载码头配置方案优化解算界面

4 结论

装载码头配置是部队制定装载方案的一项重要工作，本文运用军事运筹学多目标规划和遗传算法理论构建装载码头配置方案优化模型，有效解决了码头配置优化问题，提高了部队装载方案制定的科学性和时效性。该模型算法可以扩展运用到大规模登陆作战中两栖输送舰船同时采用码头装载、抵滩装载、泛水装载时，多种上船点的优化配置问题。但装载配置问题是典型的NP问题，随着装载舰船、上船点种类及数量的增加，优化搜索的计算量迅速增长，算法效率必然会下降。因此，必须进一步改进算法，提高算法的效率。

表5 两栖舰船装载码头配置优化方案

［1］冷画屏，徐清华.大型两栖舰艇编队陆战兵力装卸载方案及流程研究［M］.广州:海军陆战学院，2015:20-21.

［2］周智超，刘钢，徐清华.反舰导弹航路规划理论与应用［M］.北京:国防工业出版社，2015:132-133.

［3］陈文伟，周智超.海军军事数据挖掘技术［M］.北京:海潮出版社，2002.

［4］徐清华，李中良.基于遗传算法反舰导弹航路规划研究［J］.火力与指挥控制，2008，33（增刊）:60-61.

［5］王小平，曹立明.遗传算法——理论、应用与软件实现［M］.西安:西安交通大学出版社，2003.

Research on Project Optimization of Ship Loading Berth Allocation Based on Genetic Algorithm

XU Qing-hua，JI Da-qin，YING Ge
（Naval Marine Academy，Guangzhou 510430，China）

It is a key problem for the navy to make a plan during the ship loading phase，taking advantages of scientific berth allocation to make the ship loading as quickly as possible.In accordance with the characteristics and requirements of berth allocation during ship loading，the thesis applies the multi-objective programming theory of operational research to construct a loading berth allocation model，genetic algorithm theory and computer programming to work out the optimal solution to berth allocation plan model，to improve the scientificity and timeliness of the plan on berth allocation for the navy amphibious transport forces.

genetic algorithm，ship loading，berth allocation，project

E917

A

1002-0640（2017）04-0171-06

2016-02-18

2016-04-24

徐清华（1980-）男，江西鄱阳人，硕士，副教授。研究方向：兵种战术。