分布估计算法是进化计算领域新兴起的一类概率分析进化算法,它结合了智能计算和统计学习的知识,根据当前种群中若干较好个体的信息建立概率分布模型描述问题解空间的分布,并通过对概率模型随机采样产生新的种群,如此反复进行,实现种群的进化。分布估计算法通过建立概率模型描述变量之间的相关关系,能更有效地混合构造块并实现构造块重组,可以解决传统遗传算法难以解决的问题,尤其是解决非线性、高维复杂问题。分布估计算法求解问题的关键是建立一个能恰当描述问题解分布的概率模型,但是,概率模型的建立是一个非常复杂的问题,如果所建立的模型过于简单则不能正确反映问题的本质特征,影响求解效率,而模型过于复杂则会使算法学习复杂度增大。尤其对于复杂的组合优化问题,由于这类问题本身的复杂性,可行解中各变量间具有很强的相关性,建立一个能准确描述问题可行解的概率分布模型非常困难,在将分布估计算法用于求解复杂的组合优化问题时,如何建立一个能准确描述问题解分布的概率模型成为制约算法应用的瓶颈。文中结合优良模式连接的思想、Bayesian统计推断理论与离散quasi-copula理论,对概率模型的建立方式进行改进,以提高算法求解复杂组合优化问题的能力,并将算法用于求解生产调度问题和旅行商问题,主要完成了以下工作:1.根据遗传算法中的模式定理与积木块假设理论,通过概率把多个个体的相似特征结合起来考虑,发掘优势群体中个体结构的相似点,提出了基于优良模式连接的思想。在求解问题时,通过在优势群体中考虑个体相似点的信息,对以较高频率出现在后代中的多个相邻变量以概率为基础进行连接,组成一个连接块,令其为优良模式连接块,并在进化过程中以块为整体参与进化,增强那些适应度高于种群平均适应度的模式在下一代中出现的概率,相应地减少那些适应度低于种群平均适应度的模式在下一代中出现的概率。基于这种思想,使算法能有效避免构造块破坏问题,具有较好的连锁学习效果,同时为避免陷入局部最优,有条件的调整每个连接块内部各变量的排列顺序,从而有效提高分布估计算法的优化性能。2.将基于优良模式连接的分布估计算法应用于求解Job Shop调度问题、柔性Job Shop调度问题和旅行商问题中。对于Job Shop调度问题和柔性Job Shop调度问题,在建立概率模型时充分利用了相邻工序在优势群体中的信息,通过概率值对以较高频率出现在优势群体中的相邻工序进行连接,从而使建立的概率模型能较好地反应调度问题中工序排序的特点。在旅行商问题中,在建立概率模型时充分考虑相邻城市出现在优势群体中的频率信息,并通过概率的大小对其进行连接,从而使建立的概率模型能较好地反应旅行商问题中个体的结构特征。仿真结果表明,所提出的算法在求解上述问题时表现出较好的性能。3. Bayesian统计推断方法与贝叶斯网络优化方法不同,它不需要优化复杂的网络结构,而是直接利用样本提供的信息,通过建立一个后验分布对样本进行推断。因此,本文借鉴Bayesian统计推断理论中对样本的推断思想和方法,充分利用优势群体中个体的信息,建立了一种针对离散优化问题的基于Bayesian统计推理的分布估计算法。首先,针对个体结构的每一个位置,通过优势群体信息建立一种不断更新的先验分布概率模型,利用相邻变量出现在优势群体中的频率,通过计算每一个位置上的条件概率向量建立条件分布概率模型;然后,结合先验分布概率与条件分布概率,通过贝叶斯公式的转化,建立一种后验分布概率模型。这种后验概率分布模型综合了先验概率信息和样本信息,具有较好的统计推断效果,从后验概率模型中抽样产生新群体,通过对后验概率模型的不断更新,实现进化过程。4.将基于Bayesian统计推理的分布估计算法应用于求解Job Shop调度问题、柔性Job Shop调度问题和旅行商问题中。根据Job Shop问题和柔性Job Shop调度问题的特点,针对工序排序的每一个位置建立先验分布概率模型,充分利用优势群体中各台机器上工序的排列信息,通过贝叶斯公式,建立一种能较好地反映Job Shop调度问题特点的后验概率模型,并从中抽样产生新群体;对于旅行商问题,充分利用各个城市间的排列位置信息建立先验分布概率模型和条件分布概率模型,通过贝叶斯公式获得一种后验概率模型并用以指导产生新群体。针对典型算例的仿真实验结果表明,该算法具有较好的寻优能力和鲁棒性,所建立的概率模型具有较好的稳定性。5.在离散Quasi-copula理论的基础上,针对离散优化问题,提出了一种基于经验Copula的分布估计算法。对个体采用整数编码方式,采用经验分布函数求解各个变量的边缘分布函数,在估计经验Copula函数时,首先将以整数编码的个体映射到(0,1)区间上,然后对单位超立方体进行分割,等分成若干子超立方体,统计优势群体中的个体落入各个子超立方体中的个体数,构造多维经验Copula函数,得到一种针对离散变量的多变量相关的联合分布函数,并从中抽样产生新群体。由于考虑了多变量间的相关性,因而所建立的概率模型能较好地反映问题的特征。同时对算法的时间复杂性进行了分析。6.将基于经验Copula的分布估计算法应用于求解旅行商问题和柔性Job Shop调度问题中。通过估计经验Copula,建立了上述问题的多变量相关的联合分布概率模型,并从中采样。仿真实验结果表明,该算法具有较好的求解能力。