基于多色集合的遗传算法 毕业论文 .doc

摘要 生产计划与生产调度直接关系着企业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企业的效益。为了解决实际生产中的车间调度问题，提出了应用改进后的遗传算法解决方案。由于基本遗传算法存在收敛过慢和“早熟”的问题等，为解决这些问题，引入多色集合理论的围道布尔矩阵进行模型约束，在模型约束下，使编码、解码和变异过程都通过搜索围道布尔矩阵而提高了遗传算法速度，也就提高了整个遗传算法的使用效率，使改进后的遗传算法能够有效的解决实际车间调度问题。 关键字：多色集合理论；遗传算法；车间调度 Abstract Production planning and scheduling the direct relation enterprise production efficiency and production cost, effective planning and scheduling algorithms can maximize the efficiency of enterprises. In order to solve the actual production of the workshop scheduling problem, put forward the application of the improved genetic algorithm solution. Due to the basic genetic algorithm has slow convergence and premature problem, in order to solve these problems, introducing the polychromatic sets theory contour Boolean matrix model constraints, in the model, the coding, decoding and variation process through searching the contour Boolean matrix and the genetic algorithm to improve the speed, also improved the use of a genetic algorithm efficiency, so that the improved genetic algorithm can effectively solve the actual job shop scheduling problem. Key words: polychromatic sets; genetic algorithm; Job Shop Scheduling 目 录 摘要 I Abstract II 1 绪论 1 1.1 引言 1 1.2 论文研究的意义目的与主要内容 2 1.2.1 本课题研究的背景 2 1.2.2 本课题研究的意义 3 1.2.3 本课题研究的目的 4 1.2.4 本课题研究的主要内容 5 1.3 生产调度问题 5 1.3.1 引言 5 1.3.2 车间调度概述 5 1.3.3 车间调度的分类 7 1.3.4 车间调度现有研究方法 7 1.3.5 车间调度研究存在的问题及发展趋势 9 2 多色集合理论 11 2.1 多色集合理论概述 11 2.1.1 多色集合理论基础 11 2.1.2多色集合理论的特点 12 2.2 多色集合理论的基本概念 12 2.3多色集合的应用 16 2.3.1 简单车间调度 16 2.3.2 机床约束模型 17 2.3.3 工序约束模型 19 3 遗传算法理论基础 21 3.1遗传算法概述 21 3.2主要参数设计及操作流程 22 3.2.1编码 22 3.2.2适应度函数 23 3.2.3算法参数 23 3.2.4算法终止条件 24 3.2.5操作流程 26 3.3 一般遗传算法求解车间调度问题 26 4 基于多色集合的遗传算法车间调度系统建模 29 4.1车间调度系统数学模型 29 4.2车间调度系统的约束模型 30 4.3 模型约束下的改进遗传算法操作 33 4.3.1基于围道布尔矩阵的约束模型 33 4.3.2模型约束下的染色体编码 36 4.3.3模型约束下的染色体解码 37 4.3.4选择操作 39 4.3.5交叉操作 39 4.3.6模型约束下的染色体变异 39 4.4实例仿真 41 5 总结 43 致谢 44 参考文献 451 绪论 1.1 引言 随着科学技术的飞速发展和市场