0 引言
产品装配序列规划作为产品生命周期的重要一环，在产品设计开发过程中占有很重要的地位，因为产品设计总费用40%～60%被花费在装配劳动中，如何在给定产品在设计方案的条件下，寻找满足几何约束以及其它约束条件（工艺、装配成本等）的合理可行的装配序列一直是装配工艺师所面临的富有挑战性的工作。好的装配序列规划已经被视为减小装配难度、减少装配工具以及缩短装配时间的实用方法。装配序列规划问题的本质是一个NP组合优化难题，传统的装配序列规划的方式有两种：一是基于装配工程师的知识以及经验，二是图搜索算法。方法一受设计者的知识局限性和主观性影响较大，尤其是对于复杂零件的装配工艺，设计出的装配序列常常不是最优的，甚至是不可行的。方法二的局限性在于当产品零件数目较多时，将会出现装配序列组合爆炸的问题。20世纪90年代以来，人工智能被运用到组合优化求解问题中，并取得了一些成就。包括模拟退火算法、人工神经网络、蚁群算法、遗传算法及其相关混合算法。因遗传算法具有搜索速度快、算法简单，无需遍历整个解空间就能找到一个最优或次最优解，能有效解决组合优化中得组合爆炸问题，修改染色体的编码方式和适应度函数可解决不同的优化问题等特点，遗传算法被广泛的运用到装配序列规划问题的求解。
1 零件可行装配方向推理及装配基准件选择
1.1 遗传算法的相关研究及改进
Bonnevil等首先将遗传算法引入装配规划设计中，但他们的算法效果受初始迭代值的影响，而且要求初始序列都是有效的；Romeo M Marian等在建立关联矩阵和优先关系矩阵的基础上，通过向导搜索算法生成可行的装配序列后，再用遗传算法对可行的装配序列进行优化，该方法也要求初始序列都是有效的；杨鹏等改进了传统的基因算法，通过交叉和多层次变异来实现基于基因组编码表示的多信息装配序列的并行优化；周开俊等在杨鹏的研究基础上考虑子装配体稳定性的目标函数，采用带记忆的遗传算法进行装配序列规划；刘诚等将遗传学原理的基因修复技术引入用于求解装配序列规划问题的遗传算法，利用基因“修复”操作，将子代个体中违反先序约束的基因“修复”为有效基因，从而保证了整个种群的基因多样性，避免了进化过早地收敛于局部最优解。基于几何干涉矩阵的基础推导并优化装配序列，但是忽视了装配过程中装配基准和零件装配优先关系。
有鉴于此，采用改进的遗传算法，考虑装配基础件对产品的装配序列进行规划研究。通过该算法，获得一条满足几何约束、符合实际装配过程的高效率产品装配序列，用以指导产品的实际装配。
1.2 零件装配方向推理和可行性判断
在笛卡儿直角坐系下，零部件的装配方向采用该坐标系的坐标轴方向，一个装配序列的几何可行性是指：至少存在一个坐标轴方向使得将某一零部件装配到位时，而不与其他已装配好的零部件发生干涉。为评价装配序列的几何可行性，采用干涉矩阵I描述装配过程中零部件间的几何优先关系。
假定有n个零件参与装配，那么干涉矩阵是一个n行、3×n列的矩阵，3代表零件在+X、+Y、+Z的3个装配方向。其元素Iijx表示了零件j沿+X方向装配时与零件i的干涉情况，判定规则如下：如果零件j沿+X方向装配到位与零件i发生干涉，则Iijx=1；反之则Iijx=0。零件j沿-X方向装配与零件i干涉的情况即Iij-x，与零件i沿+X方向装配与零件j干涉的情况相同，由元素Iijx表示，规定Ii=0。同理，可以确定Iijy和Iijz的值。
现设{P1，P2，…Pm}为零件Pi装配前已经装配完的零件序列，则零件Pi的可行装配方向可由式(1)～式(6)判定。
其中，I[i][j]对应干涉矩阵中的元素，U表示矩阵元素求或运算，I的维数取决于装配的维数，二维的情况取2，三维的情况取3。对于序列{P1，P2，…，Pm，Pi}是否为几何可行装配序列取决于式(1)～式(6)的结果，当式(1)～式(6)中至少存在一个为零时，例如式(1)的结果为0，则说明Pi可从+X方向装配到位而不与P1，P2，…，Pm发生干涉，反之，若式(1)～式(6)的结果全不为零，则P1，P2，…，Pm，Pi是不可装配的。
1.3 装配基准件的选择
1.1节从几何角度上推理了零件的装配方向，其并不涉及装配初始零部件。现实产品装配过程中，通常会装配一个零件固定不动，其余零部件均以该零件为装配基准进行装配。一个装配体包含n个零件，所有可能的装配序列为，n!个，当指定了基准件后可能的装配序列为(n-1)!，搜索空间变为以前的1／n。可见基准件最先装配作为一条启发式规则可以在很大程度上减小搜索空间，提高装配序列生成的效率。基准件的选取对装配操作的难度、装配夹具的设计等产生重大的影响，基准件的选择一般遵循以下几个原则：与其它零件连接数多；重量大、重心低；体积大；刚性大；一般避免选用易碎的、贵重的零件做基准件，例如传动轴、齿轮等。
2 基于遗传算法的装配序列规划方法
在考虑基础件的情况下，设计了相应的交叉算子、变异算子和适应度函数，对产品的装配序列进行规划，用以获得满足相关约束条件的装配序列。
2.1 编码
采用实数序列的遗传算法编码求解产品装配序列规划问题，染色体的一个基因用以编码一个待装配零部件，每个基因所在染色体的位置代表了相应待装配零部件的在该装配顺序中的位置。群体的初始化、交叉操作及变异操作中各零件的序号仅出现．一次。例如染色体3-1-4-2-6-5-9-8-7，该染色体首先装配的零部件为3，其后，装配零部件1，依此类推。
2.2 交叉算子
采用如下的部分交叉重组方法，具体方式如下。
a.随机在种群中选择2条染色体A，B，随机在染色体中选择一个交配区域。2父染色体及交配区域选定为：
b.将B的交配区域加到A的交叉点后，将A的交配区域加到B的交叉点后得到：
c.在A＇，B＇中依次删除与交配区相同的零部件编码得到最终的2子染色体为：
这种交叉方法在能够确保基准件的位置在染色体的最前端。
2.3 变异算子
每一代种群以机率Pm进行变异，一旦变异操作发生，随机挑选K条染色体进行变异，且当染色体的基因个数为奇数时，从该染色体的第二位基因开始．每相邻2个基因前后交换；当染色体的基因个数为偶数时，从该染色体的第三位基因开始，每相邻2个基因前后交换。通过这样的变异操作不仅最大限度地打破了装配序列的排列顺序，同时能够确保基准件的位置在染色体的最前端。
2.4 适应度函数设计
遗传算法中适应度函数的设计将待求解问题的目标函数与种群的每个个体联系起来，通过将待求解问题的目标函数转化为适应度函数，再通过适应度函数求得个体的适应度，适应度值高的个体遗传到下一代的几率较大，反之，适应度值低的个体遗传到下一代的几率较小。影响装配效率的因素很多，仅从装配方向的改变次数、装配工具的更改次数、子装配的稳定性、基准件的位置四个方面考虑设计适应度函数。
a.装配换向次数C。对某一给定装配序列，由1.1节可以推理零部件的装配方向。当相邻的2个零部件装配方向改变时，序列的装配换向次数加1。该指标反映了装配操作的复杂性信息。
b.装配工具的更换次数To通过判断相邻2个零部件装配时所使用的装配工具是否相同，累加计算出给定装配序列的装配工具改变次数，该指标量化表示了装配序列的聚合性。T越小，装配工具更换的次数越小，装配效率越高。
c.装配体的稳定性。它是指某一装配操作所涉及的2个子装配体在重力和建立装配所需力的作用下，保持各自内部装配关系的能力。定义稳定联接矩阵SN×N，其中矩阵元素Sij表示零部件i与零部件j之间的联接关系，当i与j存在稳定联接关系时Sij=2，当i与j存在接触联接关系时Sij=1，当i与j不存在联接关系时Sij=0。稳定联接指有强制约束零件之间相互移动的联接，包括螺纹联接、轴与孔的过盈联接、O型圈联接和卡簧联接。则一个装配序列的装配稳定性就可以用1×（N-1）的向量K={k2，k3，…，kn}，其值S如式(7)所示。装配体的稳定性直接影响到装配操作的可靠性、夹具和工具的复杂性。
式中，n为装配零件总数；S值越大装配序列的稳定性越好，0≤S≤2n-2。
d.基准件的位置。如1.3节所述，基准件的装配应该在第一位，在初始种群中存在满足几何约束的装配序列，但是居首的零件并非装配基准件，则需要对装配基准件居首的可行装配序列与装配基准件非居首的可行装配序列予以区分。通过区分，一方面能保持种群的多样性；另一方面对装配基准件居首的可行装配序列的适应度值予以加权，提高该序列的适应度值，保证其在种群中的竞争性。
综上所述，适应度函数设计如下：
式中，S为种群的各装配序列，当装配序列满足几何约束且基础件位置位于序列非首位时取式(8)第1式，当装配序列满足几何约束且基础件位置位于序列首位时取式(8)第2式，当装配序列不满足几何约束式(8)第3式；F(S)为装配序列的适应度函值；ω1，ω2，ω3，ω4为权重系数；P为惩罚系数，根据经验，取ω4=0.8，ω1+ω2+ω3=1，取P=2。
3 遗传算法执行步骤
按照遗传算法的一般思路，结合装配序列规划应用的实际情况，在考虑基准件的基础上，该算法步骤如下：
步骤1。设定初始种群大小pop、交叉概率Pc、基因组变异概率Pm。
步骤2。确定初始种群并将其作为最初的父代种群；先随机生成初始种群，然后，在DELMIA软件中通过虚拟拆卸的方式获得一些装配序列，最后，将通过虚拟拆卸的方式获得的这些装配序列随机替换初始种群的装配序列，将替换后的种群作为最初的父代种群。
步骤3。根据事先建立的装配体干涉矩阵，先从几何约束角度判断初始种群中个体的可行性，再对几何约束可行的个体判断居首位置的零件判断是否为基准件，最后根据式(8)分别计算初始种群个体的适应度值。
步骤4。确定个体选择算法，选择轮赌盘选择方法。
步骤5。当优化结果不满足终止条件时。
a.从群体中随机两两选择出不同个体作为亲本，用交叉概率来确定染色体是否进行交叉操作。
b.用变异概率来确定染色体是否进行了交叉操作。
c.用交叉和变异产生与父代相同个数的子代。
d.同步骤3判断新个体的可行性，计算新个体的适应值。
e.通过选轮赌盘选择方法得到pop个新的个体，并用这些新的个体更新原始种群。
步骤6。当迭代次数达到预先设定的某值时，输出适应度值最高的个体，即为优化的装配序列。算法流程图如图1所示。
图1 算法流程
4 实例验证
为验证算法的有效性，采用Matlab编程软件验证分析装配基准件的改进遗传装配序列规划算法，并以如图2所示的某链轮为例进行了装配仿真验证，出于验证过程的简便化目的，对链轮做了以下简化：①由于链轮的对称结构，故只考虑了链轮一侧的装配，如图3所示；②规划过程中未出现子装配体的装配过程；③螺栓一般只考虑一组。初始种群中的个体均以随机的方式产生，并加入由DELMIA软件虚拟拆卸得到的可行装配序列，用以改善装配序列种群的组成成份。在程序运行时，初始种群的规模pop=50，迭代条件设定为gmax=50，交叉概率和变异概率(Pc，Pm)分别取0.8，0.1。最终规划出的链轮装配序列如表1所示，图4为pop，Pc，Pm分别取50，0.8，0.1时各代种群的平均适应度函数值图，该序列的适应度函数值是0.1866。
图2 链轮
图3 链轮左侧爆炸图
表1 装配序列规划结果
图4 种群各代平均适应度值
5 结束语
在考虑装配基准件的基础上，设计和改进了规划装配序列遗传算法，通过加入基础件后的改进算法，获得了更贴近实际装配过程的产品装配序列。该算法对初始装配序列无特殊要求，初始种群加入由DELMIA软件虚拟拆卸得到的可行装配序列，由于这些装配序列带有经验知识成份，其能有效地改善装配序列种群的组成成份，加快算法向最优解或近优解的收敛速度。通过实例证明，由该方法快速搜索到最优或近优装配序列，能够用于指导产品实际装配过程。
核心关注：拓步ERP系统平台是覆盖了众多的业务领域、行业应用，蕴涵了丰富的ERP管理思想，集成了ERP软件业务管理理念，功能涉及供应链、成本、制造、CRM、HR等众多业务领域的管理，全面涵盖了企业关注ERP管理系统的核心领域，是众多中小企业信息化建设首选的ERP管理软件信赖品牌。
转载请注明出处：拓步ERP资讯网http://www.toberp.com/
本文标题：基于遗传算法的产品装配序列规划研究
相关文章
