Rigorous Time Complexity Analysis of Univariate Marginal Distribution Algorithm with Margins

被引：10

作者：

Chen, Tianshi ^{[1
]}

Tang, Ke ^{[1
]}

Chen, Guoliang ^{[1
]}

Yao, Xin ^{[1
]}

机构：

[1] Univ Sci & Technol China, Dept Comp Sci & Technol, NICAL, Hefei 230027, Anhui, Peoples R China

来源：

2009 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-5 | 2009年

关键词：

PROBABILITY-INEQUALITIES;

D O I：

10.1109/CEC.2009.4983208

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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 or our proposed approach in [11, we present a rigorous proof for the result that the UMDA with margins (in [11 we merely showed the effectiveness of margins) cannot find the global optimum of the TRAPLEADINGONES problem [2] within polynomial number or 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.

引用

页码：2157 / 2164

页数：8

共 16 条

[1]

[Anonymous], 2001, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation

[2]

CHEN T, 2007, IEEE T EV UNPUB 1126

[3] On the analysis of average time complexity of Estimation of Distribution Algorithms [J].

Chen, Tianshi ;

Tang, Ke ;

Chen, Guoliang ;

Yao, Xin .

2007 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-10, PROCEEDINGS, 2007, :453-460

[4] A rigorous analysis of the compact genetic algorithm for linear functions [J].

Droste S. .

Natural Computing, 2006, 5 (3) :257-283

[5]

Gonzalez C., 2005, THESIS U BASQUE COUN

[6] The compact genetic algorithm [J].

Harik, GR ;

Lobo, FG ;

Goldberg, DE .

1998 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION - PROCEEDINGS, 1998, :523-528

[7] Towards an analytic framework for analysing the computation time of evolutionary algorithms [J].

He, J ;

Yao, X .

ARTIFICIAL INTELLIGENCE, 2003, 145 (1-2) :59-97

[8] Drift analysis and average time complexity of evolutionary algorithms [J].

He, J ;

Yao, X .

ARTIFICIAL INTELLIGENCE, 2001, 127 (01) :57-85

[9] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[10]

Motwani Rajeev, 1995, Randomized Algorithms

← 1 2 →