基于Boosting的分布估计算法

《基于Boosting的分布估计算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海交通大学硕士学位论文摘要基于Boosting的分布估计算法摘要分布估计算法是一种通过估计群体密度分布来指导生成新群体的进化算法。本文提出基于Boosting的分布估计算法，利用统计学习理论当中的Boosting算法进行密度估计用于分布估计算法。我们将Boosting算法看作是在弱学习器空间中通过梯度下降最小化损失函数的过程，并且选用高斯分布作为弱学习器将其用在分布估计算法当中。数值实验表明基于Boosting的分布估计算法在解决一些复杂函数的优化问题上效果明显超过UMDA。关键词：密度估计，分布估计算法

2、，Boosting,弱学习器,高斯分布，EDA，UMDA，BEDA第I页上海交通大学硕士学位论文ABSTRACTEstimationOfDistributionAlgorithmBasedOnBoostingABSTRACTEstimationofDistributionAlgorithm(EDA)isanevolutionaryalgorithmwhichgeneratesnewpopulationbyestimatingthedensityoftheoldpopulationtoguidethepopu

3、lationevolution.InthisarticleweproposedanewEDAbasedonBoosting(BEDA),amethodologyfromstatisticallearningtheory.WetreatBoostingasagradientdescentproceduretominimizetheriskinthespaceinducedbyweaklearnersanduseitinEDA.ToimplementouralgorithmwechooseGaussiandis

4、tributionasweaklearnersforBoosting.NumericalresultsshowBEDAoutperformUMDAinsomedifficultfunctionoptimizationproblems.Keywords:densityestimation,estimationofdistributionalgorithm,boosting,Gaussiandistribution,weaklearner,UMDA,BEDA第II页上海交通大学硕士学位论文第一章绪论第一章绪论1

5、.1分布估计算法的研究背景和意义[1]分布估计算法(EstimationOfDistributionAlgorithm，Muhlenbein&Paab,1996)是一种新型的随机进化算法，它的创新之处在于它提出了一种全新的进化模式，具体的说，它通过寻找群体的概率分布来刻画群体的特征，并且通过找到的概率分布来指导生成新的群体来进一步的搜索问题的解空间。这个新的算法在解决当前很大一部分复杂问题上表现的较好，所以最近在进化计算领域关于这个算法的改进出新了大量的研究论文，近年来国际上进化计算领域的各大学术会议，如A

6、CMSIGEVO,IEEECEC等都将分布估计算法作为重要的专题予以讨论。本文在总结部分论文的基础上，对分布估计算法提出了一些改进，并且通过实验证明了改进后的分布估计算法在解决一些多峰函数优化问题当中表现出的优越性。本小节主要介绍分布估计算法的基本概念和它到目前为止仍然需要继续探讨的问题。要理解分布估计算法的基本思想，我们需要从遗传算法(GeneticAlgorithm，JohnH.[2]Holland,1975)说起。遗传算法是从大自然的遗传现象当中获取的灵感，它是基于群体的一种进化算法。用来表示问题解的

7、串叫做染色体，这个步骤也叫做编码。串上的每个对应的编码位通常叫做基因。遗传算法初始，算法随机产生一个染色体群体，群体的大小依问题的不同而不同。遗传算法通过选择算子根据特定的规则从种群中选出优良的染色体，选择的方式有轮盘赌选择和锦标赛选择等。然后算法通过交叉算子和变异算子达到更新这些种群的目的。交叉算子将选出的优良染色体内部结构打乱并且通过重新组合生成新的群体，交叉的方式一般有单点交叉和多点交叉等。变异算子依照一定的概率对染色体进行修正，如同自然界当中的变异一样，遗传算法当中的变异算子增加了群体的多样性。循环

8、迭代，一直到遗传算法的终止准则满足为止。我们可以将遗传算法的算法步骤用图1.1表示通过选择算子，搜索被限定在较优良的群体当中进行。通过交叉和变异算子，群体被不断的更新和改进。交叉操作实际上就是染色体的重组操作，染色体的每个部分都包含了问题解的信息。一个直观的想法就是，如果一个问题能够被通过某种规则分解成若干求解难度有限的子问题并且这个问题的全局解能够由这些子问题的局部解构建产生，那么这个问题就能较好的由遗传算法求