基于遗传-蚁群算法的装配序列规划研究

孟冠军，杨大春

(合肥工业大学 机械工程学院，合肥 230009)

0 引言

装配是制造业很重要的主题，对于一个结构复杂零件众多的产品，其装配时间几乎占整个生产时间的一半，在劳动成本方面大约要占30%～50%，如果使用传统方法会产生大量可行的装配序列且效率无法保证[1]。好的装配序列会大大提高装配效率、降低装配成本和提高企业竞争力，装配序列规划(Assembly sequence planning,ASP)的重要性得到越来越广泛的重视。

近20年来，智能算法被用于装配序列规划求解领域，Bonneville首次使用遗传算法后，很多智能算法被发展起来，比如模拟退火、人工免疫系统、蚁群算法、粒子群算法等。模拟退火算法[2]可以求解一些非线性问题，能以较大的概率求得最优解，其缺陷是全局搜索能力差，当问题规模较大时，只能获得近似解。粒子群算法[3]源于对鸟类捕食行为的研究，相对于遗传算法[4]，其收敛速度更快，并且具有记忆功能，但是容易陷入局部最优。免疫算法[5]在智能算法领域属于比较新的算法，该算法在系统建模等方面存在诸多问题。

本文采用蚁群算法和遗传算法相结合的混合算法，利用遗传算法选择、交叉、变异操作对装配序列进行优化，以及蚁群算法具有较强的鲁棒性和全局搜索能力，二者可以取长补短，不仅克服了遗传算法的早熟现象，而且可以使蚁群算法可以更快、更好地收敛到全局最优解。表明遗传-蚁群算法比传统的蚁群算法在寻找最优解方面可以获得更优的路径，效率更高。

1 算法原理

蚁群算法由M Dorigo提出并初次使用，其灵感来源于蚂蚁对食物的搜寻。通过建立合适的信息矩阵，蚂蚁会搜寻到从巢穴通往食物地点的最短路径。蚂蚁在搜寻过程中会在其走过的路径上分泌信息素，通常路径越短信息素越浓，一段时间后信息素会衰减一部分，这样蚂蚁最终会集中在同一条路径上，此路径便是最短路径[6-7]。

蚁群算法部分以旅行商问题(Traveling Salesman Problem,TSP)为例说明，设定蚂蚁数量m，信息素重要程度因子α、启发函数重要程度因子β、城市数目为n，初始状态下不同城市间的信息素浓度相同，蚂蚁k根据不同零件间的信息素浓度来选择下一个要访问的城市，令Pij(t)为第t次迭代蚂蚁从城市i转移到城市j的概率。

其中，ηij(t)表示蚂蚁从城市i转移到城市j的期望程度；τij(t)表示蚂蚁从城市i转移到城市j的信息素浓度；allowk表示蚂蚁k所有待访问的城市集合；α和β这俩值越大，表示蚂蚁在转移过程中起到的作用越大。当所有蚂蚁完成一次循环后，各个城市间的连接路径上的信息素浓度需要进行一次更新，即：

本文针对蚁群算法作如下几个方面的更新：

(1)局部信息素更新。蚂蚁从城市i转移到城市j后，通过挥发掉一部分信息素，蚂蚁对已经访问过的城市就会缺乏吸引力，转而去搜寻未访问的城市，这样可以促使解的多样性，更新规则为：

τij=(1-ζ)τij

(2)全局信息素更新。该更新的目的是增加最优解节点信息素，使得蚂蚁更快得集中于最优解，即：

τij=(1-ρ)τij+ρΔτij

其中，Δτij=Q*1/min_Length，是蚂蚁k从节点i移动到节点j的信息素增量。

遗传算法部分本文主要采用交叉和变异操作对装配序列进行优化。本文采用的是部分映射交叉，产生两个[1,n]范围内随机整数以确定交叉位置，对这两交叉位置之间的数据进行交换。交换后，同一个个体中有重复的编号和有冲突的数字采用部分映射的方法消除冲突。变异操作的策略是采取随机选取两个点，将其对换位置。随机产生两个[1,n]范围内的整数，交换这两位置。

2 装配信息模型

2.1 干涉矩阵

