一种保持种群多样性的单变量边缘分布算法

龙源期刊网 http://www.qikan.com.cn

一种保持种群多样性的单变量边缘分布算法 作者：黄情操

来源：《中国科技纵横》2014年第20期

【摘 要】 针对单变量边缘分布算法（UMDA ）求解复杂优化问题时的局限性，本文将均匀变异机制引入分布估计算法 （EDAs ）领域，提出了一种基于均匀变异的单变量边缘分布算法。该算法利用均匀变异操作保持种群的多样性，提高混合算法的全局搜索能力。通过对算法的分析和仿真实验表明与单变量边缘分布算法（UMDA ）相比，改进后的保持种群多样性的单变量边缘分布算法具有更高的优化性能。

【关键词】 分布估计算法 单变量边缘分布算法 种群 收敛性 均匀变异算子 多样性 1 引言

单变量边缘分布估计算法（univariate marginal distribution algorithm，UMDA ） 是一种基于概率模型的进化算法。在该算法中，种群中各变量是相互独立的，因而是一种基础的分布估计算法（estimation of distri—bution algorithms，EDA ）[1，2]。该算法首先利用被选择的优良解集的边缘分布来构建基因变量的概率分布模型，随后通过采样算子来产生新一代种群。由于该算法是在宏观层次上对种群进行建模，因此算法有时会出现过早收敛的情况，全局最优搜索的能力较差。此外，在进化种群中，由于个体趋同往往会导致种群多样性的迅速降低，使算法陷入早熟。因此，解决UMDA 早熟收敛问题的思路之一就是重构种群的多样性。

近年来，国内外很多学者从重构种群多样性的角度出发，提出了很多种改进的UMDA 算法，归纳起来，主要有（1）Koumoutsakos 等人提出的高斯分布模型的方差制；（2）小生境技术；（3）nadera 等提出的多种群并行进化[8]等3个方面。

在各种具体的遗传操作算子中，变异算子用新的基因值来替换原有的基因值，从而改变了个体编码串的结构，是维持算法的种群多样性的重要手段一。但是，传统UMDA 算法仅仅通过选择算子和基因的重组算子来实施进化，缺少维持种群多样性的变异算子。为解决UMDA 算法的早熟收敛问题，提出一种基于均匀变异的单变量边缘分布算法（univariate marginal distribution algorithm with uniform mutation，UMDA —UM ）。

2 单变量边缘分布算法

单变量边缘分布算法是一种分布估计算法。在该算法中，种群由个个体组成。在进化的每一代，从个个体中选择个优良解，之后计算优良解集中每一位取1的概率，并由此产生概率分布模型，接着由该模型来产生新一代的种群。在二进制的搜索空间，UMDA 算法由一个概率向量开始，其表示个体中的每个变量的取值为1或0的概率是相等的，以此概率产生的初始群体可以尽量均匀地分布二进制搜索空间。算法通过提取当前群体的一些优良解提供的信息来计