Analysis of Computational Time of Simple Estimation of Distribution Algorithms

Research output: Contribution to journalArticle

Standard

Analysis of Computational Time of Simple Estimation of Distribution Algorithms. / Chen, T; Tang, Ke; Chen, G; Yao, Xin.

In: IEEE Transactions on Evolutionary Computation, Vol. 14, No. 1, 01.02.2010, p. 1-22.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@article{64c8ca20bf5d4d6183c71fd6f6c0ea65,
title = "Analysis of Computational Time of Simple Estimation of Distribution Algorithms",
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 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.",
keywords = "estimation of distribution algorithms, Computational time complexity, first hitting time, heuristic optimization, univariate marginal distribution algorithms",
author = "T Chen and Ke Tang and G Chen and Xin Yao",
year = "2010",
month = feb,
day = "1",
doi = "10.1109/TEVC.2009.2040019",
language = "English",
volume = "14",
pages = "1--22",
journal = "IEEE Transactions on Evolutionary Computation",
issn = "1089-778X",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "1",

}

RIS

TY - JOUR

T1 - Analysis of Computational Time of Simple Estimation of Distribution Algorithms

AU - Chen, T

AU - Tang, Ke

AU - Chen, G

AU - Yao, Xin

PY - 2010/2/1

Y1 - 2010/2/1

N2 - 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.

AB - 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.

KW - estimation of distribution algorithms

KW - Computational time complexity

KW - first hitting time

KW - heuristic optimization

KW - univariate marginal distribution algorithms

U2 - 10.1109/TEVC.2009.2040019

DO - 10.1109/TEVC.2009.2040019

M3 - Article

VL - 14

SP - 1

EP - 22

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 1

ER -