Rigorous time complexity analysis of Univariate Marginal Distribution Algorithm with margins
Lists
Only you see this
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.
BibTeX
@inproceedings{chen2009rigorous,
author = {Tianshi Chen and Ke Tang and Guoliang Chen and Xin Yao},
title = {{Rigorous time complexity analysis of Univariate Marginal Distribution Algorithm with margins}},
booktitle = {IEEE CEC},
year = {2009},
doi = {10.1109/cec.2009.4983208},
}Loading related content...