research-article

On the effectiveness of distributions estimated by probabilistic model building

Authors:

Chung-Yao Chuang,

Ying-ping ChenAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 391 - 398

https://doi.org/10.1145/1389095.1389169

Published: 12 July 2008 Publication History

Abstract

Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that capture the likely structure of promising solutions by explicitly building a probabilistic model and utilize the built model to guide the further search. It is presumed that EDAs can detect the structure of the problem by recognizing the regularities of the promising solutions. However, in certain situations, EDAs are unable to discover the entire structure of the problem because the set of promising solutions on which the model is built contains insufficient information regrading some parts of the problem and renders EDAs incapable of processing those parts accurately. In this work, we firstly propose a general concept that the estimated probabilistic models should be inspected to reveal the effective search directions. Based on that concept, we design a practical approach which utilizes a reserved set of solutions to examine the built model for the fragments that may be inconsistent with the actual problem structure. Furthermore, we provide an implementation of the designed approach on the extended compact genetic algorithm (ECGA) and conduct numerical experiments. The experimental results indicate that the proposed method can significantly assist ECGA to handle problems comprising building blocks of disparate scalings.

References

[1]

S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Technical report, Pittsburgh, PA, USA, 1994.

Digital Library

[2]

S. Baluja and S. Davies. Using optimal dependency-trees for combinational optimization. In Proceedings of the 4th ICML, pages 30--38, 1997.

Digital Library

[3]

T. M. Cover and J. A. Thomas. Elements of information theory. Wiley-Interscience, 1991.

Digital Library

[4]

J. de Bonet, C. Isbell, and P. Viola. MIMIC: Finding optima by estimating probability densities. Advances in Neural Information Processing Systems, 9:424--430.

[5]

R. Etxeberria and P. Larrañaga. Global optimization using bayesian networks. In Proceedings of the 2nd Symp. on Artificial Intelligence, pages 332--339, 1999.

[6]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Boston, MA, USA, 1989.

Digital Library

[7]

D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002.

Digital Library

[8]

D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6(4):333--362, 1992.

[9]

D. E. Goldberg, K. Deb, and B. Korb. Messy genetic algorithms revisited: Studies in mixed size and scale. Complex Systems, 4(4):415--444, 1990.

[10]

D. E. Goldberg and M. Rudnick. Genetic algorithms and the variance of fitness. Complex Systems, 5(3):265--278, 1991.

[11]

G. Harik. Linkage learning via probabilistic modeling in the ECGA. Technical Report 99010, Illinois Genetic Algorithms Laboratory, UIUC, IL, USA, 1999.

[12]

G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation, 3(4):287, 1999.

Digital Library

[13]

J. H. Holland. Adaptation in natural and artificial systems. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

[14]

F. G. Lobo, D. E. Goldberg, and M. Pelikan. Time complexity of genetic algorithms on exponentially scaled problems. In Proceedings of GECCO-2000, pages 151--158, 2000.

[15]

T. M. Mitchell. Machine Learning. McGraw-Hill Higher Education, 1997.

Digital Library

[16]

H. Muhlenbein and R. H¨ons. The estimation of distributions and the minimum relative entropy principle. Evolutionary Computation, 13(1):1--27, 2005.

Digital Library

[17]

H. Muhlenbein and G. Paaß. From recombination of genes to the estimation of distributions I. binary parameters. In Proceedings of PPSN IV, 1996.

Digital Library

[18]

M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The Bayesian optimization algorithm. In Proceedings of GECCO-99, pages 525--532, 1999.

[19]

M. Pelikan and H. Muhlenbein. The bivariate marginal distribution algorithm. In Advances in Soft Computing, pages 521--535, 1999.

[20]

D. Thierens, D. E. Goldberg, and ÆA. G. Pereira. Domino convergence, drift and the temporal salience structure of problems. In Proceedings of ICEC '98, pages 535--540, 1998.

Cited By

Chuang CSmith SArnold D(2014)Estimation of distribution algorithms based on n-gramstatistics for sequencing and optimizationProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2598399(53-54)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2598399
Chuang CSmith S(2014)Evolving Mixtures of n-gram Models for Sequencing and Schedule OptimizationParallel Problem Solving from Nature – PPSN XIII10.1007/978-3-319-10762-2_31(312-321)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10762-2_31
Echegoyen CSantana RLozano JLarrañaga P(2008)The Impact of Exact Probabilistic Learning Algorithms in EDAs Based on Bayesian NetworksLinkage in Evolutionary Computation10.1007/978-3-540-85068-7_6(109-139)Online publication date: 2008
https://doi.org/10.1007/978-3-540-85068-7_6

Index Terms

On the effectiveness of distributions estimated by probabilistic model building
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning

Recommendations

Sub-structural niching in estimation of distribution algorithms
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

We propose a sub-structural niching method that fully exploits the problem decomposition capability of linkage-learning methods such as the estimation distribution algorithms and concentrate on maintaining diversity at the sub-structural level. The ...
Probabilistic model-building genetic algorithms
GECCO '07: Proceedings of the 9th annual conference companion on Genetic and evolutionary computation

Probabilistic model-building algorithms (PMBGAs) replace traditional variation of genetic and evolutionary algorithms by (1) building a probabilistic model of promising solutions and (2) sampling the built model to generate new candidate solutions. ...
Multivariate multi-model approach for globally multimodal problems
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

This paper proposes an estimation of distribution algorithm (EDA) aiming at addressing globally multimodal problems, i.e., problems that present several global optima. It can be recognized that many real-world problems are of this nature, and this ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
385
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chuang CSmith SArnold D(2014)Estimation of distribution algorithms based on n-gramstatistics for sequencing and optimizationProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2598399(53-54)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2598399
Chuang CSmith S(2014)Evolving Mixtures of n-gram Models for Sequencing and Schedule OptimizationParallel Problem Solving from Nature – PPSN XIII10.1007/978-3-319-10762-2_31(312-321)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10762-2_31
Echegoyen CSantana RLozano JLarrañaga P(2008)The Impact of Exact Probabilistic Learning Algorithms in EDAs Based on Bayesian NetworksLinkage in Evolutionary Computation10.1007/978-3-540-85068-7_6(109-139)Online publication date: 2008
https://doi.org/10.1007/978-3-540-85068-7_6

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten