您当前位置:设计在线网 >> 自动控制理论 >> 浏览文章

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

分享到:
本文章讲述了浅谈遗传算法在装配线平衡中的应用.

装配线

平衡是将基本的作业元素分配到工作站,满足特定的目标和约束条件。从实质上看,装配线平衡问题就是组合优化问题,但这个问题由产品设计工艺和制造过程技术所决定的作业元素之间的先后关系而变得异常复杂。在实际生产中,由于装配线的柔性增加,很多情况都可能导致生产线不能顺畅的运行,从而造成暂时性不平衡现象发生,而且装配生产线的平衡程度不仅直接反应了装配生产线的效率,而且影响产品的质量,劳动强度大的工人为了赶上装配线的运行节拍,常常忽视了产品质量。据美国有关资料统计,即使在美国这样工业发达的国家,在工业装配生产中平均要有5%~10%的装配时间是浪费在平衡延迟中。

从装配线产生之日起,其平衡问题就一直受到人们的重视[1]。现代关于此类问题的解决方案大致可以分为四类:
①数学规划方法,包括线性规划,非线性规划,多目标规划,动态规划等;
②基于规则调度,此类方法是给不同的操作根据潜在的生产瓶颈分配不同的权重以达到优化目的。
③启发式方法,如模拟退火发、遗传算法、禁忌搜索算法、噪声算法等;
④人工智能算法,如专家系统、神经网络等[2][3]。面对大规模的装配线平衡,解决此类问题的主要趋势是采用启发式。
但一些启发式搜索方法在逼近最优解或次优解的搜索中,不断地有倒退过程,搜索效率低,还易产生"组合爆炸"现象[4]。鉴于此,本文主要采用改进的遗传算法来解决这个NP-hard问题。

1遗传算法

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

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

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

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

2.1装配线平衡的数学模型

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

2.2装配线平衡的算法设计

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

2.3编码

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

2.4初始化

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

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

Step 1:挑选没有前序操作或前序操作已分配的任务,形成可行操作集合a(i);

Step 2:判断终止条件,可选集合a(i)为空,则停止;否则进入Step3;

Step 3:从可行操作集合中随机选择一个任务,编入基因位;

Step 4:更新可行操作集合a(i),即删除已选操作,并加入符合规则的新操作;进入Step2。

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

中国设计在线网 All Rights Reserved. 互联网违法和不良信息举报
信息产业部备案号:湘ICP备09001063号