A continuous variable neighbourhood search based on specialised eas: application to the noisy BBO-benchmark 2009 testbed

ABSTRACT

Variable Neighbourhood Search is a metaheuristic combining three components: generation, improvement, and shaking components. In this paper, we design a continuous Variable Neighbourhood Search algorithm based on three specialised Evolutionary Algorithms, which play the role of each aforementioned component: 1) an EA specialised in generating a good starting point as generation component, 2) an EA specialised in exploiting local information as improvement component, 3) and another EA specialised in providing local diversity as shaking component. Experiments are carried out on the noisy Black-Box Optimisation Benchmark 2009 testbed.

REFERENCES

• 1: A. Auger and N. Hansen. Performance evaluation of an advanced local search evolutionary algorithm. In D. Corne et al., editors, Proc. of the IEEE Int. Conf. on Evolutionary Computation, volume 2, pages 1777--1784. IEEE Press, 2005.
• 2: I. Charon and O. Hudry. The noising methods: A generalization of some metaheuristics. European Journal of Operational Research, 135(1):86--101, 2001.
• 3: Kalyanmoy Deb , Ashish Anand , Dhiraj Joshi, A computationally efficient evolutionary algorithm for real-parameter optimization, Evolutionary Computation, v.10 n.4, p.371-395, December 2002 [doi>10.1162/106365602760972767]
• 4: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 5: L. Eshelman and J. Schaffer. Real-coded genetic algorithms and interval-schemata. In L. Whitley, editor, Foundations of Genetic Algorithms 2, pages 187--202. Morgan Kaufmann, 1993.
• 6: 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.
• 7: C. García-Martínez and M. Lozano. Local search based on genetic algorithms. In P. Siarry and Z. Michalewicz, editors, Advances in Metaheuristics for Hard Optimization, Natural Computing, pages 199--221. Springer, 2008.
• 8: Carlos García-Martínez , Manuel Lozano, A continuous variable neighbourhood search based on specialised EAs: application to the noiseless BBO-benchmark 2009, Proceedings of the 11th annual conference companion on Genetic and evolutionary computation conference, July 08-12, 2009, Montreal, Québec, Canada [doi>10.1145/1570256.1570319]
• 9: C. García-Martínez, M. Lozano, F. Herrera, D. Molina, and A. Sánchez. Global and local real-coded genetic algorithms based on parent-centric crossover operators. European Journal of Operational Research, 185(3):1088--1113, 2008.
• 10: C. García-Martínez, M. Lozano, and D. Molina. A local genetic algorithm for binary-coded problems. In T. Runarsson et al., editors, Proc. of the Int. Conf. on Parallel Problem Solving from Nature, volume 4193 of LNCS, pages 192--201. Springer, 2006.
• 11: F. Glover and G. Kochenberger, editors. Handbook of Metaheuristics. Kluwer Academic Publishers, 2003.
• 12: N. Hansen, A. Auger, S. Finck, and R. Ros. Real-parameter black-box optimization benchmarking 2009: Experimental setup. Technical Report RR-6828, INRIA, 2009.
• 14: 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.
• 15: 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]
• 16: 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]
• 17: F. Herrera , M. Lozano , J. L. Verdegay, Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis, Artificial Intelligence Review, v.12 n.4, p.265-319, Aug. 1, 1998 [doi>10.1023/A:1006504901164]
• 18: Kengo Katayama , Hiroyuki Narihisa, A new iterated local search algorithm using genetic crossover for the traveling salesman problem, Proceedings of the 1999 ACM symposium on Applied computing, p.302-306, February 28-March 02, 1999, San Antonio, Texas, United States [doi>10.1145/298151.298359]
• 19: S. Kirkpatrick, C. Gelatt Jr, and M. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, 1983.
• 20: Manuel Lozano , C. García-Martínez, An Evolutionary ILS-Perturbation Technique, Proceedings of the 5th International Workshop on Hybrid Metaheuristics, p.1-15, October 08-09, 2008, Málaga, Spain [doi>10.1007/978-3-540-88439-2_1]
• 21: M. Lozano and C. García-Martínez. Hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification: Overview and progress report. Computers & Operations Research. In press, 2009.
• 22: Manuel Lozano , Francisco Herrera , Natalio Krasnogor , Daniel Molina, Real-coded memetic algorithms with crossover hill-climbing, Evolutionary Computation, v.12 n.3, p.273-302, September 2004 [doi>10.1162/1063656041774983]
• 23: N. Mladenović , P. Hansen, Variable neighborhood search, Computers and Operations Research, v.24 n.11, p.1097-1100, Nov. 1997 [doi>10.1016/S0305-0548(97)00031-2]
• 24: 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
          Subjects: Global optimization

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization

General Terms:
Algorithms

Keywords:
benchmarking, black-box optimization, evolutionary computation, hybrid metaheuristics, specialised evolutionary algorithms, variable neighbourhood search