基于遗传算法的编队条件下舰船修理周期结构优化

朱晓军 张 涛 彭 飞 李 钢

1 海军工程大学 船舶与动力学院，湖北 武汉 430033 2 中国人民解放军92956部队，辽宁 大连 116041

1 引 言

舰船修理周期结构指的是舰船在全寿命周期内所进行的基地级计划修理类别、修理时间和间隔周期的组合，是舰船装备技术保障实施科学管理的基本依据，直接关系到实施修理的有效性和经济性、保障资源建设的科学性以及舰船的战备完好性。对于单舰来说，它需要一个与自身型号及使用情况相适应的修理周期结构来指导其修理保障工作。编队同样也需要一套修理周期结构来保障编队整体的使用和维修，这一套修理周期结构并不是编队内所有舰艇作为单舰的修理结构的简单叠加，而是经过组合优化形成的一套整体相互匹配的修理周期结构，所以合适的舰船修理结构是充分发挥编队战斗力的重要保证，也是提高整体作战能力的基础。我国舰船修理周期结构的研究以往多是从单舰客观的维修需求和保障资源出发进行的优化，没有考虑到编队的整体使用需求。文献［1］建立了编队修理结构模型，从减少编队修理时间的角度对编队内各个舰艇的修理周期结构做出了优化。外国海军的编队使用较早，文献［2-4］依据美海军编队的特点对编队的修理周期结构进行了深入研究。本文将在已有舰船修理结构定量描述模型的基础上建立编队条件下的修理调度模型，分析编队条件下单舰的修理周期结构优化问题，并采用改进的遗传算法进行优化计算。

2 修理周期结构的数学描述

在文献建立的修理周期结构的数学描述基础上，构建修理周期结构矩阵，如式（1）所示。基地级计划修理的本质是一种定时修理，虽然在实施基地级计划修理时，根据舰船装备的实际状态，需要结合必要的视情和事后修理项目，但从确定舰船修理结构的角度，关键是要明确舰船在规定的服役期内基地级计划修理的类别、修理时间和间隔周期这三个要素及其组合。因此，可以用矩阵MC表达修理周期结构如下：

式中，ci＝［siti］；ti为 各个 状态 的持 续时间，以“月”计；si为状态变量，表示舰船在服役期内所处于几种状态，si∈U，

以某型舰艇为例，其修理间隔期和在修时间如表1所示，组合形式如图1所示，则其修理周期结构矩阵可表示为：

在明确单舰修理结构模型的基础上，就可以进行编队内舰艇的修理周期的组合优化研究。

表1 某型舰艇的修理周期数据Tab.1 The maintenance period data of a ship

图1 某型舰艇的修理周期的组合形式Fig.1 The combination of a ship maintenance period

3 编队条件下的修理调度模型

3.1 编队修理周期结构矩阵

借鉴文献［1］建立编队修理结构矩阵的方法，假设一个典型编队［5］中的作战舰艇组成为指挥舰1艘，驱逐舰Dt艘，护卫舰Ft艘，核潜艇St艘。编队里每一艘舰艇的修理周期结构都可以用修理周期结构矩阵表示。若舍弃结构矩阵中的状态向量，并把编队中各个舰艇的修理结构矩阵组合起来，便产生了编队修理周期结构矩阵F＿MC：

其中：

1）txyi表示编队中舰艇的某种状态的持续时间。 x 表示舰型，x＝c，d，f，s；y 表示一种舰型的某艘舰艇，y＝1，2，… Nx；i表示某艘舰艇修理周期结构矩阵（MC）的状态序号。例如，td22表示编队中驱逐舰（用d表示）的第2艘舰艇处于修理周期结构的第2个状态。

2）此处规定舰艇均以可部署状态进入编队，即在各舰艇修理周期结构矩阵里，txy1对应的sxy1＝0；x＝c，d，f，s；y＝1，2，… Nx。

3）y是对同种舰型中某艘舰艇的标识，同舰型的各个舰艇进入编队的部署时间可以不同，即x相同、y不同时，txy1可以不相等。

4）编队内舰船的数目与矩阵的列数目对应，即矩阵的列数等于1＋Dt＋Ft＋St。

5）调度矩阵的行数由编队内服役周期最长的舰艇决定，修理周期结构较短的舰船在矩阵里对应的空缺位置用“0”补齐。一般情况下，指挥舰的服役周期最长，故矩阵的行数等于m。

