Paper Info
Title
Rigorous time complexity analysis of univariate marginal distribution algorithm with margins
Abstract
Univariate Marginal Distribution Algorithms (UMDAs) are a kind of Estimation of Distribution Algorithms (EDAs) which do not consider the dependencies among the variables. In this paper, on the basis of our proposed approach in [1], we present a rigorous proof for the result that the UMDA with margins (in [1] we merely showed the effectiveness of margins) cannot find the global optimum of the TRAPLEADINGONES problem [2] within polynomial number of generations with a probability that is super-polynomially close to 1. Such a theoretical result is significant in sheding light on the fundamental issues of what problem characteristics make an EDA hard/easy and when an EDA is expected to perform well/poorly for a given problem.
Year
DOI
Venue
2009
10.1109/CEC.2009.4983208
IEEE Congress on Evolutionary Computation
Keywords
Field
DocType
problem characteristic,fundamental issue,rigorous proof,theoretical result,univariate marginal distribution algorithms,trapleadingones problem,rigorous time complexity analysis,polynomial number,distribution algorithms,sheding light,univariate marginal distribution algorithm,probability density function,estimation of distribution algorithm,time complexity,genetic algorithms,data mining,convergence,stochastic processes,evolutionary computation,probability,genetics,algorithm design and analysis,computational complexity,polynomials
Mathematical optimization,Polynomial,Estimation of distribution algorithm,Stochastic process,Artificial intelligence,Time complexity,Univariate,Probability density function,Machine learning,Mathematics,Marginal distribution,Computational complexity theory
Conference
Citations 
PageRank 
References 
8
0.55
11
Authors
4
Name
Order
Citations
PageRank
Tianshi Chen160643.69
Tang Ke22798139.09
Chen Guoliang338126.16
Xin Yao414858945.63