Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis

Siddhartha Shakya; John McCall; Deryck Brown

doi:10.1145/1068009.1068130

Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis

Siddhartha Shakya, John McCall, Deryck Brown

Emirates ICT Innovation Center

Robert Gordon University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

34 Scopus citations

Abstract

This paper presents an empirical cost-benefit analysis of an algorithm called Distribution Estimation Using MRF with direct sampling (DEUM _d), DEUM_d belongs to the family of Estimation of Distribution Algorithm (EDA). Particularly it is a univariate EDA. DEUM _d uses a computationally more expensive model to estimate the probability distribution than other univariate EDAs. We investigate the performance of DEUM_d in a range of optimization problem. Our experiments shows a better performance (in terms of the number of fitness evaluation needed by the algorithm to find a solution and the quality of the solution) of DEUM_d on most of the problems analysed in this paper in comparison to that of other univariate EDAs. We conclude that use of a Markov Network in a univariate EDA can be of net benefit in defined set of circumstances.

Original language	British English
Title of host publication	GECCO 2005 - Genetic and Evolutionary Computation Conference
Editors	H.G. Beyer, U.M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E.W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, al et al
Pages	727-734
Number of pages	8
DOIs	https://doi.org/10.1145/1068009.1068130
State	Published - 2005
Event	GECCO 2005 - Genetic and Evolutionary Computation Conference - Washington, D.C., United States Duration: 25 Jun 2005 → 29 Jun 2005

Publication series

Name	GECCO 2005 - Genetic and Evolutionary Computation Conference

Conference

Conference	GECCO 2005 - Genetic and Evolutionary Computation Conference
Country/Territory	United States
City	Washington, D.C.
Period	25/06/05 → 29/06/05

Keywords

Estimation of Distribution Algorithms
Evolutionary Computation
Probabilistic Modelling

Access to Document

10.1145/1068009.1068130

Cite this

Shakya, S., McCall, J., & Brown, D. (2005). Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis. In H. G. Beyer, U. M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E. W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, & A. et al (Eds.), GECCO 2005 - Genetic and Evolutionary Computation Conference (pp. 727-734). (GECCO 2005 - Genetic and Evolutionary Computation Conference). https://doi.org/10.1145/1068009.1068130

Shakya, Siddhartha ; McCall, John ; Brown, Deryck. / Using a Markov network model in a univariate EDA : An empirical cost-benefit analysis. GECCO 2005 - Genetic and Evolutionary Computation Conference. editor / H.G. Beyer ; U.M. O'Reilly ; D. Arnold ; W. Banzhaf ; C. Blum ; E.W. Bonabeau ; E. Cantu-Paz ; D. Dasgupta ; K. Deb ; al et al. 2005. pp. 727-734 (GECCO 2005 - Genetic and Evolutionary Computation Conference).

@inproceedings{66c9e0a108e74748b7919ff716606a72,

title = "Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis",

abstract = "This paper presents an empirical cost-benefit analysis of an algorithm called Distribution Estimation Using MRF with direct sampling (DEUM d), DEUMd belongs to the family of Estimation of Distribution Algorithm (EDA). Particularly it is a univariate EDA. DEUM d uses a computationally more expensive model to estimate the probability distribution than other univariate EDAs. We investigate the performance of DEUMd in a range of optimization problem. Our experiments shows a better performance (in terms of the number of fitness evaluation needed by the algorithm to find a solution and the quality of the solution) of DEUMd on most of the problems analysed in this paper in comparison to that of other univariate EDAs. We conclude that use of a Markov Network in a univariate EDA can be of net benefit in defined set of circumstances.",

keywords = "Estimation of Distribution Algorithms, Evolutionary Computation, Probabilistic Modelling",

author = "Siddhartha Shakya and John McCall and Deryck Brown",

year = "2005",

doi = "10.1145/1068009.1068130",

language = "British English",

isbn = "1595930108",

series = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

pages = "727--734",

editor = "H.G. Beyer and U.M. O'Reilly and D. Arnold and W. Banzhaf and C. Blum and E.W. Bonabeau and E. Cantu-Paz and D. Dasgupta and K. Deb and {et al}, al",

booktitle = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

note = "GECCO 2005 - Genetic and Evolutionary Computation Conference ; Conference date: 25-06-2005 Through 29-06-2005",

}