3.2 修理调度模型

一般舰艇在服役期内进行的各基地级修理（坞修、小修、中修）都有规定的需要完成的维修项目，所以在修理周期结构矩阵MC中，基地级修理时间的可变化范围很小，这里认为各基地级修理时间在 MC 中为常量，即 si＞2 时，txyi＝consti。 但舰船的修理间隔在不超过舰上重要装备要求的最大修理间隔情况下，可调整的范围比较大，如美军舰艇在其国家战略需求的牵引下，不断延长修理间隔以达到更高的部署能力。自2003年美军提出舰队反应计划后，其大型水面编队的维修周期从24个月依次延长到27个月、32个月以及将来的42个月［6-7］。本文中的维修周期是指从一次基地级修理结束时刻至下一次基地级修理开始之间的时间。

为简化模型，认为修理周期结构的各个修理间隔期长度是相同的，决策变量V＝［v1，v2，…，vn］，其中vj表示第j艘舰船的修理周期结构中修理间隔期的变化。

优化目标函数为：

目标函数中F（S）不是一个显函数，它表示对调度矩阵的操作，其值表示编队的部署时间。

当编队修理结构矩阵中任意一列全为0，即有一艘舰艇到达其寿命终点要退出编队时，便认为整个编队的服役期结束。

4 调度模型的求解与优化

4.1 目标函数的求解

修理调度模型中目标函数F（S）根据编队中各个舰艇服役的时间序列在编队使用时间上的重合度进行编写。算法实现的功能为，给出一组决策变量即可求出相应的编队部署时间。其流程如图2所示。

图2 目标函数的算法流程Fig.2 The flow chart of the object function

4.2 优化—遗传算法

在修理调度模型中根据决策变量的不同，可以组合出多种编队的修理周期结构。假设编队由10艘舰艇组成，决策变量变化范围vj∈［-2，8］。都取整数后每一个决策变量有10种取值，则有1010种组合方案，因而不宜采用一般的穷举法寻找最优解，必须采用一种简便的优化工具来寻找，即寻找编队的最大部署时间。

遗传算法（Genetic Algorithm，GA）是借鉴生物界自然选择和群体优化的进化机制而形成的一种全局寻优算法，与传统的优化算法相比，遗传算法具有以下优点［8］：

1）不是从单个点，而是从多个点构成的群体开始搜索。

2）在搜索最优解的过程中，只需要由目标函数值转换得来的适应值信息，而不需要导数等其他辅助信息，这对于目标函数不是显函数尤为适用。

3）搜索过程不易陷入局部最优点。

所以本文选用遗传算法并加以改进后对模型进行了优化求解，遗传算法的关键步骤如下：

1）染色体编码与解码

遗传算法不对优化问题的实际决策变量进行操作，所以应用遗传算法的首要问题是通过编码将决策变量表示成串结构数据［9］。本文采用最常用的二进制编码方案，即用二进制数据构成的符号来表示一个种群个体。首先根据各决策变量的上下界及其搜索精度来确定各变量的二进制串的长度，然后用均匀分布的随机数来生成初始种群的各个个体。

编码后的个体构成的种群必须经过解码，转换成原问题空间的决策变量实值，方能计算相应的适应值。假设某一变量的取值范围为［U1，U2］，对应的编码公式为［10］：

2）选择算子

以模型的目标函数作为遗传算法的适应度函数并以此计算各个个体的适应值。标准遗传算法按与个体适应值成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会的多少。在本算子中，采用了精英保留策略与赌轮算法相结合的思路。首先找出当前群体中适应值最高和最低的个体，将最佳个体保留并用其替换掉最差个体，直接进入下一代，这种劣种淘汰的方法提高了整个种群的竞争力［11］，然后将剩下的个体按赌轮算法进行操作。将这两种方法相结合的目的是，在遗传操作中，不仅能不断提高群体的平均适应值，而且还能保证最佳个体不被交叉、变异等操作所破坏，可有效防止“早熟收敛”。

3）交叉和变异

采用单点交叉的方法实现交叉算子，即按选择概率Pc在两两配对的个体编码串随机设置一个交叉点，然后在该点相互交换两个配对个体的部分基因，从而形成两个新的个体。

对于二进制的基因码组成的个体种群，以变异概率Pm随机选择变异点并翻转该点，即0变成1，1变成0，从而产生新的基因个体。

