基于两层遗传整数规划的复杂系统设计结构矩阵重构方法

摘要

本发明涉及一种基于两层遗传整数规划的复杂系统设计结构矩阵重构方法，可应用于航空航天、汽车、船舶等工业领域。本发明采用一种双段染色体编码技术，实现对DSM中元素序列与聚类方案的同时优化，并采用整数遗传规划算法对DSM聚类问题进行分层求解，得到了重构后的最优DSM。该方法首先基于DSM的联系信息流量作为输出建立优化模型模型，并对模型进行两层优化。第一层重构采用遗传整数规划方法获得初步的DSM聚类方案；第二层重构采用相同算法，对初步方案中的每一个聚类进行第二次搜索，得到最终的DSM重构结果，从而简化设计过程，缩短了开发时间并加大设计资源利用率。

说明书

技术领域

本发明涉及一种基于两层遗传整数规划的复杂系统设计结构矩阵重构 方法，可应用于航空航天、汽车等多个工业领域。

背景技术

设计结构矩阵(DSM)最早由美国学者Steward提出，是一种用于对 产品开发过程进行规划和分析的矩阵工具。DSM是一个代表复杂任务或团 队关系的信息交互模型，如包含多个学科的复杂系统或复杂产品设计流程， 通过此模型可以确定合理的任务序列或者分组，提高整个系统的工作效率。 在DSM中用矩阵的对角线单元表示过程中的各项任务，通常代表复杂系 统中的各学科或产品设计过程中的各个环节；用非对角线单元表示对应行 列元素之间的联系，即各学科间或产品设计过程中的数据传递关系；用矩 阵单元相对于对角线的上下位置来描述对应的行列元素之间联系的方向。 若定义对角线上方为正向传递，对角线下方则为反馈传递，反之亦然。

一个复杂的产品或系统通常涉及多个学科，且各个学科之间相互交叉， 相互作用，具有很强的耦合关系，需要多部门型号设计人员协同工作才能 完成，导致设计周期增长，设计成本增加。针对这种情况，在产品开发过 程或系统设计过程中，需要对产品或系统中各个结构进行模块化划分和管 理，来简化设计过程，缩短开发时间并加大设计资源利用率。为实现以上 目的，需要对设计结构矩阵进行聚类重构，从而得到更为合理的模块化系 统结构。

为更好的说明本发明的技术方案，下面对所涉及的相关知识进行说明：

(1)设计结构矩阵联系信息流量

设计结构矩阵联系信息流量的概念由南京航空航天大学刘建刚提出 (刘建刚,马安,王宁生.基于设计结构矩阵的产品结构模块聚类方法[J].华 南理工大学学报(自然科学版),2006,(11):45-48+86)。根据该评估标准，首 先将DSM中的元素分为三类：独立元素、bus元素和其它元素。其中独立 元素为与其它任何行列元素都没有联系的元素，代表与其它学科或环节不 存在数据传递关系的学科或环节；bus元素为与大部分其它行列元素都有联 系的元素，代表与其它学科或环节具有复杂数据耦合关系的学科或环节； 余下的为其它元素。在其它元素中，从任一个元素出发，查找与之有强联 系的元素，然后再查找与这些元素有强联系的元素，直到找到全部与该集 合有强联系的元素为止，所得到的一个集合记为一个聚类(模块)。然后 再以剩下的元素中任一个为起点，重复上述过程，直到这些集合包括了所 有元素为止，即依据强联系进行了初步的聚类划分。

DSM聚类后，即可根据聚类结果计算整个DSM的联系信息流量，作为 DSM聚类结果的评估准则。每一个元素的联系信息流量考虑了两个元素之 间联系的强度，以及它们所在聚类中的元素数量。bus聚类与其它类的联系 信息流量是确定的，因此为了降低计算的复杂程度，在进行联系信息流量 计算的时候不计bus类在内。因而元素i的联系信息流量可由下式计算：

$C_i=\underset{j=1}{\overset{n}{\Sigma }}\{D\left(i,j\right)+D\left(j,i\right)\}{N}_{i,j}^2$

式中：C_i为第i个元素的联系信息流量，D(i，j)是DSM中元素i和元素 j之间联系的权重；n为DSM中元素的总个数；若i、j属于同一聚类，则 N取二者所在聚类的元素数量；若i、j不属于同一聚类，则N取DSM中 所有元素的数量。

DSM模型的全部联系信息流量是所有单个元素联系信息流量的总和， 即为

$C=\underset{i=1}{\overset{n}{\Sigma }}{C}_i$

式中：C为全部的联系信息流量(不包含bus类的联系信息流量)；n 为DSM中的元素总个数。

(2)小生境遗传算法

遗传算法(GeneticAlgorithm，GA)是模拟达尔文遗传选择和自然淘 汰的生物进化过程的一种全局优化概率搜索算法。其基本思想是：将设计 空间内的可能解看作种群中的个体，并对其进行编码存储。以目标函数为 标准，对个体进行适应度评估，通过选择、复制保留优良个体(目标函数 较小的解)，同时通过交叉和变异产生新的个体，并对种群进行更新。反 复执行上述过程，直至找到最优个体，即优化问题的全局最优解。

在解决非单调函数或多峰值函数的优化问题时，通常需要在遗传算法 中加入小生境方法即小生境遗传算法。小生境方法的基本思想来源于生物 在进化过程中总是与自己相同的物种生活在一起的特性，反映到遗传算法 中就是使遗传算法中的个体在一个特定的环境中进化。相比于其它的优化 方法，小生境遗传算法可以避免在进化后期，适应值高的个体大量繁殖， 充满整个种群，提高种群的物种多样性，从而使算法具有更高的搜索效率， 并可以在一次搜索中得到目标函数的多个极值点，但容易产生进化停滞和 局部最优性差等缺陷，局部搜索能力有待提高。

代表性的小生境操作有预选择(Preselection)、排挤(Crowding)、 共享(Sharing)等。本发明中，采用排挤方法来提高遗传算法的全局搜索 能力。

发明内容

本发明的目的是为了解决对设计结构矩阵进行重构前，通常需要依赖 人工经验确定聚类数量，使重构过程缺乏可靠性且设计效率低下的问题， 提出一种基于两层遗传整数规划的复杂系统设计结构矩阵重构方法，通过 一种双段染色体编码技术(DualChromosomeCoding，DCC)，实现了DSM 中元素序列与聚类方案的同时编码，并以分层优化的方法，经过两层重构， 得到最终的DSM重构结果。

本发明的目的是通过下述技术方案实现的。

一种基于两层遗传整数规划的复杂系统设计结构矩阵重构方法，具体 实现步骤为：

步骤1：以数值表示DSM中各个元素的耦合关系，并以DSM的联系 信息流量作为输出，初始化DSM聚类分析模型。

步骤2：以DSM的联系信息流量为目标函数，建立优化如下优化模型：

findX＝[x₁，x₂...x_N]

l₁，l₂...l_N-1∈{0，1}

minf(X，l₁，l₂...l_N-1)，

其中，X代表N个学科的排列顺序，l₁，l₂...l_N-1用于表示DSM的聚类方式， 二者共同决定了DSM的聚类方案，具体编码方式见步骤3。f(X，l₁，l₂...l_N-1)为 当前聚类方案下DSM的联系信息流量总和，优化目的是使DSM的联系信 息流量总和最小。

步骤3：采用遗传整数规划方法进行第一层重构，流程如细节如下：

步骤3.1：双段染色体编码

本发明中通过一种双段染色体编码方式，实现了将聚类数量作为变量 之一随算法迭代，并自动找出最优聚类数量。若DSM中包含N个元素， 则染色体编码长度为2×N-1，如下所示。

其中，第一段染色体编码以前N项白色元素表示，由整数1～N的排列 组成，用于表示N个元素的排列顺序；第二段染色体以后N-1项灰色元素 表示，由0-1编码序列表示，用于确定DSM的聚类数量以及各个聚类所包 含的元素。在第二段染色体中，若第i个元素为1，则说明在第一段染色体 第i个元素后切割染色体，将两侧的元素分为两个聚类。二者合并共同构成 双段染色体编码，决定DSM的聚类方式。例如DSM中包含5个元素，且 编码如下：

1 2 3 4 5 1 0 1 0

其中，前五位为第一段染色体，代表5个元素的排列顺序；后四位为 第二段染色体，代表5个元素的聚类方案，其中第一位和第三位为1，表 示在第一个和第三个元素后切割序列，将两侧元素分为两个聚类，即

