基于改进引力搜索算法的异步并行拆卸序列规划研究*

李佰霖,武攀旗,吴志超,付文龙

(1.三峡大学 电气与新能源学院,湖北 宜昌 443002;2.三峡大学 梯级水电站运行与控制湖北省重点实验室,湖北 宜昌 443002;3.哈尔滨电机厂有限责任公司,黑龙江 哈尔滨 150040)

0 引 言

机械设备维修涉及对维修目标件的拆卸,维修人员通过更换或维修有缺陷或磨损的零部件,使设备恢复到正常的运行状态。

在执行拆卸操作之前,工程师需要确定可行且最优的拆卸顺序[1],这有利于人力和物力的合理调度,缩短维修时间,提高维修效率。而寻找最佳的拆卸顺序是一个拆卸序列规划问题。然而由于设备的复杂约束,拆卸序列规划是一个具有挑战性的组合优化问题[2]。

早期的拆卸序列规划研究主要倾向于图论研究,如与或图、有向图和Petri网等方法。虽然这些图适合数学分析,但随着零部件数量的增多,问题的求解难度呈指数增长。于是许多学者利用图形表示和启发式算法相结合以解决该问题[3]。常见的启发式算法有遗传算法[4,5]、粒子群算法[6]和蚁群算法[7]等。

目前,拆卸序列规划的研究主要集中在串行拆卸,即仅有一个操作者将零部件依次顺序拆卸,而并行拆卸允许多人执行不同的拆卸任务。

在实际应用中,异步并行拆卸对于大型复杂设备的拆卸更具有重要意义。然而,异步并行拆卸存在并行拆卸序列长度不确定、非线性、拆卸操作区域干涉等问题,因此,异步并行拆卸比串行拆卸更复杂。

郭砚荣等人[8]提出了基于分布估计算法来求解并行拆卸序列规划,但拆卸时间只考虑了零件的基本拆卸时间,而拆卸零件的准备时间也影响任务的完成时间。邓明星等人[9]构建了异步并行拆卸的数学模型,使用改进的遗传算法进行了求解,以方向改变作为准备时间。ZHU J F等人[10]提出了双链编码方法和译码算子,使用改进的蛙跳算法优化序列。郭钧等人[11]以拆卸时间最短、利润最大为优化目标,设计了三层链表的编码方法,并使用改进的生物地理优化算法进行了求解。

上述研究虽然取得了很好的结果,但是还存在以下问题:(1)在拆卸准备时间上主要考虑了方向和工具改变造成的时间,对于体积较大的设备,拆卸工位的移动时间没有考虑;(2)拆卸过程中假设无操作空间区域干涉,而在实际拆卸中工作区域的干涉必然导致拆卸不能按计划进行[12];(3)许多算法在求解含有大量零部件的复杂设备时,收敛速度慢,易陷入局部最优,寻找到最优值的概率低。

引力搜索算法(GSA)是模拟个体之间由万有引力引起相互作用的优化算法[13]。由于GSA具有良好的收敛特性和参数少的优点,它已广泛应用于解决多个研究领域的组合优化问题。

在现有研究的基础上,笔者综合考虑拆卸作业空间冲突和零部件的几何约束关系,分析影响拆卸时间的多个因素,并提出改进的引力搜索算法;最后,通过实例对改进的引力搜索算法求解异步并行拆卸序列规划的优越性进行验证。

1 问题的描述

1.1 优先约束模型建立

要获得一个可行的拆卸序列,零部件之间的几何约束和工作区域冲突是必须要考虑的。几何约束是指设备中紧固件对零件的约束,以及零件沿d(d=±x,±y,±z)方向移动中受到其他零件的约束;工作区域冲突是指在并行拆卸过程中,参与拆卸的操作者所需工作空间上的干涉。

有向图能简洁有效地表达零部件之间的几何约束关系,零部件的拆卸有向图如图1所示。

图1 拆卸有向图

在图1中:节点表示零部件,有向边的始端零部件约束箭头指向的零部件。为了适应多个零部件一起拆卸的情况,图1中又引入了组合节点的概念。如组合节点6表示其内部包含的零部件作为一个整体进行拆卸。在图1中:使用粗实线来聚合有向线,使有向图更简洁。

工作区域的干涉关系通过文献[14]提出的工作区域碰撞矩阵得到。

