基于改进鲸鱼优化算法的装配线再平衡方法*

郭 宏,闫炳南,罗 雷,冒 源,原 超,徐 壮

(1.太原科技大学机械工程学院,太原 030024;2.山西平阳重工机械有限责任公司,侯马 043003)

0 引言

装配线平衡问题(assembly line balancing problem,ALBP)主要是研究在满足各类约束的前提下,将各装配任务分配到工作站,来实现减少成本和提升效率的目的[1]。

当前,已有许多学者对装配线平衡问题进行了较深入地研究。ALBUS等[2]采用一种基于混合整数规划的线性优化方法来解决装配线的动态资源分配问题。KATIRAEE等[3]提出了一个双目标线性规划模型来解决装配线平衡问题。黄辉等[4]提出一种混合算法来解决多目标双边装配线平衡问题。赵联鹏等[5]提出了一种新的搜索算法去求解装配线平衡问题,以提高装配线效率。

现有的大多数模型都建立在确定需求的情况下,虽然一些模型考虑了需求的变化,但很少考虑再平衡成本的问题。李金霖等[6]使用多能工应对需求变化的混装线平衡问题,以最小化人工成本并满足不同情境的需求。CHICA等[7]提出了一个用于装配线平衡的多目标模型,并使用自适应进化算法提高效率。张于贤等[8]为了解决算法的最优解存在着达不到装配线平衡最优准则且无法对瓶颈工序进行操作分析的情形,提出了算法和IE技术两阶段组合求解法,求出了一个能满足生产需要的有效可行解。

针对不确定需求下的再平衡问题,本文采用只改变工作站数量以及重新规划边界的方式来建立装配线模型,并提出了一种改进多目标鲸鱼的优化算法来求解该模型。最后,与其他多目标算法进行对比验证了此算法的可行性。

1 问题描述与数学建模

1.1 可调整产能装配线平衡问题描述

当订单需求改变时,装配线的生产周期也需要随之变化。此时,有必要重新平衡装配线。但为了减少成本,设施布局应避免改动。在不改变装配线上工位设备顺序的前提下,可以通过增加或减少工作台的数量以及重新规划工作台的边界来实现不同的任务分配。如图1所示,分为两种情境,生产周期C=30和生产周期C=50,已知每个设备所分配任务时间,要求每个工作站所有设备任务时间之和不大于周期时间。当生产周期较小时(图中举例为C=30),设备1和2分配给工作站1 的工人,设备3,4,5分配给工作站2的工人;当需求减少时,生产周期增加(图中示例为C=50),工作站1的工人操作设备1和2仍有余力,此时将设备3也交给此工人操作。

本文所述的装配线平衡问题可描述为:在已知两个或多个不同需求情境的条件下,如何完成任务分配,以最小化多个需求下平均工作站数量和平均时间均衡指数。

为有效描述该问题,做以下基本假设:①装配图已给定且其中不存在回路;②为了减少成本,同一个任务只能分配给同一个设备;③每个任务都对应一个设备;④可调整产能装配线全部使用多能工进行装配;⑤普通工人的每天工作时间为T小时,多能工每天可用装配时间设为T/2小时,多能工每天的工资水平是普通工人的2倍。

1.2 符号说明

N为装配顺序图中任务的数量,N*为所有任务所组成的集合,S*为所有需求情境组成的集合,Ps为需求情境s发生的比例,Ds为情境s下每天的需求数量(单位:件/天),T为1个工人1天可使用的工作时间,Cs为需求情境s的生产节拍,Cs=T/Ds;Tsj为需求情境s下第j个工作站的总体任务时间,Lsj为情境s下第j个工作站的时间均衡指数,Lsj=(Cs-Tsj)/Cs;H*为已使用设备所组成的集合,xih为任务i被分到第h个设备,则为1,否则为0;yhjs为设备h在情境s被分到第j个工作台,则为1,否则为0。

1.3 建立数学模型

建立变产能装配线数学模型,其目标函数为:

minF={f1,f2}

