article

Sensibility of linkage information and effectiveness of estimated distributions

Authors:

Chung-Yao Chuang,

Ying-ping ChenAuthors Info & Claims

Evolutionary Computation, Volume 18, Issue 4

Pages 547 - 579

https://doi.org/10.1162/EVCO_a_00010

Published: 01 December 2010 Publication History

Abstract

The probabilistic model building performed by estimation of distribution algorithms (EDAs) enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, it may not be possible to completely and accurately identify the whole problem structure by probabilistic modeling due to certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems consisting of structures with unequal fitness contributions. Based on the illustrative example, we introduce a notion that the estimated probabilistic models should be inspected to reveal the effective search directions and further propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented on the extended compact genetic algorithm (ECGA) and experiments are performed on several sets of additively separable problems with different scaling setups. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire problem structure cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.

References

[1]

Baluja, S. (1994). Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Tech. Rep. CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, Pennsylvania.

Digital Library

[2]

Baluja, S., and Davies, S. (1997). Using optimal dependency-trees for combinational optimization. In Proceedings of the 14th International Conference on Machine Learning (ICML '97), pp. 30-38.

Digital Library

[3]

Bosman, P. A. N., and Thierens, D. (1999). Linkage information processing in distribution estimation algorithms. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference 1999 (GECCO-99), Vol. 1, pp. 60-67.

[4]

Chen, Y.-p., and Goldberg, D. E. (2005). Convergence time for the linkage learning genetic algorithm. Evolutionary Computation, 13(3):279-302.

Digital Library

[5]

Cover, T. M., and Thomas, J.A. (1991). Elements of information theory. New York: Wiley-Interscience.

Digital Library

[6]

De Bonet, J., Isbell, C., and Viola, P. (1997). MIMIC: Finding optima by estimating probability densities. In M. C. Mozer, M. I. Jordan, and T. Petsche (Eds.), Advances in Neural Information Processing Systems, Vol. 9, pp. 424-430.

[7]

Deb, K., and Goldberg, D. E. (1993). Analyzing deception in trap functions. In Foundations of Genetic Algorithms 2, pp. 93-108.

[8]

Deb, K., and Goldberg, D. E. (1994). Sufficient conditions for deceptive and easy binary functions. Annals of Mathematics and Artificial Intelligence, 10(4):385-408.

[9]

Echegoyen, C., Lozano, J. A., Santana, R., and Larrañaga, P. (2007). Exact Bayesian network learning in estimation of distribution algorithms. In Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC 2007), pp. 1051-1058.

[10]

Etxeberria, R., and Larrañaga, P. (1999). Global optimization using Bayesian networks. In A. O. Rodriguez, M. S. Ortiz, and R. S. Hermida (Eds.), Proceedings of the Second Symposium on Artificial Intelligence (CIMAF-99), pp. 332-339.

[11]

Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley.

Digital Library

[12]

Goldberg, D. E. (2002). The design of innovation: Lessons from and for competent genetic algorithms. Dordrecht, The Netherlands: Kluwer Academic Publishers.

Digital Library

[13]

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

[14]

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

[15]

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

[16]

Grünwald, P. (2007). The minimum description length principle. Cambridge, MA: MIT Press.

Digital Library

[17]

Harik, G. R. (1997). Learning gene linkage to efficiently solve problems of bounded difficulty using genetic algorithms. PhD thesis, University of Michigan, Ann Arbor.

Digital Library

[18]

Harik, G. R. (1999). Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report No. 99010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign.

[19]

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

Digital Library

[20]

Hauschild, M., Pelikan, M., Lima, C. F., and Sastry, K. (2007). Analyzing probabilistic models in hierarchical BOA on traps and spin glasses. In Proceedings of ACM SIGEVO Genetic and Evolutionary Computation Conference (GECCO-2007), pp. 523- 530.

Digital Library

[21]

Hauschild, M. W., Pelikan, M., Sastry, K., and Goldberg, D. E. (2008). Using previous models to bias structural learning in the hierarchical BOA. In Proceedings of ACM SIGEVO Genetic and Evolutionary Computation Conference (GECCO-2008), pp. 415-422.

Digital Library

[22]

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

Digital Library

[23]

Larrañaga, P., and Lozano, J. A. (2001). Estimation of distribution algorithms: A new tool for evolutionary computation, Vol. 2 of Genetic Algorithms and Evolutionary Computation. Dordrecht, The Netherlands: Kluwer Academic Publishers.

Digital Library

[24]

Lima, C. F., and Lobo, F. G. (2004). Parameter-less optimization with the extended compact genetic algorithm and iterated local search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pp. 1328-1339.

[25]

Lima, C. F., Lobo, F. G., and Pelikan, M. (2008). From mating pool distributions to model overfitting. In Proceedings of ACM SIGEVO Genetic and Evolutionary Computation Conference (GECCO- 2008), pp. 431-438.

Digital Library

[26]

Lima, C. F., Pelikan, M., Goldberg, D. E., Lobo, F. G., Sastry, K., and Hauschild, M. (2007). Influence of selection and replacement strategies on linkage learning in BOA. In Proceedings of 2007 IEEE Congress on Evolutionary Computation (CEC 2007), pp. 1083-1090.

[27]

Lima, C. F., Pelikan, M., Sastry, K., Butz, M.V., Goldberg, D. E., and Lobo, F. G. (2006). Substructural neighborhoods for local search in the Bayesian optimization algorithm. In Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN IX), pp. 232- 241.

Digital Library

[28]

