第五章--分布估计算法研究

第五章分布估计算法研究遗传算法是广泛应用的智能优化算法，通过选择、交叉和变异三种基本操作实现全局最优解的搜索。遗传算法获得巨大成功的理论基础是建筑块理论[1]，该理论指出遗传算法具有通过组合个体的建筑块获得最优解的能力。建筑块理论能够有效使用的重要条件是在数据编码中能够明确表示建筑块的位置[2,3]，否则遗传算法中的交叉和变异操作就有可能破坏建筑块，特别是那些较长的或距离较远的块，从而导致算法的收敛速度下降或找不到最优解[4]。分布估计算法（EstimationofDistributionAlgorithm,EDA）源于遗传算法，是为解决遗传算法中存在的因交叉、变异操作而导致的建筑块破坏问题而提出的[5,6]。在分布估计算法中没有交叉和变异操作，取而代之的是对于选择出来的优势群体的概率分布模型进行估计，并根据估计的模型进行采样。由于分布估计算法具有更强的理论基础，因此受到广大学者的重视，成为当前进化计算领域的研究热点[7~10]。5.1引言与遗传算法类似，分布估计算法也是基于群体的一种进化算法，算法由一个初始群体开始，在每代循环中，首先根据每个个体的适应值选择出具有代表性的适应值较好的一些个体组成优势群体。然后根据优势群体估计其中的个体所服从的概率分布模型，比如联合正态分布。第三步便是根据估计的概率分布模型采样产生一些新个体，并用来替换原有群体中的部分个体，从而组成新一代的群体。当满足循环终止条件时，算法结束，当前群体中的适应值最好的个体就是算法优化的结果。与遗传算法相比，分布估计算法中没有了交叉和变异两个操作，而是对选择群体的概率分布模型进行估计和采样。由于建筑块中的变量相关性要比其他变量之间的相关性强。分布估计算法更注重变量的相关结构，对建筑块的分布情况进行整体估计，这样不仅可以避免交叉变异所带来的建筑块破坏问题，反而有助于建筑块的增长。分布估计算法的基本步骤如下：Step1：初始化群体。在搜索空间内按均匀分布随机产生PS个点，组成初始群体，记进化代数g为1。Step2：计算适应值。根据适应值评价函数计算第g代群体中的各点的适应值。第七章分布估计算法研究•97•97Step3：选择优势群体。根据适应值，运用一定的选择策略（如截断选择，轮赌选择等）选出适应值较好的s个个体组成优势群体。Step4：估计优势群体的概率分布模型。一般假设优势群体服从某一类概率分布模型，然后以优势群体为样本，对具体的概率分布F进行估计。Step5：根据估计的概率模型进行采样，产生一些新个体。在搜索空间内按概率分布F随机产生l个点，作为新生代中的部分个体。Step6：更新群体。由第g代群体中m个适应值较好的个体，新生的l个个体，以及随机产生（或者以较好个体为初始点搜索等方式产生）的PS-m-l个个体组成新一代群体，并将进化代数g←g+1。Step7：若满足某种停止准则，则算法结束，g代群体中的最好个体就是优化的结果；否则算法转到Step2继续执行。根据变量相关性的情况，一般认为分布估计算法可分为以下三类：各变量相互独立的分布估计算法，变量两两相关的分布估计算法和多变量相关的分布估计算法。前两类分布估计算法在运算复杂度方面优于第三类算法，但由于其不能充分考虑变量的相关性，因此在复杂问题的优化效果方面要次于第三类算法。下面对这三类算法中的代表性算法进行简单的介绍和分析。5.1.1变量相互独立的分布估计算法PBIL（Population-BasedIncrementalLearning）[11]和UMDA（UnivariateMarginalDistributionAlgorithm）[12]都是典型的变量相互独立的分布估计算法，它们仅考虑离散变量。对于选择出来的优势群体，根据每个变量的取值情况估计其一维边缘分布，由于在这类算法中所考虑的变量是相互独立的，因此反映群体分布情况的联合分布为各边缘分布之积。两种方法的不同之处在于它们更新概率模型的方式不同。PBIL采用线性调整概率模型的方式，在原有概率模型的基础上，根据优势群体的分布情况，各边缘分布按一定的学习速率进行线性调整，即pk(X)=∏ipk(xi)=∏i[α×pk-1(xi)+(1-α)×ni/N]。当α=0时，PBIL等价于UMDA。UMDA则根据优势群体的分布情况直接确定概率模型，即pk(X)=∏ip(xi|Dk-1s)。cGA（compactGeneticAlgorithm）[13]也是变量独立的分布估计算法，它需要较小空间，因为其群体规模仅为2，在每代运行时比较两个个体的适应值，并将较好的个体作为概率模型。在连续域内的变量独立的分布估计算法有PBILc[14,15]和UMDAcG[16],它们分别是PBIL和UMDA在连续域内的扩展，边缘分布使用的是一元正态分布。这类算法在解决优化变量之间独立的问题时表现非常好，并能有效解决遗传算法带来的建筑块破坏问题，但是在优化变量之间存在相关性的问题时则表现的非常差，其原因是算法中没有考虑到优化变量的相关性。第七章分布估计算法研究•98•985.1.2变量两两相关的分布估计算法最初考虑变量相关性的分布估计算法将变量关系简化为两两相关，典型的算法有MIMIC（MutualInformationMaximizationforInputClustering）[17]、COMIT（CombiningOptimizerwithMutualInformationTree）[18]和BMDA（BivariateMarginalDistributionAlgorithm）[19]。它们分别采用链状结构、树结构和森林来表示两两相关的变量关系。在MIMIC中概率模型表示为pkπ(X)=pk(xi1|xi2)…pk(xin-1|xin)pk(xin)，为了找到变量(x1,x2,…,xn)的最佳排列π=(i1,i2,…,in)，MIMIC算法使用贪婪算法最小化两个概率分布之间的K-L距离。COMIT采用树结构表示变量的两两相关性，通过反复最小化相互信息指标来向树结构中不断加入最大的枝。BMDA使用Pearson的χ2测试决定变量连接到哪棵树中以及树中变量的依赖关系。连续域的此类算法如MIMIC在连续域中的扩展MIMICcG[16]，其中使用了二元正态分布表示边缘分布。为找到最优排列，MIMICcG最小化的条件熵为22221(|)[(1log2)log()]2ijijijjHXX。两两相关的分布估计算法考虑了优化变量的部分关系并且其结构学习也比较容易，在解决一些变量不独立的优化问题时表现也较好，比如算法COMIT和BMDA能够有效的优化二维spin-glass问题。但对于变量关系更为复杂的优化问题，这类算法则表现得较差。5.1.3多变量相关的分布估计算法多变量相关的分布估计算法能够全面考虑优化问题的结构，但其模型学习的复杂度也相对较高。根据表示变量关系的网络结构可以分为有向网络的分布估计算法、基于无向网络的分布估计算法和基于一般网络结构的分布估计算法。Bayesian网络是有向无环图，典型的基于Bayesian网络的分布估计算法有BOA（BayesianOptimizationAlgorithm）[20,21]、EBNA（EstimationofBayesianNetworkAlgorithm）[22,23]和EGNA（EstimationofGaussianNetworkAlgorithm）[24]。此类算法中使用Bayesian网络表示变量关系，根据选择出的群体估计网络的结构和参数，并根据估计的Bayesian网络模型进行采样生成下一代群体。BOA使用BD量（Bayesian-Dirichletmetric）和贪婪算法学习网络结构。EBNA使用BIC量（BayesianInformationCriteriametric）来衡量网络结构。此类算法在优化复杂的变量相关问题时效果很好，但是Bayesian网络的学习本身是NP难问题，因此算法的时间复杂度较高，多数时间花费在模型的估计上。EGNA是连续域分布估计算法，使用高斯网络表示变量的关系，该网络由贝叶斯得数、惩罚极大似然得数第七章分布估计算法研究•99•99和边排除测试决定，变量的概率密度由高斯分布表示。Markov网络是无向图，基于Markov网络的分布估计算法有FDA（FactorizedDistributionAlgorithm）[25]、DEUM（DistributionEstimationUsingMarkovnetworkalgorithm）[26-28]、MN-FDA（MarkovNetworkFactorizedDistributionAlgorithm）[29]、MN-EDA（MarkovNetworkEstimationofDistributionAlgorithm）[30]、MOA（MarkovianitybasedOptimizationAlgorithm）[31]和MARLEDA（MarkovianLearningEstimationofDistributionAlgorithm）[32]。FDA用固定的概率图模型表示变量关系，但需要有关于变量关系的专家知识来完成概率分布函数的分解。DEUM根据无向图中的集群建立适应函数的模型，并将联合分布分解成Gibbs分布，模型参数通过解群体进行估计，采样时使用了Markov链蒙特卡洛方法（包括Gibbs采样和Metropolis采样）。MN-FDA用无向图近似表示联合分布，并从中构造出连接图，然后根据连接图采样。MN-EDA用联合分布的Kukichi近似来构建概率模型并用Gibbs采样产生新群体。MOA和MARLEDA是依赖于局部Markov性的分布估计算法，它们通过无向网络估计条件概率并由此采样。MARLEDA根据χ2测试估计结构，MOA采用基于交互信息的方式采样并利用退火温度表来控制探索与开采。这类算法同样适用于优化变量强耦合的问题，但其中的FDA对于黑箱问题或形式复杂的优化问题则无能为力。ECGA（ExtendedCompactGeneticAlgorithm）[33]是cGA的扩展，该算法将变量分成若干个相互独立的组，在每一组中变量之间有相关性，而与其它组中的任何变量都不相关。所有变量的联合分布为各组变量的分布函数之积。EMNA（EstimationofMultivariateNormalAlgorithm）[34]用所有变量的联合正态分布表示解分布模型，根据选择的群体估计均值向量和协方差矩阵作为模型参数，并从联合正态分布中采样得到新一代群体。钟伟才等在文献[35]中提出一种建立在一般Gauss网络上的算法，并采用Cholesky分解的方式产生新个体。这类算法全面考虑了变量之间的相关性，并且省去了复杂网络结构的学习，但是估计协方差矩阵的运算量是优化空间维数的平方，其时间复杂度仍然较高。目前已有的分布估计算法中要么不能充分考虑变量之间的相关性，对变量强相关的问题优化效果较差，要么模型估计的时间开销很大。最近的研究表明分布估计算法中90%的运算时间花费在模型估计阶段[36]，为减少算法的时间开销，学者们采用了不同的方法对其进行改进，如并行方式[37,38]、与其他算法融合的方式[39-41]、混合局部搜索的方式[42]，使用迭代的[43]或偶然的模型建立方式[44]以及初始信息优化的方式[45,46]等。如果基础算法中能够用较小的时间开销实现模型估计是最好的。所有变量的联合分布无疑是反映变量关系的准确且简捷的方式。第七章分布估计算法研究•100•1005.2copula分布估计算法基于copula理论的分布估计算法是近几年来提出的一种新型的分布估计算法，据我们所有的中英文资料显示，我们在2009年IEEECEC会议中发表的论文[47]是这方面最早的论文。后来也有文献显示在2007年就有西班牙文的论文将高斯copula函数用于分布估计算法的研究中[48]。美国密苏里州分布估计算法实验室对分布估计算法的综述中特别指出，基于copu