Extreme: dynamic multi-armed bandits for adaptive operator selection

ABSTRACT

The performance of evolutionary algorithms is highly affected by the selection of the variation operators to solve the problem at hand. This abstract presents a survey of results that have been obtained using the "Extreme - Dynamic Multi-Armed Bandit" (Ex-DMAB), a technique used to automatically select the operator to be applied between the available ones, while searching for the solution. Experiments on three well-known artificial problems of the EC community are presented, namely the OneMax, the long k-path and the Royal Road, demonstrating some improvements over both any choice of a single-operator alone, and the naive uniform choice of one operator at each application. The Ex-DMAB approach is also compared to the optimal choice of operators, whenever available. The results are discussed in the light of the new parameters that are introduced to tune the selection technique...

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´a. On adaptive operator probabilities in real coded genetic algorithms. In Proc. Intl. Conf. Chilean Computer Science Society, 2000.
• 3: 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
• 4: 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]
• 5: Lawrence Davis, Adapting Operator Probabilities in Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.61-69, June 01, 1989
• 6: Á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]
• 7: 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.
• 8: Álvaro Fialho , Marc Schoenauer , Michèle Sebag, Analysis of adaptive operator selection techniques on the royal road and long k-path problems, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada [doi>10.1145/1569901.1570009]
• 9: David E. Goldberg, Probability Matching, the Magnitude of Reinforcement, and Classifier System Bidding, Machine Learning, v.5 n.4, p.407-425, Oct. 1990 [doi>10.1023/A:1022681708029]
• 10: 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'07, July 2007.
• 11: 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
• 12: F. Lobo and D. Goldberg. Decision making in a hybrid genetic algorithm. In Proc. ICEC'97, pages 121--125. IEEE Press, 1997.
• 13: J. Maturana, A. Fialho, F. Saubion, M. Schoenauer, and M. Sebag. Extreme compass and dynamic multi-armed bandits for adaptive operator selection. In CEC'09: Proceedings of the IEEE International Conference on Evolutionary Computation (to appear). IEEE, 2009.
• 14: 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]
• 15: E. Page. Continuous inspection schemes. Biometrika, 41:100--115, 1954.
• 16: 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]
• 17: 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]
• 18: 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]
• 19: Wong, Lee, Leung, and Ho. A novel approach in parameter adaptation and diversity maintenance for GAs. Soft Computing, 7(8):506--515, 2003.

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