论文部分内容阅读
随着改革开放30年来我国经济的高速发展,科学有效的工业生产已变得越来越重要。车间调度问题作为工业生产的代表,对其的有效求解也就意义重大。作为一个NP-hard难的多目标优化问题,许多进化智能算法已经成为有效解决车间调度问题的手段,比如粒子群算法。目前已有大量文献资料表明将粒子群算法应用到多目标优化中是可行和有效的,但也有许多亟待改进和完善的地方。由于车间调度问题的复杂性和离散性特点,传统的粒子群算法很难圆满的解决。为此,本文以置换流水车间调度问题(PFSP)为研究对象,凭借遗传进化操作来离散化粒子的运动过程,配合局部搜索优化等改进策略,可以比较有效的解决置换流水车间调度问题。
由于粒子群算法中全局搜索和局部搜索的能力可以通过参数设置来平衡,而遗传算法局部搜索能力不强,但其遗传操作算子思想简单,易于实现,本文有效的结合二者,取长补短,设计出效果良好的、具有全局优化性能的、适合求解多目标优化问题的混合离散粒子群算法-HDPSOBNEH。
本文首先介绍了论文选题的背景、意义及相关问题的国内外的研究现状,表明课题研究的必要性。由于车间调度问题的多目标性,接着介绍了多目标优化的起源、发展、基本概念和多目标优化算法的分类,进而详细介绍了几种典型的多目标优化进化算法,包括NSGA—Ⅱ和SPEA2这两种优秀的算法。
然后介绍了粒子群算法的基本原理和实现流程,总结并归纳了几种常见的、有效的改进粒子群算法的方式,对多目标粒子群算法及其改进策略有一个初步的归纳与讨论,并简要地对比了粒子群算法与遗传算法,总结了粒子群算法的研究方向。
最后,针对多目标置换流水车间调度问题的数学模型,引入遗传算法中的交叉和变异算子来改进粒子群算法的进化公式,使粒子的运动轨迹离散化,从而更切合所求问题的模型。同时改进NSGA—Ⅱ的选择策略,提出自己的适应度评价函数,配合自适应的参数更新与新的局部搜索机制BNEH,得到的新算法HDPSOBNEH对多目标置换流水车间调度问题的求解是可行的并且有效的。
本文的研究工作预期对车间调度问题的求解开拓了思路,同时也提供了一种可行的新方法,具有一定的理论意义和实际应用价值。本论文涉及粒子群算法、遗传算法、多目标优化理论等的交叉研究,是一个多学科交叉课题。