基于自适应遗传算法的船舶分段装配序列优化研究

黄晓雪 程相茹

（渤海船舶职业学院 船舶工程系 葫芦岛125105 ）

引 言

船舶设计建造过程是一个复杂而庞大的系统工程，纯依靠工程人员知识经验安排和编制生产计划的方式已不能满足现代造船模式的生产要求，更不能达到未来“模块化建造”的造船模式提出的高标准。因此，分段装配序列优化的研究对于指导实际生产装配具有现实意义。

装配序列规划主要是解决零部件装配顺序的问题，作为一个复杂的组合优化问题，已有许多学者进行了相关的研究。陈国华［1］、王春雷［2］在其各自的文献中，提出了利用装配体在给定方向上的干涉矩阵生成其装配序列的方式，是最典型的基于优先关系的推理方式之一。西北工业大学白芳妮从图分解的角度研究了装配序列生成算法；方建新［3］运用蚁群算法求解装配序列，林喜波［4］将遗传算法运用于海尔洗衣机生产线的工序优化，王孝义［5］将模拟退火算法运用于装配序列生成等，都是对运用启发式算法求解装配序列规划问题的研究和探索。

通过分析我们发现：基于优先关系和图论的方法，其可行解的搜索空间和评价规模巨大，搜索效率低，对于结构复杂的大型装配体，求解效果差强人意；基于启发式算法的求解方法，由于其不要求问题模型的精确数学描述，并且全局搜索能力强，能有效缩小搜索和评价空间；因此得到越来越多的装配规划研究工作者的青睐。

本文根据船舶分段装配序列优化问题的特点，将装配序列的评价标准融入到目标函数中，采用自适应遗传算法进行装配序列优化并进行计算。并在此基础上进行装配序列优化系统的总体设计，将优化后的装配序列进行装配流程可视化，验证了算法的有效性。

1 数学模型及目标函数的建立

装配序列的优劣有着许多不同的评价标准，对于装配成本存在影响的因素也多种多样。在分段建造过程中，建造场地的成本、使用材料的费用、焊接形式的效率、吊装工具的利用率等因素都对船舶的建造成本产生很大影响。在当今现代化造船“壳舾涂”一体化理念的引导下，船舶建造周期的缩短显得尤为重要。由于“壳舾涂”一体化对于船舶建造周期的影响难以进行量化，本文主要考虑零件装配对整个建造流程的影响。根据影响装配进行的工艺因素以及所研究问题具备的特点，总结了在装配序列评价过程相对比较容易量化的评价准则，建立了包括连接关系约束条件、干涉关系评价函数、重定向评价函数、吊装工具评价函数、装配效率评价函数的装配序列优化目标函数体系。

1.1 船舶分段装配几何约束分析

对于一个船舶分段装配序列在对其进行优化之前，首先需要考虑其装配序列的几何可行性，所以首先需要建立分段的连接矩阵以及干涉矩阵。

1.1.1 分段装配组立连接关系

每一个组立必须与其他组立相连接，才能够成装配关系，所以每一个待装配组立进行装配之前都要进行连接关系判断，得出组立的连接关系矩阵。式（1）为分段装配连接关系矩阵，其中Cij表示第i个组立与第j个组立之间是否存在接触关系，若存在接触关系，Cij值为1；反之，Cij的取值为0。

1.1.2 装配干涉矩阵分析

仅仅得到待装配组立之间的连接关系是不够的，还要对其进行干涉分析。对于一个可行的装配序列，不仅仅是在装配完成时装配组立之间不存在干涉现象，而且装配组立在向既定位置运动时，也不可以与已装配好或待装配的其他组立以及装配工具之间发生干涉现象［6］。

