混合差分—分布估计算法及其在车间调度中的应用研究

发布时间：2017-10-29 11:14

  本文关键词：混合差分—分布估计算法及其在车间调度中的应用研究

  更多相关文章： 差分进化算法 分布估计算法 置换流水车间调度 作业车间调度

【摘要】：伴随着计算机集成制造系统(CIMS)的发展,智能车间调度已经成为提高企业生产效率的重要途径。车间调度问题是一类NP-hard组合优化问题,随着问题规模的扩大,问题复杂度随之升高。相比传统的确定性和启发式算法,智能优化算法(IOA)因其搜索效率高、鲁棒性强、可移植性强,而被广泛应用于车间调度中。分布估计算法(EDA)是一种基于概率统计学的搜索算法,运用概率模型描述基因变量间的相互联系,具有良好的全局搜索能力。差分进化算法(DE)是一种启发式随机搜索算法,通过交换个体间方向和距离信息产生后代。混合算法结合不同算法的寻优特点,因而具有较好的搜索性能。针对此,本文研究了混合差分-分布估计算法及其在车间调度问题中的应用,主要内容包括：(1)根据EDA和DE算法的特点,引进了基于优秀种群适应度学习因子改进了两种算法的搜索机制,进而提出了基于自适应增量学习策略的混合差分-分布估计算法(AILHDE-EDA)。该算法混合了两种搜索机制,加快收敛速度,提高求解精度；同时运用马尔科夫链分析了AILHDE-EDA算法的收敛性,并用仿真实验证明了该算法是有效性。(2)引入了LOV (Larger-Order-Value)规则将AILHDE-EDA中的连续变量映射到工件序列,用于解决置换流水车间调度问题(PFSP),同时设计了基于工件的局部搜索算法加强局部搜索能力。利用SOV (Small-Order-Value)规则将AILHDE-EDA用于解决作业车间调度问题(JSP)。最后,对标准车间调度问题的测试证明了AILHDE-EDA解决两类车间调度问题的有效性。(3)针对智能优化算法解决组合优化问题的不足,结合了DE和EDA的特性,提出了一种混合离散差分-分布估计算法(HDDE-EDA)用以解决PFSP。在概率模型不再用于采样生成个体,而是产生一个指导个体用于指导交叉和变异产生后代;同时,采用了多样的变异和交叉方式来平衡全局搜索和局部搜索,并通过变邻域搜索(VNS)来进一步提高局部搜索能力。仿真实验比较了HDDE-EDA与PFSP经典调度算法结果,证明了HDDE-EDA解决PFSP问题的优越性。
【关键词】：差分进化算法 分布估计算法 置换流水车间调度 作业车间调度
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TB497
【目录】：

• 中文摘要3-4
• Abstract4-9
• 第一章 绪论9-19
• 1.1 研究背景及意义9-10
• 1.2 车间调度问题10-12
• 1.2.1 车间调度问题描述10
• 1.2.2 车间调度算法10-12
• 1.3 差分进化算法12-15
• 1.4 分布估计算法15-17
• 1.5 本文研究内容及章节安排17-19
• 第二章 混合差分-分布估计算法及其理论分析19-38
• 2.1 增量分布估计搜索19-22
• 2.2 差分搜索22-23
• 2.3 混合差分-分布估计算法23-25
• 2.4 AILHDE-EDA算法收敛性分析25-29
• 2.4.1 基本定义25-27
• 2.4.2 收敛性证明27-29
• 2.5 实验仿真29-37
• 2.5.1 测试函数及实验环境29-32
• 2.5.2 参数设置32-33
• 2.5.3 实验结果及其分析33-37
• 2.6 小结37-38
• 第三章 基于混合差分-分布估计算法的车间调度38-52
• 3.1 AILHDE-EDA算法在PFSP中的应用38-45
• 3.1.1 PFSP问题描述38-39
• 3.1.2 算法编码机制39
• 3.1.3 局部搜索39-41
• 3.1.4 AILHDE-EDA算法求解PFSP问题41-45
• 3.2 AILHDE-EDA在JSP中的应用45-51
• 3.2.1 JSP描述45-46
• 3.2.2 编码机制46-47
• 3.2.3 解码机制47-48
• 3.2.4 AILHDE-EDA算法求解JSP问题48-51
• 3.3 小结51-52
• 第四章 基于混合离散差分-估计算法的置换流水车间调度52-70
• 4.1 HDDE-EDA算法52-60
• 4.1.1 解的表达52
• 4.1.2 种群初始化52-53
• 4.1.3 概率模型53-56
• 4.1.4 差分搜索56-57
• 4.1.5 局部搜索57-58
• 4.1.6 HDDE-EDA算法流程58-60
• 4.2 HDDE-EDA求解PFSP问题60-69
• 4.2.1 实验环境及评价指标60
• 4.2.2 Carlier和Reeve问题测试结果60-66
• 4.2.3 Taillard问题测试结果66-69
• 4.3 小结69-70
• 第五章 工作总结及展望70-72
• 5.1 主要工作及结论70-71
• 5.2 研究展望71-72
• 参考文献72-78
• 在学期间研究成果78-79
• 致谢79

【参考文献】

中国期刊全文数据库 前1条

1 张庆彬;刘波;田彦平;贺媛媛;;基于自适应学习搜索框架的混合分布估计算法[J];计算机工程与应用;2012年06期

，

本文编号：1112737