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 -