所谓干涉矩阵是指任意两个装配零件之间是否存在干涉关系的判断矩阵，假设整个装配体共存在n个零件，则在判断待装配零件与这n个零件间是否存在干涉关系后可形成一个1×n的干涉矩阵，当每个零件都进行干涉判断后则可构成一个n×n的干涉矩阵。这个干涉矩阵需要包含（+X，+Y，+Z，-X，-Y，-Z）六个方向的干涉关系，而在实际装配过程中，组立i与组立j沿+X方向的干涉关系与组立j相对于组立i沿-X方向的干涉关系是相同的，如果判断（+X，+Y，+Z，-X，-Y，-Z）六个方向的干涉关系，会造成干涉关系的冗余，会降低装配序列优化的效率，所以只需判断沿+X方向上的干涉关系即可得到所有零件在±X方向上的干涉关系，±Y，±Z同理。则干涉矩阵可以用式（3）表示：

1.1.3 装配序列可行性分析

已知一装配序列为A=｛A1，A2，L，An｝，设待装配组立为Ai，并且在Ai之前已经有m个组立装配完成，当组立之间存在连接关系且组立在装配过程中不存在干涉关系，则装配序列可行。

（1）连接关系可行性分析

每个待装配组立在装配之前都需要判断，如果存在与其相连接的组立，装配序列才是可行的；否则不可行。第一个装配的组立不需要判断其连接关系，因为它是整个分段装配的基准组立。待装配组立 的装配连接关系可以用式（4）来表达：

（2）干涉关系可行性分析

对于一个既存的装配序列，可以根据其干涉矩阵判断其可装配性。在此，我们定义一个数组如下：

对于待装配组立Ai可以判断它与在它之前装配的组立之间是否存在干涉关系，若存在干涉关系则相应的的值为1，则的值为1，那么Ai不可以沿+dk方向装配。对于待装配组立而言，的值或者-的值必须有一个为0，否则待装配组立的装配不可行。

1.2 分段装配工艺约束分析

装配序列的评价标准虽然有很多，但是评价准则难以进行量化。以下为根据研究问题所具备的特点概括出来的相对比较容易量化的关于工艺约束方面的评价准则。

1.2.1 重定向次数

对于已知的装配序列A=｛A1，A2，L，An｝，将零件的装配方向表示为则判断相邻的零件的装配方向是否相同，若装配方向相同，即则装配方向没有发生改变；若零件装配方向不同，即则装配方向发生了改变，需要进行重定向。

1.2.2 吊装工具改变次数

组立装配时需要使用起重机进行吊装，对于不同重量的组立需要不同起重能力的起重机，设有四种起重能力的起重机ma，mb，mc，md，且ma＜mb＜mc＜md，存在某一组立重量为mi，则此组立所使用的吊装工具Ti根据式（7）来判断：

对于已知装配序列A=｛A1，A2，L，An｝，根据组立的质量进行选择起重机，判断相邻近的两个零件在装配过程中的吊装工具是否相同，若吊装工具相同，即，则吊装工具没发生改变；若吊装工具不同，即则吊装工具发生了改变，需要更换吊装工具，则增加了装配成本。

1.2.3 装配效率

在船舶实际分段建造中，根据零件所处的空间位置的不同装配效率各不相同。相比较而言由于其所处空间位置不同，由上而下的装配比水平的装配效率高，自下至上的装配效率会更低，所以更多采用由上而下的装配方式就会大大提高分段的装配效率。对于已知的装配序列A=｛A1，A2，L，An｝，设nd为由上而下进行的装配次数，nh为水平进行的装配次数，nu为自下至上进行的装配次数，λd、λh、λu分别为沿其方向的效率且有λd＞λh＞λu，则有nd越大越好。

1.3 分段装配序列优化目标体系

根据影响分段装配的各种因素，对船舶分段装配的几何约束和工艺约束分别进行分析，可以建立分段装配序列优化的目标体系，为实现船舶分段装配序列优化提供基础。

1.3.1 连接关系约束条件

1.3.2 干涉关系评价函数

根据上文所建立的装配干涉矩阵可以判断一个已知的装配序列A=｛A1，A2，L，An｝在装配过程中存在的干涉次数In。第一个组立不需要考虑其干涉性，从第二个组立开始判断与前面的组立干涉性，若沿dk方向装配，k表示组立i之前进行装配的任意一个组立，表示第i个进行装配的组立与之前任意一个装配组立的干涉关系。