(1)

式中:

(2)

(3)

约束条件如下:

(4)

(5)

(6)

(7)

(8)

(9)

xih∈(0,1),∀i∈N*,∀h∈H*

(10)

yhjs∈(0,1),∀h∈H*,∀s∈S*

(11)

式(1)～式(3)表示最小化每个场景中使用的工作站数量的平均值,以及每个场景下每个工作站的时间平衡指数。式(4)表示每个任务都对应一个设备。式(5)表示每个站点上都只有一个设备。式(6)表示任务优先顺序约束,每个任务在生产线上的工位必须在它所有前置任务完成之后。式(7)表示在给定情境下每个位置只能分配到一个工作站,不同的工作站之间不能共享同一个设备。式8)表示每个工作站的所包含的区域必须是连续。式(9)表示生产节拍约束,这意味着必须完成每种情况下所需的任务。式(10)和式(11)分别表示xij和yhjs的值范围。

2 算法构建

本文研究的装配线平衡问题属于NP难问题,而群智能算法很适合解决这一问题。鲸鱼优化算法(WOA)是一种群智能算法,具有结构简单、计算方便的优点,在工程领域已广泛应用[9]。

为更好地求解变产能装配线模型,本文提出了一种改进多目标鲸鱼优化算法。首先,使用混沌映射初始化种群;其次,在位置更新时对搜索步长进行动态调整来提高算法的效率,并使用新的头鲸选择方式来避免局部最优;最后,采用改进拥挤距离来更新外部档案以得到最优解集。

2.1 鲸鱼优化算法(WOA)

鲸鱼优化算法(WOA)是一种新的元启发式优化算法,WOA的主要灵感来自座头鲸的特殊捕食行为。鲸鱼在猎物周围以螺旋形移动,在觅食时使用缩小的圆圈向猎物移动,这种行为被称为泡泡网觅食。

2.1.1 包围捕食阶段

WOA通过在螺旋模型和收缩包围猎物之间进行50%的选择概率来模拟这种狩猎机制,以生成当前鲸鱼的新位置。通常,包围机制的数学表达式为:

D=|C·X*(t)-X(t)|

(12)

X(t+1)=X*(t)-A·D

(13)

A=2a×r-a

(14)

C=2×r

(15)

(16)

式中:X为位置矢量,X*(t)为一个向量,包含迄今为止找到的最佳位置;t为当前迭代次数,||为绝对值运算,·为逐个元素相乘,A和C为系数变量,a为一个随着迭代从2不断线性减小到0的参数,r为[0,1]范围内随机生成的数。

2.1.2 螺旋捕食阶段

WOA试图用螺旋模型来模拟鲸鱼的螺旋形运动,以得出猎物和鲸鱼之间的位置。螺旋形状的数学表达式为:

D=|X*(t)-X(t)|

(17)

X(t+1)=D*·ebl·cos(2πl)+X*(t)

(18)

式中:b为一个常数,用来描述对数螺旋运动;l为一个1和-1范围内的随机数。

2.1.3 随机搜索阶段

为了使WOA能够探索优化问题搜索空间内的大部分区域,它从当前种群中随机选择一个个体,将当前的鲸鱼移向它。如果|A|>1,则当前鲸鱼将移向从种群中随机选择的鲸鱼。该阶段的数学公式为:

X(t+1)=X*(t)-A·D

(19)

D=|C·Xr(t)-X(t)|

(20)

式中:Xr(t)为从当前种群中随机选择的个体。

2.2 头鲸选择方式

在WOA的进化过程中,头鲸在逃离局部最优解方面发挥着重要作用。所以本文通过提出一种成对竞争机制来选择更好的头鲸,以其来指导鲸鱼种群的更新。

在成对竞争机制中,鲸鱼个体通过竞争机制更新,而不是使用全局和单个最优个体,从而大大提高了种群的多样性,避免过早收敛。具体来说,在成对竞争机制中,从当前种群中随机配对选择个体进行竞争,并通过向优胜者学习来更新竞争中的失败者,而优胜者则直接传递给下一代种群。

