作者：郑晓敏

  现有文献中讨论了不同的多层、多级的LORA模型[1-9]，这些模型无不涉及大量的决策变量，因此，通过传统优化方法如整数规划和分支定界等很难对LORA问题进行优化求解，而遗传算法及其混合策略在求解非常耗时的大规模组合问题时显示出了极高的效力。鉴于此，本文提出一种遗传禁忌搜索混合算法，将其应用于LORA问题求解，并利用算例的比较分析，表明该算法能在可接受计算时间内求得最优解。

1  LORA问题模型的建立

1.1航空装备维修级别和层次划分

    LORA分析是以维修级别与装备修理的约定层次的划分为基础的。维修级别根据装备的范围和深度区分任务，并按维修时所处场所划分等级。航空装备维修级别分为三级，即基层级(O)、中继级(I)和基地级(D)。装备修理约定层次一般划分为外场可更换件(LRU)、车间可更换件(SRU)、车间可更换件子部件( SSRU)三个层次。对于一个给定的设计，修理级别分析师必须决定哪些部件要修理、哪些部件要报废、在惨理网络中何处执行这些活动，从而确定部件进行修理或报废的位置，并以最低成本满足维修要求。

1.2 建立数学模型

    本文研究中，设i为所研究系统的部件，i=1，2，…，n，n为部件总数；r为修理选项，包括修理、报废、移动；e为维修级别。本文参考文献[1，3，4]所描述的模型，对LORA问题进行建模，通过最小化维修成本获得最优修理决策。

建立的数学模型如下：

    式(2)确保在基层级（e=1）选择一个修理选项。式(3)表示如果在e级上采取移动决策，在e+1级上应只采取修理决策，否则，在e+1级上不选择任何修理选项。式(4)表示子部件与父部件在各维修级别上采取相同的报废或者移动决策；j表示部件i的子部件。式(5)表示在最高级维修级别上（e=3）仅有两种修理决策（修理或报废）可供选择。2  求解算法设计

2.1  算法思路

    遗传算法和禁忌搜索( Tabu Search，TS)都是求解组合优化问题的常用算法[10]。遗传算法及其混合策略在求解非常耗时的大规模组合问题时显示出了极高的效力，缺点是当种群规模较大时求解速度较慢，而禁忌搜索又较依赖于初始解。因此，提出两者混合算法即GATS算法，克服两种算法的缺点并保留各自的优势，对NP-hard和组合优化的LORA问题进行求解。

    本文的GATS算法首先生成N个初始可能解；然后利用禁忌搜索的迭代过程进行邻域搜索，对这些解进行更新；之后，流程返回遗传算法，再进行一个迭代过程；通过遗传算子产生新的后代，并根据新的后代的适应值对最佳解的禁忌表进行更新。GATS算法的终止准则是达到了预定义的连续迭代次数，迭代过程获得的最佳解相同。

GATS算法流程如图1所示。

    GATS算法的具体步骤如下：

    (1)随机产生一个解集（20个解），验证式(2)、式(3)、式(4)、式(5)。

    (2)通过邻域搜索改进解的适应度值。邻域解仅通过修改解的值为1或o获得。另外，直到验证了式(2)～式(5)，才接受邻域解。然后，更新禁忌表，其中包含所有已探索过的解的适应度值。接着，仅当适应度值不出现于禁忌表中时，探索一个新的邻域。

    (3)重复步骤(2)，直到最佳适应度值没有改进。

    (4)用最佳邻域替换该解。

    (5)基于遗传算法的选择算子和交叉算子，选择两个解来产生新的染色体。当验证了式(2)～式(5)时，接受这些新的解。

    (6)利用变异算子，生成新的染色体。

    (7)更新最佳染色体的禁忌表。

    (8)重复以上步骤，直到最佳染色体没有改进。

2.2   GATS算法设计