假设零件只能沿着{+X,+Y,+Z,-X,-Y,-Z}6个方向进行装配，一次性装配只能是一个方向和一个工具。例如，Pi,j=101表示零件j沿着+X和+Z方向与零件i发生干涉，但是如果沿着+Y方向则不发生干涉，可以正常装配。Pj,i表示零件i与零件j的干涉情况，同时也表示零件j沿着-X,-Y,-Z与零件i的干涉情况[8-9]。如果Pi,j=111011，表示零件j可以沿着-X方向在零件i后安装，Pi,j=111111，表示零件j无法在零件i后安装。

本文建立的干涉矩阵形式如下：

为求解简便，本文将干涉矩阵分拆为三个矩阵，分别表示X、Y、Z三个方向。

2.2 启发信息

启发信息所表达的是可以让蚂蚁对于接下来需要去的节点作一个大概的判断。通常情况下对于一个给定的装配序列，蚂蚁对节点的一次搜寻会被已经完成的序列深深的影响到。

mj表示零件j的质量；lj表示零件j的体积；dij表示零件j在零件i后安装其安装方向是否发生变化，如果变化则是1，否则是0；nij表示零件装配在不同方向的值，如果沿着重力方向nij为0.0001，如果与重力方向相反，则是1，如果与重力方向垂直，nij为0.5；tij表示零件j在零件i后安装其安装工具发生变化情况，如果发生变化，tij为1，不变则是0；gij表示零件的安装难易程度，如果可以正常安装，gij为1，如果有点难度gij为0.05，如果特别难以安装gij为0.0001[10]。

2.3 判断装配序列

有些零件虽然不发生干涉，但是在装配时却存在优先约束关系，如果反过来装配的话，其本身不符合逻辑且在实际中根本无法装配。针对这种情况，可以设置一个优先约束矩阵PR，如果两零件不符合逻辑的话，则令PRij=1，否则PRij=0。例如刚刚装配好的零件Ik，如果发现PRij=1，那么就调换两零件的顺序这样就符合逻辑且可以正常装配。

2.4 适应度函数

为了评价生成好的装配序列，需要通过几个参数来确定此装配序列的优劣，为了尽可能地提高装配效率，本文通过以下几个参数来评价装配序列：

(1)装配序列的稳定性。为了提高装配的稳定性和可靠性，我们需要建立接触矩阵确保装配过程的正常进行[11]。设稳定性参数为S1，如果两零件直接接触且保持稳定连接关系则S1=0.1，两零件仅仅直接接触则S1=0.4，否则S1=1。

(2)装配序列的连续性。连续性表示零件间具有一定的接触连接关系，产品是否可以实现连续安装。设连续性参数为S2，如果两零件具有配合关系则S2=0.1，否则S2= 1。

(3)装配方向的改变次数。装配的方向如果变化的过于频繁会大大增加装配的成本和难度，因此我们需要尽量减少装配的重定向。设方向改变参数为S3，如果两零件方向不发生变化则S3=0.1，否则S3=1。

(4)装配工具的改变次数。每一个零件都有一个装配工具，如果连续几个零件装配时使用的都是不同的装配工具，同样会增加装配的成本。设连续性参数为S4，如果两零件装配工具不发生变化则S4=0.1，否则S4=1。

根据以上4个参数建立一个适应度函数：F=w1S1+w2S2+w3S3+w4S4。此适应度函数可以通过其较大的区分度来评价装配的优劣，提高了装配序列规划搜索范围。

3 遗传蚁群算法操作步骤

(1)信息初始化。首先要对算法相关参数进行初始化，包括蚂蚁的数量m，最大迭代次数iter_max，信息素重要程度因子α，启发信息重要程度因子β，全局信息素挥发因子ρ，局部信息素挥发因子ζ，信息素释放总量Q，各优化目标的相对权重w1～w4,流程图如图1所示。

图1 流程图

(2)构建解空间。计算启发信息，让蚂蚁全部集中于基础件，对所以蚂蚁按照公式1进行选择下一个要去的零件，蚂蚁每访问一个零件进行局部信息素更新，这样可以让蚂蚁有更多的选择。

(3)可行解判断。使用干涉矩阵判断所有的装配序列，如果某一零件与之前所有零件在所有6个方向均发生干涉，可以判断该序列为不可行序列。遍历所有可行的装配序列，若发现不符合逻辑的两零件，调换二者位置。

(4)遗传操作。针对所有可行的装配序列进行遗传操作，包括选择、交叉、变异，结束后再重新插入种群。