式中：Iikx，Iiky，Iikz分别表示在装配序列中第i个进行装配的组立与在它之前进行装配的组立在x，y，z三个方向上的干涉值。则第i个进行装配的组立的干涉关系如式（10）所示：

那么，整个装配序列的干涉次数In可作如下表示：

1.3.3 重定向评价函数

重定向次数作为装配序列评价的一项重要指标，直接影响着装配序列的优劣。对于一个已知的装配序列A=｛A1，A2，L，An｝可以根据式（12）判断其重定向次数。

式中：δ代表装配序列中重定向的次数，式（13）中δi代表每一个待装配的组立与在它之前装配组立是否发生重定向，若发生重定向则计数1，若不发生重定向则计数0。

1.3.4 吊装工具评价函数

在船舶建造过程中，恰当使用和更换吊装工具能很大程度上的提分段的装配效率。对于一个已知的装配序列A=｛A1，A2，L，An｝，可以根据式（14）判断其吊装工具改变的次数。

式中：e代表装配序列中吊装工具改变的次数，式（15）中ei代表每一个待装配的组立与在它之前装配组立的吊装工具是否改变，若吊装工具改变则计数1，若不发生改变则计数0。

1.3.5 装配效率评价函数

不同的装配方式下分段的装配效率不同，尽量采用由上而下的装配方式可以提高装配效率。对于一已知的装配序列A=｛A1，A2，L，An｝，可以根据式（16）得到该序列的装配效率评价函数。式中λd、λh、λu及nd、nh、nu所代表的意义上文已经交代，λd、λh、λu分别取值为90%、60%、30%，使用n代表各种装配方式的次数之和，其中n=nd+nh+nu，则效率P的最大值为n×λd，P的表达式如式（16）所示：

2 问题模型求解

2.1 分段装配序列优化数学模型的建立

问题模型是一个多目标优化问题，处理这类问题通常是用加权法［7］将多目标转化为单目标优化进行处理。然而各评价函数的重要性并不相同，针对一个评价函数比较优秀的装配序列，对于其他的评价函数可能很差，而且仅依靠主观的判断也难以说明其合理性，所以必须综合考虑各个指标对于整个系统的重要性来科学地确定权重。层次分析法自问世以来，以其思想清晰、能处理定性信息和适用于多指标分析问题等优点，获得多个领域的广泛应用，并在实践应用中证实了其有效性和先进性。层次分析法的具体步骤包括确定所要解决的问题、建立问题的递阶层次结构、建立问题的判断矩阵、层次关系单排序和层次关系总排序五个步骤。

为了确定目标函数体系中各个评价函数的权重首先建立层次结构，设定研究问题的目标层为权重的确定，根据重定向次数、装配工具改变次数以及装配效率对于目标评价系统的重要性不同来确定其所占的权重。

首先将准则层的三个评价因素按照表1的重要性分级进行对比，根据某船厂实际情况，并对现场施工人员以及专家进行调查，据此建立判断矩阵A如式（17）所示，并将矩阵A列向量归一化，并依此求出特征向量λ=3.109。则该特征值对应的归一化特征向量为w=（0.156，0.224，0.62）T，λmax=3.109。

进行一致性检测时，若通过了检测，即为权向量；若一致性检测没有通过，则需要再一次构造对比矩阵，并再次进行一致性检测直至检测通过。根据表2随机一致性指标得出RI= 0.58，根据式（18）求得CI的值为0.054，又根据式（19）得出一致性指标CR= 0.094 2 ，小于0.1，表明通过了一致性检测。

表1 重要性比较分级

表2 随机一致性指标

重定向次数、吊装工具改变次数、装配效率的权重依次为0.156，0.224，0.62。对于一个装配序列，如果待装配零件与已装配零件之间存在干涉关系，则装配序列不可行；那么，即使其他三个评价函数再优异装配序列评价也失去了进行优化的意义，对于不满足干涉条件的装配序列可以采取两种方法进行改善：