5 算法实例与讨论

本文计算的编队由1艘指挥舰、2艘驱逐舰、2艘潜艇和2艘护卫舰共7艘舰艇组成。由各舰艇的修理结构得到编队修理周期结构矩阵F＿MC，其数据如表2所示（单位为月）。

将表2的编队部署数据输入到模型算法中，令 X＝［x1，x2…x7］＝［0，0…0］，则由目标函数 FDeployTime＝F（S）计算得出编队整体的部署时间a＝60（月）。然后依照遗传算法参数设置的一般原则（表3），并通过反复调试。

表2 编队的修理周期数据Tab.2 The maintenance period data of the fleet

表3 遗传算法的参数设置Tab.3 The setting of the genetic algorithm parameter

为提高舰艇的在航率，通用的做法是延长修理周期，但考虑到编队内各艘舰艇的相互配合，也可适当缩短。因此，变量的范围设定为xi∈［-2，8］，i＝1，2…7，可以根据需要进行调整。

使用组合台式机进行计算，机器配置有1.80 GHz的 Intel（R）Pentium（R）Dual E2160处理器，2.00 GB内存。计算结果如表4所示。

表4 优化计算结果Tab.4 The optimization results

由计算结果可知：

1）由图3、图4可以看出，算法遗传100代后最佳个体及适应值都能稳定收敛，说明用本算法优化计算出的结果是可靠的。

2）编队中各舰艇的部署时间依次加上约0.5，8，-2，4.2，6.3，-0.8，-0.8 个月后，编队的部署时间可达近110个月，相对于没有优化前提高了50个月，该结果非常可观。

3）调整后，编队内3艘舰艇的修理间隔期均被延长，最多的延长了8个月。对于一艘新服役的舰艇，其寿命周期将延长7年左右。

4）本算法遗传进化200代需要72.52 s，在实际应用中比较高效。

6 结 论

本文在编队的修理周期结构模型的基础上，建立了编队修理调度模型，为定量分析编队的部署能力奠定了基础。模型利用改进的遗传算法对编队的部署时间进行了优化，并取得了显著的效果，但将一艘舰艇的服役期延长7年左右，在实践中是否可行还需进一步的论证研究。

虽然本文提出了定量分析编队条件下的舰船修理周期结构，并运用实例证明编队的部署能力经过优化后可以大幅提高，但模型中没有考虑编队内同一种舰型的多艘舰艇可以相互顶替使用等情况，这也将是下一步的研究重点。

［1］张涛，朱晓军，彭飞.编队作战需求下舰船修理周期结构的优化［J］.中国修船，2011，21（4）：51-55.

［2］Chief of Naval Operation.Representative intervals，durations，maintenance cycles，and repair mandays for depot level maintenance availabilities of U.S.navy ships ［R］.OPNAV Notice 4700，June 13，2005.

［3］JACOBS K S，ROBERT L C.The maintenance requirements system：risk-based resource planning comes of ages［C］／／American Society of Naval Engineers Conference，2001.

［4］ROLAND J Y，JAMES G K，JOHN F S，et.al.Increasing aircraft carrier forward presence：changing the length of the maintenance cycle［R］.RAND，2008.

［5］MATTHEW H H，MATTHEW W C.The impact of longteam aircraft carrier maintenance scheduling on the fleet readiness plan［D］.Naval Postgraduate school，Monterey，California，2004，9.

［6］ROLAND J Y，JOHN F S，JAMES G K.Aircraft carrier maintenance cycles and their effects［R］.RAND，2008.

［7］ROLANDLY J Y，RAJ R，JESSIE R.Impacts of the fleet response plan on surface combatant maintenance ［R］.RAND，2006.

［8］刘国华，包宏，李文超.用MATLAB实现遗传算法程序［J］.计算机应用研究，2001，18（8）：80-82.

［9］ROLAND J Y，JOHN F S，JAMES G K.A methodology for estimating the effect of carrier operational cycles on the maintenance industrial base［R］.RAND，2007.

［10］雷英杰，张善文，李续武，等.MATLAB遗传算法工具箱及应用［M］.西安电子科技大学出版社，2005.

［11］夏华波，纪卓尚，张明霞.改进遗传算法在驳船配载中的应用［J］.中国舰船研究，2010，5（6）：51-55.