research-article

Adaptive operator selection with dynamic multi-armed bandits

Authors:

Marc Schoenauer,

Michèle SebagAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 913 - 920

https://doi.org/10.1145/1389095.1389272

Published: 12 July 2008 Publication History

Abstract

An important step toward self-tuning Evolutionary Algorithms is to design efficient Adaptive Operator Selection procedures. Such a procedure is made of two main components: a credit assignment mechanism, that computes a reward for each operator at hand based on some characteristics of the past offspring; and an adaptation rule, that modifies the selection mechanism based on the rewards of the different operators. This paper is concerned with the latter, and proposes a new approach for it based on the well-known Multi-Armed Bandit paradigm. However, because the basic Multi-Armed Bandit methods have been developed for static frameworks, a specific Dynamic Multi-Armed Bandit algorithm is proposed, that hybridizes an optimal Multi-Armed Bandit algorithm with the statistical Page-Hinkley test, which enforces the efficient detection of changes in time series. This original Operator Selection procedure is then compared to the state-of-the-art rules known as Probability Matching and Adaptive Pursuit on several artificial scenarios, after a careful sensitivity analysis of all methods. The Dynamic Multi-Armed Bandit method is found to outperform the other methods on a scenario from the literature, while on another scenario, the basic Multi-Armed Bandit performs best.

References

[1]

P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2/3):235--256, 2002.

Digital Library

[2]

H. J. C. Barbosa and A. M. Sá. On adaptive operator probabilities in real coded genetic algorithms. In Proc. XX International Conference of the Chilean Computer Science Society, 2000.

[3]

R. Bertrand. Pratique de l'analyse statistique des donnees. Presses de l'Universite du Quebec, Quebec, QC, 1986.

[4]

L. Davis. Adapting operator probabilities in genetic algorithms. In Proc. 3rd International Conference on Genetic Algorithms, pages 61--69. Morgan Kaufman, 1989.

Digital Library

[5]

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.

[6]

A. E. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in Evolutionary Algorithms. IEEE Trans. Evolutionary Computation, 3(2):124, 1999.

Digital Library

[7]

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.

[8]

D. Goldberg. Probability Matching, the Magnitude of Reinforcement, and Classifier System Bidding. Machine Learning, 5(4):407--426, 1990.

Digital Library

[9]

J. Grefenstette. Optimization of Control Parameters for Genetic Algorithms. IEEE Trans. Systems, Man and Cybernetics, 16:122--128, 1986.

Digital Library

[10]

D. Hinkley. Inference about the change point from cumulative sum-tests. Biometrika, 58(3):509--523, 1970.

[11]

Z. Hussain, P. Auer, N. Cesa-Bianchi, L. Newnham, and J. Shawe-Taylor. Exploration vs. exploitation challenge. In http://www.pascal-network.org/Challenges/EEC/, 2006.

[12]

B. A. Julstrom. What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm on genetic algorithms. In Proc. 6th International Conference on Genetic Algorithms, pages 81--87. Morgan Kaufmann, 1995.

Digital Library

[13]

T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6:4--22, 1985.

Digital Library

[14]

F. Lobo and D. Goldberg. Decision making in a hybrid genetic algorithm. In Proc. IEEE International Conference on Evolutionary Computation, pages 121--125. IEEE Press, 1997.

[15]

F. Lobo, C. Lima, and Z. Michalewicz, editors. Parameter Setting in Evolutionary Algorithms. Springer, 2007.

Digital Library

[16]

G. A. Moore. Crossing the Chasm: Marketing and Selling High-Tech Products to Mainstream Customer. Collins Business Essentials, 1991.

[17]

E. Page. Continuous inspection schemes. Biometrika, 41:100--115, 1954.

[18]

G. Piriou, F. Coldefy, P. Bouthemy, and J.-F. Yao. Détection supervisée d'événements à l'aide d'une modélisation probabiliste du mouvement perçu. In Proc. 14ème Congrès Francophone AFRIF-AFIA de Reconnaissance des Formes et Intelligence Artificielle, 2004.

[19]

W. Spears. Adapting crossover in evolutionary algorithms. In Proc. 4th Annual Conference on Evolutionary Programming, pages 367--384. MIT Press, Cambridge, MA, 1995.

[20]

D. Thierens. An adaptive pursuit strategy for allocating operator probabilities. In Proc. Genetic and Evolutionary Computation Conference, pages 1539--1546. ACM Press, 2005.

Digital Library

[21]

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.

[22]

A. Tuson and P. Ross. Adapting operator settings in genetic algorithms. Evolutionary Computation, 6(2):161--184, 1998.

Digital Library

[23]

J. M. Whitacre, T. Q. Pham, and R. A. Sarker. Use of statistical outlier detection method in adaptive evolutionary algorithms. In Proc. Genetic and Evolutionary Computation Conference, pages 1345--1352. ACM, 2006.

Digital Library

Cited By

