论文部分内容阅读
本文系统的回顾了分布估计算法(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测试实例的测试,证实了所提调度算法的有效性和优良性。