(5)评价装配序列。使用公式评价所有可行的装配序列，计算最短距离和平均距离，更新全局信息素以突出最优解，这样算法会收敛得更快。

(6)结束。当迭代次数等于iter_max，则该算法终止运行，定义最后一次迭代所获得的最优解为全局最优装配序列。

4 实例

本文的算法在Matlab平台上编写，将与传统的蚁群算法想比较，考察遗传蚁群算法的优化性能。如图2所示为二冲程发动机，该装配体共包含19个零件，零件装配信息如表1所示。

图2 二冲程发动机

表1 二冲程发动机零件属性表

该算法所使用的相关参数为蚁群数目m=35，最大迭代次数iter_max=100，α=6，β=7，ρ=0.2，ζ=0.1，交叉概率PC=0.9，变异PM=0.05，w1=0.3，w2=0.3，w3=0.4，w4=0.3。最终获得最优解为11.09，最优路径为：(1,X)→(2,Z)→(9,Z)→ (10,Z)→(3,-X)→ (8,X)→(6,Z)→(4,Z)→(5,X)→(11,-X)→(17,Z)→(7,Z)→(18,Z) →(12,Z)→(13,-X)→ (14,Z) →(16,Z)→(15,Z)→(19,-Y)，如图3所示，传统蚁群算法最优解为12.58。当然算法的最优解不唯一，其他的最优路径在这里就不一一列举了。

为了验证遗传蚁群算法的有效性和优越性，通过多次试验，将遗传蚁群算法与蚁群算法作比较。由图3～图6可知，蚁群算法搜索速度较慢，需要花费较长的代数才能找到最优解，遗传蚁群算法可以在较短的时间内寻找到最优解，且遗传蚁群算法所搜寻到的最短路径比传统蚁群算法更加优秀。对比来看遗传蚁群算法可以获得更理想的结果。

图3 蚁群算法最短距离 图4 蚁群算法可行解个数

图5 遗传蚁群算法最短距离 图6 遗传蚁群算法可行解个数

5 结束语

本文对蚁群算法作了部分改进，并且和遗传算法相结合，在求解装配序列规划问题上取得很好的效果。干涉矩阵和工具列表矩阵表达了产品可行装配方向等信息，在此基础上，基于遗传算法和蚁群算法的原理和模型，构建了面向装配序列规划的遗传蚁群算法，并从装配可行方向的改变次数和装配工具的改变次数等四方面建立目标优化函数，求解装配序列。最后通过实例研究，证明了遗传蚁群算法能较好地搜索出装配最优序列。

[参考文献]

[1] Ghandi S, Masehian E. Assembly sequence planning of rigid and flexible parts[J]. Journal of Manufacturing Systems,2015,36:128-146.

[2] 王孝义,张友良,张帆.基于模拟退火算法的装配序列生成与优化[J].机械科学与技术(西安),2005,24(5):624-627.

[3] 邢彦锋,赵晓昱.粒子群算法在装配顺序规划中的应用[J].计算机集成制造系统,2011(3):80-82.

[4] 蒋超,吴波,李明宇,等.基于遗传算法的产品装配序列规划研究[J].机械与电子,2012(4):7-11.

[5] 宁黎华,古天龙.基于免疫算法的装配序列规划问题求解[J].计算机集成制造系统，2007,13(1):81-87.

[6] 邓明星,唐秋华,雷喆.基于蚁群算法的改进装配序列规划方法[J].武汉大学学报(工学版),2013,46(2):246-251.

[7] 谢龙,付宜利,马玉林.基于蚁群算法的装配序列生成策略[J].哈尔滨工业大学学报,2006,38(2):180-184.

[8] 彭涛,李世其,王峻峰,等.基于集成干涉矩阵的蚁群装配序列规划[J].计算机科学,2010,37(4):179-182.

[9] 崔小龙, 刘新华, 宋国民.基于子装配的装配序列规划方法研究[J].组合机床与自动化加工技术,2012(5):78-81,85.

[10] 史士财,李荣,付宜利,等.基于改进蚁群算法的装配序列规划[J].计算机集成制造系统,2010,16(6):1189-1194.

[11] 于嘉鹏,王成恩,王健熙.基于最大_最小蚁群系统的装配序列规划[J].机械工程学报,2012,48(23):152-166.

(编辑李秀敏)