Rigorous time complexity analysis of Univariate Marginal Distribution Algorithm with margins

Tianshi Chen, Ke Tang, Guoliang Chen, Xin Yao

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...

Figure