为了便于计算机处理分析,笔者将几何约束关系和工作区域冲突转变成矩阵的形式,数学表达式如下所示:

Mp={bi,j}n×n,Mc={ai,j}n×n

(1)

式中:n—零部件个数;Mp—几何约束矩阵;Mc—工作区域冲突矩阵。

其中:

1.2 待拆卸零部件集合的获取

笔者以维修目标件为起始点进行逆向递归搜索,以此来获取待拆卸零部件。设S为待拆零部件集合,搜索集合S1,优先集合S2,其具体步骤如下:

步骤1。把检修的目标零部件加入S1、S中;

步骤2。判断S1是否为空集,如果为空,执行步骤5;否则,根据Mp搜索出S1中零部件的优先零部件,并将其放入S2中;

步骤3。判断S2是否为空集,如果是执行步骤5;否则,将S2去重,然后把S2中与S中有交集的部分从S2中删除,并把S2中的零部件放入S中;

步骤4。让S2替换S1,使S2中的零部件成为新的搜索集合S1,返回步骤2;

步骤5。输出待拆卸集合S。

1.3 数学模型

异步并行拆卸序列规划问题可描述如下:设设备有s个待拆卸零部件,以总体拆卸时间最小为目标,并行序列总数为r,且满足优先约束关系。

根据所描述问题,笔者做出以下假设:

(1)每个拆卸任务不可中断;(2)拆卸过程无破坏;(3)每个操作者均可以独立完成所分配的拆卸任务;(4)不同的操作者拆卸相同的零部件所用的基本拆卸时间相同。

根据上述问题描述,建立数学模型如下:

操作者之间无拆卸工作区域冲突满足条件:

stpi≥etpj或stpj≥etpi,pj∈W[pi]

(2)

式中:stpi—拆卸零部件pi的开始时间;etpj—拆卸零部件pj的结束时间;W[pi]—零部件pi的工作区域冲突零部件集合。

零部件之间满足几何约束条件:

stpi≥TC[pi],∀pi∈S

(3)

式中:TC[pi]—零部件pi的优先零部件集合中最大结束时间;S—待拆卸零部件集合,S={p1,p2,…,ps}，s—为了拆卸目标零部件必须要拆卸的零部件的数量。

目标函数:

(4)

结束时间为:

(5)

开始时间为:

(6)

(7)

(8)

式(6～8)表示不同约束情况下的开始时间计算公式。

准备时间为:

(9)

其中:

(10)

(11)

式中:dj-1,j—操作者k移动到下一个拆卸任务所需的距离,它由零部件之间的欧拉距离确定;vk—操作者k的移动速度。

根据不同的工具类型,拆卸工具单次变换时间标准如表1所示。

表1 拆卸工具变换时间标准 (单位:s)

2 改进的引力搜索算法

在GSA中,搜索空间中的每个个体都作为一个待优化的解决方案,并根据其质量衡量解的优劣。在迭代的过程中,低质量的个体会向高质量的个体移动,在该过程中寻找最优值。

由于标准的引力搜索算法是用来解决连续优化问题,因此笔者提出了改进的引力搜索算法,以适应异步并行拆卸序列规划的离散性,并对其进行求解。

2.1 个体位置的编码和初始群体的产生

有效的编码方式可以避免不可行序列的产生。笔者针对异并行拆卸序列的特点,采用两段式编码结构来构成个体的位置:X={X1,X2}。X1={p1,p2,…,pi,…,ps}代表一个可行拆卸任务序列。X2={k1,…,ki,…,ks,}代表操作者序列,其中ki∈{1,2,…,r}。两个序列中相同位置的元素是一一对应的,即零部件pi由操作者ki拆卸。

一个可行个体的生成步骤如下:

步骤1。更新几何约束矩阵Mp,Mp只包含待拆卸零部件集合S中零部件之间的几何约束关系;定义拆卸任务序列X1,当前可拆卸集合A,X1=Ø,A=Ø;

步骤2。根据几何约束矩阵Mp获得当前可拆卸零部件集合A;

步骤3。从A中随机选择零部件pi放在X1的第一个空缺位置;

步骤4。更新几何约束矩阵Mp,将pi所在的列置零,解除对其他零部件的约束;

步骤5。判断集合A是否为空,如果是，执行步骤6,否则执行步骤2;

