Convergence analysis of UMDAC with finite populations: a case study on flat landscapes

ABSTRACT

This paper presents some new analytical results on the continuous Univariate Marginal Distribution Algorithm (UMDA_C), which is a well known Estimation of Distribution Algorithm based on Gaussian distributions. As the extension of the current theoretical work built on the assumption of infinite populations, the convergence behavior of UMDA_C with finite populations is formally analyzed. We show both analytically and experimentally that, on flat landscapes, the Gaussian model in UMDA_C tends to collapse with high probability, which is an important fact that is not well understood before.

REFERENCES

• 1: Aitchison, J. and Brown, J. The Lognormal Distribution with Special Reference to its Uses in Economics. Cambridge: University Press, 1957.
• 2: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 3: Barnett, H. The Variance of the Product of Two Independent Variables and Its Application to an Investigation Based on Sample Data. Journal of the Institute of Actuaries, 81, 190, 1955.
• 4: Arnaud Berny, Selection and Reinforcement Learning for Combinatorial Optimization, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.601-610, September 18-20, 2000
• 5: Gonzalez, C., Lozano, J. and Larrañaga, P. Analyzing the PBIL algorithm by means of discrete dynamical systems. Complex Systems, 12 (4), 465--479, 2000.
• 6: Gonzalez, C., Lozano, J. and Larrañaga, P. Mathematical Modelling of UMDAc algorithm with tournament selection. Behaviour on linear and quadratic functions. International Journal of Approximate Reasoning, 31, 313--340, 2000.
• 7: Grahl, J., Minner, S. and Rothlauf, F. Behaviour of UMDAc with Truncation Selection on Monotonous Functions. In Proceedings of 2005 Congress on Evolutionary Computation, 2005, 2553--2559.
• 8: He, J. and Yao, X. From an Individual to a Population: An Analysis of the First Hitting Time of Population-based Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 6 (5), 495--511, 2002.
• 9: Jun He , Xin Yao, Towards an analytic framework for analysing the computation time of evolutionary algorithms, Artificial Intelligence, v.145 n.1-2, p.59-97, April 2003 [doi>10.1016/S0004-3702(02)00381-8]
• 10: Hohfeld, M. and Rudolph, G. Towards a Theory of Population-Based Incremental Learning. In Proceedings of IEEE International Conference on Evolutionary Computation (ICEC 97), pp. 1--6, 1997.
• 11: Larrañaga, P. and Lozano, J. Eds., Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.
• 12: Heinz Mühlenbein, The equation for response to selection and its use for prediction, Evolutionary Computation, v.5 n.3, p.303-346, Fall 1997 [doi>10.1162/evco.1997.5.3.303]
• 13: Mühlenbein, H. and Mahnig, T. Convergence Theory and Applications of the Factorized Distribution Algorithm. Journal of Computing and Information Technology, 7 (1), 19--32, 1999.
• 14: Michèle Sebag , Antoine Ducoulombier, Extending Population-Based Incremental Learning to Continuous Search Spaces, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.418-427, September 27-30, 1998
• 15: Shapiro, J. Scaling of Probability-based Optimization Algorithms. In Advances in Neural Information Processing Systems 15 (NIPS2002), 2002, 383--390.
• 16: Yuan, B. Towards Improved Experimental Evaluation and Comparison of Evolutionary Algorithms. Ph.D. Thesis, The University of Queensland, 2006.
• 17: Yuan, B. and Gallagher, M. A Mathematical Modelling Technique for the Analysis of the Dynamics of a Simple Continuous EDA. In Proceedings of 2006 Congress on Evolutionary Computation, 2006, 1585 -- 1591.
• 18: Zhang, Q. On stability of fixed points of limit models of univariate marginal distribution algorithm and factorized distribution algorithm. IEEE Transactions on Evolutionary Computation, 8 (1), 80--93, 2004.
• 19: Zhang, Q. and Mühlenbein, H. On the convergence of a class of estimation of distribution algorithms. IEEE Transactions on Evolutionary Computation, 8(2), 127--136, 2004.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
EDAs, UMDA_C, finite population, theory