该列编码所代表的聚类结果为：

表1示例1聚类结果

聚类1 元素1 聚类2 元素2、元素3 聚类3 元素4、元素5

同样的，若编码为

5 1 4 2 3 0 1 0 1

其所代表的聚类结果为：

表2示例二聚类结果

聚类1 元素1、元素5 聚类2 元素2、元素4 聚类3 元素3

通过这种编码方式，可以表示出DSM中元素所有的分类方式，并且 可以将聚类数量作为变量随遗传算法迭代，自动找出最优的聚类数量和各 个聚类所包含的元素。

步骤3.2：双段染色体遗传操作

由于前后两段染色体所代表的意义不同，且第一段染色体的编码方式 为整数编码，第二段染色体的编码方式为0-1编码，因此在进行遗传操作 时，前后两段染色体相互独立，需分别对两段基因进行判断是否进行交叉 或变异操作。

a)选择

进行选择操作前需确定各个染色体的适应度。由于DSM的联系信息 流量总和越小，其聚类结果越好，因此取DSM联系信息流量总和的倒数 作为染色体的适应度。

选择轮盘赌作为选择方式，每个染色体被选择的概率为其适应度与全 体染色体适应度总和的比值。

b)交叉

在双段染色体编码中，由于第一段染色体为整数序列，且各个基因间 互不相同，因此采用部分映射交叉算子作为交叉方式，该方法通过在两条 染色体的基因间建立映射关系对基因序列进行调整，避免出现染色体内部 出现基因冲突的情况，具体操作方法如下：

1)在一条染色体中选择一段基因作为交叉段，同样的，将另一条染色 体中相同位置的基因也选择为交叉段并前者对应，如下所示：

parents1：(c₁c₂c₃|c₄c₅c₆|c₇c₈)

parents2：(c₃c₇c₅|c₁c₆c₈|c₂c₄)

其中第一条父代染色体中的c₄、c₅、c₆、第二条父代染色体中的c₁、c₆、c₈为 交叉段。

2)将交叉段中相同位置的基因一一建立映射关系，即之后将两条染色体的交叉段基因交叉并分别复制到子 代染色体中，即：

offspring1：(xxx|c₁c₆c₈|xx)

offspring2：(xxx|c₄c₅c₆|xx)

3)在剩余基因中，从第一条父代染色体的第一位基因开始，判断其是 否与交叉段基因冲突，即该基因是否与交叉段中某一基因相同。若与交叉 段基因均不相同，则将其直接复制到子代染色体中相同的基因位，并继续 对下一个位置的基因进行判断；若与交叉段基因存在冲突，则进入第四步。

4)若某一位基因与交叉段基因相同，则按照第二步中建立的映射关系， 将该基因转换为与之对应的基因，并再次判断，若不再与交叉段基因冲突， 则将其复制到子代染色体中相同的基因位上，若仍与交叉段基因冲突，则 继续按照映射关系转换，直至与交叉段基因不再冲突。

5)重复第三步和第四步的操作，直至确定两条染色体上所有基因位的 基因，并将其作为子代染色体。按照上述操作，对初始两条染色体进行交 叉后得到子代染色体为:

offspring1：(c₄c₂c₃|c₁c₆c₈|c₇c₅)

offspring2：(c₃c₇c₈|c₄c₅c₆|c₂c₁)

同样，若定义父代染色体为：

parents1：(157|623|48)

parents2：(423|186|75)

经过部分映射交叉算子运算后，得到的子代染色体为：

offspring1：(657|186|42)

offspring2：(481|623|75)

第二段染色体为0-1编码序列，采用典型的交叉算子，其操作方法为 在染色体中选择一段基因作为交叉段，将其与另一染色体相同位置的基因 交换。

c)变异

前后两段编码均采用交换变异方式，其操作方法为在染色体中随机选 择一位基因，并将其随机插入到另一个位置中，同时，处于其原始位置和 新位置之间的基因共同向后移动一位。

步骤3.3：遗传整数规划

为提高遗传算法的全局搜索能力，本发明中提出了一种基于罚函数思 想的排挤小生境方法，具体的实现方法为：将每一代个体都保留一半，与 下一代进行比较。比较时，分别计算各个个体间的距离，并将其看做是个 体间的相似程度。考虑到该问题染色体的编码特性，采用Hamming距离表 示个体间的距离，在两条编码相同位置上，若携带的基因不同，Hamming 距离则加1。若Hamming距离小于染色体编码长度的一半，则看做两条个 体过于相似，二者中目标函数值较大的一个个体需将其函数值乘以一个较 大的罚系数，以此类推，最后将函数值最优的结果保留下来，形成新的种 群，继续迭代。为保证前后两段染色体均保持多样性，对前后两段染色体 分别进行判断，在两条染色体中，只要有一段染色体过于相似，则看做两 条染色体整体过于相似。

遗传整数规划方法流程为：

1)应用双段染色体编码方式，生成初始种群；

2)保留种群数量一半的个体，用于与后代进行比较；

3)对种群分别进行选择，交叉，变异操作，得到下一代种群；

4)将之前保留的个体与下一代种群合并，两两进行比较，对其中目标 函数值较大的个体乘以罚系数。

5)将处理后的个体按照目标函数值从小到大排列，选出其中最小的个 体作为新的种群继续迭代，直至达到最大迭代次数。

步骤4：基于第一层重构所得到的聚类结果，进行第二层重构。在第 二层重构中，需对第一层重构所得到的每个聚类进行进一步的重构，第二 层重构所用的算法与第一层重构相同。若第一层重构得到的某一聚类非最 优聚类，则第二层重构能够将其进一步分解为更优的聚类；第一层重构得 到的某一聚类已无法再进行分解，则该聚类内的联系信息流量不变，不会 影响DSM的联系信息流量总和。考虑到每个聚类中元素个数较少，第二 层重构中算法的全局收敛性以及求解效率相较于第一层重构都会大幅提 升，因此在进行第二层重构时只需令算法迭代很少的代数即可保证找到最 优聚类方案。对每个聚类都进行检查之后，将每个聚类所优化的结果相加， 则得到最优的联系信息流量总和以及最优的重构方案。

有益效果

本发明实现了对DSM中元素序列与聚类方法的同时编码，大大减少 了DSM聚类重构过程中所需的人为操作，避免了传统聚类重构过度依赖 人工经验、可靠性和鲁棒性差的缺点，使设计人员可以快速找到最优DSM 聚类方案，降低复杂系统内部的耦合程度，提高设计效率。

附图说明

图(1)基于两层遗传整数规划的复杂系统设计结构矩阵重构方法流程 图

图(2)为初始DSM示意图；

图(3)为遗传整数规划方法流程图；

图(4)为部分映射交叉算子示意图；

图(5)为典型交叉算子示意图；

图(6)为典型变异算子示意图；

图(7)为10次优化结果箱线图；

图(8)为优化后的设计结构矩阵聚类结果示意图。

具体实施方式

本发明提出一种基于两层遗传整数规划的复杂系统设计结构矩阵重构 方法，该方法可在优化迭代过程中自动寻找最优的聚类方案，在处理涉及 学科较多的设计结构矩阵时可大幅减少优化过程中的人为操作，提高整体 设计效率，缩短设计周期，减少设计成本。

为了更好的说明本发明的目的与优点，下面通过引文中的设计矩阵重 构算例为设计实例，结合附图与表格对本发明做进一步说明，并对本发明 的综合性能进行验证分析。

以某复杂工程系统(涉及17个学科)的学科数据关系DSM重构为例， 详细说明本发明的具体实施步骤，并检验本发明的有效性。

该设计实例的实施步骤如图(1)所示。

具体实施步骤为：

步骤1：以数值表示DSM中各个元素的耦合关系，并以DSM的联系 信息流量作为输出，初始化DSM聚类分析模型。本实例涉及17个学科， 初始DSM如图(2)所示。若某一学科与超过一半的学科存在数据传递关 系，即与超过9个学科存在数据传递关系，即将其归为bus聚类中。

步骤2：以DSM的联系信息流量作为目标函数，建立优化模型：

findX＝[x₁，x₂...x₁₇]

l₁，l₂...l₁₆∈{0，1}

minf(X，l₁，l₂...l₁₆)

其中，X代表17个学科的排列顺序，用于表示DSM的聚类方式， 二者共同决定了DSM的聚类方案，具体编码方式见步骤3。f(X)为当前聚 类方案下DSM的联系信息流量总和，优化目的是使DSM的联系信息流量 总和最小。

步骤3：采用遗传整数规划方法进行第一层重构，流程如细节如下：

遗传整数规划方法的流程如图(3)所示。

在第一层重构中，遗传算法的各项参数设置如下：

表3第一层重构各项遗传参数设置

种群规模 2000 前段交叉概率 0.9 后段交叉概率 0.9 前段变异概率 0.4 后段变异概率 0.4 最大遗传代数 2000

由于DSM中共包含17个学科，因此染色体编码为：

其中，第一段染色体中的17位基因决定了17个学科的排列顺序，第 二段染色体中的16位基因决定了17个学科的聚类方式，二者共同构成双 段式染色体，决定了DSM的聚类方式。

第一段染色体交叉时采用部分映射交叉算子，流程如图(4)所示，第 二段染色体交叉时采用典型交叉算子，流程如图(5)所示。第一段染色体 和第二段染色体变异时均采用典型变异算子，流程如图(6)所示。

此外，为了使遗传算法具有更好的全局搜索能力，在遗传算法中加入 一种基于罚函数思想的排挤小生境方法。具体操作为：在进行每代遗传操 作前，保留种群数量一半的即1000个个体，在经过交叉、变异操作之后， 将下一代种群与之前保留的1000个个体合并，总共3000个个体两两进行 比较。若二者间的Hamming距离小于编码长度的一半，则认为二者距离过 近，需要选择其中目标函数值较大的个体并将其目标函数值乘20。同样由 于前后两段编码具有不同意义，因此需要对两段编码分别进行判断。若前 后两段编码中存在一段不满足距离要求，即前17个基因有10个以上相同 或后16个基因具有9个以上相同，则看做两条基因距离过近，其中目标函 数值较大的一个个体需将其目标函数值乘20。以此方式对全部个体进行处 理后，在总共3000个个体中选择目标函数值最小的2000个作为新的个体， 继续迭代，直至达到最大迭代次数。

步骤4：基于第一层重构所得到的聚类结果，对每个聚类进行第二层 重构。

在第二层重构中，选择与第一层重构相同的算法，遗传算法的各项参 数设置如下：

表4第二层重构各项遗传参数设置

种群规模 2000 前段交叉概率 0.9 后段交叉概率 0.9 前段变异概率 0.4 后段变异概率 0.4 最大遗传代数 10

由于第二层重构只是对每个聚类进行重构，因此问题维度相较于第一 层重构大大缩小，最优解的求解难度也大大降低，因此只需迭代10次即可 寻找到局部的最优方案。在求解得到每个聚类的最优方案后，将每个聚类 的联系信息流量相加，即得到DSM的联系信息流量总和。

使用本发明中的遗传整数规划方法与Matlab自带的整数规划遗传算法 分别对该问题重复优化10次，优化结果对比如图(7)所示。算例DSM联 系信息流量的理论最优解为2752，从图中可以看出，两层遗传整数规划每 次均能获取理论最优DSM，具有良好的全局收敛性，并且具有良好的鲁棒 性；而Matlab中的整数规划遗传算法则无法收敛到全局最优解，而且求解 结果具有较大的不确定性。重构后的DSM如图(8)所示，从图中可以看 出，重构后的DSM中耦合关系紧密的元素被聚集到同一群组中，不同群 组之间耦合关系减弱，从而实现了系统的解耦，有效降低了系统复杂程度。 上述结果表明：本发明所提出的基于两层遗传整数规划的DSM重构方法 具有更高的全局收敛性与鲁棒性，能够有效地降低复杂工程系统学科间的 耦合强度，提高多学科耦合分析的效率。

根据DSM聚类重构实例分析可见，本发明实现了预期的发明目的， 能够在对DSM序列进行重构的同时，决定其聚类数量和各个聚类中所包 含的元素，减少了重构过程中的人为操作，尤其在处理涉及大量学科的 DSM重构问题时，可以降低设计流程中的反馈耦合状态变量的规模或者反 馈路径的长度，从而降低复杂系统内部耦合程度，减少多学科耦合分析迭 代次数，提高设计效率。