Estimation of fitness landscape contours in EAs

ABSTRACT

Evolutionary algorithms applied in real domain should profit from information about the local fitness function curvature. This paper presents an initial study of an evolutionary strategy with a novel approach for learning the covariance matrix of a Gaussian distribution. The learning method is based one stimation of the fitness landscape contour line between the selected and discarded individuals. The distribution learned this way is then used to generate new population members. The algorithm presented here is the first attempt to construct the Gaussian distribution this way and should beconsidered only a proof of concept; nevertheless, the empirical comparison on low-dimensional quadratic functions shows that our approach is viable and with respect to the number of evaluations needed to find a solution of certain quality, it is comparable to the state-of-the-art CMA-ES incase of sphere function and outperforms the CMA-ES in case of elliptical function.

REFERENCES

• 1: A. Auger, M. Schoenauer, and N. Vanhaecke. LS-CMA-ES: A second-order algorithm for covariance matrix adaptation. In X. Y. et al., editor, Parallel Problem Solving from Nature VIII, number 3242 in LNCS, pages 182--191. Springer Verlag, 2004.
• 2: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 3: P. A. Bosman and J. Grahl. Matching inductive bias and problem structure in continuous estimation-of-distribution algorithms. European Journal of Operational Research, 2006.
• 4: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 5: 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]
• 6: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer series in statistics. Springer Verlag, 2001.
• 7: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms. GENA. Kluwer Academic Publishers, 2002.
• 8: Ryszard S. Michalski, LEARNABLE EVOLUTION MODEL: Evolutionary Processes Guided by Machine Learning, Machine Learning, v.38 n.1-2, p.9-40, Jan.&slash;Feb. 2000 [doi>10.1023/A:1007677805582]
• 9: R. S. Michalski. Attributional calculus: A logic and representation language for natural induction. Reports of the Machine Learning and Inference Laboratory MLI 04-2, George Mason University, Fairfax, VA, April 2004.
• 10: P. Poaík. Real-parameter optimization using the mutation step co-evolution. In IEEE Congress on Evolutionary Computation, pages 872--879. IEEE, 2005. ISBN 0-7803-9364-3.
• 11: G. Rudolph. Self-adaptive mutations may lead to premature convergence. IEEE Trans. on Evolutionary Computation, 5(4):410--413, August 2001.
• 12: M. I. Schlesinger and V. Hlaváč. Ten Lectures on Statistical and Structural Pattern Recognition. Kluwer Academic Publishers, Dodrecht, The Netherlands, 2002.
• 13: B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, Cambridge, Massachusetts, 2002.
• 14: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 15: V. Vapnik and A. Lerner. Pattern recognition using generalized portrait method. Automation and Remote Control, 24:774--780, 1963.
• 16: J. Wojtusiak and R. S. Michalski. The LEM3 system for non-darwinian evolutionary computation and its application to complex function optimization. Reports of the Machine Learning and Inference Laboratory MLI 04-1, George Mason University, Fairfax, VA, February 2006.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

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

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
estimation of distribution algorithms, evolutionary computation, function optimization, learnable evolution model, separating ellipsoid