改进的小生境遗传算法在作业车间调度中的应用研究

改进的小生境遗传算法在作业车间调度中的应用研究

论文摘要

车间作为机械加工企业创造利润的执行单元一直受到企业的关注,但目前车间用于非加工性的时间占总时间的比例较大,很长时间作业在流动等待加工,而车间调度员无法对全部作业有很好的控制,经常出现调度员不知道目前每台机床在加工什么,下一步能加工什么作业的问题。对于高层领导想对企业的具体加工情况有所了解,就更困难了。车间调度问题属于NP-hard问题,是典型优化问题中最难求解的问题。遗传算法以其通用性强,算法简单等特点,被广泛应用到车间调度问题的优化中。但是,正是由于其通用性强,而导致其灵活性差,尽管能够保证全局收敛性,但不可避免出现局部退化现象。针对标准遗传算法的早熟问题,小生境技术被认为是一种行之有效的方法,它可以维持种群多样性,能增强新搜索区域的探测能力。在小生境中最适应的个体将保持不变或高的适应度值,而小生境中其它个体将被大幅度地减小它们的适应度值。因此种群中个体就被分散到整个搜索空间中,这样就能在种群迭代时有效地维持一定的多样性。本文的主要工作是:针对传统的基于群体内个体适应度共享的小生境技术不能有效利用群体中优良因素的缺点,结合生物学中的种群进化理论,提出了一种基于群体间共享的改进小生境遗传算法,在进化过程中充分考虑了群体间互相影响,互相制约的关系,有效地利用了优良种群的特性,其他种群适应度根据共享群体的适应度进行调整,改善种群的品质,从而使进化过程沿着较优的方向发展,有效地避免了早熟现象,改善了算法的收敛性能。并将该算法运用到典型10×10JSP问题上,结果证明比普通的适应值共享机制在收敛速度和求得最优解的结果上有了很大改进。目前,该算法成功应用到“车间调度仿真系统”中,针对某交通运输设备制造企业的生产线的实际数据进行求解,获得了良好的运行效果。

论文目录

  • 摘要
  • Abstract
  • 目录
  • 绪论
  • 一、课题研究背景、目的及意义
  • 二、课题研究的主要内容及意义
  • 第一章 车间调度问题的研究
  • 1.1 问题的提出
  • 1.2 车间生产调度问题的描述
  • 1.2.1 调度问题的描述及其发展过程
  • 1.2.2 车间调度问题的分类与特点
  • 1.2.3 Job shop问题的数学描述及表示方法
  • 1.3 车间调度问题的研究方法
  • 1.4 车间调度问题的研究策略
  • 1.5 车间调度研究存在问题的分析
  • 本章小结
  • 第二章 遗传算法概述
  • 2.1 遗传算法的概述
  • 2.2 遗传算法的基本原理和实现步骤
  • 2.2.1 GA的基本原理
  • 2.2.2 GA的实现步骤
  • 2.3 遗传算法的特点
  • 2.4 遗传算法的理论基础
  • 2.4.1 模式理论
  • 2.4.2 积木块假设
  • 2.4.3 欺骗问题
  • 2.4.4 收敛性定理
  • 2.5 遗传算法研究现状与发展动向
  • 2.5.1 遗传算法研究现状
  • 2.5.2 遗传算法的发展动向
  • 本章小结
  • 第三章 小生境技术的研究
  • 3.1 遗传算法过早收敛的原因分析
  • 3.2 小生境技术的引入
  • 3.3 当前小生境技术的分析
  • 3.3.1 基于预选择(preselection)机制的小生境技术
  • 3.3.2 基于共享(sharing)机制的小生境技术
  • 3.3.3 自适应小生境算法
  • 3.4 基于小生境的遗传算法(NGA)
  • 本章小结
  • 第四章 改进的小生境遗传算法
  • 4.1 小生境技术的优缺点
  • 4.2 算法的改进及算法流程
  • 4.2.1 改进算法的思想
  • 4.2.2 编码与解码
  • 4.2.3 算法参数与初始化
  • 4.2.4 结合启发式调度规则保证初始种群多样性
  • 4.2.5 适应度函数
  • 4.2.6 改进的选择操作
  • 4.2.7 基于工序编码的交叉算子POX的引入
  • 4.2.8 变异操作
  • 4.2.9 算法流程
  • 4.3 改进算法的特点
  • 4.4 改进算法的收敛性
  • 4.5 改进算法性能验证
  • 4.5.1 参数设置
  • 4.5.2 算法性能指标
  • 4.5.3 仿真结果及分析
  • 本章小结
  • 第五章 基于改进算法的调度仿真系统的研究与开发
  • 5.1 仿真实验系统的意义
  • 5.2 调度仿真系统应用背景
  • 5.3 仿真调度系统设计
  • 5.3.1 仿真系统的组成
  • 5.3.2 系统的外部接口设计
  • 5.3.3 系统的体系结构
  • 5.4 数据库表清单
  • 5.5 仿真调度系统的应用
  • 5.5.1 标准测试数据平台
  • 5.5.2 实际数据测试平台
  • 本章小结
  • 结论
  • 参考文献
  • 攻读硕士学位期间发表的学术论文
  • 致谢
  • 相关论文文献

    标签:;  ;  ;  ;  

    改进的小生境遗传算法在作业车间调度中的应用研究
    下载Doc文档

    猜你喜欢