From mating pool distributions to model overfitting

ABSTRACT

This paper addresses selection as a source of overfitting in Bayesian estimation of distribution algorithms (EDAs). The purpose of the paper is twofold. First, it shows how the selection operator can lead to model overfitting in the Bayesian optimization algorithm (BOA). Second, the metric score that guides the search for an adequate model structure is modified to take into account the non-uniform distribution of the mating pool generated by tournament selection.

REFERENCES

• 1: David H. Ackley, A connectionist machine for genetic hillclimbing, Kluwer Academic Publishers, Norwell, MA, 1987
• 2: Tobias Blickle , Lothar Thiele, A comparison of selection schemes used in evolutionary algorithms, Evolutionary Computation, v.4 n.4, p.361-394, Winter 1996 [doi>10.1162/evco.1996.4.4.361]
• 3: A. Brindle. Genetic Algorithms for Function Optimization. PhD thesis, University of Alberta, Edmonton, Canada, 1981. Unpublished doctoral dissertation.
• 4: D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning Bayesian networks with local structure. Technical Report MSR-TR-97-07, Microsoft Research, Redmond, WA.
• 5: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 6: K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Foundations of Genetic Algorithms 2, pages 93--108, 1993.
• 7: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 8: D. E. Goldberg, B. Korb, and K. Deb. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems, 3(5):493--530, 1989.
• 9: D. E. Goldberg and K. Sastry. Genetic Algorithms: The Design of Innovation (2nd Edition). Springer, 2008.
• 10: D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research, Redmond, WA, 1994.
• 11: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 12: C. F. Lima, , D. E. Goldberg, M. Pelikan, F. G. Lobo, K. Sastry, and M. Hauschild. Influence of selection and replacement strategies on linkage learning in BOA. In IEEE Congress on Evolutionary Computation (CEC--2007). IEEE Press, 2007.
• 13: H. Mühlenbein and D. Schlierkamp-Voosen. Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization. Evolutionary Computation, 1(1):25--49, 1993.
• 14: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 15: M. Pelikan. Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms. Springer, 2005.
• 16: M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The Bayesian Optimization Algorithm. In W. Banzhaf et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference GECCO--99, pages 525--532, San Francisco, CA, 1999. Morgan Kaufmann.
• 17: K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2001.
• 18: G. Schwarz. Estimating the dimension of a model. The Annals of Statistics, 6:461--464, 1978.
• 19: Dirk Thierens , David E. Goldberg, Mixing in Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.38-47, June 01, 1993

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Performance, Theory

Keywords:
bayesian networks, bayesian optimization algorithm, estimation of distribution algorithms, overfitting, selection