基于角色复杂性的损伤修复方案优化模型

曾 庆，尤志锋，石 全

(陆军工程大学石家庄校区 装备指挥与管理系，石家庄 050003)

制定出分工的方案后，如何评价其效果有着重要的意义：它既可以对分工方案作出评价，又可以对制定方案的人的水平、能力进行评估。便于发现分工方案存在的问题，既可以用来改进方案，提高执行的效率，又可以发现人员能力、水平方面的差距，以便有针对性的进行训练，以提高抢修员的抢修能力、水平。对抢修分工方案最直接最准确的办法就是对其分工后任务的执行效率和执行时间进行测度。然而这种方法需要实际执行抢修操作，具有成本高、危险性强的不足，又因为许多场合需要在不执行方案的情况下进行评估。因此，必须寻找一种更好的办法来对这种直接的方法进行替代。复杂性是难度和不确定性的度量，能够反应时间、效率等指标，因此这里用分工所带来的抢修员角色复杂性来对其效果进行评估。并用分工所带来的角色复杂性与时间进行相关性分析，对该方法进行验证。最后结合第三章的分工复杂性给出了抢修员角色复杂性的两个应用。

1 抢修员角色复杂性分析

文献[1-2]通过实验论证了组织结构适应性的测度参数为：工作负载、交流和个体间的依赖关系，并用这3个关系来对组织结构的适应性进行评价。其实这里的组织结构的适应性也可以看作是组织结构的复杂性。其中组织可以退化成单个抢修人员，单个抢修人员可以进化为抢修组织的一个特例。组织的适应性其实就是抢修人员复杂性的一种体现。因此抢修人员的角色复杂性应当包含负载、协作量等。除此之外角色复杂性还应当包含角色所负责作业的内聚性和所需资源的内聚性。因此角色复杂性主要包含以下5个方面：

1) 抢修人员的内部负载。文献[2]只考虑了分配到任务执行人员的任务总数量。由前面章节的分析可知，不同的抢修作业的复杂性系数是不同的。因此只考虑数量，忽略抢修作业的复杂性系数显然是不精确的。因此这里加入抢修作业复杂性系数，用复杂性系数之和来代表抢修员的内部工作负载。设任务分工的结果为

则第j个抢修人员的内部总负载为

其中，w(i)为第i个基本抢修作业的复杂性系数，其具体求法见第6章。n为j抢修员所负责的抢修任务的数量。则m个抢修员总的角色复杂性为

其中m为抢修人员的总数量。

2) 抢修员之间的耦合关系。抢修员之间的耦合关系其实是抢修员的外部负载。耦合关系主要有重合关系和衔接关系组成。重合关系：由于损伤的复杂性，抢修操作往往需要多人协作才能完成。因此在同一基本抢修作业上相关的抢修员之间就构成了耦合关系。抢修作业衔接关系是两个抢修员负责的基本抢修任务在逻辑顺序上存在直接的前后衔接关系，即为紧前作业或紧后作业。这两种关系越多，抢修员之间的交流、协同就越多，其执行过程就越复杂。设m个抢修员之间的协作矩阵[A]m×m为其中：

则第j个抢修员的外部协作负载为

则由抢修员之间的耦合关系引起的外部协作负载总和为

3) 基本抢修作业的内聚性。在执行抢修任务分配时需要遵循“尽量将相近的任务分配给同一抢修员”这一原则。因为任务相近时可以相互参考、相互借鉴，这样可以省去思维、动作、工具的转换带来的时间浪费。由于基本抢修作业的粒度较大，所以在操作过程图中距离较近的抢修作业的相近度较高。因此这里用分配给抢修员的所有基本抢修作业间在BDR_EPN模型上的距离来表示其内聚性：

其中nj=|T(j)|为分配给第j个抢修员的抢修作业的总数量。则：

4) 资源的内聚性。资源主要指抢修过程所用到的工具、设备、资料等物质资源。资源的内聚性是指某个抢修员所负责的抢修作业集中，所有两两作业的相同的资源交集的数量之和的大小。由于在有些抢修过程中，虽然使用的资源相同，但是其使用的方式大不相同，如标准使用和应急他用。这种情况下可以将其看作两种不同的资源。显然如果两个作业之间的资源内聚性较大，就可以省去许多不必要的资源转换时间，也可以利用资源使用的连续性提高资源的使用效率。设T(j)为第j个抢修员所分配到的抢修作业集，|T(j)|为其数量。则抢修物质资源内聚性为

其中n(i)为第i个基本抢修作业和第j个基本抢修作业所需的物质资源的交集中资源的数量。

由于内聚性与复杂性成反向关系，所以得资源内聚性引发的抢修员角色复杂性为

其中n(i)为第个抢修作业所需的资源总数量。

