基于遗传算法装配线平衡问题探究

1、基于遗传算法装配线平衡问题探究摘要：文中针对装配线平衡问题，提出了一种基于可行作业序列的多种群遗传算法。该算法依据可行作业序列产生 初始种群，并据此构造交叉、变异算子，以保证后代种群都 是可行解；而且多种群的遗传算法，扩大了搜索的空间范围, 所以可以有效的避免局部最优的情况发生，而且还能增强算 法的运行效率。文章在最后，用实例进行了运行效果的验证。abstract： for assembly line balancing problem in the text, put ting forward a viable job sequence-based multiple-population g

2、enetic algorithm. the algorithm based on feasible operating sequences produce initial population , and thus constructed crossover and mutation operator , to ensure future generations populations are viable solutions ； and multiple-population genetic algorithm broadens the scope of the search space,

3、so it can avoid local optimization , also enhance the efficiency of algorithms finally an illustrative example is given to testify the validity of this algorithm.关键词：装配线平衡；改进遗传算法；约束矩阵key words： assembly line balance； improved ga；constraint matrix中图分类号:f273文献标识码：a文章编号:1006-4311(2013) 05-0123-030引言自从装

4、配线平衡(assembly line balancing alb)问题被提出后，就一直为研究热点。在装配线上，工件一次进 入各个工位进行加工，如何在满足生产线节拍以及作业之间 优先顺序的情况下，组合并优化分配作业单元，使各个工作 站的工时尽可能相等，从而避免因资源过于空闲或忙碌而产 生不良后果，这就是装配线平衡问题(assembly line balancing problem, albp问题)1 o通常情况下，根据所 要优化的目标不同，可将装配线生产平衡问题分为两类2。第一类是在给定生产节拍、装配作业时间和作业逻辑关系的 情况下，求解最小工作站数；第二类是先给定工作站数目、 装配线的作业时间

5、和作业优先关系，来求出最小的生产节拍 及列出每个工作站内的作业分配情况，本文主要针对第二类 装配线问题进行研究。从实质上说，装配线平衡问题就是在一定约束条件下的 组合优化问题。现代用来解决此类问题的方法大致可分为如 下四类：数学规划方法；基于规划调度的优化方法； 启发式算法，如模拟退火法和遗传算法等；人工智能算法, 如神经网络等。余晓光等提出了一种禁忌搜索遗传混合算 法，提高了算法的运行效率3；蒋艳等引入小生环境的改 进遗传算法，进行了协同优化设计；肖中华等提出一种非标 准遗传算法，确保算法收敛到最有或近优解4。鉴于遗传 算法在实验及应用中取得的显著效果，本文采用多种群该进 行遗传算法来解决a

6、lb问题。1装配线平衡问题描述装配线平衡中，用m表示工作站数，n个作业元素，用 c表示生产节拍，作业所用时间ti表示第i个作业元素的作 业时间，工作站时间用t (sk)表示，sk表示所有分配给第 k个工作站作业的集合，则分配给第k个工作站的作业时间 为t (sk)二工iwkti；总作业时间为t二工ti。在进行alb规划，首先必须满足单元作业之间的先后顺 序约束条件，即某些作业之间在技术上存在先后的执行顺 序。采用矩阵来描述作业装配的优先关系，若装配线上有n 个作业，其优先关系矩阵为nxn的方阵，为p= (pij) nxn, 其中p«=l,若i为j的紧前作业元素0,否则(1)式中i,

7、j为作业元素序号。在对装配线的平衡效果进行评价时，基本的评价指标包 括：节拍、工位数、总空闲时间、平衡延迟、平滑性指标、 装配线利用率、装配线生产能力增长指标等等5。本文根 据所研究问题采用平衡延迟和平滑系数来。平衡延迟：p二x100% (2)平滑系数：si=h (3)这两个指标越小，越接近零，说明平衡效果越理想。2装配线平衡的遗传算法设计2.1编码 本文采用基于可行作业序列的原则来对ga进 行有效编码。按照装配关系优先关系矩阵中的作业元素的先 后顺序，将作业元素序号排成一列，每个作业元素对应一个 基因位，从而保证所有作业分配方案都是可行的，并且所有 可行的作业序列都有一定的概率被搜索到，在排

8、成列的工序 中，每个基因对应一个工序。这种编码方式对适应函数和算 子操作的适应性好。图1是经过编码的一个染色体图解，该 染色体说明了作业分配的先后顺序，以此为作业3、5、1、7、 2、 4、 6o2.2译码译码就是根据编码的方式，在满足约束的条 件下，将基因转换成装配线平衡问题解的形式，即在给定工 作站数目，不违反工序优先关系的情况下，事先预设一个节 拍ct,将一个时间较多的工作站中的元素和一个时间较少的 工作站中作业元素交换或转移，逐步增加各个工序工时，达 到优化均衡指数的目的。2. 3初始化种群种群的初始化一般要考虑种群个体的 多样性，本文参照文献(6),采用随机法，循环搜索，直至 产生n