步骤6。根据操作者的数量随机产生X2;

步骤7。输出结果X。

假设种群规模为N,重复以上步骤1～7N次即可初始化种群。种群中第i个粒子表示为Xi=(X1,X2),i=1,2,…,N。

2.2 个体位置的解码

根据异步并行拆卸的特点,操作者k完成一次拆卸任务后,由于几何约束和空间区域干涉可能需要等待其他操作者完成任务之后才能继续拆卸,上述情况对异步并行序列的求解造成困难,因此,笔者提出了一种高效的解码方法。

求解零部件结束时间的具体流程如下:

步骤1。定义F为已拆卸零部件集合,ck为操作者k正在执行的任务编号;F=Ø,ck=1,k∈{1,2,…,r};

步骤2。根据个体的编码X,确定每个操作者的拆卸任务序列;

步骤10。若操作者k所有拆卸任务已完成,则该操作者停止拆卸,否则ck=ck+1;

步骤11。若所有零部件的完工时间已被求出,结束解码过程,否则返回步骤3。

2.3 个体的质量

较重质量的个体表示更有效的解决方案。通过以下公式更新质量:

(12)

(13)

式中:fi(t)—个体i在第t代的目标函数值;worst(t)—最差适应度值;best(t)—最佳适应度值;Mi(t)—第i个个体的质量。

其中:

best(t)=min{fi(t)},j∈(1,…,N)worst(t)=max{fi(t)},j∈(1,…,N)

(14)

2.4 个体的进化

为了在全局探索和局部优化之间达到平衡,GSA中只有Kbest中的个体作用于其他个体,使种群中的个体向更优的个体移动。Kbest是一组较大质量个体的集合,并且随着迭代的进行而减少。

笔者采用交叉的方式更新个体,根据个体质量的大小采用正比例选择策略从Kbest中选择个体来构成交叉集合G,针对两段式编码结构形式分别对X1、X2采用不同的交叉策略来保证新个体的可行性。

在第t代,Kbest中个体的数量为b,把即将更新的个体放入Kbest中,Kbest={KX1,KX2,…,KXb+1}。个体的质量在数值上等于个体的选择概率。

根据下式确定Kbest中每个个体的累计概率:

(15)

式中:Pi—Kbest中第i个个体的累计概率,i=(1,2,…,b+1);Mj—Kbest中第j个个体的质量。

设初始值P0=0,产生s个随机数ξa,ξa∈(0,Pb+1),a=1,2,…,s。当Pi-1≤ξa≤Pi,则从Kbest中选择个体KXi,并把其放入交叉集合G中。每一个ξa对应Kbest中的一个个体,质量越大,被选择的次数越多。最后G={GX1,GX2,…,GXs}包含s个个体。

每个GXi的X1和X2中的相应变量分别产生新解决方案中的一个变量。

关于X2交叉更新的数学模型如下:

(16)

X2采用上述模型的交叉方式,但对于X1需要采用优先关系保留的交叉方式,使交叉后的序列依旧满足优先关系。

X1的具体交叉方法如下:从G中选择个体GXi,然后在GXi的X1中从左到右寻找新个体中未出现的变量,把找到的第一个变量放在新个体的X1的第一个空缺位置;遍历G中的每一个个体重复交叉过程,直到完整的X1的生成。

生成新个体的两段式编码对应的交叉示意图如图2所示。

图2 交叉示意图

在图2中,操作者序列无优先拆卸关系,其元素来自交叉个体对应位置上的元素。

对于X1,其步骤为:(1)GX1的X1的第一个元素1被选择;(2)元素3未在新个体的X1中,且按从左到右的顺序被首先找到,因此,把3放在新个体的X1的第一个空缺位置。

2.5 逃脱算子

算法在搜索最优解的过程中,当种群中的粒子全部聚集到一起时,种群就会陷入局部最优解。

为了在种群陷入局部最优时种群具有一定的寻优能力,笔者提出了逃脱算子。在种群收敛时:

(1)从当前种群中选择c1个优质解加入交叉集合G中;

(2)根据第2.1节新生成c2个新的解作为多样性解放入交叉集合G中;

(3)按照第2.4节所述方法更新个体。

值得注意的是c1+c2=s。当种群中worst(t)等于best(t)时,认为算法已经陷入局部最优。

2.6 算法流程