5) 抢修员角色复杂性的综合。对复杂性指标进行综合，是一个情境选择问题，要根据不同的情况，采用不同的方法。其中效果最好的两个是欧几里得范式综合与信息熵综合。但是一般情况下信息熵所得的复杂性测度结果都比较小，一般不便于两者之间进行比较。由于该章所得复杂性结果要与前面的进行比较以便对分工方案和抢修员的能力进行评估，因此这里选用欧几里德范式进行综合。

由于上述熵指标都已经是效益型指标。即指标越大，复杂性越大，且求取的方法相同，因此无需对原始指标进行变换，可直接应用。经过专家组的评判其各个指标的权重为：W=(w1,w2,w3,w4)，第i个指标的复杂性评价值为hf，可得其抢修员的角色复杂性测度为

2 基于角色复杂性的方案优化[3-4]

由上面抢修过程模型可以看出，不同的分工方案对应着不同的抢修逻辑模型。因此，不易用一个固定的流程来对所有的方案进行优化分析。当抢修方法和抢修工艺确定后，抢修基本作业的顺序关系基本上就确定了。尤其是有着紧密连接关系的基本抢修作业之间，谁先谁后是必须固定的。但是对于一些没有紧密连接关系的抢修作业，则需根据总体优化的目标来进行安排，确定他们之间是并行还是串行或是其他关系[5]。由抢修员的角色复杂性影响机制可以看出，当分工方案确定后，这些作业之间的关系安排将直接影响到抢修员的角色复杂性。因此利用角色复杂性可以实现对抢修作业的调度与优化，为顺利实现抢修任务打下基础。下面基于抢修员角色复杂性利用分层嵌套遗传算法对分工方案以及流程逻辑结构设计方案进行优化[6]。

2.1 嵌套遗传算法求解的基本思路

抢修员角色复杂性主要是由分工方案和抢修流程的逻辑结构两个因素决定的[7]。因此，需要对两者展开搜索优化，以便找到与最小复杂性相适应的分工方案和逻辑结构。其基本思路为：利用两步搜索遗传算法。第一步：对任务分工方案进行搜索。第二部：在某一个分工方案的基础上对流程结构进行搜索，找到使特定方案的角色复杂性最小的逻辑结构。最后选择所有的方案中角色复杂性最小的逻辑结构。并将其对应的方案和逻辑结构作为最终结果进行输出[8]。这其实是一个嵌套结构，第二部嵌在第一步之中，其基本原理如图1所示。

2.2 基本步骤

1) 固定方案优化结构。为每一个可能的方案找到其使作业内聚性和外部协作性最小的逻辑结构，其基本模型如下；

min={W(m)+J(m)}

s.t 不同的逻辑结构

抢修作业的约束

2) 固定逻辑结构优化方案。找到一个可能使内部负载和资源内聚性最小的分工方案，其基本模型如下；

min={N(m)+T(m)}

s.t 不同的分工方案

3) 第2步所得到的方案及其对应的在第一步求出的结构，即为最终结果。

2.3 逻辑结构优化算法设计

1) 编码方案。由于紧前作业和紧后作业是一对对偶关系，即若是的紧前作业，则必然是的紧后作业。所以只需对其中一个进行确定就可以确定抢修作业过程的逻辑结构图。这里采用紧后作业进行表示，利用二进制矩阵编码。基因座号的横纵坐标都用基本抢修作业的编号表示，其编号范围为[1，n]。基因的值为1或0，1表示所在基因座所表示的基本抢修作业属于其紧后作业，0表示不属于。这个编码的前提是需要知道开始作业。

如图2所示，Xij表示第i个抢修作业与第j个抢修作业的关系。Xij表明第j个抢修作业是第i个抢修作业的紧后作业，0则表明不是紧后作业。

如图3所示的逻辑结构可以用如下编码表示。

010100|001000|000010|000010|000001|000000

由于在确定结构的过程中，需要用到任务分配方案，所以需知道第二步的编码方案。任务分工的编码方案仍然采用二进制矩阵编码。基因座编号横坐标为基本抢修作业的编号，纵坐标为抢修单元的编号，基因值为抢修单元与抢修作业之间的关系(图4)。

这种编码方案既可以表示一个作业由多人同时完成，也可以表示一个人在不同的时段可以完成多个作业。

2) 初始种群生成。为了对流程的逻辑结构进行表示，这里用一个二元组来表示抢修作业，即(xi,xi·)，其中xi·表示抢修作业xi的紧后作业集合。这样所有抢修作业的二元组表示即可以确定一个唯一的抢修流程结构。流程结构的选择就是选择每个抢修作业的紧后作业集合。由编码方案可以看出基因的长度较长为：n×n。如果不对其中部分基因座的基因值进行限制，则搜索的空间太大，当n的值较大时，搜索的速度很慢，也容易陷入局部最优。这个集合的大小决定了搜索空间的大小。按照抢修方法确定的抢修工艺对某个作业的两个集合进行限定，以缩小搜索的空间，提高搜索的效率和准确性。抢修作业的紧后作业集不具有传递性，这样可以保证对循环结构仍然有效。