（1）将不可行的装配序列进行修复或者丢弃；

（2）将干涉条件作为惩罚项加入到目标函数中。其中第一种方法进行丢弃不可行基因时可能会使可行基因缺乏从而导致算法收敛速度变慢，所以本文将干涉条件作为目标函数的惩罚项来进行优化。

根据上文所提出的几何约束条件和工艺约束条件可以得出船舶分段装配序列优化的数学模型如式（20）所示：

其中

该问题模型是一个最小化问题，f1、f2、f3、f4分别代表重定向次数、吊装工具改变次数、装配效率、干涉次数，它们都属于越小越好的子目标项。与其它三个子目标不同，f4是对于装配序列干涉情况的一种衡量，而可行的装配序列是不允许存在干涉情况的。因此，本文在处理干涉项f4时，对其赋予一个较大的权重以产生惩罚效果，使得整个优化搜索过程受干涉情况影响较大，引导搜索过程向着干涉量迅速减小的方向进行。基于以上分析，对式（20）中权重项α1、α2、α3、α4取值依次为 0.163 8、0.297 3、0.539 0、5。

2.2 基于改进的自适应遗传算法的分段装配序列算法设计

2.2.1 算法参数及操作设计

（1）基因型编码方案及种群初始化

要解决船舶分段装配序列优化问题需要有以下几个基础信息，即待装配组立编号，装配所需的吊装工具，待装配组立的装配方向，所以染色体需要包含以上三种基础信息，则组立基因型可通过下面的编码方式来表达：

采用十进制编码方案，用A1、A2、A3…An来表示所有组立的编号；用1、2、3分别表示组立沿x，y，z三个方向上的正方向平动；用1、2、3、4分别来表示不同组立的吊装工具T1、T2、T3、T4。

根据编码方案可随机产生初始种群，但是所产生的初始种群未必存在连接关系，所以本文采用串行进度方案生成初始种群，采用这种方法可以生成满足连接关系约束条件的装配序列。

本文将所研究问题设置为三个数组，分别为已装配完成的组立数组Di，装配虽未完成中但可以作为下一个装配组立的数组Yi，装配既未完成又不可以作为下一个装配组立的数组Ni。由于船体组立重量大，吊装翻身代价高，小组立装配过程中不便于频繁将中组立翻身，所以一般选取重量大、接触组立多的构件为装配基准件，本文选择编号为1的组立为基准件进行装配。则组立1进入已装配完成的组立数组Di，根据连接关系矩阵将与组立1存在连接关系的组立进入到装配虽未完成中但可以作为下一个装配组立的数组Yi，其它组立进入到装配既未完成又不可以作为下一个装配组立的数组Ni中。采用随机函数random选取数组Yi中任意一个组立进入到已装配完成的组立数组Di中，接着重复上述过程，直至数组Yi和数组Ni中的组立为空，则随机生成了即完整又满足连接关系约束条件的初始种群。

（2）适应度函数的选取

由于采用轮盘赌的选择方式，所以需要满足适应度函数非负数的要求，且适应度值越大的个体对于目标函数的搜索能力越强，并且本文所解决问题为目标函数最小化的问题，所以将装配序列优化问题的适应度函数设计如 （22）所示：

（3）选择操作

对于一个已知种群，适应度函数值较大的个体被选为父代遗传给后代的概率比较大，本文采用轮盘赌方法这种常用的选择方法来进行选择操作。首先根据蒙特卡罗法计算出个体被选择的概率，即对于某一个体的适应度值为fi，则其被选作父代遗传给后代的概率为Pi，然后分别计算出每个个体的累计概率，随机产生一个0到1 区间的数，如果此数介于之间时，则此个体被选择为父代，否则，未被选中。其中概率为Pi的表达式如下：

（4）交叉操作

采用单点交叉法进行算法的交叉操作，已知两个即将进行交叉的个体Pi和Pj，生成一个范围为［1，n-1］的随机数，选择此点作为发生交叉操作的临界点，将Pi中此随机数之前的基因保留，将Pj中此随机数之后的基因补齐至Pi中，得到子代个体Ci，同理可求得子代个体Cj。