假设种群P(t)中有N个个体,每个个体都有一个n维位置Xi(t)=(xi,1(t),xi,2(t),…,xi,n(t))和n维速度向量Vi(t)=(vi,1(t),vi,2(t),…,vi,n(t))。在第k轮比赛中,胜利者和失败者的位置和速度分别表示为Xw,k(t)、Xl,k(t)、Vw,k(t)和Vl,k(t),其中k=1,2,…,N/2。在第k轮比赛后,失败者的速度将使用以下策略进行更新:

(21)

而失败者的位置可以根据新的速度更新:

Xl,k(t+1)=Xl,k(t)+Vl,k(t+1)

(22)

在创建精英种群之后,将在其中的鲸鱼个体之间进行成对竞争,获胜者将被用来指导当前种群中鲸鱼个体的移动方向。对于每一次竞争,给定要更新的种群中的一个鲸鱼个体p,从精英种群中随机选择两个精英鲸鱼个体a和b。分别计算a、b和p之间的角度,角度较小的精英个体获胜,这样鲸鱼个体p将从更接近其收敛方向的精英个体学习。具体示例如图2所示。

图2 成对竞争机制示例

图2中Xi是要更新的解决方案;X1和X2是从精英列表中随机选择的精英个体;θ1是X1和Xi之间的角度;θ2是X2和Xi之间的角度。因为θ2<θ1;X2是获胜者,被选为领导者。

2.3 外部档案更新策略

外部归档是多目标鲸鱼算法(MOWOA)中常用的模块,在更新外部档案的策略方面,有许多选择,如网格选择、非支配排序、高效非支配排序(ENS)和拥挤距离法等。

由于拥挤距离法可以更好地维持种群中个体的多样性,所以本文使用拥挤距离法更新外部档案。然而,使用传统的拥挤距离来反映密度在某种程度上是有缺陷的,所以本文采用一种新的方法来计算距离。其具体方法如图3所示。

图3 拥挤距离

图3中有3种解决方案,用x1,x2,x3表示;目标数为2。解x2的传统拥挤距离为CD(x2)=R1+R2+S1+S2。事实上,只要x2位于边界框中,其中x1和x3是对角顶点,CD(x2)的值就不会改变。为了解决这个问题,本文使用一种改进的拥挤距离,其表达式定义为[10]:

(23)

式中:M为目标数,Si和Ri为图3所示的距离。

2.4 多策略改进多目标鲸鱼优化算法

原始WOA算法通常使用随机生成初始种群的方法。然而根据现有研究,初始种群将直接影响算法的计算效率。因为混沌序列有较强的随机性以及整体稳定的特性,所以本文使用混沌序列初始化。其中,Tent映射公式为:

(24)

式中:X(t)∈[0,1]。

在WOA中,因子a是一个距离控制参数,从2线性减少到0。因子a随固定步长变化,因此当迭代次数较大时,大多数迭代将在找到最佳解之前结束,否则将消耗大量迭代次数而没有任何进展。所以,本文设计了新的动态控制系数,使其与迭代次数成比例减少。其数学表达式如下:

(25)

(26)

式中:r是一个介于0和1之间的随机数。在前面的方程中,我们试图控制距离控制参数a以值2开始,该值随着迭代逐渐减小,并乘以0和1之间的随机数r,直到达到标准参数无法达到的区域。

步骤1:初始化。首先初始化外部档案,设置初始容量为C,并在满足优先关系前提下使用式(24)生成N个初始个体X1,X2,…,XN;

步骤2:确定非支配解集。对每一个鲸鱼个体位置Pi计算适应度函数,并对其进行Pareto非支配排序,得到非支配解集;

步骤3:更新外部档案。使用式(23)计算前C个个体,并将其加入外部档案;

步骤4:头鲸选择。使用竞争机制进行头鲸选择, 首先,根据拥挤距离排序从外部档案中选择出前10个个体并组成集合E,从E中随机选择两个个体X1和X2;然后,从当前种群中取出一个个体Xi,计算X1和Xi之间的角度θ1以及X2和Xi之间的角度θ2,如果θ1<θ2,X1为领导者X*,否则,X2为领导者X*;之后,将X*代入到式(13)或式(18)或式(19)中得到X(t+1),并将其添加到集合X′,最后,判断集合X是否为空,为空则重新从E中随机选择两个个体循环执行,否则返回新种群X′;

步骤5:鲸鱼位置更新。根据式(25)和式(26)更新参数a和C,并相应地更新算法中A、l和r等相关参数。然后根据p和|A|的大小来选择相应的更新方案,并使用步骤4选出的头鲸来指导更新。

MIMOWOA算法流程图如图4所示。

图4 MIMOWOA算法流程图

3 仿真实验分析

3.1 参数分析

使用python实现上述算法程序,并在CPU为CMD 6-Core,内存为8 GB的PC上进行。实验参数设定为种群规模30,迭代次数1000。实验选用SALBP-1标准算例库中的9个不同规模的数据进行实验。

3.2 实验对比

为了验证此算法的优越性,将它与原有的多目标鲸鱼优化算法进行比较,求解结果如表1所示。

表1 不同问题规模下的结果对比

表1中分为小,中,大3种不同任务数量的任务,给定相应的周期时间,对比MOWOA和MIMOWOA 两种算法对同一问题的计算结果。从表中可以明显看出,MIMOWOA算法得出的站点数量和均衡指数都低于MOWOA算法。如图5所示,为了更加直观地体现出优越性,对比任务数量为101的帕累托前沿。其中,MIMOWOA在两个目标函数方向都能实现帕累托最优。这主要由于MIMOWOA采用动态距离控制系数以及成对竞争机制后,在一定程度上提高了装配线的均衡性。

图5 任务数量为101的帕累托前沿

为了进一步验证算法的有效性,将改进算法与其他多目标优化算法进行比较。其中将算法性能的评价指标设定为帕累托解的个数(NF)、解的均匀性(ES)和非支配解的最优度(DPS)[11]。各项评价指标计算为:

(1)非支配解的数量:

NF=|Np|

(27)

式中:NF为算法得到的帕累托解的数量,NF值越大,算法越优。

(2)非支配解最优度:

(28)

(3)解的均匀性指标:

(29)

(30)

式中:Di为xi与其他相邻解的距离。ES越小,说明解越分散。

实验包含3种不同规模的任务数量,每个任务重复15次,选取平均值作为最终结果如表2所示。MW为改进多目标鲸鱼算法,NS为遗传算法,MP为粒子群算法,加粗字体表示不同问题规模下各项评价指标的最优值。

表2 3种算法的数值结果对比

分析表2可得:

(1)分析评价性能NF的值可知,MIMOWOA得到的帕累托解的数量明显更多。

(2)分析评价性能DPS的值可知,MIMOWOA得到的DPS值较其余算法更大一些,表明MIMOWOA的全局搜索性更好。

(3)分析评价性能ES的值可知,MIMOWOA得出的解的分布与其他算法相比较均匀。这是因为MIMWOA采用了拥挤距离排序的外部档案更新策略,使解的分布更均匀。

总而言之,MIMOWOA算法在解的数量或者质量方面都明显优于其余两个算法,这也验证说明了其求解ALBP问题时的可行性。

4 结束语

本文研究了可调整产能装配线平衡问题,采用只改变工作站数量以及重新规划边界的方式来建立装配线模型,降低了装配线再平衡成本。并针对该模型构建了一种改进多目标鲸鱼优化算法,在原始鲸鱼算法中使用混沌映射初始化种群,并在鲸鱼搜索过程中引入动态距离控制系数和成对竞争机制来提高算法的收敛速度。最后用实验验证了所提出的算法在解决可调整产能装配线平衡问题上的可行性和有效性。

当然本文只考虑了在两种周期下进行转换的装配线方案,后续可以进一步开展多周期转换的研究。