遗传算法在装配线平衡中的应用

遗传算法在装配线平衡中的应用

肖中华,邓明星,唐秋华

肖中华①XiaoZhonghua；邓明星②DengMingxing；唐秋华①TangQiuhua

（①武汉科技大学机械自动化学院，武汉430081；②武汉科技大学汽车与交通工程学院，武汉430081）

摘要：装配线平衡是混合装配生产线调度的重要基础，是面向订单装配（ATO）得以实施的技术瓶颈，对提高生产率和设备利用率也具有重要意义。在工位数量给定的条件下，文章针对装配线平衡的数学模型，提出了一种面向装配线平衡的非标准遗传算法。该算法基于各操作之间的逻辑优先关系产生可行操作序列而生成初始种群，保证解的可行性；在此基础上实现寻找最小节拍、选定较优序列进行遗传，并采用最优保存策略确保算法收敛到最优或近优解。最后通过实例验证了该算法的有效性和可行性。

关键词：遗传算法；装配线平衡；可行序列

中图分类号：TH16文献标识码：A文章编号：1006-4311（2010）02-0253-03

0引言

装配线平衡是将基本的作业元素分配到工作站，满足特定的目标和约束条件。从实质上看，装配线平衡问题就是组合优化问题，但这个问题由产品设计工艺和制造过程技术所决定的作业元素之间的先后关系而变得异常复杂。在实际生产中，由于装配线的柔性增加，很多情况都可能导致生产线不能顺畅的运行，从而造成暂时性不平衡现象发生，而且装配生产线的平衡程度不仅直接反应了装配生产线的效率，而且影响产品的质量，劳动强度大的工人为了赶上装配线的运行节拍，常常忽视了产品质量。据美国有关资料统计，即使在美国这样工业发达的国家，在工业装配生产中平均要有5％～10％的装配时间是浪费在平衡延迟中。从装配线产生之日起，其平衡问题就一直受到人们的重视[1]。现代关于此类问题的解决方案大致可以分为四类：①数学规划方法，包括线性规划，非线性规划，多目标规划，动态规划等；②基于规则调度，此类方法是给不同的操作根据潜在的生产瓶颈分配不同的权重以达到优化目的。③启发式方法，如模拟退火发、遗传算法、禁忌搜索算法、噪声算法等；④人工智能算法，如专家系统、神经网络等[2][3]。面对大规模的装配线平衡，解决此类问题的主要趋势是采用启发式。但一些启发式搜索方法在逼近最优解或次优解的搜索中，不断地有倒退过程，搜索效率低，还易产生“组合爆炸”现象[4]。鉴于此，本文主要采用改进的遗传算法来解决这个NP-hard问题。

1遗传算法

遗传算法（GA）是J.Holland于1975年受生物进化论的启发而提出的。GA的提出一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难，其自组织、自适应、自学习和群体进化能力使其适合于大规模复杂优化问题。GA是一种通用的优化算法，它对优化设计的限制较少，由于它的进化特性，它在解的搜索中，不需要了解解的内在性质，可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的，甚至是混合的搜索空间；它的另一个显著优点就是能够有效地进行概率意义下的全局搜索，而且能够以较大的概率求得全局最优解。

对于装配线平衡问题来说，标准的遗传算法的操作算子可能产生早熟收敛或收敛缓慢等缺点，甚至由于算子的不可行而无法得出可行解。这也是遗传算法在实际应用遇到的最大障碍，鉴于此本文采取基于可行序列的非标准遗传算子，保证算子的可行性，并采取最有保留策略，避免最优解丢失或算法退化。

2装配线平衡的遗传算法设计

装配线平衡问题的一般提法是：给定产品装配作业表（包括各项装配作业、作业时间及其先后关系）或者直接给出装配作业先后关系图，优化某一特定的目标函数。一般可以分以下几类：①生产节拍C给定，在满足生产线约束条件的前提下最小化工作站；②工作站数量给定，在满足生产线约束条件的前提下最小化生产节拍，使节拍与工作站负荷之差最小；③生产节拍给定，最大化分配同一工位的操作相关性。

2.1装配线平衡的数学模型

本文主要对上述提及的第二类装配线问题进行研究，即已知工作站数量，最小化生产节拍，使节拍与工作站负荷之差最小。目标值设定为负荷方差（WorkloadVariance），最小节拍CT等于最优方案中的最大工位时间。

2.2装配线平衡的算法设计

改算法采用的是基于可行序列的遗传算法来求解装配线平衡问题，无论是初始种群的产生还是遗传算子的构造，都是直接从作业元素之间的顺序关系出发，从而保证它搜索的所有作业序列以及相应的作业分配方案都是可行的，并且所有的可行分配方案都可能被搜索到，效率极高。如图1是该算法的流程图描述。

2.3编码

编码就是将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应，这很大程度上依赖于问题的性质，并将影响遗传操作的设计。本文采取的基于可行序列的编码方式：按作业元素分派至工作站的先后顺序，将作业元素排成一列，每个作业元素对应一个基因位，这种编码方式对目标函数和操作算子的适应性较好。经过编码后的一染色体的图解。这个染色体说明了各个作业元素被分配的先后顺序，其中第一次分配作业元素1，第二次分配作业元素2第三次分配作业元素4…第八次分配作业元素7，最后分配作业元素9。

2.4初始化

