Analysis of Computational Time of Simple Estimation of Distribution Algorithms

被引:60
作者
Chen, Tianshi [1 ]
Tang, Ke [1 ]
Chen, Guoliang [1 ]
Yao, Xin [1 ,2 ]
机构
[1] Univ Sci & Technol China, Nat Inspired Computat & Applicat Lab, Sch Comp Sci & Technol, Hefei 230027, Anhui, Peoples R China
[2] Univ Birmingham, Ctr Excellence Res Computat Intelligence & Applic, Sch Comp Sci, Birmingham B15 2TT, W Midlands, England
基金
中国国家自然科学基金;
关键词
Computational time complexity; estimation of distribution algorithms; first hitting time; heuristic optimization; univariate marginal distribution algorithms; GENETIC ALGORITHM; EVOLUTIONARY; OPTIMIZATION; CONVERGENCE; COMPLEXITY; MODELS;
D O I
10.1109/TEVC.2009.2040019
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Estimation of distribution algorithms (EDAs) are widely used in stochastic optimization. Impressive experimental results have been reported in the literature. However, little work has been done on analyzing the computation time of EDAs in relation to the problem size. It is still unclear how well EDAs (with a finite population size larger than two) will scale up when the dimension of the optimization problem (problem size) goes up. This paper studies the computational time complexity of a simple EDA, i.e., the univariate marginal distribution algorithm (UMDA), in order to gain more insight into EDAs complexity. First, we discuss how to measure the computational time complexity of EDAs. A classification of problem hardness based on our discussions is then given. Second, we prove a theorem related to problem hardness and the probability conditions of EDAs. Third, we propose a novel approach to analyzing the computational time complexity of UMDA using discrete dynamic systems and Chernoff bounds. Following this approach, we are able to derive a number of results on the first hitting time of UMDA on a well-known unimodal pseudo-boolean function, i.e., the LeadingOnes problem, and another problem derived from LeadingOnes, named BVLeadingOnes. Although both problems are unimodal, our analysis shows that LeadingOnes is easy for the UMDA, while BVLeadingOnes is hard for the UMDA. Finally, in order to address the key issue of what problem characteristics make a problem hard for UMDA, we discuss in depth the idea of "margins" (or relaxation). We prove theoretically that the UMDA with margins can solve the BVLeadingOnes problem efficiently.
引用
收藏
页码:1 / 22
页数:22
相关论文
共 45 条
[1]  
Baluja S., 1994, Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning
[2]  
Cestnik B., 1990, PROC EUROPEAN C ARTI, P147
[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 New Approach for Analyzing Average Time Complexity of Population-Based Evolutionary Algorithms on Unimodal Problems [J].
Chen, Tianshi ;
He, Jun ;
Sun, Guangzhong ;
Chen, Guoliang ;
Yao, Xin .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2009, 39 (05) :1092-1106
[5]  
Cormen T., 2001, Introduction to Algorithms
[6]   The variant call format and VCFtools [J].
Danecek, Petr ;
Auton, Adam ;
Abecasis, Goncalo ;
Albers, Cornelis A. ;
Banks, Eric ;
DePristo, Mark A. ;
Handsaker, Robert E. ;
Lunter, Gerton ;
Marth, Gabor T. ;
Sherry, Stephen T. ;
McVean, Gilean ;
Durbin, Richard .
BIOINFORMATICS, 2011, 27 (15) :2156-2158
[7]   On the analysis of the (1+1) evolutionary algorithm [J].
Droste, S ;
Jansen, T ;
Wegener, I .
THEORETICAL COMPUTER SCIENCE, 2002, 276 (1-2) :51-81
[8]   A rigorous analysis of the compact genetic algorithm for linear functions [J].
Droste S. .
Natural Computing, 2006, 5 (3) :257-283
[9]   Upper and lower bounds for randomized search heuristics in black-box optimization [J].
Droste, Stefan ;
Jansen, Thomas ;
Wegener, Ingo .
THEORY OF COMPUTING SYSTEMS, 2006, 39 (04) :525-544
[10]  
González C, 2005, LECT NOTES COMPUT SC, V3512, P42