基于混合进化算法的装配线平衡问题研究

论文摘要

装配线是典型的流导向生产系统,是大规模、标准化工业生产的重要组成部分。而在企业的生产规划中,装配线平衡问题是设计、管理装配线的主要内容之一。装配线平衡（Assembly Line Balancing）就是在不违背约束条件下,将装配产品的作业（任务）合理分配至一系列工作站上,并使得一个或多个目标函数最优化。多年来,这个问题得到了众多运筹学研究人员的重视,并提出了许多精确求解方法。这些方法大致可以分为两类:分支定界和动态规划。然而,由于该问题的复杂性（NP-hard）,对于具有实际应用规模的例子,建立数学模型并用传统方法寻求最优解并不现实。近年来,进化计算的研究取得了许多进展,为装配线平衡问题的求解提供新的思路。作为强有力且应用广泛的随机搜索和智能优化算法,遗传算法可能是目前影响最广泛的进化计算方法之一。在过去的几年中,学术界也尝试着运用遗传算法来解决装配线平衡问题,并且取得了一些初步的成果。但是,对于复杂装配线平衡问题,直接应用简单的遗传算法,效果并不理想。因此,如何结合问题自身特性,设计出针对复杂装配线问题的有效算法,构成了本文的核心内容。本文的主要工作和创新点可以归纳如下:1.综述了遗传算法应用于优化问题的基本特征和方法,在此基础上,分析了如何把一般性的遗传算法用于求解某个具体问题的框架模型。这一模型既是对目前应用在制造优化问题中的遗传算法的归纳和提炼,同时也有助于我们为这些问题探索新的混合遗传算法。2.针对单一型装配线平衡问题,构建数学模型,提出了基于成组技术的遗传算法,设计出适应问题特征的染色体表示和遗传操作算子。成组技术能有效的保留父代优良的基因片段,避免在进化过程中优良基因的遗失,使种群朝着最优解区域逼近。在算法的设计中研究了适应度函数的选择问题,提出了能够实现目标持续改进的适应度函数。另外,结合Lamarckian进化原理,嵌入局部爬山算法以提高整个算法的搜索能力。3.扩展单一型装配线平衡问题,研究了含工人指派的装配线平衡问题,构建其数学模型,并设计出基于混合遗传算法的解决方式。该遗传算法采用了部分编码技术,未表达的决策信息通过一个有效的解码程序得出,为具有两个向量的染色体设计混合交叉算子和移位变异算子,提高了算法的遗传性能。而且,构建基于种群平均适应度变化的模糊逻辑控制器,动态调节算法策略性参数（交叉率、变异率）,以平衡算法的局部搜索和全局搜索,避免种群退化和早熟。4.针对各种不同规模的装配线平衡问题的标准数值算例,分别用本文提出的新算法和已存在的经典算法实验,结果显示新算法不仅有更强的搜索能力,而且能有效的预防早熟。总之,本文对装配线平衡问题提出了有效的编码方法,把基于问题的具体知识应用到编码和解码中来,从而提高了编码质量,缩小了搜索空间。并混合局部爬山算法和模糊逻辑控制器,提高算法性能。最终,我们能够在可接受的时间内为所关注的问题提供满意解。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究意义
• 1.3 本文研究的主要内容
• 第2章 装配线平衡的基本概念
• 2.1 装配线的基本原理
• 2.2 装配线的基本特征
• 2.3 装配线的分类
• 2.3.1 按装配产品的种类分类
• 2.3.2 按装配线的布局分类
• 2.4 装配线平衡的基本概念
• 2.5 小结
• 第3章 进化算法基础
• 3.1 生物进化的模拟
• 3.2 进化算法
• 3.2.1 遗传算法
• 3.2.2 遗传规划
• 3.2.3 进化规划
• 3.2.4 进化策略
• 3.3 遗传算法
• 3.3.1 编码
• 3.3.2 初始群体生成
• 3.3.3 适应度函数
• 3.3.4 遗传操作
• 3.3.5 增强遗传算法性能的技术
• 3.4 小结
• 第4章 单一型装配线平衡问题模型与算法
• 4.1 问题描述
• 4.2 数学模型
• 4.3 算法设计
• 4.3.1 优先权编码
• 4.3.2 译码
• 4.3.3 交叉算子
• 4.3.4 变异算子
• 4.3.5 评价函数
• 4.3.6 选择操作
• 4.3.7 局部爬山算法
• 4.3.8 总体程序结构
• 4.4 仿真实验
• 4.5 小结
• 第5章 组遗传算法在装配线平衡中的应用
• 5.1 分组问题简介
• 5.2 分组问题遗传编码分析
• 5.2.1 装箱问题概述
• 5.2.2 基于箱子的编码
• 5.2.3 基于物品的编码
• 5.3 组遗传算法的设计
• 5.3.1 基于组的编码
• 5.3.2 初始种群的产生
• 5.3.3 基于组的杂交
• 5.3.4 基于组的变异
• 5.3.5 评价与选择
• 5.4 试验分析
• 5.5 小结
• 第6章 含工人指派的装配线平衡问题
• 6.1 问题引入
• 6.2 数学模型
• 6.3 混合遗传算法的设计
• 6.3.1 部分编码策略
• 6.3.2 种群初始化
• 6.3.3 二分译码
• 6.3.4 遗传算子
• 6.3.5 适应度函数
• 6.3.6 模糊逻辑控制器（FLC）
• 6.4 数值试验
• 6.5 小结
• 第7章 结论与展望
• 7.1 结论
• 7.2 展望
• 参考文献
• 附录
• 致谢
• 作者攻硕期间完成的学术论文