许晓伟,于海武,刘 超,张海峰
(1.合肥工业大学 电气与自动化工程学院,合肥 230000;2.中国科学院合肥物质科学研究院先进制造技术研究所,常州213164;3.中国科学技术大学 工程科学学院,合肥 230000;4.中国科学技术大学 信息科学技术学院,合肥 230000)
基于改进遗传算法的无刷电机装配线平衡优化
许晓伟1,2,于海武2,刘 超3,张海峰4
(1.合肥工业大学 电气与自动化工程学院,合肥 230000;2.中国科学院合肥物质科学研究院先进制造技术研究所,常州213164;3.中国科学技术大学 工程科学学院,合肥 230000;4.中国科学技术大学 信息科学技术学院,合肥 230000)
为提高无刷电机装配线的生产效率,减少在制品积压,提出了一种改进遗传算法对其进行优化。建立了以工位和平滑指数相结合的多目标优化数学模型,应用双种群自适应遗传算法在MATLAB中编程,对无刷电机装配线平衡问题进行仿真和优化。结果表明,优化后的装配线提高了各个工位的生产效率,减少了在制品积压,验证了算法的有效性和可行性。
无刷电机;装配线平衡;遗传算法;多目标;双种群
在制造行业中,装配线平衡[1~3](Assembly Line Balance,ALB)问题无论是在规划设计阶段还是在生产管理中都是一个受到重视的问题,它关系到装配线的生产效率和产品质量的稳定,是一个不断发现、不断改进、不断完善的过程。ALB问题的实质是装配线各工位的协调与配合,在满足一定优先关系约束条件下,使各工位的作业时间总和尽可能相当,减少在制品积压,提高生产效率。根据装配线优化目标函数的不同,ALB问题可以分为三类:1)给定节拍时间(CT),求最小工位数m。2)给定工位数m,求最小节拍时间(CT)。3)工位数m和生产节拍CT已确定,求最小平滑指数SI(Smooth Index)。针对ALB问题,国内外学者做进行了较多此方面的研究[4~11]。文献[6]运用遗传算法和工业工程方法对某发动机公司缸盖装配线进行了研究分析;文献[7]运用启发式算法对空调电路板组装线进行平衡计算和改善,取得了满意的效果;文献[8]运用蚁群算法对第一类装配线平衡问题进行了研究;文献[9]运用一种缩放适应度的遗传算法对第二类装配线平衡问题进行了研究,提出了一种较好的解决方案;文献[10]运用自适应遗传算法,对服装生产的缝制流水线的平衡问题进行了研究;文献[11]受鳗鱼效应的启发提出了一种针对装配线平衡问题改进的遗传算法。无刷电机装配线同样存在平衡问题,将平衡优化算法应用于无刷电机装配线,还少有报道。
本文将对无刷电机装配线平衡问题进行研究,通过建立以工位数和平滑指数相结合的多目标优化数学模型,采用双种群自适应的遗传算法进行优化,以期达到工位数最少,负荷均衡,从而提高装配线生产效率,减少在制品积压。
某公司太阳能用无刷电机[12]装配线由定子、转子和总装配三部分组成,是典型的离散型流水线装配线。该无刷电机装配线的具体情况如下:
1)生产纲领:年产20万套;
2)工作条件:8小时/班,2班/日,250日/年;
3)根据工艺流程,通过调研、论证,时间测定,确定的无刷电机装配工艺如表1所示;
4)生产节拍和生产效率计算如表2所示;
5)无刷电机装配线优先关系图如图1所示。
图1 无刷电机装配线优先关系图
表1 无刷电机装配工艺
表2 装配线计算
图中的节点(圆圈)表示工序任务及其序号,节点上面的数字表示该工序的作业时间,箭头表示工序之间先后约束关系。
一般情况下,装配线生产效率在50%~60%是一种没有人和科学管理意识的粗放式生产,60%~70%存在人为平衡的因素,70%~85%是在科学管理的原则下进行的,大于85%时生产过程就是按照“一个流”的方式进行的, 由表二可知该装配线生产效率为61.69%,说明各工序间存在不平衡现象,本文正是在此背景下,对无刷电机装配线第一类平衡问题进行了研究。
一个平衡的装配线,不仅要求工位数最小,而且要考虑负荷是否均衡,而平滑指数SI越小,则表示装配线各工位的负荷越均衡,如式(1)所示。
其中,STj为分配到第j个工位的所有任务的加工时间和,CT为生产节拍,m为工位数。
本文将综合考虑工位数和平滑指数问题,采用线性加权和法将多目标优化问题转化为单目标优化问题进行求解。转化后的目标函数如式(2)所示。
其中,α、β为目标函数的权重,一般取α+β=1。若α>β,则表示工位数目标比平滑指数目标更重要,由于本文侧重于第一类平衡问题,所以取α=0.6,β=0.4。
约束条件为:
4)工序优先关系矩A=(aij)n×n,其中:
常规的优化方法基于梯度寻优技术,计算速度快,但要求优化问题具有可微性,且通常只能求得局部最优解;遗传算法适用于求解组合优化问题以及目标函数不可微或约束条件复杂的非线性优化问题。但常规遗传算法存在过早收敛,容易陷入局部最优解等问题。鉴于此,本文采用双种群自适应[13,14]的遗传算法来求解无刷电机装配线平衡问题,如图2所示。
图2 双种群自适应遗传算法流程图
3.1 编码
按照工序优先关系,采用实数编码。染色体的长度等于工序数,每个经过编号的工序对应于一个基因位,按工序优先关系图进行排列,以经典的Jackson生产线平衡模型为例(如图3所示),给出了两个染色体的编码如图4所示。
图3 Jackson生产线平衡模型
图4 染色体编码
3.2 初始化种群
在保证工序优先关系条件下,通过随机的方式生成初始种群,同时要保证初始化种群的多样性和差异性。
3.3 译码
根据编码的顺序,依次计算工序的累积作业时间Ti,并与生产节拍CT进行比较,当计算到第i个工序时,累积作业时间Ti大于生产节拍CT,则以前面i-1个编码对应的工序分配给第1个工位,依次进行计算、分配,直到把对应的编码中的工序分配完毕。以Jackson生产线平衡编码为例,假设生产节拍为10s,译码后的结果如图5所示。
图5 染色体译码
3.4 构造适应度函数
适应度函数也即评估函数,通常要满足单值、连续、非负、最大化等条件,本文中的目标函数为最小化问题,将其转化为最大化问题,可以构造适应度函数如式(3)所示。
3.5 选择操作
采用最优染色体保留与轮盘赌相结合进行选择。为了使进化过程中的最优解不被交叉或变异操作所破坏,种群中适应度最高的染色体不进行配对交叉而直接复制到下一代中,然后对剩余染色体进行轮盘赌选择,适应度大的被选择的概率越高。选择概率pi如式(4)所示。
其中fi为染色体i的适应度值,为群内所有染色体的总适应度值。
3.6 交叉与变异操作
对于标准遗传算法,交叉、变异概率为常数,不能很好的适应优化过程中参数变化问题。为此,本文采用了自适应交叉、变异概率,如式(5)、式(6),以保证算法在进化初期有较强的全局搜索能力,而在进化后期则集中于局部择优,保护优良染色体。
其中,pc为交叉概率,pm为变异概率,pcmax为最大交叉概率,pmmax为最大变异概率,fit'为要交叉的染色体中较大的适应度值,fitavg为种群平均适应度值。
交叉操作采用两点交叉法,从种群中任选两个染色体作为双亲,随机产生两个交叉点。假设染色体有M个基因,首先在[1,M-1]之间产生交叉点1,然后在[交叉点1,M]之间产生交叉点2。两个交叉点把染色体分为头部,身体,尾部3部分,交叉就是对两个染色体身体部分进行交叉。根据图6所示,父代染色体1需要交叉的基因为[3,5,7,9,6],在染色体2中搜索[3,5,7,9,6]的排列方式为[5,3,7,6,9],将其作为父代染色体1的身体部分,于是就产生了子代染色体1。父代染色体2采用同样的方法产生子代染色体2。
变异操作如图7所示。从种群中任选一个染色体,选择染色体中的一点进行变异,将变异点前的基因片段保留到子代染色体中,变异点后的基因片段根据工序优先关系重新排列。
图6 交叉操作
图7 变异操作
3.7 算法终止条件
当满足式(7)时,算法终止。
其中,fmax为最优染色体适应度值,favg为染色体适应度值的平均值,为极小值,这里取=0.001。
在MATLAB环境中编程,采用双种群自适应遗传算法对无刷电机装配线进行优化,双种群大小各为100,α=0.6,β=0.4,pcmax=0.4,pmmax=0.08,改进后的遗传算法运行结束后,得出的最优工序分配方案如表3所示。
表3 工序分配方案
表4 优化结果
图8 标准遗传算法与改进遗传算法迭代曲线
标准遗传算法和双种群自适应遗传算法迭代曲线如图8所示,可以看出标准遗传算法迭代曲线的适应度值在经过约90代进化后才趋于稳定,达到最优值,而双种群自适应遗传算法迭代曲线的适应度值随着进化代数的增加而迅速收敛,经过约40代进化后趋于稳定,达到了最优值,说明了改进后的遗传算法能够快速收敛找到最优解,验证了算法的有效性和可行性。
通过表4,我们可以看出优化后,无刷电机装配线的生产效率由61.69%提高到了84.12%,工位数由30个减少到了22个,装配线的平滑指数由25.13下降到了8.258,有效的提高了各个工位的作业效率。优化前、后的直方图如图9所示,可以看出各工位的作业时间更加均衡。
图9 无刷电机装配线优化前后直方图
本文对无刷电机装配线平衡问题进行了分析研究,提出了运用双种群自适应遗传算法对其进行优化。结果表明,改进后的遗传算法保证了种群的多样性,加快了算法的收敛速度,保护了优良个体,优化后的无刷电机装配线减少了在制品积压,提高了生产效率,验证了算法的有效性和可行性。
[1] 陈星宇.基于改进遗传算法的装配生产线平衡技术研究[D].上海交通大学,2011.
[2] 肖中华.基于改进遗传算法的汽车装配线平衡问题研究[D].武汉科技大学,2010.
[3] 赵云飞.基于遗传算法的生产线平衡改善研究[D].南昌大学,2014.
[4] Amen M.Heuristic methods for cost-oriented assembly line balancing:A comparison on solution quality and computing
【】【】time[J].International Journal of Production Economics, 2001,69(3):255-264.
[5] Bowman E H. Assembly-Line Balancing by Linear Programming[J].Operations Research,1960,8(3):385-389.
[6] 林秀木.汽车发动机装配线平衡优化研究[D].沈阳工业大学,2016.
[7] 唐海波,吴斌,王正兰.启发式算法的装配线的平衡改善应用[J].上海电机学院学报,2014(5):306-310.
[8] 毛凌翔,郑永前.蚁群算法求解装配线平衡第一类问题[J].计算机系统应用,2010,19(1):140-143.
[9] 张瑞军,陈定方,杨琴.用改进的遗传算法解决ALB问题[J].计算机工程与设计,2006,27(20):3731-3733.
[10] 梁会芹,费树岷.自适应遗传算法在服装生产流水线平衡问题中的应用[J].工业控制计算机,2009,22(11):57-59.
[11] 陈晓峰,肖田元,郝新,等.应用遗传算法解决装配线平衡问题[J].计算机工程与应用,2001,37(23):81-83.
[12] 张涛.无刷直流电机的设计与性能研究[D].河南理工大学,2012.
[13] 秦伟娜.基于多种群的遗传算法研究[D].山东师范大学,2009.
[14] 陈超.自适应遗传算法的改进研究及其应用[D].华南理工大学,2011.
An optimization for brushless motor assembly line balancing based on improved genetic algorithm
XU Xiao-wei1,2, YU Hai-wu2, LIU Chao3, ZHANG Hai-feng4
TP29
:A
1009-0134(2017)06-0055-05
2017-03-24
中国科学院青年创新促进会资助(2016387)
许晓伟(1982 -),男,河南平顶山人,硕士研究生,研究方向为电机及其控制。