Projects per year
Abstract
Estimation of Distribution Algorithm (EDA) is a wellknown stochastic optimization technique. The average time complexity is a crucial criterion that measures the performance of the stochastic algorithms. In the past few years, various kinds of EDAs have been proposed, but the related theoretical study on the time complexity of these algorithms is relatively few. This paper analyzed the time complexity of two early versions of EDA, the Univariate Marginal Distribution Algorithm (UMDA) and the Incremental UMDA (IUMDA). We generalize the concept of convergence to convergence time, and manage to estimate the upper bound of the mean First Hitting Times (FHTs) of UMDA (IUMDA) on a wellknown pseudomodular function, which is frequently studied in the field of genetic algorithms. Our analysis shows that UMDA (IUMDA) has O(n) behaviors on the pseudomodular function. In addition, we analyze the mean FHT of IUMDA on a hard problem. Our result shows that IUMDA may spend exponential generations to find the global optimum. This is the first time that the mean first hitting times of UMDA (IUMDA) are theoretically studied.
Original language  English 

Title of host publication  IEEE Congress on Evolutionary Computation, 2007. CEC 2007. 
Publisher  Institute of Electrical and Electronics Engineers (IEEE) 
Pages  453460 
Number of pages  8 
ISBN (Electronic)  9781424413409 
ISBN (Print)  9781424413393 
DOIs  
Publication status  Published  1 Sept 2007 
Event  IEEE Congress on Evolutionary Computation, 2007 (CEC 2007)  Singapore, Singapore Duration: 25 Sept 2007 → 28 Sept 2007 
Conference
Conference  IEEE Congress on Evolutionary Computation, 2007 (CEC 2007) 

Country/Territory  Singapore 
City  Singapore 
Period  25/09/07 → 28/09/07 
Fingerprint
Dive into the research topics of 'On the analysis of average time complexity of estimation of distribution algorithms'. Together they form a unique fingerprint.Projects
 1 Finished

Computational Complexity Analysis of Evoloutionary Algarithms.
Engineering & Physical Science Research Council
1/05/05 → 31/10/08
Project: Research Councils