混合进化算法及其在生产调度中的应用

论文摘要

工程设计具有复杂性,多约束等特点,我们经常会遇到需要使多个目标在给定可行区域上都尽可能最优的决策问题。其中生产调度问题可以说是最具代表性的一系列问题被学界广泛研究。半导体制造工业具有高度复杂的生产流程,.其中包括数种类型的工作站,大型并且多种多样各异的产品,尤其是带有重入式的处理流程更是非常复杂以至于它很难在一个动态的环境下进行充分地有效地排程。本文以半导体制造业中晶圆片的生产为例,针对于具有重入式特点的流水线生产调度问题,提出了一个基于遗传进化思想的重入式混合进化算法,通过对基因变异方式的改进来有效地减小产品的总滞留时间。特别地,改进后的算法能够很好地自适应流水线中突发情况的产生,进行有效的重排序。多目标的优化思想也被广泛地应用在流水车间的排程问题之中。本文针对多目标优化问题的特点,提出了一种基于局部搜索的多目标混合进化算法,主要着重于寻求遗传搜索和局部搜索二者之间的平衡以更多更快地找到非支配解来提高种群的收敛速率。此算法的适度值是由染色的排序(rank)值和此染色体相对于相邻的两条染色体的拥挤度值共同决定的。本文根据Pareto排序的方法对初始化的种群进行优化,通过计算种群中每条染色体的排序(rank)值和拥挤度值将其排序。而后提出了混合局部搜索的想法以减少计算时间,提高算法效率和收敛性,保持种群的多样性。并采用二分锦标赛法来选择交配池中的个体集,根据两点法和插入法对优秀种群做交叉变异操作以生成新的种群。最后将提出的混合算法与几种多目标进化算法进行了比较实验,结果表明新算法能产生于真正Pareto最优解更的近似Pareto前沿解集。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 生产调度问题产生背景
• 1.2 带有重入式的生产调度问题
• 1.3 多目标优化方法的发展历史和研究现状
• 1.4 多目标优化问题概述
• 1.4.1 多目标优化的基本概念
• 1.4.2 多目标问题的研究难点
• 1.4.3 多目标进化算法研究现状
• 1.4.4 问题的结构和特性
• 1.5 本论文的研究目标及组织结构
• 1.5.1 本论文的研究目标
• 1.5.2 本论文的组织结构
• 2 进化算法综述
• 2.1 进化算法概述
• 2.2 进化算法的发展历史
• 2.3 多目标进化算法的设计机制
• 2.3.1 收敛性
• 2.3.2 适度值分配机制
• 2.3.3 精英机制
• 2.4 多目标优化问题的基本求解方法
• 2.4.1 基于偏好方法求解
• 2.4.2 产生式方法求解
• 2.5 本章小结
• 3 带有重入式流水车间生产调度问题
• 3.1 带有重入式的生产调度
• 3.2 问题模型定义
• 3.3 基于遗传算法的RFSP求解
• 3.4 改进的遗传算法
• 3.5 实验比较
• 3.6 本章小结
• 4 多目标生产调度优化问题
• 4.1 多目标生产调度问题背景
• 4.2 多目标生产调度问题的定义
• 4.3 多目标生产调度问题的解决方法
• 4.3.1 基于运筹学的方法
• 4.3.2 基于人工智能的方法
• 4.3.3 基于进化算法的方法
• 4.4 本章小结
• 5 基于Pareto排序的多目标进化算法
• 5.1 Pareto排序方法概述
• 5.1.1 Pareto最优解
• 5.1.2 Pareto前沿解
• 5.1.3 拥挤距离
• 5.2 局部搜索策略（local search strategy）
• 5.3 选择策略（selection strategy）
• 5.3.1 轮盘赌选择（roulette wheel selection）
• 5.3.2 锦标赛选择（tournament selection）
• 5.3.3 选择算子的定义
• 5.4 算法具体流程
• 5.5 本章小结
• 6 算法在流水车间问题中的应用
• 6.1 生产调度建模
• 6.2 生产调度问题编码方式
• 6.2.1 适度值的确立
• 6.2.2 遗传操作
• 6.3 实验仿真对比
• 6.4 本章小结
• 7 问题测试以及结果比较
• 7.1 算法性能评价
• 7.2 评价实例
• 7.2.1 测试问题和性能评价方法
• 7.2.2 比较其他多目标进化算法
• 7.3 本章小结
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