一种病毒进化遗传算法在作业车间调度中应用研究

论文摘要

遗传算法是一种模拟生物进化过程的随机搜索算法，其自组织、自适应、自学习和种群进化能力使其适合于大规模复杂优化问题。它将问题的求解表示成“染色体”的适者生存过程，通过种群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或者满意解。随着计算机技术的发展，遗传算法越来越受到人们的重视，并在机器学习、模式识别、神经网络、优化控制、组合优化等领域得到了成功的应用。生产调度问题几乎在现实环境中，特别是在工业工程领域无所不在。许多制造工业提出的调度问题从本质上讲非常复杂，难以用传统优化方法求解。由于该问题表现出约束组合优化问题的所有特征，因此，调度问题成为遗传算法领域里的一个热门话题，并且成为测试新算法思想的范例。本文主要针对车间调度中典型的作业车间调度问题(Job Shop Scheduling Problem)，提出了一种适合该问题的病毒进化遗传算法。该改进算法首先从病毒个体的生成上进行了改进，其中部分病毒个体从优秀的主个体复制生成，提高了整个病毒群体的适值和感染能力，并引入了静态繁殖理论，有效的避免了问题最优解的丢失。其次，将基于优先规则的启发式方法与病毒进化遗传算法相结合，一方面通过该启发式算法来改进初始主群体的性能，另一方面让其配合病毒感染操作，调整局部搜索能力，加快进化速度，改善GA收敛慢的缺点。最后应用算法性能测试函数和标准测试集中的测试用例对改进后的算法进行了测试，结果表明算法在整体性能上有明显的提高。并且将改进后的算法用于求解实际调度问题，得到的结果是有效和可行的。

论文目录

• 摘要
• Abstract
• 目录
• 绪论
• 一 论文研究的背景、目的及意义
• 二 遗传算法的发展及研究现状
• 三 论文的主要工作
• 第一章 作业车间调度问题的研究
• 1.1 作业车间调度问题概述
• 1.2 古典作业车间调度
• 1.2.1 问题的描述
• 1.2.2 问题的数学模型
• 1.3 作业车间调度问题的研究方法
• 1.4 遗传算法解决作业车间调度问题
• 1.4.1 编码
• 1.4.2 适应度函数
• 1.4.3 遗传操作
• 1.4.4 算法的终止条件
• 本章小结
• 第二章 遗传算法及病毒进化遗传算法
• 2.1 引言
• 2.2 遗传算法
• 2.2.1 遗传算法概要
• 2.2.2 遗传算法的基本思想及特点
• 2.2.3 遗传算法的基本操作及流程
• 2.3 病毒进化遗传算法
• 2.3.1 病毒进化遗传算法概要
• 2.3.2 病毒进化遗传算法的基本思想
• 2.3.3 病毒进化遗传算法的基本操作及流程
• 本章小结
• 第三章 改进的病毒进化遗传算法
• 3.1 引言
• 3.2 算法的改进及算法的流程
• 3.2.1 编码
• 3.2.2 初始种群的产生
• 3.2.3 适应度函数
• 3.2.4 选择、交叉和变异
• 3.2.5 静态繁殖理论
• 3.2.6 启发式算法
• 3.2.7 病毒个体的进化操作
• 3.2.8 改进的病毒进化遗传算法流程
• 3.2.9 终止条件
• 3.3 改进算法的性能验证
• 3.3.1 函数计算实例
• 3.3.2 MT10×10问题
• 本章小结
• 第四章 遗传算法及车间调度平台的设计及实现
• 4.1 引言
• 4.2 遗传算法及车间调度研究平台的总体设计思想
• 4.3 遗传算法及车间调度研究平台的功能模块
• 4.4 数据库的设计
• 4.5 开发工具
• 4.6 研究平台实例运行
• 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