鉴于保优GA的概率1收敛特性，初始种群通常是随机产生的。本文基于各操作之间的优先关系，随机产生一组的可行作业序列作为初始种群。

假设a（i）为完成操作i之后可行的操作集合。根据优先关系，操作j能进入可行操作集合a（i）的条件是它所有的前序操作都已经完成而本身未完成。因此，生成可行操作序列的具体步骤如下：

Step1：挑选没有前序操作或前序操作已分配的任务，形成可行操作集合a（i）；

Step2：判断终止条件，可选集合a（i）为空，则停止；否则进入Step3；

Step3：从可行操作集合中随机选择一个任务，编入基因位；

Step4：更新可行操作集合a（i），即删除已选操作，并加入符合规则的新操作；进入Step2。

以9个操作元素的工位分配问题为例，图3为其优先关系图。表1为其一染色体各个基因产生的过程。将此过程循环P次，则可得出P个可行序列，即产生初试种群P（i）。

2.5解码及适应度计算

按照个体中的顺序将操作分配至工位，要满足每个工位的操作时间和不超过节拍CT，因此在解码过程中首先必须求出每个可行序列下的最小节拍CT′，具体步骤如下：

Step1：计算理论最小节拍

Step2：以CT为节拍，按照可行序列将任务分配到工位，直至（N-1）工位，剩余操作全部分配至N工位；

Step3：计算Tj（j=1，2…N）和Tj′=Tj+tj+1（j=1，2，3…N-1，tj+1为分配至j+1工位的第一个操作对应时间）；

Step4：计算CT′=max{Tj|j=l，2…N}andCT=min{Tj′|j=l，2…N-I}，如果CT′?燮CT，则进入Step5，CT′即为最小节拍，此分配方案为该序列下的最优方案。否则转向Step2；

2.6选择

选择操作用于避免有效基因的损失，使高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效率。为避免最优解的丢失，本文采取最优保存策略，即上代最优个体直接复制到新代种群。其他个体则采用锦标赛法。具体如下：

Step1：选择竞标赛规模K=2；

Step2：在当前种群中随机产生K个个体；

Step3：比较所选择个体的适应度值，将值较小的个体复制成为新代个体；

Step4：重复step2、step3直至新代个体数目达到种群数量；

2.7交叉

从选择操作产生的新染色体种群中任取两个染色体。随机产生一个小于操作数的整数，确定交叉点（例如产生随机数7，则交叉点进在第7个基因和第8个基因之间）在这个交叉点上将这两个体成左右两部分。取出第一个染色体的左面部份，同时在第二个染色体中删除第一个染色体左边部份的基因，剩余的基因按照原来的顺序排列。以第一个染色体的左部和第二个染色体中按上述步骤处理得到的基因为右部，重组为一个新的染色体。把用于交叉操作的两个父代染色体从种群中删除。把产生的后代染色体加入新种群。

2.8变异

为了保证优先关系约束，文中采用移位变异法，任意选择一个个体，任意选择一个基因（作业元素）进行变异。先找出其满足约束关系的可行区间，然后将变异基因插入其中任意一个位置。

3实例分析

基于上述所提出的遗传算法，本文采用C++语言实现了相应的程序。下面以一个具有三十个装配操作的装配生产线为例。该装配线设计工位为9个。图4为其各个操作之间的优先关系图。图中的每个节点表示一个操作，有向边表示各操作之间的逻辑优先关系，节点上数值表示每个操作对应的操作时间。

将程序运行6次

生产效率高达97.36%，文献[2]中用GAMS和CPlex求解该类问题的MILP模型，在此案例的应用中，其运行结果各工位的时间分别为：58，57，59，61，60，53，54，52，63。计算其平衡延迟d1=8.81%，生产效率为91.18%。证明本文提出的方法在配置装配线工位可以降低平衡延迟，提高生产效率，但在计算效率上与文献[2]中的方法相比还需要改进。

4结论

本文给出了的初始种群方法及各种遗传算子的实现步骤，在寻求各工位负荷最平衡的同时，寻求最小生产节拍。并用实例证明该方法在对装配线平衡问题的求解，能得出理想的结果。

参考文献：

[1]唐秋华，席忠民，陈平和，严运兵.混装线投产序列和工位任务的协同调度机理[J].工业工程，2008，11（1）：19-24.

[2]QiuhuaTang，ChristodoulosA.Floudas2，JianyiKong，etcANovelApproachForSchedulingMixed-modelAutomobileAssemblyLineBasedOnMILP.WCGO-2009.

[3]杜运普，杨月新.装配生产线的平衡问题研究[J].机械设计与制造，2003，（2）：104-16.

[4]王福林，王吉权，吴昌友等.实数遗传算法的改进研究[J].生物工程学报，2006，21（1）：153-158.

[5]YeoKeunKim，YongJuKim，YeonghoKim,Geneticalgorithmsforassemblylinebalancingwithvariousobjectives.Computersind.1996.30：397-409.

[6]SerenOzmehmetTasan，Areviewofthecurrentapplicationsofgeneticalgorithmsinassemblylinebalancing.JIntellManuf，2008，19：49-69.

[7]唐秋华，席忠民，陈平和，严运兵.面向高效精准柔性混装作业的智能元胞调度方法研究[J].武汉科技大学学报（自然科学版）2007.30（4）：379-383.