Analysis of adaptive operator selection techniques on the royal road and long k-path problems

ABSTRACT

One of the choices that most affect the performance of Evolutionary Algorithms is the selection of the variation operators that are efficient to solve the problem at hand. This work presents an empirical analysis of different Adaptive Operator Selection (AOS) methods, i.e., techniques that automatically select the operator to be applied among the available ones, while searching for the solution. Four previously published operator selection rules are combined to four different credit assignment mechanisms. These 16 AOS combinations are analyzed and compared in the light of two well-known benchmark problems in Evolutionary Computation, the Royal Road and the Long K-Path.

REFERENCES

• 1: Peter Auer , Nicolò Cesa-Bianchi , Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, v.47 n.2-3, p.235-256, May-June 2002 [doi>10.1023/A:1013689704352]
• 2: H. J. C. Barbosa and A. M. Sá. On adaptive operator probabilities in real coded genetic algorithms. In Proc. Intl. Conf. Chilean Computer Science Society, 2000.
• 3: T. Bartz-Beielstein, C. Lasarczyk, and M. Preuss. Sequential parameter optimization. In Proc. CEC, pages 773--780. IEEE Press, 2005.
• 4: Mauro Birattari , Thomas Stützle , Luis Paquete , Klaus Varrentrapp, A Racing Algorithm for Configuring Metaheuristics, Proceedings of the Genetic and Evolutionary Computation Conference, p.11-18, July 09-13, 2002
• 5: Luis DaCosta , Alvaro Fialho , Marc Schoenauer , Michèle Sebag, Adaptive operator selection with dynamic multi-armed bandits, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389272]
• 6: Lawrence Davis, Adapting Operator Probabilities in Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.61-69, June 01, 1989
• 7: K. De Jong. Parameter Setting in EAs: a 30 Year Perspective. In F. Lobo, C. Lima, and Z. Michalewicz, editors, Parameter Setting in Evolutionary Algorithms,chapter 1, pages 1--18. Springer Verlag, 2007.
• 8: A. E. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in Evolutionary Algorithms. IEEE Trans. on Evolutionary Computation, 3(2):124, 1999.
• 9: A. E. Eiben, Z. Michalewicz, M. Schoenauer, and J. E. Smith. Parameter Control in Evolutionary Algorithms. In F. Lobo, C. Lima, and Z. Michalewicz, editors, Parameter Setting in Evolutionary Algorithms, chapter 2, pages 19--46. Springer Verlag, 2007.
• 10: Álvaro Fialho , Luís Costa , Marc Schoenauer , Michèle Sebag, Extreme Value Based Adaptive Operator Selection, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_18]
• 11: A. Fialho, L. DaCosta, M. Schoenauer, and M. Sebag. Dynamic multi-armed bandits and extreme value-based rewards for adaptive operator selection. In Proc. LION-3. Springer--Verlag, 2009.
• 12: J. Garnier and L. Kallel. Statistical distribution of the convergence time of evolutionary algorithms for long-path problems. IEEE Trans. Evolutionary Computation, 4(1):16--30, 2000.
• 13: J. J. Grefenstette. Deception considered harmful. In Foundations of Genetic Algorithms 2, pages 75--91. Morgan Kaufmann, 1993.
• 14: C. Hartland, N. Baskiotis, S. Gelly, O. Teytaud, and M. Sebag. Change point detection and meta-bandits for online learning in dynamic environments. In Proc. CAp, July 2007.
• 15: D. Hinkley. Inference about the change point from cumulative sum--tests. Biometrika, 58(3):509--523, 1970.
• 16: J. H. Holland. Royal road functions. In Internet Genetic Algorithms Digest 7:22. Massachusetts Institute of Technology, 1993.
• 17: Jeffrey Horn , David E. Goldberg , Kalyanmoy Deb, Long Path Problems, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.149-158, October 09-14, 1994
• 18: F. Hutter, Y. Hamadi, H. H. Hoos, and K. Leyton-Brown. Performance prediction and automated tuning of randomized and parametric algorithms. In Proc. CP, number 4204 in LNCS, pages 213--228. Springer Verlag, 2006.
• 19: Terry Jones, A description of holland's royal road function, Evolutionary Computation, v.2 n.4, p.409-415, Winter 1994 [doi>10.1162/evco.1994.2.4.409]
• 20: Bryant A. Julstrom, What Have You Done for Me Lately? Adapting Operator Probabilities in a Steady-State Genetic Algorithm, Proceedings of the 6th International Conference on Genetic Algorithms, p.81-87, July 15-19, 1995
• 21: T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6:4--22, 1985.
• 22: F. Lobo and D. Goldberg. Decision making in a hybrid genetic algorithm. In Proc. ICEC, pages 121--125. IEEE Press, 1997.
• 23: Fernando G.. Lobo , Cludio F. Lima , Zbigniew Michalewicz, Parameter Setting in Evolutionary Algorithms, Springer Publishing Company, Incorporated, 2007
• 24: V. Maniezzo, R. Battiti, and J.-P. Watson, editors. Learning and Intelligent Optimization, Foundations of Computing. Springer Verlag, 2008.
• 25: Jorge Maturana , Frédéric Saubion, A Compass to Guide Genetic Algorithms, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_26]
• 26: M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In Proc. ECAL, pages 245--254, Cambridge, MA, 1992.
• 27: V. Nannen and A. E. Eiben. Relevance estimation and value calibration of evolutionary algorithm parameters. In Proc. IJCAI, pages 975--980, Hyderabad, India, 2007.
• 28: R. J. Quick , Victor J. Rayward-Smith , G. D. Smith, The Royal Road Functions: Description, Intent and Experimentation, Selected Papers from AISB Workshop on Evolutionary Computing, p.223-235, April 01-02, 1996
• 29: G. Rudolph. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovac, 1997.
• 30: Dirk Thierens, An adaptive pursuit strategy for allocating operator probabilities, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068251]
• 31: D. Thierens. Adaptive Strategies for Operator Allocation. In F. Lobo, C. Lima, and Z. Michalewicz, editors, Parameter Setting in Evolutionary Algorithms, pages 77--90. Springer Verlag, 2007.
• 32: Andrew Tuson , Peter Ross, Adapting operator settings in genetic algorithms, Evolutionary Computation, v.6 n.2, p.161-184, Summer 1998 [doi>10.1162/evco.1998.6.2.161]
• 33: James M. Whitacre , Tuan Q. Pham , Ruhul A. Sarker, Use of statistical outlier detection method in adaptive evolutionary algorithms, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144205]
• 34: B. Yuan and M. Gallagher. Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. In Xin Yao et al., editor, PPSN VIII, pages 172--181. LNCS 3242, Springer Verlag, 2004.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
adaptive operator selection, genetic algorithms, parameter control