分布估计算法的一种改进与应用

论文摘要

本文系统的回顾了分布估计算法（EDA）的发展历史背景和理论基础,简要的介绍了分布估计算法和置换流水车间调度问题（PFSP）的研究现状,详细的分析了分布估计算法在求解复杂的连续域优化问题时所面临的难题。然后,将嵌套阿基米德Copula函数引入到了分布估计算法中,对分布估计算法进行了改进。最后,研究了分布估计算法在PFSP问题中的应用,并提出了一种基于EDA的二阶段置换流水车间调度算法。论文的主要工作可归纳为以下两点:1、提出了一种基于Lévy从属过程构建的嵌套阿基米德Copula的改进型分布估计算法。复杂的连续域优化问题,其抽象出来的多维随机向量中变量间往往存在着复杂的相互依赖关系,而嵌套阿基米德Copula函数能够简便灵活的构建其联合概率分布函数。为此,在利用分布估计算法对其进行求解时,为了降低概率模型构建的复杂性同时解决计算开销大的难题。本文首先利用Lévy从属过程构建了一类部分嵌套阿基米德Copula函数,巧妙的规避了嵌套Copula函数构造过程中嵌套条件检查难的问题。然后,利用嵌套阿基米德Copula函数在构建这类复杂连续域优化问题概率分布函数上的优势,对分布估计算法进行了改进。最后,利用测试函数对改进算法进行了测试,并与其它基于Copula改进的分布估计算法进行了比较,实验结果证实了本文算法的有效性。2、应用分布估计算法对PFSP问题进行了研究,并在此基础上提出了一种基于EDA的二阶段置换流水车间调度算法。该算法最大的特点是:一方面,有效的利用了EDA全局搜索能力强、早期收敛速度快的优势。另一方面,第二阶段混合邻域搜索算法中的随机重组搜索机制,较好的弥补了第一阶段中EDA局部搜索能力弱的缺陷。通过对OR-Library中51个Benchmark测试实例的测试,证实了所提调度算法的有效性和优良性。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题的研究背景及研究意义
• 1.2 课题的研究现状
• 1.3 课题的研究目的
• 1.4 本文的结构安排
• 1.5 本章小结
• 第二章 分布估计算法
• 2.1 分布估计算法的理论背景
• 2.2 分布估计算法的理论框架
• 2.3 分布估计算法的分类
• 2.3.1 离散型分布估计算法
• 2.3.2 连续型分布估计算法
• 2.4 分布估计算法的一个简单优化实例
• 2.5 本章小结
• 第三章 基于嵌套阿基米德Copula 的改进分布估计算法
• 3.1 Copula 理论
• 3.1.1 Copula 函数的定义
• 3.1.2 Copula 函数的分类
• 3.1.3 Copula 函数的采样算法
• 3.2 Lévy 从属过程
• 3.3 Lévy 从属过程构建一类部分嵌套阿基米德Copula 函数
• 3.4 基于部分嵌套阿基米德Copula 函数的改进分布估计算法
• 3.5 仿真实验
• 3.5.1 测试函数
• 3.5.2 实验设置
• 3.5.3 实验结果及分析
• 3.6 本章小结
• 第四章 分布估计算法在PFSP 中的应用
• 4.1 置换流水车间调度问题
• 4.1.1 PFSP 问题简述
• 4.1.2 PFSP 问题的数学模型
• 4.1.3 PFSP 问题的求解方法
• 4.2 求解PFSP 问题的分布估计算法
• 4.2.1 解的表示及种群初始化
• 4.2.2 选择策略
• 4.2.3 构建概率分布模型
• 4.2.4 采样及种群更新
• 4.2.5 终止准则
• 4.3 求解PFSP 问题的混合邻域搜索算法
• 4.3.1 邻域搜索算法
• 4.3.2 求解PFSP 问题的混合邻域搜索算法
• 4.4 求解PFSP 问题的一种基于EDA 的两阶段调度算法
• 4.5 仿真实验
• 4.5.1 实验设置及实验结果
• 4.5.2 结果分析
• 4.6 本章小结
• 第五章 总结与展望
• 5.1 本文工作总结
• 5.2 展望
• 附录
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文