Lima, C. F., Sastry, K., Goldberg, D. E., and Lobo, F. G. (2005). Combining competent crossover and mutation operators: A probabilistic model building approach. In Proceedings of ACM SIGEVO Genetic and Evolutionary Computation Conference (GECCO-2005), pp. 735-742.

Digital Library

[29]

Lobo, F. G., Goldberg, D. E., and Pelikan, M. (2000). Time complexity of genetic algorithms on exponentially scaled problems. In D. Whitley, D. Goldberg, E. Cantú-Paz, L. Spector, I. Parmee, and H.-G. Beyer (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pp. 151-158.

[30]

Mitchell, T. M. (1997). Machine learning. New York: McGraw-Hill Higher Education.

Digital Library

[31]

Mühlenbein, H., and Höns, R. (2005). The estimation of distributions and the minimum relative entropy principle. Evolutionary Computation, 13(1):1-27.

Digital Library

[32]

Mühlenbein, H., and Mahnig, T. (1999). FDA: A scalable evolutionary algorithm for the optimization of additively decomposed functions. Evolutionary Computation, 7(4):353-376.

Digital Library

[33]

Mühlenbein, H., and Paaß, G. (1996). From recombination of genes to the estimation of distributions. I. Binary parameters. In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature (PPSN IV), pp. 178-187.

Digital Library

[34]

Ocenasek, J. (2006). Entropy-based convergence measurement in discrete estimation of distribution algorithms. In J. A. Lozano, P. Larrañaga, I. Inza, and E. Bengoetxea (Eds.), Towards a new evolutionary computation. Advances in estimation of distribution algorithms, Vol. 192 of Studies in Fuzziness and Soft Computing (pp. 39-50). Berlin: Springer.

[35]

Pelikan, M., Goldberg, D. E., and Cantú-Paz, E. (1999). BOA: The Bayesian optimization algorithm. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, pp. 525- 532.

[36]

Pelikan, M., Goldberg, D. E., and Lobo, F. G. (2002). A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21(1):5-20.

Digital Library

[37]

Pelikan, M., Goldberg, D. E., and Sastry, K. (2001). Bayesian optimization algorithm, decision graphs, and Occam's razor. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 519-526.

[38]

Pelikan, M., and Lin, T.-K. (2004). Parameter-less hierarchical BOA. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pp. 24-35.

[39]

Pelikan, M., and Mühlenbein, H. (1999). The bivariate marginal distribution algorithm. In R. Roy, T. Furuhashi, and P. K. Chawdhry (Eds.), Advances in soft computing--Engineering design and manufacturing (pp. 521-535). Berlin: Springer.

[40]

Pelikan, M., Sastry, K., and Goldberg, D. E. (2002). Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning, 31(3):221-258.

[41]

Rissanen, J. (1978). Modelling by shortest data description. Automatica, 14:465-471.

Digital Library

[42]

Sastry, K. (2001). Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign. Also IlliGAL Report No. 2002004.

[43]

Sastry, K., Abbass, H. A., Goldberg, D. E., and Johnson, D. D. (2005). Sub-structural niching in estimation of distribution algorithms. In Proceedings of ACM SIGEVO Genetic and Evolutionary Computation Conference (GECCO-2005), pp. 671-678.

Digital Library

[44]

Sastry, K., and Goldberg, D. E. (2004). Designing competent mutation operators via probabilistic model building of neighborhoods. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pp. 114-125.

[45]

Sastry, K., Lima, C. F., and Goldberg, D. E. (2006). Evaluation relaxation using substructural information and linear estimation. In Proceedings of ACM SIGEVO Genetic and Evolutionary Computation Conference (GECCO-2006), pp. 419-426.

Digital Library

[46]

Sastry, K., Pelikan, M., and Goldberg, D. E. (2004). Efficiency enhancement of genetic algorithms via building-block-wise fitness estimation. In Proceedings of the 2004 IEEE Congress on Evolutionary Computation (CEC 2004), pp. 720-727.

[47]

Schwarz, G. (1978). Estimating the dimension of a model. The Annals of Statistics, 6(2):461-464.

[48]

Thierens, D., Goldberg, D. E., and Pereira, Â. G. (1998). Domino convergence, drift and the temporal salience structure of problems. In Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, pp. 535-540.

[49]

Yu, T.-L., Sastry, K., Goldberg, D. E., and Pelikan, M. (2007). Population sizing for entropy-based model building in discrete estimation of distribution algorithms. In Proceedings of ACM SIGEVO Genetic and Evolutionary Computation Conference (GECCO-2007), pp. 601-608.

Digital Library

Cited By

Omidvar MLi XYao X(2022)A Review of Population-Based Metaheuristics for Large-Scale Black-Box Global Optimization—Part IIIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.313083526:5(823-843)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TEVC.2021.3130835
Chuang CHsu WPelikan MBranke J(2010)Multivariate multi-model approach for globally multimodal problemsProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830544(311-318)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830544

Index Terms

Sensibility of linkage information and effectiveness of estimated distributions
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
      2. Modeling methodologies
2. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

On the effectiveness of distributions estimated by probabilistic model building
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

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 ...
Probabilistic model-building genetic algorithms
GECCO '08: Proceedings of the 10th 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. ...
Probabilistic model-building genetic algorithms
GECCO '10: Proceedings of the 12th 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. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 18, Issue 4

Winter 2010

170 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 December 2010

Published in EVOL Volume 18, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
88
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Omidvar MLi XYao X(2022)A Review of Population-Based Metaheuristics for Large-Scale Black-Box Global Optimization—Part IIIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.313083526:5(823-843)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TEVC.2021.3130835
Chuang CHsu WPelikan MBranke J(2010)Multivariate multi-model approach for globally multimodal problemsProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830544(311-318)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830544

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents