A memetic algorithm using local search chaining forblack-box optimization benchmarking 2009 for noise free functions

ABSTRACT

Memetic algorithms with continuous local search methods have arisen as effective tools to address the difficulty of obtaining reliable solutions of high precision for complex continuous optimisation problems. There exists a group of continuous search algorithms that stand out as brilliant local search optimisers. Several of them, like CMA-ES, often require a high number of evaluations to adapt its parameters. Unfortunately, this feature makes difficult to use them to create memetic algorithms.

In this work, we show a memetic algorithm that applies CMA-ES to refine the solutions, assigning to each individual a local search intensity that depends on its features, by chaining different local search applications.

Experiments are carried out on the noise free Black-Box Optimization Benchmarking BBOB'2009 test suite.

REFERENCES

• 1: A. Auger and N. Hansen. Performance Evaluation of an Advanced Local Search Evolutionary Algorithm. In 2005 IEEE Congress on Evolutionary Computation, pages 1777--1784, 2005.
• 2: A. Auger, M. Schoenauer, and N. Vanhaecke. LS-CMAES: a second-order algorithm for covariance matrix adaptation. In Proc. of the Parallel problems solving for Nature -- PPSN VIII, Sept. 2004, Birmingham, 2004.
• 3: L. Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.
• 4: W.B. et al., editor. Optimizing global-local search hybrids. Morgan Kaufmann, San Mateo, California, 1999.
• 5: S. Finck, N. Hansen, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Presentation of the noisy functions. Technical Report 2009/21, Research Center PPE, 2009.
• 6: N. Hansen. Compilation of Results on the CEC Benchmark Function Set. In 2005 IEEE Congress on Evolutionary Computation, 2005.
• 7: N. Hansen, A. Auger, S. Finck, and R. Ros. Real-parameter black-box optimization benchmarking 2009: Experimental setup. Technical Report RR-6828, INRIA, 2009.
• 8: N. Hansen, S. Finck, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Noisy functions definitions. Technical Report RR-6869, INRIA, 2009.
• 9: N. Hansen and S. Kern. Evaluating the CMA Evolution Strategy on Multimodal Test Functions. In X. Y. at al., editor, Parallel Problem Solving for domly (keeping the best individual). Nature -- PPSN VIII, LNCS 3242, pages 282--291. Springer, 2004.
• 10: 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]
• 11: N. Hansen and A. Ostermeier. Adapting Arbitrary Normal Mutation Distributions in Evolution Strategies: The Covariance Matrix Adaptation. In Proceeding of the IEEE International Conference on Evolutionary Computation (ICEC '96), pages 312--317, 1996.
• 12: William Eugene Hart, Adaptive global optimization with local search, University of California at San Diego, La Jolla, CA, 1994
• 13: N. Krasnogor and J. Smith. A Tutorial for Competent Memetic Algorithms: Model, Taxonomy, and Design Issue. IEEE Transactions on Evolutionary Computation, 9(5):474--488, 2005.
• 14: Mark William Shannon Land , Richard K. Belew, Evolutionary algorithms with local search for combinatorial optimization, University of California, San Diego, 1998
• 15: P. Merz. Memetic Algorithms for Combinational Optimization Problems: Fitness Landscapes and Effective Search Strategies. PhD thesis, Gesamthochschule Siegen, University of Siegen, Germany, 2000.
• 16: D. Molina, M. Lozano, C. García-Martínez, and F. Herrera. Memetic algorithms for continuous optimization based on local search chains. Evolutionary Computation. In press, 2009.
• 17: P. Moscato. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical report, Technical Report Caltech Concurrent Computation Program Report 826, Caltech, Pasadena, California, 1989.
• 18: Pablo Moscato, Memetic algorithms: a short introduction, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 19: P. Suganthan, N. Hansen, J. Liang, K. Deb, Y. Chen, A. Auger, and S. Tiwari. Problem definitions and evaluation criteria for the CEC 2005 special session on real parameter optimization. Technical report, Nanyang Technical University, 2005.
• 20: Gilbert Syswerda, Uniform Crossover in Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.2-9, June 01, 1989
• 21: E.-G. Talbi, A Taxonomy of Hybrid Metaheuristics, Journal of Heuristics, v.8 n.5, p.541-564, September 2002 [doi>10.1023/A:1016540724870]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
benchmarking, black-box optimization, evolutionary computation, hybrid metaheuristics, memetic algorithms