Abdul Halim ADas SIsmail IAbdul Halim ADas SIsmail I(2025)Algorithm Parameters: Tuning and ControlInto a Deeper Understanding of Evolutionary Computing: Exploration, Exploitation, and Parameter Control10.1007/978-3-031-75577-4_2(153-283)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-3-031-75577-4_2
Chen XLiao XWei FChen WLi XHandl J(2024)An Order-aware Adaptive Iterative Local Search Metaheuristic for Multi-depot UAV Pickup and Delivery ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654106(1183-1191)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654106
Becerra-Rozas MLemus-Romani JCrawford BSoto RTalbi E(2024)Intelligent decision-making for binary coverage: Unveiling the potential of the multi-armed bandit selectorExpert Systems with Applications10.1016/j.eswa.2024.124112(124112)Online publication date: Apr-2024
https://doi.org/10.1016/j.eswa.2024.124112
Show More Cited By

Index Terms

Adaptive operator selection with dynamic multi-armed bandits
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Operator Selection using Improved Dynamic Multi-Armed Bandit
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Evolutionary algorithms greatly benefit from an optimal application of the different genetic operators during the optimization process: thus, it is not surprising that several research lines in literature deal with the self-adapting of activation ...
Multi-armed bandit problem with known trend

We consider a variant of the multi-armed bandit model, which we call multi-armed bandit problem with known trend, where the gambler knows the shape of the reward function of each arm but not its distribution. This new problem is motivated by different ...
Multi-armed Bandit with Additional Observations
SIGMETRICS '18

We study multi-armed bandit (MAB) problems with additional observations, where in each round, the decision maker selects an arm to play and can also observe rewards of additional arms (within a given budget) by paying certain costs. We propose ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

96
Total Citations
View Citations
774
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abdul Halim ADas SIsmail IAbdul Halim ADas SIsmail I(2025)Algorithm Parameters: Tuning and ControlInto a Deeper Understanding of Evolutionary Computing: Exploration, Exploitation, and Parameter Control10.1007/978-3-031-75577-4_2(153-283)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-3-031-75577-4_2
Chen XLiao XWei FChen WLi XHandl J(2024)An Order-aware Adaptive Iterative Local Search Metaheuristic for Multi-depot UAV Pickup and Delivery ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654106(1183-1191)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654106
Becerra-Rozas MLemus-Romani JCrawford BSoto RTalbi E(2024)Intelligent decision-making for binary coverage: Unveiling the potential of the multi-armed bandit selectorExpert Systems with Applications10.1016/j.eswa.2024.124112(124112)Online publication date: Apr-2024
https://doi.org/10.1016/j.eswa.2024.124112
He CTian YLu Z(2024)Artificial evolutionary intelligence (AEI): evolutionary computation evolves with large language modelsJournal of Membrane Computing10.1007/s41965-024-00172-xOnline publication date: 12-Nov-2024
https://doi.org/10.1007/s41965-024-00172-x
Wang ZWang LJiang QDuan XWang ZWang L(2024)Multiple search operators selection by adaptive probability allocation for fast convergent multitask optimizationThe Journal of Supercomputing10.1007/s11227-024-06016-w80:11(16046-16092)Online publication date: 9-Apr-2024
https://doi.org/10.1007/s11227-024-06016-w
Soria-Alcaraz JOchoa GSotelo-Figueroa MEspinal A(2024)Hypervolume Indicator as an Estimator for Adaptive Operator Selection in an On-Line Multi-objective Hyper-heuristicNew Horizons for Fuzzy Logic, Neural Networks and Metaheuristics10.1007/978-3-031-55684-5_14(197-208)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-55684-5_14
Soria-Alcaraz JOchoa GSotelo-Figueroa MEspinal A(2024)Hypervolume Indicator as an Estimator for Adaptive Operator Selection in an On-Line Multi-objective Hyper-heuristicNew Directions on Hybrid Intelligent Systems Based on Neural Networks, Fuzzy Logic, and Optimization Algorithms10.1007/978-3-031-53713-4_9(99-110)Online publication date: 9-Apr-2024
https://doi.org/10.1007/978-3-031-53713-4_9
Zhang SYang TLiang JYue C(2023)A Novel Adaptive Bandit-Based Selection Hyper-Heuristic for Multiobjective OptimizationIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2023.329998253:12(7693-7706)Online publication date: Dec-2023
https://doi.org/10.1109/TSMC.2023.3299982
Tian YLi XMa HZhang XTan KJin Y(2023)Deep Reinforcement Learning Based Adaptive Operator Selection for Evolutionary Multi-Objective OptimizationIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2022.31468827:4(1051-1064)Online publication date: Aug-2023
https://doi.org/10.1109/TETCI.2022.3146882
Xia WHongwei GMingde ZYaqing HMingyang S(2023)Stochastic online decisioning hyper-heuristic for high dimensional optimizationApplied Intelligence10.1007/s10489-023-05185-054:1(544-564)Online publication date: 15-Dec-2023
https://doi.org/10.1007/s10489-023-05185-0
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten