基于引力搜索算法的复杂产品装配规划研究

史亚斌++李翌辉++吴安乐

摘 要：将引力搜索算法引入到复杂产品装配序列规划中，详细讨论了引力搜索算法在装配规划中的应用。以装配成本最低为目标，采用装配方向的重定向、装配工具更换、装配类型的改变等三个装配评价指标，确定了序列规划目标函数；通过设置算法最大迭代次数、初始引力常数、衰减系数等计算参数，完成了序列规划的迭代结束条件的设置与粒子引力合力的计算；通过对装配序列的规划结果进行迭代更新，达到迭代结束条件后输出了最优解。以某型号搅拌机构装配為例，分析了引力搜索算法在复杂产品装配序列规划中的具体应用与验证，结果表明：引力搜索算法能够高效、合理地完成序列规划优化的计算，避免由于装配序列枚举引起的计算量较大的问题。

关键词：引力搜索算法 装配成本 装配序列规划

中图分类号：TG95 文献标识码：A 文章编号：1674-098X（2017）10（c）-0136-04

Abstract： The gravitational search algorithm（GSA） is introduced into the planning of complex product assembly sequence， and the application of GSA in assembly planning is discussed in detail. With the minimum cost as the goal，a sequence planning objective function is determined. This function uses three assembly evaluation indexes such as redirection of assembly direction， replacement of assembly tools and change of assembly type. By setting the maximum number of iterations， the initial gravitational constants and the attenuation coefficients， the parameters of the iterative end condition of the sequence planning and the calculation of the force of the particle force are completed. The iterative updating of the planning result of the assembly sequence results in the optimal solution after the iteration end condition. Taking the assembly of a certain type of mixing mechanism as an example， the paper analyzes the application and verification of GSA in complex product assembly sequence planning. The results show that the GSA can efficiently and reasonably complete the calculation of sequence planning optimization and avoid the problem of large computation caused by the assembly sequence enumeration. The results show that the GSA can meet the requirements of assembly planning as well.

Key Words： Gravitational Search Algorithm； Assembly Cost； Assembly Sequence Planning

在现代设计与制造过程中，随着产品结构越来越复杂，零部件数量越来越多，零部件之间的装配约束关系也随之增多。研究表明，装配序列数量与零部件数量呈指数增长关系，因此，针对复杂产品进行装配规划时，很容易导致序列组合爆炸问题，工程师往往会凭借经验，花费大量的时间和精力来寻找装配序列，而且找到的装配序列往往不是可行装配序列或最优装配序列。

2009年伊朗的克曼大学的Esmat Rashedi 等人基于牛顿的万有引力定律和第二运动定律提出了引力搜索算法[1]GSA（Gravitational Search Algorithm），该算法具有结构简单、易于实现、参数设置少和全局优化能力强等特点，且已经在很多优化问题中都得到了成功应用。本文利用引力搜索算法来解决复杂产品装配序列规划问题，以获取复杂产品的最优装配序列。

1 引力搜索算法在装配序列规划中的应用

本文将引力搜索算法引入到装配序列规划当中，通过对在装配过程的影响因素进行分析，构建适应度函数，以装配成本作为评价装配序列优劣的标准，同时根据零部件的几何约束关系构建装配约束数学模型，保证装配序列的正确性与可行性。基于引力搜索算法装配序列规划步骤如下。

1.1 待装配零件群体和序列规划目标函数的确定

假设复杂产品的装配体由个待装配零件组成，此时搜索空间就为N维搜索空间，则在搜索空间中的第个粒子的位置标记为：

（1）

其中表示该粒子在第d维搜索空间的位置。

将适应度函数作为装配序列规划中的目标函数，采用装配成本来构造适应度函数，包括装配方向的重定向、装配工具更换、装配类型的改变。endprint

依据上述3个评价标准分别添加权重系数，构造适应度函数为：

（2）

上式中，表示粒子的装配花费成本，表示第个零件到第个零件在装配过程的成本，其中公式为：

（3）

其中，表示完成第个零件到第个零件的装配过程所花费的成本，，代表装配方向的重定向次数，代表装配工具更换次数，代表装配类型的改变次数，d是装配方向的重新定向在总装配成本中的权重系数，是装配工具更换在总装配成本中的权重系数，是装配类型的改变在总装配成本中的权重系数，且满足。

1.2 设置序列规划的迭代结束条件并进行粒子引力合力的计算

设置算法最大迭代次数T为100，设置初始迭代值t为0， 指的是在t时刻粒子的适应度函数值，即代表当前装配序列装配成本。和是t时刻粒子群中最差函数值和最优函数值，即当前装配可能序列中的最差适应度函数值和最优适应度函数值，定义解决该装配序列规划问题时使用最小排序规则，则：

（4）

（5）

根据当前粒子的最差函数值式（4）和最优函数值式（5），计算出当前t时刻粒子的质量。

（6）

（7）

万有引力常数公式定义为：

（8）