2.2.1编码方式

    用遗传算法求解特定问题时，首先要确定编码方式。本文采用的编码方式是一个二进制矩阵（n×d），其中n为所有部件（即项目）的数量，d为所有修理决策的数量。该编码方式中，xij=1意味着部件i和级别j选择了修理、报废或者移动决策。图2是染色体或解的二进制编码方式，其中“项目”表示待分析产品，可以是部件或子部件。

    另外，任何技术系统都可视为装配的集合，这些装配又可视为一些子装配的集合。出于建模的考虑，系统分解结构用一个矩阵来表示，称为共性矩阵，如图3所示。其中列代表父部件，行表示子部件，子部件4、5、6属于父部件3，或者说父部件3包含了子部件4、5、6。根据式(4)，无论何时父部件3采取报废或移动决策，子部件4、5、6都将采取同样的决策。

2.2.2适应度函数

    本文的目标函数是求解最小值问题，算法的选择过程采用轮盘选择法，因此本文采用的适应度函数为：

2.2.3遗传算法算子

    GATS算法使用适应度值比例选择的轮盘赌抽样作为交叉算子。每一代采用最优保存策略，用满足式(1)的最好的解替换最差的。选择一对父代进行交叉运算产生两个新的子代。交叉算子通过交换信息作用于这两个父染色体。由于每一对父代染色体的基因密码有着相同的结构，因此随机选择交叉点进行单点交叉，接着根据式(4)调整子代修理决策。

    变异运算是遗传算法的另一重要特点，是产生新个体的辅助方法，变异运算的目的是维持群体的多样性，防止解陷入局部最优。本文中变异算子从最优解列表中随机选出一个染色体，并用一个同样是随机产生的新的染色体替换；另外，选择一个最优解，并随机为部件产生一个修理决策；然后再根据式(4)调整修理决策。

2.2.4邻域结构

    TS的框架由产生自初始解的一些邻域解组成，通过目标函数对这些解进行评估并分类。禁忌表通过最优解的适应度进行更新，然后确定一个新的解并从中产生额外的邻域搜索。当一系列迭代之后最佳解保持不变时，便求得了最优解。本文采用互换的方法产生邻域结构。

2.2.5禁忌对象和禁忌表的确定

    本文将禁忌对象设定为状态本身，将每次迭代最终接受的解作为禁忌对象放入禁忌表中。禁忌表是禁忌对象的集合。

3实例分析

    本节将根据数值实验的结果测试GATS算法的有效性。为了比较起见，对文献[3]执行过的案例进行研究。文献[3]中给出了航空发动机的三层结构和两轰修理网络，以及所有项目在不同级别上不同修理选项的固定成本和可变成本。另外，图4给出共性矩阵，显示父部件（项目1到项目10）与子部件（项目11到项目32）之间的关系。用MATLAB语言对GATS算法进行编译，并在电脑上实施该算法。表1为本文GATS算法获得的最优解，与文献[3]的修理决策相同。另外，文献[7]中也对文献[3]执行过的案例进行了研究，其中所使用的免疫粒子群算法(IA-PSO)和本文GATS算法得出相应的总维修成本分别是4 277. 27美元和4 216. 27美元，计算时间分别为32 s和21 s，如表2所示。

4结论

    (1)在现有LORA研究的基础上，对LORA问题进行了建模，以最小化维修成本为目标，获得最佳修理级别决策。

    (2)利用遗传-禁忌搜索混合算法，对LORA问题进行了优化求解，并给出了算法的求解步骤。利用文献[3]中的数据，通过算例的比较分析，对三级修理网络和多级系统结构的修理决策进行了优化，结果表明在合理的时间内可获得LORA问题的最优解，证明该算法是切实可行的。与免疫粒子群算法的比较结果表明了本文算法的有效性。

(3)与相关文献研究结果相比，本文提出的算法更适于求解涉及大量决策变量的LORA问题。结合工程实际对LORA模型进行改进后，可以用本文提出的算法对LORA问题进行优化求解，为维修决策的制定提供参考。

5摘要：

修理级别分析(LORA)是维修决策制定的一个重要工具。由于已有的修理级别分析整数规划模型涉 及大量的决策变量，用传统的优化方法很难对其进行优化求解，故提出了一种遗传禁忌搜索混合算法，以最小化维修成本为目标，对LORA问题进行求解，确定最佳修理决策组合。最后通过算例的比较分析，表明了本算法的有效性。