Projects per year
Abstract
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 wellknown unimodal pseudoboolean 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.
Original language  English 

Pages (fromto)  122 
Number of pages  22 
Journal  IEEE Transactions on Evolutionary Computation 
Volume  14 
Issue number  1 
DOIs  
Publication status  Published  1 Feb 2010 
Keywords
 estimation of distribution algorithms
 Computational time complexity
 first hitting time
 heuristic optimization
 univariate marginal distribution algorithms
Fingerprint
Dive into the research topics of 'Analysis of Computational Time of Simple 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