Initial-population bias in the univariate estimation of distribution algorithm

ABSTRACT

This paper analyzes the effects of an initial-population bias on the performance of the univariate marginal distribution algorithm (UMDA). The analysis considers two test problems: (1) onemax and (2) noisy onemax. Theoretical models are provided and verified with experiments. Intuitively, biasing the initial population toward the global optimum should improve performance of UMDA, whereas biasing the initial population away from the global optimum should have the opposite effect. Both theoretical and experimental results confirm this intuition. Effects of mutation on performance of UMDA with initial-population bias are also investigated.

REFERENCES

• 1: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 2: Juergen Branke , Clemens Lode , Jonathan L. Shapiro, Addressing sampling errors and diversity loss in UMDA, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277068]
• 3: W. Feller. An introduction to probability theory and its applications. Wiley, New York, NY, 1970.
• 4: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992.
• 6: D. E. Goldberg and M. Rudnick. Genetic algorithms and the variance of fitness. Complex Systems, 5(3):265--278, 1991. Also IlliGAL Report No. 91001.
• 7: 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. Also IlliGAL Report No. 2001015.
• 8: George Harik , Erick Cantú-Paz , David E. Goldberg , Brad L. Miller, The gambler's ruin problem, genetic algorithms, and the sizing of populations, Evolutionary Computation, v.7 n.3, p.231-253, Fall 1999 [doi>10.1162/evco.1999.7.3.231]
• 9: A. Juels, S. Baluja, and A. Sinclair. The equilibrium genetic algorithm and the role of crossover. Unpublished manuscript, 1993.
• 10: B. L. Miller and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Complex Systems, 9(3):193--212, 1995.
• 11: Brad L. Miller , David E. Goldberg, Genetic algorithms, selection schemes, and the varying effects of noise, Evolutionary Computation, v.4 n.2, p.113-131, Summer 1996 [doi>10.1162/evco.1996.4.2.113]
• 12: H. Mühlenbein. How genetic algorithms really work: I.Mutation and Hillclimbing. In R. Manner and B. Manderick, editors, Parallel Problem Solving from Nature, pages 15--25, Amsterdam, Netherlands, 1992. Elsevier Science.
• 13: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 14: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, 2005.
• 15: K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, Department of General Engineering, Urbana, IL, 2001.
• 16: D. Thierens and D. Goldberg. Convergence models of genetic algorithm selection schemes. Parallel Problem Solving from Nature, pages 116--121, 1994.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Performance

Keywords:
edas, estimation of distribution algorithms, noisy onemax, onemax, population bias, population size, scalability, time to convergence, umda, univariate marginal distribution algorithm