其中，为衰减系数，为初始引力常数，T为实际计算中定义的最大迭代次数或者时间周期，这样就保证引力常数是随着时间改变的变量。本文设置初始引力常数为100，衰减系数为20。

在粒子搜索的过程中由于惯性质量小的粒子向惯性质量大的粒子方向移动，因此粒子间的距离是逐渐变小的，定义万有引力公式为：

（9）

式（9）中，是一个常数，当两个粒子随着迭代的运行，粒子之间的距离逐渐减小直至重合，此时为0，分母为0不符合定义，因此设置是保障分母不为0从而保证公式的正确性，本文中将常数设置为5。即为粒子分别受到群体中其他粒子万有引力的大小。在实际应用中，粒子在特定系统中受到的是粒子群中其他粒子的共同作用，因此需要根据计算粒子的万有引力合力。定义如下：

（10）

其中Rand代表的是随机数，该随机数取值范围是[0，1]，设置该随机数的目的是为了防止算法求解陷入局部最优，体现算法具有的随机性特点，得出的结果更符合实际情况。

1.3 对装配序列的规划结果进行迭代更新，达到迭代结束条件后输出最优解

利用公式（2～10）得出粒子的合力，由牛顿第二运动定律求得t时刻粒子的加速度：

（11）

根据t时刻已确定的粒子速度和位置，更新t+1时刻粒子的、粒子的位置：

（12）

（13）

在的定义中，Rand同样代表的是随机数，该随机数取值范围是[0，1]。通过对粒子速度和位置的不断更新于迭代，进而不断优化装配序列规划结果。

本文中迭代结束条件为达到预先设定的最大迭代次数，当达到最大迭代次数就停止循环，并输出此时每个粒子的位置值，根据以上定义为最小排序规则，将的最终输出值按从小到大排序，则得出的序列为使用引力搜索计算出的装配序列。

2 装配序列实例分析与验证

本文以某搅拌机构的装配序列规划为例，对基于引力搜索算法的装配序列规划方法进行分析与验证。

在不影响装配规划结果的前提下，为了减少计算量，提高计算速度，本文对搅拌机构的实际装配情况做如下简化。

（1）将搅拌机构的所有零部件都看作是刚体，同时，忽略零部件在装配过程中产生的变形、公差累积等影响因素。

（2）只考虑每个零部件沿±X、±Y、±Z六个坐标轴方向的平移与旋转的装配，而不考虑零件沿其他方向的旋转装配。

（3）本文研究的产品模型不涉及电气、非机械零部件以及螺钉等联接件。

（4）在装配过程中，一个零件一次只能在一个方向装配。

简化后该机构主要包含14个零件，如图1所示。

搅拌机构零部件爆炸图如图2所示，其中，、…表示每个零件的编号。

零件序号、零部件名称以及零件编号的对照表如表1所示。

由于搅拌机构简化后有14个零部件，则搜索空间为14维，该群体中第粒子的位置标记为：

其中，所构造的适应度函数为：

基于引力搜索算法的装配序列规划中执行步骤进行编码，并按照参数讨论中得出的相关结论设置参数值，将的最终输出值按从小到大规则排序后输出最优装配序列，如表1所示。由于篇幅限制只列出最后20次的运行结果，第一行代表的是装配前各零件的编号，总共有14个零件则编号为1～14，最后一行代表的是经过引力搜索算法计算后最终输出的装配序列。

從程序运算输出的装配序列分析可知，该序列装配稳定性较佳，装配方向改变次数较少，满足实际装配过程的要求，零件装配序列中未出现装配干涉的情况，满足几何可行性的要求。搜索代理相互之间由于万有引力作用会聚集在一起，因此用引力搜索算法来解决序列规划这种非线性优化问题具有自身优越性，符合装配规划的需求，可使装配序列更加合理、更能够贴近实际的装配过程，大大提高了运算效率，可有效解决由于零件数量较多对所有装配序列一一枚举时引起计算量较大的问题，从而避免对所有装配序列进行全排列。

3 结语

产品的设计制造中，合理高效的装配序列规划起到了非常重要的作用，决定了产品设计制造方案是否合理与可行。本文将最低装配成本作为优化目标，提出了基于引力搜索算法的装配序列规划方法，通过建立产品装配序列优化模型，利用粒子位置和速度更新规则，实现了复杂产品装配规划序列的寻优，并通过搅拌机构装配序列规划的实例，对算法进行了分析和验证，结果表明，基于引力搜索算法的装配序列规划方法具有稳定性好、收敛速度快等优点，可有效提高复杂产品最优装配序列规划的效率。

参考文献

[1] Esmat Rashedi，Hossein Nezamabadi-pour，Saeid Saryazdi.A Gravitational Search Algorithm[J].Information Sciences，2009，179（13）：2232-2248.

[2] 张爱竹，孙根云，王振杰，等.一种基于数据场的多目标引力搜索算法[J].控制与决策，2017，32（1）：47-54.

[3] 陶俐言，杨海斌.基于改进引力搜索算法的公差多目标优化设计[J].机械设计与研究，2017，33（2）：133-137.endprint