根据抢修方法和抢修工艺所确定的抢修作业约束对部分基因座的值进行限制。如某些作业只能在另一个作业的紧后面发生，或流程中不存在循环等。当限制确定后，在可以选择的基因座处，用随机数产生器产生0或1的值，作为一个个体，假设共有n′个基因座可以选择，则共产生2n′个个体。根据其大小按照轮盘赌选择地方法从中选出20、40、100个个体作为初始种群。

3) 适应度函数。从角色复杂性的影响因素可以看出，逻辑结构只对基本作业的内聚性、角色的耦合性产生影响。角色耦合性越大复杂性越大；作业的内聚性越大，复杂性越小，然而在求取角色内聚性对复杂性的影响时，已经对其做了一定的变换，与复杂性成正相关关系，所以W(m),J(m)与复杂性是一致正相关的关系，因此这里用两者之和作为逻辑结构优化的适应度函数：

f=W(m)+J(m)

其具体的计算公式已在2中给出。只需将公式转换成代码即可。

4) 交叉算子。矩阵编码，在遗传操作的过程中将整个矩阵作为遗传个体进行操作。随机产生一个区间[1,n]的服从均匀分布的随机数，将两个矩阵染色体中随机数所代表的两个行(或列)照一定的概率pc进行交换。这样虽然是对位交换，可以保证交换后的染色体仍满足原来的约束。但是却可以改变各个作业节点之间的关系使其出现以下两种情况：

一个节点的今后节点集中的两个节点之间出现今后关系(图5)；编码当中除第一列(起始节点)和最后一行(结束节点)外，出现列中全部为零或行全部为零的现象(图)。这两种情况都与抢修作业流的定义不符(DBR-EPN)，需要排除。因此，当交叉后若出现上述两种情况之一，则需要将其中不符合要求的基因值进行改变使上述两种情况不再出现。

5) 变异算子.随机产生两个区间[1,n]的服从均匀分布的随机数，将产生的这两个数作为坐标值，来定位染色体矩阵中基因的位置。若该该基因位置由于约束的设定而不能改变，或变异后出现上述两种情况，则重新生成随机数，直到找到没有约束限制可以改变为止。以一定的概率pm将该基因值与1相减后去绝对值。

6) 终止条件。如果连续3次迭代所得到的种群中适应度最大的值之间差的绝对值都小于某一个制定的值，则增大选择和变异的概率，重新迭代。若所得种群的最大值仍然与没有改变之前的最大值之间差值的绝对值仍然小于给定的值ξ，则停止迭代，否则继续，直到满足上述条件为止。

分工方案优化算法设计与逻辑结构优化的算法设计基本相同，这里就不在重复，只说明一下初始种群的限制：根据抢修员的能力水平及专业限制结合抢修作业本身的特征进行人工初步分配。其原则经过初步分析是只要抢修员不能完成或不适合完成该项抢修作业，则将该抢修作业基因座对应的抢修员设置为0。

3 实例分析与应用[6]

这里以火炮身管拆卸为例对算法的运行情况进行测试。火炮身管拆拼是战场上经常遇到的抢修操作，其拆卸的快于否，直接影响着抢修操作的成败，因此合理优化身管拆卸作业步骤，对提高身管抢修效率具有十分重要的意义。火炮身管拆卸分为以下6步：① 打平炮身；② 抽出驻退机；③ 抽出复进机；④ 卸下后座冲铁；⑤ 后退炮身并固定；⑥ 用吊车抽出炮身。为了更加清楚的说明问题，以前五步为例进行说明。共有2名中级修理工任何一名修理工可以胜任全部五项工作。打平炮身必须作为起始，后退炮身并固定必须作为结束。因此，该优化内容就变为了对(2)(3)(4)步的逻辑优化，及两名修理工的分工。按照上述嵌套遗传算法模型，设置交叉概率为0.85，变异概率为0.05，最大进化代数为200，初始种群数量为50。其遗传进化过程如图6(左)所示。

经过优化得最优方案为：1，2，3由抢修人员1完成，4，5由抢修人员2完成。(如图7右所示)。其对应的最优逻辑结构的编码矩阵及最优逻辑结构图分别如图7(左和右)所示。最优逻辑结构所对应的抢修人员角色复杂性为：8.843 0。算法运行时间为0.13 ms。虽然该实例较为简单但是与运行同等简单实例的普通遗传算法(文献[9])相比(3 ms)仍然具有较高的效率。

图7 最优逻辑结构矩阵及流程

4 结论

提出了抢修员角色复杂性的概念及其计算模型。角色复杂性由分工方案和流程的逻辑结构共同决定。与第三章任务分工本身的复杂性与抢修员角色复杂性相结合可以实现对抢修方案的评估，进而评估抢修员的能力水平；同时基于抢修员角色复杂性，利用嵌套遗传算法可以同时对分工和抢修逻辑结构进行优化，为合理的安排基本抢修作业的顺序、充分利用已有资源提供了更加科学的依据。