（5）变异操作

船舶分段装配序列优化问题模型的变量主要是指组立装配的顺序、装配方向、装配工具，那么变异也主要是发生在这几个方面，下面具体介绍变异的实现方式：

首先，装配顺序的变异方式。随机产生两个不同的在［1，n］之间的数字，将编号为这两个数字的组立的装配顺序互换。

其次，装配方向的变异方式。随机产生不同于原始装配方向的数字，然后将这个数字替换原始数字。

最后，吊装工具的变异方式。吊装工具必须满足组立对于吊装能力的要求，所以吊装工具不可发生变异，即根据组立重量来确定吊装工具。

（6）交叉概率和变异概率的自适应调整

交叉概率和变异概率决定了遗传算法的搜索能力，所以选择适宜的Pc和Pm尤为重要。本文借鉴自适应算法的思想，当某一个体适应度处于种群最大适应度值时使其交叉概率和变异概率不为0，提升到Pc2、Pm2，这种方法不但有效的避免了最大适应度个体一直处于停滞状态，而且有效地跳出了局部最优解。交叉概率和变异概率的自适应变化方式如下：

式中：Pc1＞Pc2，Pm1＞Pm2其他字母代表含义与上文基本相同，其中f1表示要交叉的两个个体中较大的适应度值；f′表示要变异个体的适应度值。

式（24）、式（25）中，各个交叉概率和变异概率为Pc1= 0.9，Pc2= 0.6，Pm1= 0.1，Pm2= 0.001。图1可以形象地表达出交叉概率和变异概率的公式：

图1 自适应交叉概率及变异概率

（7）终止准则

终止条件即为当种群进化满足一定条件时，算法结果收敛，种群进化停止，得到结果。根据不同终止条件的分析对比，采用如下终止准则：

① 迭代次数达到预先设定的计算次数；

② 子父代个体多次迭代适应度函数值；

③ 变化不明显终止进化，得出优化结果。

2.2.2 算法求解步骤及流程图

（1）求解步骤

① 初始化n个个体的初始种群并编码，设定包含种群规模、交叉和变异概率、算法最大计算次数等参数，初始化计数器t=0。

③ 根据自适应交叉概率Pc对 进行交叉，得到交叉后的子一代个体

④ 根据自适应变异概率Pm对子一代进行变异，得到变异后的子二代个体

⑤ 终止准则设定。若不满足终止准则，转到第③步；若满足，则输出计算结果，进化终止，得出问题解。

（2）流程图

根据求解问题的步骤，可得到如图2所示具体流程图。

3 实例验证

建立一个完整的装配序列优化体系对于提高装配质量，节约装配成本，缩短装配工时有重要的意义。采用本文算法对某平行中体分段的装配进行研究，以平行中体分段的装配问题为例可以简化分析工作，但本系统同样适用于装配更为复杂的首尾分段，只是首尾分段的干涉矩阵更为复杂，使系统运行的时间增加。用编程工具对船舶分段装配序列优化系统进行实现，验证算法有效性，最后将经优化后的装配序列进行装配流程检验。

3.1 某平行中体分段装配序列的优化

根据在CATIA软件中所建立的平行中体模型确定出所包含的组立总数X，并通过点击导入组立信息按钮可以打开所存储的包含组立重量和组立吊装工具的txt文件。干涉矩阵以及连接矩阵相关信息的导入和添加与其相似。设置算法的相关参数，设定种群大小为100，最大遗传数为100，交叉概率1为0.9，交叉概率2为0.6，变异概率1为0.1，变异概率2为0.001，具体如图3所示。

图2 自适应遗传算法流程图

图3 算法输入界面

利用改进的自适应遗传算法进行编程设计，点击开始计算，程序开始运行，得到如图4的界面，表明已经完成了计算。

图4 完成计算界面