综上所述,笔者在综合考虑各类因素的情况下，提出一种改进算法。

算法的流程图如图3所示。

图3 算法流程图

3 实验及结果分析

笔者以水轮机主轴密封为例进行实验,以验证笔者所提GSA算法的有效性。

所有的试验都是在MATLAB R2019b软件上进行算法编程,求解环境为Win10 Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz。

水轮机主轴密封爆炸图如图4所示。

图4 水轮机主轴密封爆炸图

水轮机主轴密封有向图如图5所示。

图5 水轮机主轴密封有向图

零部件的拆卸信息如表2所示。

表2 零部件的基本拆卸信息

拆卸的主要参数是指定的目标零部件x和并行度r。

根据不同的操作者数量和维修的目标零部件共设置4个案例,设操作者的移动速度为0.5 m/s,各案例的基本信息如表3所示。

表3 测试案例的基本信息

3.1 参数分析

从上述内容可知,c1和c2的取值会影响种群优质解和多样性解的平衡,进而影响最优值的求解。为了确定合适的c1和c2,对比5组不同的值进行实验分析。

每组的取值如表4所示(其中,c1、c2取整数)。

表4 5组c1、c2的取值

以T2为实验对象,种群大小为20,每组运行10次,算法迭代100次,每组得到的10个解的分布如图6所示。

由图6可知:c1=0.1×s时算法没有找到最优的解,因为当c1太小时,整个交叉集合G中优质解的个数太少,种群依旧处于全局探索阶段;

图6 不同c1值的运行结果

当c1在0.2×s到0.6×s之间时,随着c1的增大,种群开始局部搜索并取得较好的解,而在c1=0.4×s时算法在全局探索和局部寻优之间取得了平衡,求解出了良好的解;

当c1=0.8×s时,解的最优值很差,这是因为种群缺乏多样性易陷入局部最优。

因此,改进引力搜索算法中设置c1=0.4×s,c2=0.6×s。

3.2 算法对比及结果分析

为了进一步验证笔者所提算法的优越性,笔者将该算法与SSO[15]和GA[16]算法进行了对比。

根据表3所示案例进行了测试,种群大小为20,每个算法独立运行20次,迭代次数设置为100。对比算法采用相同的问题模型、编码方式和解码规则。

不同算法最优值的收敛曲线如图7所示。

图7 3种算法在不同测试案例中最优值的收敛曲线

各组案例的测试结果如表5所示。

表5 3种算法在不同测试案例中的对比结果

在测试T1时,由于拆卸规模过小,3种算法寻到的最优值近似,但GSA整体质量较好;

在测试中等规模T2时,GSA能够求解到更好的完工时间,但运行时间大于SSO;

通过测试T3和T4,在求解大规模案例时,GSA的最优值、平均值明显优于其他2种算法,并且随着拆卸人员的增加,拆卸完成时间明显缩短。

4 结束语

针对异步并行拆卸序列规划复杂的建模和求解效率低的问题,笔者考虑了实际拆卸中多人操作空间区域干涉的问题,构建了符合实际拆卸所花费时间的优化目标模型,对异步并行拆卸序列规划的拆卸模型和求解算法进行了研究,提出了一种基于改进引力搜索算法的异步并行拆卸序列规划方法。

首先,建立了优先约束模型,逆向搜索出了最小待拆卸零部件集合;然后,建立了异步并行拆卸序列规划的数学模型,构造了其编码和解码方法;最后,以水轮机主轴密封检修为例进行了实验,以验证GSA算法的有效性,并将其结果与采用传统算法所得结果进行对比,以证明新方法的优越性。

研究结论如下:

(1)基于GSA在解决组合优化方面的优势,提出了改进的引力搜索算法;将所提算法与SSO和GA算法进行了对比。测试结果表明,在求解大规模案例时,GSA的最优值、平均值明显优于其他两种算法,并且随着拆卸人员的增加,拆卸完成时间明显缩短;

(2)通过水轮机主轴密封实例,验证了所提算法在求解大型复杂设备维修拆卸中的有效性,所得到的结果可以很好地指导工业应用中的维修拆卸。

在未来,笔者将要研究不确定因素,以建立一个随机的拆卸序列规划模型,如拆卸零部件的质量、操作人员的熟练程度、拆卸零部件的状况等,使拆卸模型更加符合实际工业现场。