Population sizing for entropy-based model building in discrete estimation of distribution algorithms

ABSTRACT

This paper proposes a population-sizing model for entropy-based model building in discrete estimation of distribution algorithms. Specifically, the population size required for building an accurate model is investigated. The effect of selection pressure on population sizing is also preliminarily incorporated. The proposed model indicates that the population size required for building an accurate model scales as Θ(m log m), where m is the number of substructures of the given problem and is proportional to the problem size. Experiments are conducted to verify the derivations, and the results agree with the proposed model.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: C. Aporntewan and P. Chongstitvatana. Building-block identification by simultaneity matrix. Proceedings of the Genetic and Evolutionary Computation Conference, pages 1566--1567, 2003.
• 3: Thomas Bäck, Generalized Convergence Models for Tournament- and (mu, lambda)-Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.2-8, July 15-19, 1995
• 4: Tobias Blickle , Lothar Thiele, A Mathematical Analysis of Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.9-16, July 15-19, 1995
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: R. Etxeberria and P. Larranaga. Global optimization using bayesian networks. Proceedings of the Second Symposium on Artificial Intelligence Adaptive Systems, pages 332--339, 1999.
• 7: W. Feller. An Introduction to Probability Theory, volume 2. Wiley, New York, 1966.
• 8: D. E. Goldberg. Simple genetic algorithms and the minimal, deceptive problem. In Genetic Algorithms and Simulated Annealing, chapter 6, pages 74--88. Pitman Publishing, London, 1987.
• 9: David E. Goldberg, Sizing Populations for Serial and Parallel Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.70-79, June 01, 1989
• 10: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 11: D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992.
• 12: D. E. Goldberg, K. Sastry, and T. Latoza. On the supply of building blocks. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 336--342, 2001.
• 13: G. Harik. Linkage learning via probabilistic modeling in the ecga. IlliGAL Report No. 99010, University of Illinois at Urbana-Champaign, Urbana, IL, February 1999.
• 14: G. Harik, E. Cantu-Paz, D. E. Goldberg, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, pages 7--12, 1997.
• 15: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 16: M. Hutter and M. Zaffalon. Distribution of mutual information from complete and incomplete data. Computational Statistics and Data Analysis, 48(3):633--657, 2005.
• 17: P. Larranaga and J. Lozano, editors. Estimation of Distribution Algorithms. Kluwer Academic Publishers, Boston, MA, 2002.
• 18: M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. Towards a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, pages 245--254, 1992.
• 19: Heinz Mühlenbein , Robin Höns, The Estimation of Distributions and the Minimum Relative Entropy Principle, Evolutionary Computation, v.13 n.1, p.1-27, January 2005 [doi>10.1162/1063656053583469]
• 20: M. Munetomo and D. E. Goldberg. Identifying linkage groups by nonlinearity/non-monotonicity detection. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), 1:433--440, 1999.
• 21: J. Ocenasek. Entropy--based convergence measurement in discrete estimation of distribution algorithms. In L. Jose A., L. Pedro, and I. Inaki, editors, Towards a New Evolutionary Computation: Advances in Estimation of Distribution Algorithms, pages 39--49. Springer Verlag, New Yorks, 2006.
• 22: M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO--1999), I:525--532, 1999.
• 23: M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. Bayesian optimization algorithm, population sizing, and time to convergence. Proceedings of the Genetic and Evolutionary Computation Conference, pages 275--282, 2000.
• 24: Martin Pelikan , Kumara Sastry , Erick Cantú-Paz, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 25: M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning, 31(3):221--258, 2003.
• 26: Colin R. Reeves, Using Genetic Algorithms with Small Populations, Proceedings of the 5th International Conference on Genetic Algorithms, p.92-99, June 01, 1993
• 27: K. Sastry and D. E. Goldberg. On extended compact genetic algorithm. Late-Breaking Paper at the Genetic and Evolutionary Computation Conference, pages 352--359, 2000.
• 28: K. Sastry and D. E. Goldberg. Designing competent mutation operators via probabilistic model building of neighborhoods. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), 2:114--125, 2004.
• 29: C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:379--423, 1948.
• 30: A. Wright, R. Poli, C. Stephens, W. B. Landgon, and S. Pulavarty. An estimation of distribution algorithm based on maximum entropy. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pages 343--354, 2004.
• 31: Tian-Li Yu , David E. Goldberg, Conquering hierarchical difficulty by explicit chunking: substructural chromosome compression, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144210]
• 32: T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-p. Chen. Genetic algorithm design inspired by organizational theory: Pilot study of a dependency structure matrix driven genetic algorithm. Proceedings of Artificial Neural Networks in Engineering (ANNIE 2003), pages 327--332, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms, Theory

Keywords:
entropy, estimation of distribution algorithms, genetic algorithms, model building, mutual information, population sizing