点击查看结果按钮，弹出如图5计算结果。根据图5中适应度进化曲线可以看出目标函数值呈现下降趋势，并最终趋于稳定，并且算法在进化过程中收敛速度较快，在很短的时间内即获得问题的最优解，表明算法性能优越。

图5 装配序列输出界面

3.2 装配流程可视化验证

随着船舶制造业的发展，产品设计过程中的三维仿真技术的地位越来越重要。运用CATIA软件的电子样机装配仿真模块对船舶分段装配过程进行模拟，并进行干涉检查，可以进一步验证经自适应遗传算法优化后的装配序列的合理性和正确性。

3.2.1 装配过程可视化

根据优化出来的分段装配序列进行装配过程的三维动态仿真，利用CATIA软件将整个分段的装配流程进行演示，并记录存储为影片，实现装配流程可视化，具体效果如图6所示。在CATIA软件电子样机装配仿真模块下按照既有的装配序列建立一个装配树结构，将待装配组立插入到既定位置，给出装配过程中的引导路径，设置动作进行的速度和时间并将整个过程记录成Replay的动态记录。

图6 装配过程仿真

3.2.2 装配干涉检查

干涉检查可以实现产品在实际装配进行之前验证装配的可行性、路径的可达性以及设计的合理性，利于用户在实际的生产之前的分析和决策。它具体包括静态干涉检查和动态干涉检查。

（1）静态干涉检查

所谓静态干涉检查是指在装配体静止的情况下，检查零件间是否存在干涉关系，设计是否合理。从静态干涉检查中可以得到装配体的干涉信息，具体包括零件之间的碰撞关系及接触关系。干涉信息可以存储为干涉报告，利于对于装配体信息的分析、修改以及管理。从下页图7可知模型只存在接触干涉这种正常的干涉现象，即模型设计合理。

图7 平行中体静态干涉信息

（2）动态干涉检查

动态干涉检查是指在装配过程中，装配体是否与已经装配好的或者待装配的零件间存在运动干涉。动态干涉检查具体包括产品机构分解、产品布局协调以及干涉检测。通过图8中平行中体分段的装配过程，可以看到本文所生成的装配序列不存在动态干涉。

图8 装配过程中的动态干涉检查

4 结 论

为了解决某典型的平行中体分段装配序列优化问题，本文提出基于自适应遗传算法的船舶分段装配序列优化求解方法。根据其几何模型得出包含干涉关系和连接关系的分段几何约束信息，并据此建立包含干涉关系、重定向次数、吊装工具改变次数、装配效率等评价函数的目标优化体系。随即，分析了遗传算法的基本原理和不足，采用改进的自适应遗传算法进行装配序列优化，并将评价标准作为目标函数来进行优化计算，既降低了问题的繁琐程度，又提高了系统的工作效率。设计并实现了船舶分段装配序列优化问题的总体系统框架及界面功能，得出经优化后的装配序列，并在此基础上进行优化输出结果分析及船舶分段装配流程的可视化仿真，验证了经算法优化后的装配序列的合理性和正确性。

［1］ 陈国华，程本松，杨敏.基于CATIA的机械零件虚拟装配方法［J］.机械研究与应用，2006（3）： 43-45.

［2］ 王春雷，许建新，朱斌.基于三维产品模型的装配顺序规划实现技术研究［J］.机械设计，2009（5）：21-25.

［3］ 方建新.基于蚁群算法的装配序列规划研究［D］.武汉：华中科技大学硕士学位论文，2007：10-15.

［4］ 林喜波.基于遗传算法的装配序列优化［D］.南京：南京理工大学硕士学位论文，2004：7-18.

［5］ 王孝义，张友良，张帆.基于模拟退火算法的装配序列生成与优化［J］.机械科学与技术，2005（5）： 624-627.

［6］ 曾贤虎.虚拟装配理论与方法研究［D］.兰州：兰州理工大学硕士学位论文，2006：9-14.

［7］ 李俊华，陈宾康，应文桦，等.基于功能要求的舰艇指挥舱室优化布置设计数学模型［J］.武汉交通科技大学学报，2000（5）：551-555.