9、 (p)个个体为止。2.4适应度函数适应度函数 这个概念用来衡量群体中各个个体在优化计算中能达到或 接近或有助于找到最优的优良程度，针对目标函数制定出适 当的适应度函数，是算法演化过程的驱动力，使种群不断地 向着优化的方向调整。在装配线平衡问题适应度函数的选择 上，一般是直接以待解的目标函数f(x)转化为适应度函数 fit (f (x),即令第i个个体的适应度函数为：fit (f (x) ti/mc (4)这种适应度函数简单直观，但存在一些问题，会使某些 待求解的函数值分布上相差很大，由此得出的平均适应度函 数可能不利于体现种群的平均性能，而影响算法的性能。此 处将适应度函数转换为：fit (

10、f (x) =l/l+y-zbbti/mc,(y?叟 0, v-xbbti/mc ?叟0)(5)其中y为目标函数zhbti/mc界限的保守估计值。2.5选择操作 在本文中采用比较常用的轮盘赌选择方法。许多的选择技术采用轮盘赌原理，个体的选择概率是基 于他们的性能的一些计算。实值范围一总和是所有个体期望 的选择概率的总和或当前种群中所有个体原始适应度的总 和。个体采用一对一方式映像到范围0, sum的一连续区间， 每一个体区间的大小与对应个体的适应度值相匹配，适应度 值越高，被选中的可能性就越大，进入下一代的概率就越大。每个染色体被选择的概率为:p=fit (f (x) /zbbfit (f (

11、x)(6)其中z表示种群中个体个数。2.6交叉操作采用两点交叉的方法，随机产生2个交 叉点，先在1, n-1之间随机产生第一个交叉点crossl,再 在（crossl, nt之间随机产生第二个交叉点cross20染色 体的交叉工作就是在随机产生的这两个点之间的部分进行 交叉变换的，图1、图2详细解释了具体的交叉过程。父代染色体parent 1要进行交叉部分的基因为2、6、4、 5；此基因序列在染色体parent2中的基因序列为2、4、6、 5；用染色体parent2中的序列代替parent 1中的序列，便 得到一个交叉的薪染色体（图3）。同理可得到另一个新的染 色体new2,见图4。2.7变异

12、操作变异操作，实际上是染色体按照小概率事件扰动产生的变化，能避免算法收敛于某一局部的最优 解，所以变异算子的设计对遗传算法的效果起着至关重要的 作用。变异算子按照一定的概率随机在当前的种群中选择染 色体完成变异的操作，然后产生一条新的染色体来替换原个 体。本文变异操作采用移位的方式实现。首先在1, n之间 产生一个随机数，例如6,表示第6个位置的基因变异，对 应基因为5,在根据作业的优先关系矩阵找出5的紧前工序3和紧后工序8,然后在工序3和8之间随机产生选择一个位置与基因5进行交换，即产生新的个体，如图5所示。2.8种群之间基因交换将两个种群间适应度最好的种 群基因进行交换，这样既能使算法的收

13、敛速度得到提高，同 时也保证了种群的多样性，有效的避免陷入局部最优。3算例验证现举例以说明算法的效果，主要工具为matlab2009,运 行环境为win7系统，硬件环境：cpu20ghz、2g内存。本文采用brahim rekiek参考文献中(7)列出的装配 生产线的各个工序和相应的工作时间来验证本文提出的改 进型遗传算法的可行性及有效性。图6表示各个作业的优先 作业顺序及作业时间，根据图6,应用改进遗传算法可以对 装配线的平衡问题进行优化求解。本文采用matlab编程来实现此遗传算法。算法设置的 运行环境如下：最大的进化代数为300；两个出事种群的个 数为150；种群1交叉概率为0. 85；

14、种群2交叉概率为0. 15； 种群1的变异概率为0. 2；种群2的变异概率为0. 05o表1 列出了实例运行的结果，如表1所示。借助工位工时的标准差，来与原方案比较在工位数相同 时的不同作业分配方案之间的优劣，发现用改进遗传算法得 到的作业分配方案的标准差均明显低于原作业方案的标准 差，与原方案相比较改进效果明显。从表1中可以明显发现，当工位数小于14时，平衡延 迟均维持在教低的水平上，当工位数为14时，平衡延迟上 升至9.03%,此时平衡系数也较高，达到9.644,相对于其 他方案，改进效果不明显。在工位数为7、8、9、10、11、 12时，节拍有显著的下降，工位数为12时，节拍减少至28,

15、 而且平衡延迟也处于较低的4. 67%,并且其平衡系数及工位 工时标准差明显低于其临近方案，所以综合考虑，可选择工 位数为12的方案作为优化解决方案。表2列出了工作站数 位12时的具体作业划分情况。4结束语本文针对装配线平衡问题，提出了一种基于约束矩阵的 作业序列编码地改进遗传算法来进行问题求解，并设计多种 群遗传算法的各个算子操作。最后用该改进算法进行了实例 运行，并将其结果与原解决方案进行了比对，取得了比较满 意的结果，验证了该算法的可行性和有效性。参考文献：1 watanable t, hashimoto y, nishikawa i, et al. line balancing using a genetic mode j. contriol eng practice, 1995 (31 )： 69-76.2 皮兴忠，范秀敏，等.基于可行作业序列的遗传算法 求解第二类装配线平衡问题j上海交通大学学报，2005, 39 (7)： 1123-1127.3 余晓光，严洪森.基于禁忌搜索遗传混合算法的装配线平衡j.计算机技术与发展,2010, 20 (5)： 5-12.4 蒋艳，黎向锋，左敦稳，焦光明基于改进遗传算法 的混流装配线的优化设计j中国机械工程，2010, 21(19)：