The correlation-triggered adaptive variance scaling IDEA

ABSTRACT

It has previously been shown analytically and experimentally that continuous Estimation of Distribution Algorithms (EDAs) based on the normal pdf can easily suffer from premature convergence. This paper takes a principled first step towards solving this problem. First, prerequisites for the successful use of search distributions in EDAs are presented. Then, an adaptive variance scaling theme is introduced that aims at reducing the risk of premature convergence. Integrating the scheme into the iterated density--estimation evolutionary algorithm (IDEA) yields the correlation-triggered adaptive variance scaling IDEA (CT-AVS-IDEA). The CT-AVS-IDEA is compared to the original IDEA and the Evolution Strategy with Covariance Matrix Adaptation (CMA-ES) on a wide range of unimodal test-problems by means of a scalability analysis. It is found that the average number of fitness evaluations grows subquadratically with the dimensionality, competitively with the CMA-ES. In addition, CT-AVS-IDEA is indeed found to enlarge the class of problems that continuous EDAs can solve reliably.

REFERENCES

• 1: C. W. Ahn, R. S. Ramakrishna, and D. E. Goldberg. Real-coded Bayesian optimization algorithm: Bringing the strength of BOA into the continuous world. In K. Deb et al., editors, Proceedings of the GECCO - 2004 Genetic and Evolutionary Computation Conference, pages 840--851, Berlin, 2004. Springer--Verlag.
• 2: T. W. Anderson. An Introduction to Multivariate Statistical Analysis. John Wiley & Sons Inc., New York, New York, 1958.
• 3: T. Blickle and L. Thiele. A comparison of selection schemes used in evolutionary algorithms. Evolutionary Computation, 4(4):361--394, 1996.
• 4: P. A. N. Bosman. Design and Application of Iterated Density-Estimation Evolutionary Algorithms. PhD thesis, University of Utrecht, Institute of Information and Computer Science, 2003.
• 5: P. A. N. Bosman and J. Grahl. Matching inductive search bias and problem structure in continuous estimation-of-distribution algorithms. Technical Report 03/2005, Mannheim Business School, Dept. of Logistics, 2005.
• 6: Peter A. N. Bosman , Dirk Thierens, Expanding from Discrete to Continuous Estimation of Distribution Algorithms: The IDEA, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.767-776, September 18-20, 2000
• 7: P. A. N. Bosman and D. Thierens. Advancing continuous IDEAs with mixture distributions and factorization selection metrics. In M. Pelikan and K. Sastry, editors, Proceedings of the Optimization by Building and Using Probabilistic Models OBUPM Workshop at the Genetic and Evolutionary Computation Conference GECCO - 2001, pages 208--212, San Francisco, California, 2001. Morgan Kaufmann.
• 8: P. A. N. Bosman and D. Thierens. Learning probabilistic models for enhanced evolutionary computation. In Y. Jin, editor, Knowledge Incorporation in Evolutionary Computation, pages 147--176. Springer-Verlag, Berlin, 2004.
• 9: M. Gallagher, M. Frean, and T. Downs. Real-valued evolutionary optimization using a flexible probability density estimator. In W. Banzhaf et al., editors, Proc. of the Genetic and Evolutionary Computation Conference GECCO - 1999, pages 840--846, San Francisco, California, 1999. Morgan Kaufmann.
• 10: C. González, J. A. Lozano, and P. Larrañaga. Mathematical modelling of UMDAc algorithm with tournament selection. Behaviour on linear and quadratic functions. International Journal of Approximate Reasoning, 31(3):313--340, 2002.
• 11: J. Grahl, S. Minner, and F. Rothlauf. Behaviour of UMDAc with truncation selection on monotonous functions. In The 2005 IEEE Congress on Evolutionary Computation. IEEE CEC 2005, 2005.
• 12: Nikolaus Hansen , Sibylle D. Müller , Petros Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evolutionary Computation, v.11 n.1, p.1-18, Spring 2003 [doi>10.1162/106365603321828970]
• 13: Nikolaus Hansen , Andreas Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, v.9 n.2, p.159-195, June 2001 [doi>10.1162/106365601750190398]
• 14: R. V. Hogg and A. T. Craig. Introduction to Mathematical Statistics. Macmillan, New York, 5th edition, 1995.
• 15: Stefan Kern , Sibylle D. Müller , Nikolaus Hansen , Dirk Büche , Jiri Ocenasek , Petros Koumoutsakos, Learning probability distributions in continuous evolutionary algorithms– a comparative review, Natural Computing: an international journal, v.3 n.1, p.77-112, 2004 [doi>10.1023/B:NACO.0000023416.59689.4e]
• 16: P. Larrañaga, R. Etxeberria, J. A. Lozano, and J. M. Peña. Optimization in continuous domains by learning and simulation of Gaussian networks. In M. Pelikan et al., editors, Proc. of the Optimization by Building and Using Probabilistic Models OBUPM Workshop at the Genetic and Evolutionary Computation Conference GECCO - 2000, pages 201--204, San Francisco, California, 2000. Morgan Kaufmann.
• 17: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 18: H. Mühlenbein and T. Mahnig. FDA - a scalable evolutionary algorithm for the optimization of additively decomposed functions. Evolutionary Computation, 7(4):353--376, 1999.
• 19: 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
• 20: J. Ocenasek, S. Kern, N. Hansen, and P. Koumoutsakos. A mixed Bayesian optimization algorithm with variance adaptation. In X. Yao et al., editors, Parallel Problem Solving from Nature - PPSN VIII, pages 352--361, Berlin, 2004. Springer-Verlag.
• 21: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258 ]
• 22: 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
• 23: Isabelle Servet , Louise Travé-Massuyès , Daniel Stern, Telephone Network Traffic Overloading Diagnosis and Evolutionary Computation Techniques, Selected Papers from the Third European Conference on Artificial Evolution, p.137-144, October 01, 1997
• 24: Maurice M. Tatsuoka, Multivariate analysis: techniques for educational and psychological research, 2nd ed., Macmillan Publishing Co., Inc., Indianapolis, IN, 1987
• 25: Bo Yuan , Marcus Gallagher, On the importance of diversity maintenance in estimation of distribution algorithms, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068129]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods

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

General Terms:
Algorithms, Performance

Keywords:
adaptive variance scaling, estimation of distribution algorithms, evolutionary algorithms, numerical optimization