（计算数学专业论文）基于boosting的分布估计算法.pdf

上海交通大学硕士学位论文 摘要 第 i 页 基于 boosting 的分布估计算法 摘要 基于 boosting 的分布估计算法 摘要 分布估计算法是一种通过估计群体密度分布来指导生成新群体的进化 算法。本文提出基于 boosting 的分布估计算法， 利用统计学习理论当 中的 boosting 算法进行密度估计用于分布估计算法。我们将 boosting 算 法看作是在弱学习器空间中通过梯度下降最小化损失函数的过程，并且 选用高斯分布作为弱学习器将其用在分布估计算法当中。数值实验表明 基于 boosting 的分布估计算法在解决一些复杂函数的优化问题上效果明 显超过 umda。 关键词：关键词： 密度估计， 分布估计算法， boosting, 弱学习器,高斯分布， eda， umda，beda 上海交通大学硕士学位论文 abstract 第 ii 页 estimation of distribution algorithm based on boosting abstract estimation of distribution algorithm(eda) is an evolutionary algorithm which generates new population by estimating the density of the old population to guide the population evolution. in this article we proposed a new eda based on boosting (beda), a methodology from statistical learning theory. we treat boosting as a gradient descent procedure to minimize the risk in the space induced by weak learners and use it in eda. to implement our algorithm we choose gaussian distribution as weak learners for boosting. numerical results show beda out perform umda in some difficult function optimization problems. keywords: density estimation, estimation of distribution algorithm, boosting, gaussian distribution, weak learner, umda, beda 上海交通大学硕士学位论文 第一章 绪论 第一章第一章 绪论绪论 1.1 分布估计算法的研究背景和意义分布估计算法的研究背景和意义 分布估计算法(estimation of distribution algorithm，muhlenbein the case of linear least squares, advances in neural information processing systems, vol. 7, eds. g. tesauro, d.touretzky and t. leen,1995 17 m. jordan and r. jacobs, hierarchical mixtures of experts and em algorithms, neutral computation,6, pp 181-214 18 baluja, s., & davies, s.(1997). using optimal dependency-trees for combinatorial optimization: learning the structure of the search space. in proceedings of the 14th international conference on machine learning(pp. 30-38). morgan kaufmann. 19 optimum branching. j. res. nbs，71b，233-240 20 pelikan m, muhlenbein h. the bivariate marginal distribution algorithm. advances in soft computing engineering design and manufacturing, london, springer-verlag, 1999, 521-535. 21 muhlenbein h, mahnig t. convergence theory and applications of the factorized distribution algorithms. journal of computing and information technology, 1999,7(1):1932 22 muhlenbein h, mahnig t. the factorized distribution algorithm for additivetly decomposable functions. in: second symposium on artificial intelligence. adaptive systems. cimap 99, la habana,1999.301-313 23muhlenbein h, mahnig t. fda a scaleable evolutionary algorithm for the optimization of additively decomposed functions. evolutionary computation, 1999, 7(4):353-376 24 muhlenbein h, mahnig t. ochoa a r. schemata, distributions and graphical models in evolutionary optimization. journal of heuristics, 1999,5: 215-247 25 pelikan m, goldberg d e, cantu-paz. boa: the bayesian optimization algorithm, in: proceedings of the genetic and evolutionary computation conference gecco-99, orlando, fl:1999. 525-532 26 chickering d m, geiger d, heckerman d. learning bayesian networks is np-hard. technical report msr-tr-94-17, microsoft research, redmond, wirginia, 1994 27 pelikan m. hierachical bayesian optimization algorithm: toward a new generation of evolutionary algorithms. new york：spinger verlag, 2005. 28 sebag m, ducoulombier a. extending population-based incremental learning to continuous search spaces. in: back th, eiben g, schoenauer m, schwefel h p, editors, proceedings of the 5th conference on parallel problems solving from nature ppsn v, springer-verlag, 1998. 418-427 29 r. shachter and c. kenley, “no free lunch theorems for optimization”, ieee trans. evolutionary 上海交通大学硕士学位论文 统计学习理论 computation. vol.1, no. 1, pp. 67-82, apr. 1997 30 shapiro j l. drift and scaling in estimation of distribution algorithms. evolutionary computation,2005,13(1):99-123 31 zhang q, muhlenbein h. on the convergence of a class of estimation of distribution algorithms. ieee transactions on evolutionary computation, 2004, 8(2): 127-136 32 muhlenbein h, hons r. the estimation of distributions and the minimum relative entropy principal. evolutionary computation, 2005,13(1):1-27 33 roberto s. estimation of distribution algorithms with kikuchi approximations. evolutionary computation,2005,13(1):67-97 34 jiri o. entropy-based convergence measurement in discrete estimation of distribution algorithms. in: lozano et al(eds): towards a new evolutionary computaion: advances in the estimation of distribution algorithms. spings-verlag,2002.125-142. 35 vladimir vapnik. the nature of statistical learning theory. springer-verlag 36 l.g. valiant. a theory of learnable. communications of the acm. 27(11):1134-1142 37 kearns m., valiant l.g., learning boolean formulae or factoring. technical report tr- 1488,cambridge, ma: havard university aiken computation laboratory, 1988. 38 robert e. schapire. the strength of weak learnability. machine learning,5(2):197-227,1990. 39 freund y., boosting a weak learning algorithm by majority, information and computation, 1995,121(2) : 256-285 40 freund y., schapire r.e.a., decision-theoretic generalization of on-line learning and an application to boosting. journal of computer and system sciences,1997,55(1):119-139 41 robert e. schapire. the boosting approach to machine learning: an overview. nonlinear estimation and classification. springer,2003 42 viola p, jones m. robust real time object detectiona. 8th ieee international conference on computer visionc. vancouver,2001 43 liew mason, jonathan baxter, peter bartlett, marcus frean. boosting algorithms as gradient descent in function space. 44 dimitri p. bertsekas. nonlinear programming: 2nd edition. mit press. 45 l. breiman. prediction games and arcing algorithms. technical report 504, department of statistics, university of california, berkeley, 1998. 46 william m. boothby. an introduction to differentiable manifolds and riemannian geometry. elsevier pte. ltd. 上海交通大学硕士学位论文 统计学习理论 47 saharon rosset, eran segal. boosting density estimation. advances in nerual information processing systems, vol 15. 48 b. s. everitt, d. j. hand. finite mixture distributions, chapman and hall, new york, 1981. 49 qiang lu, xin yao. clustering and learning gaussian distribution for continuous optimization. systems, man and cybernetics, part c: applications and reviews. 35(2),195-204 50 zhou s, sun z. a new approach belonging to edas: quantum-inspired genetic algorithm with only one chromosome. in: proceedings of first international conference on natrual computation(icnc05), changsha,china,2005.141-150 51 michalsk r. s. learnable evolution model: evolutionary processes guided by machine learning. machine learning 2000, 38: 9-40 52 alden wright, riccardo poli, christoper r. stephens, w.b. landon and sandeep. an estimation of distribution algorithm based on maximum entropy. lecture notes in computer science 343-354. spinger berlin/heidelberg. 53 spiegelhalter, david j., et al.,2002. bayesian measures of model complexity and fit. statistical methodology, 64(4),583-639 54 shude zhou, zengqi sun. can ensemble method convert a weak evolutionary algorithm to a strong one?. proceedings of the international conference on computational intelligence for modelling, control and automation and international conference on intelligent agents, web technologies and internet commerce vol-2(cimca-iawtic06). 68-74 55li h, zhang q，tsang e p k, ford j. hybrid estimation of distribution algorithm for multiobjective knapsack problem. in: proceedings of 4th european conference on evolutionary computation in combinatorial optimization. coimbra, portugal:2004,145-154 56laummans m, ocenasek j. bayesian optimization algorithms for multi-objective optimization. in: proceedings of the 7th international conference on parallel problem solving from nature. london, uk:spring-verlag,2002. 298-307 57 thierens d, bosman p a n. multi-objective mixture based iterated density estimation evolutionary algorithms. in: proceedings of genetic and evolutionary computation conference. san francisco, usa: morgan kaufmann, 2001, 663-670 58 lozano j a, sagarna r, larranaga p. parallel estimation of distribution algorithms. in: estimation of distribution algorithms. a new tool for evolutionary computation. boston: kluwer academic publishers,2002. 125-142 59 pelikan m, muhlenbein h. the bivariate marginal distribution algorithm. in: advances in soft 上海交通大学硕士学位论文 统计学习理论 computing engineering design and manufacturing. london: springer-verlag,1998. 521-535 60 baluja s. using a priori knowledge to create probabilistic models for optimization. international journal of approximate reasoning, 20