Name
Abstract | ||
|---|---|---|
Estimation of Distribution Algorithm (EDA) is a well-known 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 well-known pseudo-modular function, which is frequently studied in the field of genetic algorithms. Our analysis shows that UMDA (IUMDA) has O(n) behaviors on the pseudo-modular 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/CEC.2007.4424506 | IEEE Congress on Evolutionary Computation |
Keywords | Field | DocType |
probability method,evolutionary algorithm,mean first hitting time,time complexity,estimation of distribution algorithm,incremental univariate marginal distribution algorithm,convergence time,i. introduction,stochastic optimization algorithm,convergence,computational complexity,univariate marginal distribution algorithm,genetic algorithm,genetic algorithms,pseudo-modular function,stochastic programming,probability,modular function,stochastic optimization,upper bound | Convergence (routing),Stochastic optimization,Mathematical optimization,Estimation of distribution algorithm,Upper and lower bounds,Artificial intelligence,Time complexity,Stochastic programming,Mathematics,Machine learning,Genetic algorithm,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-1-4244-1340-9 | 18 | 0.80 |
References | Authors | |
18 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chen Tianshi | 1 | 1205 | 59.29 |
| Tang Ke | 2 | 2798 | 139.09 |
| Chen Guoliang | 3 | 381 | 26.16 |
| Xin Yao | 4 | 14858 | 945.63 |