基于蚁群算法的改进装配序列规划方法研究.doc

基于蚁群算法的改进装配序列规划方法研究摘要：机械产品的装配序列直接影响到产品质量和成本，装配序列规划是产品设计的重要内容。为快速实现产品装配序列规划，根据零部件间的装配优先关系，提出了一种改进的装配序列规划方法，并基于蚁群算法予以实现。该方法充分考虑装配过程中的几何约束关系，并引入稳定性、装配经验等因素的影响，以稳定性、装配经验、装配工具和方向的改变次数为影响因子构建优化目标评价体系，使所得解更具有实际指导意义。在求解过程中，根据几何约束关系运用动态候选集合策略限制蚁群的搜索空间，提高了搜索效率；考虑稳定性因素的影响改进了蚁群的状态转移规则，同时引入局部-全局信息素更新规则，保证了蚁群获得最优或近优解。最后，通过实例研究验证了算法的可行性和高效性。关键词：装配序列规划；蚁群算法；稳定性；装配经验；优先关系中图分类号：TH122；TP391 文献标识码：AA Novel Approach for Assembly Sequence Planning Based on Ant Colony AlgorithmAbstract：Assembly sequence affects the quality and cost of mechanical products, and it is important in product design. In order to obtain the assembly sequence rapidly, precedence relations among components were introduced and an improved approach for assembly sequence planning based on ant colony algorithm was proposed. Considering the geometric constraint, components stability and assembling experience in assembly process, the approach can be more practical than before. Dynamical candidates set strategy based on precedence relations was adopted to constrain the searching space of assembly sequence; state transition rule was improved based on assembly stability and local-global updating rule of pheromone were introduced to ensure obtaining the optimal or near-optimal solutions. Finally, the feasibility and calculation efficiency of the proposed approach were verified by a case study.Key words: Assembly sequence planning; Ant colony algorithm; Precedence relation; Stability; Experience11. 引言装配序列规划（Assembly sequence planning，ASP）是先进制造技术中的一个研究热点。产品装配序列规划是指在满足一系列设计约束（如几何特征、配合关系等）的条件下，来确定产品合适的装配顺序。它对产品的装配效率和成本有着直接的影响1。长久以来，许多学者致力于装配序列规划问题的研究。Bourjault2首先将装配关系联接图引入装配序列规划，此后De Fazio和Whitney3等在此基础上进行了一系列研究，但问题规模始终是此类方法的瓶颈1。随着研究的深入，专家系统、模拟退火算法、Petri网及神经网络等人工智能技术，也被应用于装配序列规划中，并有不少研究成果出现。遗传算法作为一种有效的算法也被广泛应用于序列规划4-8。1991年M. Dorigo9等提出蚁群算法，1999年Failli和Dini10首次将之用于装配序列规划后，蚁群算法就被广泛用于序列规划研究中11-15。这些方法从不同的角度取得了不少研究成果，但多数在于对算法本身的改进，而对装配序列规划方法本身的关注不够。在装配序列规划中通常考虑较多的是装配体本身的几何约束关系，而对重力作用下影响装配顺序的装配稳定性考虑不多，仅有少数涉及到6,14，且多仅在评价指标中给予了一定的体现；对在实际生产过程具有重要指导意义的装配经验更是甚少关注。为使所求序列更贴近实际生产过程，本文将装配过程稳定性、装配经验，纳入序列规划影响因素中；并基于此改进了蚁群的搜索策略、转移规则、信息素更新策略，将稳定性、装配经验等影响因素直接用于指导蚁群转移，使得算法更适应于所研究的装配序列规划方法。 2 产品装配信息的矩阵描述产品的装配序列规划，实质是基于装配约束关系，找出各零件间的合理安装顺序。产品装配信息是装配约束关系的具体描述，合理的产品信息表达方式是实现装配序列规划的基础。2.1 增强优先关系图及其矩阵描述零部件的装配实际上是它相对于基准零部件先定位、再施加约束的过程。这个过程表明了被装配件与基准件之间的局部装配优先关系，也即基准件的装配需优先于被装配件。通过遍历装配体中所有零部件间的定位、约束信息，则可以得到各零部件间的装配优先关系，由此得到连接所有零部件的装配优先关系图。它的起点是基础件，即装配中引入的第一个零件模型11。文献11,12对此种装配优先关系图的建立方法有详细论述。但是，这类仅由装配约束关系建立起来的装配优先关系图只描述了零部件间的几何约束关系。基于此进行装配序列规划时，都未考虑零件本身的重力，即装配过程都是在失重状态下进行，显然缺乏实际意义。本文在上述装配优先关系图基础上，考虑重力的影响将装配稳定性纳入考虑，构建增强装配优先关系图EG，并通过增强邻接矩阵C来描述装配体中各零部件间的装配优先关系，及存在稳定性连接的零部件间的增强联接关系。这里的稳定性连接主要是指在重力作用下，建立两个零部件间重力支撑关系、以保证装配体各零部件稳定的连接，如螺栓对零部件的紧固连接等。增强装配优先关系图表示为：EG=P,E。其中，P是零件集合，E是边集合。对于有向边，eijE表示零件j相对于零件i定位，也就是表明零件i优先于零件j装配。对于存在稳定性连接关系的两个零部件则用加强边来表达它们之间的强约束关系,则其增强邻接矩阵可表示为C=cij，它表示零件j对零件i给予重力支撑以保证零件i的稳定性。如果有向边eij存在，则cij =1，即零件i优先于零件j安装；特别的，若节点i、j间存在加强边，即零件i、j还存在稳定性连接关系，则cij =2，则零件j需紧接零件i安装以保证i的稳定性；有向边eij不存在，则cij =0，即零件i、j之间不存在直接的优先关系。即 （1）82.2装配工艺信息矩阵描述在进行装配序列规划时，除了需要满足几何约束关系外，装配经验也是指导装配序列规划的另一重要信息。在装配过程中存在一些在优先关系约束上并行的零部件，它们之间本身不存在优先关系，但根据操作经验存在一定的先后顺序。装配经验对实际装配过程有着重要影响。这里，我们定义当零部件i和j本身不存在直接或间接优先关系，但是为了操作方便或操作习惯等原因，i装配之后j最好马上安装，则表明i和j之间存在经验影响关系。本文引入经验值矩阵V=vij来表达经验影响关系，当零部件i与j根据经验连续安装时vij=1，否则vij=0。另外装配工具以及装配方向也是指导装配序列规划的重要工艺信息，本文通过建立装配方向与装配工具库对零部件的装配方向和工具进行描述，从而可以分别用矩阵V1=v1ij、V2=v2ij描述局部装配操作ij之间装配方向和工具的改变情况。当零部件j紧接i安装时，如果装配方向(工具)相同，则v1ij=1(v2ij=1)，否则v1ij=0(v2ij=0)。3优化目标体系构造在装配过程中，所有的零部件都需要保持稳定，这是装配必须满足的条件。为了提高装配效率、降低成本，就需要尽可能的减少装配方向和工具改变的次数。另外，装配经验是指导装配序列规划的重要因素。因此，在进行装配序列规划时，故本文以装配过程的稳定性、操作经验值、装配方向的改变次数和装配工具的改变次数四个方面作为指导装配序列规划的指标。(1) 装配过程的稳定性：装配过程的稳定性表明了在重力和装配约束力的作用下，装配体保持其内部装配关系的能力。只有具有良好的稳定性，才能保证装配过程顺利进行。装配过程的稳定性直接影响着装配操作的可靠性。根据前述建立的增强装配优先关系图及邻接矩阵有：当cij=2时，S1=0.1；否则S1=1。(2)装配经验影响：装配经验是长期较优操作的一个积累。在装配过程中，如果根据操作经验两零部件需连续安装，即vij=1时，S2=0.1；否则S2=1。(3) 装配方向的改变：装配方向对装配效率有很大影响，从而影响装配代价。对于装配操作ij，如果装配方向相同，即v1ij=1，则S3=0.1；否则S3=1。(4) 装配工具的更换：在装配过程中每一个零部件都有相应的操作工具，如果频繁更换工具则影响生产效率。对于装配操作ij，若装配工具相同，即v2ij=1时，则S4=0.1；否则S4=1。则单次操作的装配评价指标可以表示为：fij(s)=wisi，其中wi(i=1,2,3,4)为权重系数。最优装配序列则是装配中稳定性最好、最符合装配经验、装配方向和工具改变次数最少，则优化目标函数则为f(s)=minfij(s)。4 基于蚁群算法的装配序列规划4.1装配序列求解过程4.1.1 初始化产品的装配都是从基础件开始，因此首先将蚂蚁集中于基础件位置，即置于基础节点上。所有的蚂蚁从基础节点出发，在启发信息和信息素浓度的指导下，向下一个节点转移。为指导蚁群求解可行解，本文引入装配过程信息矩阵A=aij来表达装配体中各零件的装配信息11，其 aij=mij, ij, ij为一个多元组，表达了装配过程中零部件之间的各信息。其中，初始化mij=cij，当零件i安装完成之后则改变，它用来表示优先零部件的装配情况；ij与装配代价相关，是蚁群算法中的启发信息；ij为信息素浓度，与局部装配顺序ij被选择情况有关，初始化时ij为常数。ij,ij在装配序列规划中共同作用以指导蚁群搜索到最优路径。4.1.2 蚁群转移在构建装配序列的过程中，每只蚂蚁从基础件出发，根据状态转移概率从候选列表allowedki(t)选取下一个待装配零件。状态转移概率由启发信息和信息素浓度来确定，如公式(1)： （2）其中ij(t)是信息素浓度，信息素的堆积是一个正反馈过程；ij=1/fij(s)是贪婪搜索中与装配代价相关的启发信息；、为非负数，且是信息启发因子，反映了该蚂蚁在运动过程中先验信息的重要程度，是期望启发因子，反映了蚂蚁运动过程中启发信息的受重视程度。allowedki(t)为t时刻蚂蚁k在零件i安装完成后的可行转移范围候选列表。为减小求解空间，本文引入动态候选策略9。根据优先关系知，零件j能进行安装的条件是优先关系图中它所有的父节点都已经装配完成而本身未装配。因此，当零件i安装完成后，其候选集allowedki(t) 动态更新步骤如下：1）mil=0，l=(1,2,n)，即装配信息矩阵中第i行的元素mij置零；2）从allowedki(t)删除i；3）添加零件i的可行子零件：考察零件i的子零件j，如果装配信息矩阵中第j列元素mij全部为零，即mhj=0，h=(1,2,n)，向allowedki(t)添加零件j，直到遍历零件i的所有子零件。4.1.3 信息素更新人工蚂蚁在走过的路径上会留下信息素以指导后续蚂蚁的路径选择，同时路径上的信息素也会挥发。在序列构造过程中，如果蚂蚁从节点i移动到节点j，则根据局部信息素更新规则对节点i和j之间的信息素浓度进行更新： (3)其中是局部信息素挥发因子；(i,j)=1/fij(s)是蚂蚁从节点i移动到节点j所释放的信息素增量。局部更新规则的应用使已选局部路径的信息素量逐渐减少，减少此局部路径对蚂蚁的吸引力，提高解的多样性，有效的避免了局部收敛。当所有的蚂蚁都构造完其路径后，对装配序列进行可行性检查。这里引入干涉矩阵13来表示装配过程中各零部件间的空间阻碍关系。在笛卡儿坐标中，一般将产品的拆卸/装配方向分成(x,y,z)六个方向。干涉矩阵从(x,y,z)六个方向给出了零件在装配过程中与装配体中其他零件的干涉关系。如果零件j能沿k方向与零件i无干涉地被装配到位，Iijk=0，否则Iijk=1。设已知序列1,2,m为零件i装配前已完成的可行装配序列，则如果vk(i)=mj=1Ijik=0，则装配序列1,2,m, i可行，否则不可行。可行性检查后对所有可行解进行评价，并进行全局信息素更新。全局信息更新规则为 (4) (5)其中01，表示轨迹上的信息素挥发；L是当前迭代最优解或全局最优解；f(L)是蚁群所构建序列的装配评价值；Q为信息素增加强度系数。这种更新策略增强了较优路径上的信息素量，使得其对后来的蚂蚁更有吸引力。在序列的构建过程中，局部信息素更新促使蚂蚁寻找不同的解，使解多样化；而全局信息素更新突出较优解，促使蚁群找出最优解。当信息素更新完毕之后，当前迭代结束，清除相应的工作记录，开始新的迭代，直到满足终止迭代条件。4.2 算法主要框架上述基于蚁群算法的装配序列规划算法实现过程如下：Begin ASP参数初始化：装配模型的增强优先关系矩阵C，装配过程信息矩阵A；信息启发因子和期望启发因子；信息素挥发系数、； 信息素增加强度系数Q，零件总数n和蚂蚁数量m。while(不满足终止条件)Do清空序列记录、侯选列表，将所有蚂蚁集中到基础件；将基础件放入装配序列； While(所有零部件已装配) Do While(所有蚂蚁已转移) Do 根据动态转移策略生成allowedki(t)；计算状态转移概率并转移；局部信息素更新； 装配序列可行性检查并评价；全局信息素更新；End5 算法实现和实例研究基于上述装配序列规划方法，作者在MATLAB平台下开发了相应的蚁群算法程序。其中，优先关系图、各零部件的装配方向和装配工具为人工输入；基础件根据装配经验指定。为验证本文的内容，以文献6中8E150ZLC柴油机机油泵装配体为对比研究实例进行装配序列规划，如图1所示。图2 装配优先关系图Fig 2 Assembling preference graph图1 8E150ZLC柴油机机油泵装配体Fig 1 Assembly of 8E150ZLCs oil pump 20103111251713987162115141819412176表1装配工艺信息表 Tab 1 Information of assembly processNumberNameToolnumberDirectionNumberNameToolnumberDirection1end cover of pump 1+z12pin5+z2component of driving shaft1+z13the middle pump cover1+z3bolt2+z14stationary shaft1+z4washer1+z15adjusting shim1+z5adjusting shim1+z16pin5+z6woodruff key1-y17component of driven gear1+z7pin 3-z18cover board1+z8nut2-z19washer1+z9washer1-z20bolt2+z10gear1-z21gasket1+z11component of pump body1+z通过前文建立优先关系图的方法，上述装配体的增强优先关系如图2所示，其装配工具和装配方向信息如表1。根据装配经验，需连续安装的零部件组包括：214,112，1417。为验证文中的方法，对上述实例中的装配体进行10次装配序列规划，每次运算迭代次数为300代。算法中的主要参数设置沿用常用设置方法：m=25，=2，=8，=0.2，=0.1， w1=2，w2=1.5，w3=2，w4=1。图3 装配序列规划算法求解性能Fig 3 Performance of the assembly sequence planning approach表2 装配序列规划结果比较Tab 2 Comparison of assembly sequence planning resultsOptimal or near optimal solution of assembly sequence planningThis paper112141751213151211819201643610987Ref 6 111451213172151614321181920610987由图3可以看出该算法经历较早的代数就找到较优解，且具有良好的收敛性能。从表2可以看出规划结果满足优先关系，在装配过程中能较好保证装配体的稳定性，且整个装配过程符合实际装配习惯。文献6的规划结果中，11145的装配顺序明显很难保证装配过程中14的稳定性且不符合一般装配经验；13172的装配顺序与先里后外的实际装配经验不符，且此种装配顺序本身不合理。因此，相对于文献6的规划结果而言，本文所得优化结果具有更好的稳定性，且明显符合一般装配经验。因此，本文所得序列更符合实际装配过程，对实际装配有一定的指导意义。需要说明的是：1）本实例中最优结果有多个，如112141712513151211819201643610987、112141751213151211819204316610987。考察上述解可知均满足几何关系、装配经验，装配过程中各零部件均能保持稳定，且装配方向、工具改变次数最少，为本文所定义的最优装配序列。由此表明，通过该方法所得到的装配序列，能满足指导实际生产的需求。2）对于零部件众多的装配体而言，基于优先关系的动态候选策略可减少求解过程中的搜索空间，能有效避免此类问题的组合爆炸可能。基于上述实例研究，从图3可以看出，蚁群能很快找到较优解，且能迅速收敛。因此，由于蚁群的求解过程基于优先关系图，使得本文所提出的方法对零部件众多的复杂产品装配序列规划问题具有良好的解决能力，且针对该方法而改进的蚁群算法，能迅速寻找较优解并快速收敛。6 结论本文提出了一种基于蚁群算法的改进装配序列规划方法，其主要优势如下：在传统装配序列规划方法的基础上，采用增强优先关系图将装配体各零部件的几何约束和装配过程中的稳定性予以考虑，同时考虑了装配经验因素的影响，使得所求解更适合于指导实际生产过程。在蚁群求解过程中，基于零部件间优先关系的动态候选策略，有效减少了蚁群求解过程中的搜索空间；同时基于稳定性因素的影响改进了蚁群转移规则，使算法能更好的满足装配序列规划需求。相关实例验证表明，此算法能快速搜索到具有实际指导意义的最优或近优装配序列。参考文献1 TSENG H E, WANG W P, SHIH H Y. Using mimetic algorithms with guided local search to solve assembly sequence planning J. Expert Systems with Applications, 2007, 33 :451-467.2 BORUJAULT A, HENRIOUD J M. LEGA: Computer-Aided Generator of Assembly Plans J. Computer-aided Mechanical Assembly Planning, 1991:191-215.3 DEFAZIO T L, WHITNEY D E. Simplified generation of all mechanical assembly sequence J. IEEE Journal of Robotics and Automations, 1987, 3(6): 640-658.4 DINI G., FAILLI F, LAZZERINI B,et al. Generation of optimized assembly sequences using genetic algorithms J. Annals of the CIRP, 1999, 48(1): 17-20.5 ROMEO M M, LEE H S, KAZEM A. A genetic algorithm for the optimization of assembly sequences J. Computers & Industrial Engineering, 2006, 50: 503527. 6 ZHOU Kaijun, LI Dongbo. Product assembly sequences planning based on genetic simulated annealing algorithm J. Computer Integrated Manufacturing Systems, 2006, 12(7): 10371041 (in Chinese). 周开俊, 李东波. 基于遗传模拟退火算法的产品装配序列规划方法J. 计算机集成制造系统, 2006, 12 (7): 10371041.7 LI Yuan, ZHANG Kaifu, WANG Ting,et al. Assembly sequence planning optimization for aircraft assembly based on GAJ. Computer Integrated Manufacturing Systems, 2006, 12 (2):188191 (in Chinese) . 李原，张开富，王挺等，基于遗传算法的飞机装配序列规划优化方法J. 计算机集成制造系统, 2006, 12 (2):188191.8 HUANG Jie, DU Ping-an, LIAO Weizhi. Genetic algorithm for assembly sequences planning based on assembly constraintJ. Computer Integrated Manufacturing Systems, 2007, 13(4): 757-761 (in Chinese). 黄洁, 杜平安, 廖伟智. 基于配合约束的装配序列规划的遗传算法研究J. 计算机集成制造系统, 2007, 13(4): 757-7619 COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant coloniesC. Proceedings of the 1st European Conference on Artificial Life, 1991:134-142.10 FAILLI F, DINI G. Searching optimized assembly sequences by ant colony systems C. 4th AITEM Congress, Brescia, 1999,9(13)