Shakya, S, McCall, J & Brown, D 2005, Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis. in HG Beyer, UM O'Reilly, D Arnold, W Banzhaf, C Blum, EW Bonabeau, E Cantu-Paz, D Dasgupta, K Deb & A et al (eds), GECCO 2005 - Genetic and Evolutionary Computation Conference. GECCO 2005 - Genetic and Evolutionary Computation Conference, pp. 727-734, GECCO 2005 - Genetic and Evolutionary Computation Conference, Washington, D.C., United States, 25/06/05. https://doi.org/10.1145/1068009.1068130

Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis. / Shakya, Siddhartha; McCall, John; Brown, Deryck.
GECCO 2005 - Genetic and Evolutionary Computation Conference. ed. / H.G. Beyer; U.M. O'Reilly; D. Arnold; W. Banzhaf; C. Blum; E.W. Bonabeau; E. Cantu-Paz; D. Dasgupta; K. Deb; al et al. 2005. p. 727-734 (GECCO 2005 - Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Using a Markov network model in a univariate EDA

T2 - GECCO 2005 - Genetic and Evolutionary Computation Conference

AU - Shakya, Siddhartha

AU - McCall, John

AU - Brown, Deryck

PY - 2005

Y1 - 2005

N2 - This paper presents an empirical cost-benefit analysis of an algorithm called Distribution Estimation Using MRF with direct sampling (DEUM d), DEUMd belongs to the family of Estimation of Distribution Algorithm (EDA). Particularly it is a univariate EDA. DEUM d uses a computationally more expensive model to estimate the probability distribution than other univariate EDAs. We investigate the performance of DEUMd in a range of optimization problem. Our experiments shows a better performance (in terms of the number of fitness evaluation needed by the algorithm to find a solution and the quality of the solution) of DEUMd on most of the problems analysed in this paper in comparison to that of other univariate EDAs. We conclude that use of a Markov Network in a univariate EDA can be of net benefit in defined set of circumstances.

AB - This paper presents an empirical cost-benefit analysis of an algorithm called Distribution Estimation Using MRF with direct sampling (DEUM d), DEUMd belongs to the family of Estimation of Distribution Algorithm (EDA). Particularly it is a univariate EDA. DEUM d uses a computationally more expensive model to estimate the probability distribution than other univariate EDAs. We investigate the performance of DEUMd in a range of optimization problem. Our experiments shows a better performance (in terms of the number of fitness evaluation needed by the algorithm to find a solution and the quality of the solution) of DEUMd on most of the problems analysed in this paper in comparison to that of other univariate EDAs. We conclude that use of a Markov Network in a univariate EDA can be of net benefit in defined set of circumstances.

KW - Estimation of Distribution Algorithms

KW - Evolutionary Computation

KW - Probabilistic Modelling

UR - http://www.scopus.com/inward/record.url?scp=32444439999&partnerID=8YFLogxK

U2 - 10.1145/1068009.1068130

DO - 10.1145/1068009.1068130

M3 - Conference contribution

AN - SCOPUS:32444439999

SN - 1595930108

T3 - GECCO 2005 - Genetic and Evolutionary Computation Conference

SP - 727

EP - 734

BT - GECCO 2005 - Genetic and Evolutionary Computation Conference

A2 - Beyer, H.G.

A2 - O'Reilly, U.M.

A2 - Arnold, D.

A2 - Banzhaf, W.

A2 - Blum, C.

A2 - Bonabeau, E.W.

A2 - Cantu-Paz, E.

A2 - Dasgupta, D.

A2 - Deb, K.

A2 - et al, al

Y2 - 25 June 2005 through 29 June 2005

ER -

Shakya S, McCall J, Brown D. Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis. In Beyer HG, O'Reilly UM, Arnold D, Banzhaf W, Blum C, Bonabeau EW, Cantu-Paz E, Dasgupta D, Deb K, et al A, editors, GECCO 2005 - Genetic and Evolutionary Computation Conference. 2005. p. 727-734. (GECCO 2005 - Genetic and Evolutionary Computation Conference). doi: 10.1145/1068009.1068130

Using a Markov network model in a univariate EDA: An empirical cost-benefit analysis

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this