基于改进型GA的车间作业调度问题研究与实现

论文摘要

车间作业调度问题（Job Shop Problem,JSP）是一类典型的NP-hard问题,已被证明在多项式时间内得不到最优值。遗传算法（Genetic Algorithm,GA）作为一种通用的优化算法,在求解JSP中得到了广泛的应用。在求解JSP时,GA显示出很强的适用性,但GA的优化性能对遗传参数（尤其是交叉率和变异率）的依赖性很强,不合适的参数往往会使得GA的优化性能大打折扣。在寻求GA的最优参数方面,已有不少深入的研究,但这些研究往往从工程背景和工程应用展开,鲜有从GA基础数学模型入手的。为了更好地解决问题,对传统的遗传算法加以改进,将一些启发式的思想融合于算法之中,成为目前研究的热点。本文分别应用病毒遗传算法和单亲遗传算法来求解车间作业调度问题。针对遗传算法求解的早熟和收敛速度慢等问题,设计了一种新的改进型病毒进化遗传算法IVEGA（Improved Virus Evolutionary Genetic Algorithm,IVEGA）,从横向和纵向同时搜索解空间;并在进化过程中分别建立主群体优秀染色体知识库和病毒优秀个体知识库,引入学习机制,避免了优秀解的丢失;其次,定义了一种基于整数的编码机制,既避免了进化过程中产生无效染色体的问题,也便于解空间和染色体空间的转换,大大地加快了对问题全局近似最优解的搜索速度。根据11个典型的JSP对比实验,证明了该算法对于求解JSP的有效性。考虑到传统遗传算法（TGA）在求解组合优化问题时,其优化性能对遗传参数（尤其是交叉率和变异率）的依赖性强,并且会出现“早熟收敛”现象等问题,设计了一种新的基于整数编码的单亲遗传算法IPGA（Integer Coded Partheno Genetic Algorithm,IPGA）。在进化过程中只产生单个个体群,取消了以往传统遗传算法的交叉操作,在一条染色体上进行变异操作,同时也继承了传统遗传算法遗传迭代等特性,大大地增加了遗传算法的搜索效率。对3个不同规模的FT类问题的仿真结果表明算法具有收敛速度快、优化结果好等优点。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 课题背景及研究意义
• 1.2 车间调度问题的发展及研究现状
• 1.2.1 调度问题的提出
• 1.2.2 调度问题的分类
• 1.2.3 生产调度的环境特征
• 1.2.4 调度问题的特点
• 1.2.5 调度问题的研究方法
• 1.2.6 车间调度问题存在问题及解决途径
• 1.3 课题主要工作
• 1.4 全文的结构安排及主要内容
• 第2章 车间调度问题及其基本理论
• 2.1 JOB SHOP 调度问题描述
• 2.1.1 描述问题的变量说明
• 2.1.2 JSP 问题的约束条件
• 2.1.3 目标函数
• 2.2 甘特图表示法
• 2.3 析取图表示法
• 2.4 JSP 的原空间和解空间分析
• 2.5 本章小结
• 第3章 遗传算法理论与实现技术
• 3.1 遗传算法的基本概念
• 3.2 遗传算法的特点
• 3.3 遗传算法的基本流程
• 3.4 遗传算法的基本操作
• 3.4.1 编码
• 3.4.2 适应度函数
• 3.4.3 种群初始化
• 3.4.4 选择操作
• 3.4.5 交叉操作
• 3.4.6 变异操作
• 3.4.7 替换策略
• 3.4.8 算法终止条件
• 3.5 本章小结
• 第4章 车间调度问题的改进型病毒进化遗传算法
• 4.1 病毒进化遗传算法简介
• 4.1.1 病毒进化遗传算法产生背景
• 4.1.2 病毒进化遗传算法的基本概念
• 4.1.3 病毒个体的感染操作
• 4.1.4 VEGA 算法框架
• 4.2 改进型病毒进化遗传算法的设计与实现
• 4.2.1 编码机制
• 4.2.2 适应度函数
• 4.2.3 进化操作
• 4.2.4 改进型病毒进化遗传算法
• 4.3 模拟实验及结果分析
• 4.4 本章小结
• 第5章 车间调度问题的单亲遗传算法
• 5.1 单亲遗传算法简介
• 5.1.1 单亲遗传算法的产生背景
• 5.1.2 PGA 的遗传算子
• 5.1.3 PGA 的运行机理分析
• 5.1.4 PGA 的运行步骤
• 5.1.5 PGA 的全局收敛性分析
• 5.2 IPGA 的设计与实现
• 5.2.1 编码策略及实现
• 5.2.2 父代群体及适应度函数
• 5.2.3 单亲遗传算子操作
• 5.2.4 算法描述
• 5.3 模拟实验及结果分析
• 5.4 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