TY - GEN
T1 - Rigorous time complexity analysis of univariate marginal distribution algorithm with margins
AU - CHEN, Tianshi
AU - TANG, Ke
AU - CHEN, Guoliang
AU - YAO, Xin
PY - 2009/5
Y1 - 2009/5
N2 - 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. © 2009 IEEE.
AB - 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. © 2009 IEEE.
UR - http://www.scopus.com/inward/record.url?scp=70450057358&partnerID=8YFLogxK
U2 - 10.1109/CEC.2009.4983208
DO - 10.1109/CEC.2009.4983208
M3 - Conference paper (refereed)
SN - 9781424429592
SP - 2157
EP - 2164
BT - 2009 IEEE Congress on Evolutionary Computation, CEC 2009
ER -