Abstract
Several techniques have been proposed to tackle the Adaptive Operator Selection (AOS) issue in Evolutionary Algorithms. Some recent proposals are based on the Multi-armed Bandit (MAB) paradigm: each operator is viewed as one arm of a MAB problem, and the rewards are mainly based on the fitness improvement brought by the corresponding operator to the individual it is applied to. However, the AOS problem is dynamic, whereas standard MAB algorithms are known to optimally solve the exploitation versus exploration trade-off in static settings. An original dynamic variant of the standard MAB Upper Confidence Bound algorithm is proposed here, using a sliding time window to compute both its exploitation and exploration terms. In order to perform sound comparisons between AOS algorithms, artificial scenarios have been proposed in the literature. They are extended here toward smoother transitions between different reward settings. The resulting original testbed also includes a real evolutionary algorithm that is applied to the well-known Royal Road problem. It is used here to perform a thorough analysis of the behavior of AOS algorithms, to assess their sensitivity with respect to their own hyper-parameters, and to propose a sound comparison of their performances.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multi-armed bandit problem. Mach. Learn. 47(2–3), 235–256 (2002)
Barbosa, H.J.C., Sá, A.M.: On adaptive operator probabilities in real coded genetic algorithms. In: XX Intl. Conference of the Chilean Computer Science Society (2000)
Bartz-Beielstein, T., Lasarczyk, C., Preuss, M.: Sequential parameter optimization. In: McKay, B. (ed.) Proc. Congress on Evolutionary Computation, pp. 773–780. IEEE (2005)
Birattari, M., Stützle, T., Paquete, L., Varrentrapp, K.: A racing algorithm for configuring metaheuristics. In: Langdon, W.B., et al. (eds.) Proc. Genetic and Evolutionary Computation Conference, pp. 11–18. Morgan Kaufmann (2002)
Collet, P., Schoenauer, M.: GUIDE: unifying evolutionary engines through a graphical user interface. In: Liardet, P., et al. (eds.) Proc. Intl. Conference on Artificial Evolution. LNCS, vol. 2936, pp. 203–215. Springer (2003)
Conover, W.J.: Practical Nonparametric Statistics. Wiley (1999)
Da Costa, L., Fialho, A., Schoenauer, M., Sebag, M.: Adaptive operator selection with dynamic multi-armed bandits. In: Keijzer, M., et al. (eds.) Proc. Genetic and Evolutionary Computation Conference, pp. 913–920. ACM (2008)
Davis, L.: Adapting operator probabilities in genetic algorithms. In: Schaffer, J.D. (ed.) Proc. Intl. Conference on Genetic Algorithms, pp. 61–69. Morgan Kaufmann (1989)
DeJong, K.: Evolutionary Computation. A unified Approach. MIT (2006)
DeJong, K.: Parameter setting in EAs: a 30 year perspective. In: Lobo, F., Lima, C., Michalewicz, Z. (eds.): Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, vol. 54, pp. 1–18. Springer (2007)
Eiben, A.E., Hinterding, R., Michalewicz, Z.: Parameter control in Evolutionary Algorithms. IEEE Trans. Evol. Comput. 3(2), 124–141 (1999)
Eiben, A.E., Michalewicz, Z., Schoenauer, M., Smith, J.E.: Parameter control in evolutionary algorithms. In: Lobo, F., Lima, C., Michalewicz, Z. (eds.): Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, vol. 54, pp. 19–46. Springer (2007)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Springer (2003)
Fialho, A., Da Costa, L., Schoenauer, M., Sebag, M.: Extreme value based adaptive operator selection. In: Rudolph, G., et al. (eds.) Proc. Intl. Conference on Parallel Solving from Nature. LNCS, vol. 5199, pp. 175–184. Springer (2008)
Fialho, A., Da Costa, L., Schoenauer, M., Sebag, M.: Dynamic multi-armed bandits and extreme value-based rewards for adaptive operator selection in evolutionary algorithms. In: Stützle, T. (ed.) Proc. 3rd Intl. Conference on Learning and Intelligent Optimization. LNCS, vol. 5851, pp. 176–190. Springer (2009)
Fialho, A., Schoenauer, M., Sebag, M.: Analysis of adaptive operator selection techniques on the royal road and long k-path problems. In: Raidl, G., et al. (eds.) Proc. Genetic and Evolutionary Computation Conference, pp. 779–786. ACM (2009)
Fogel, D.B.: Phenotypes, genotypes and operators in evolutionary computation. In: Proc. Intl. Conference on Evolutionary Computation. IEEE (1995)
Gagliolo, M., Schmidhuber, J.: Algorithm Selection as a Bandit Problem with Unbounded Losses. Tech. Rep. IDSIA-07-08, IDSIA (2008)
Goldberg, D.: Probability matching, the magnitude of reinforcement, and classifier system bidding. Mach. Learn. 5(4), 407–426 (1990)
Gould, S., Eldredge, N.: Punctuated equilibria: the tempo and mode of evolution reconsidered. Paleobiology 3(2), 115–151 (1977)
Hartland, C., Baskiotis, N., Gelly, S., Teytaud, O., Sebag, M.: Change point detection and meta-bandits for online learning in dynamic environments. In: Proc. Conférence Francophone sur l’Apprentissage Automatique (2007)
Hartland, C., Gelly, S., Baskiotis, N., Teytaud, O., Sebag, M.: Multi-armed bandit, dynamic environments and meta-bandits. In: Online Trading of Exploration and Exploitation Workshop, NIPS (2006)
Hinkley, D.: Inference about the change point from cumulative sum-tests. Biometrika 58(3), 509–523 (1970)
Holland, J.H.: Royal road functions. In: Internet Genetic Algorithms Digest, vol. 7, p. 22. Massachusetts Institute of Technology (1993)
Jones, T.: A description of Holland’s Royal Road. Evol. Comput. 2(4), 409–415 (1994)
Julstrom, B.: What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm. In: Eshelman, L.J., et al. (eds.) Proc. Intl. Conference on Genetic Algorithms, pp. 81–87. Morgan Kaufmann (1995)
Kallel, L., Schoenauer, M.: Fitness Distance Correlation for Variable Length Representations. Tech. Rep. 363, CMAP, Ecole Polytechnique (1996)
Lai, T., Robbins, H.: Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6(1), 4–22 (1985)
Lobo, F., Goldberg, D.: Decision making in a hybrid genetic algorithm. In: Porto, B. (ed.) Proc. Intl. Conference on Evolutionary Computation, pp. 121–125. IEEE (1997)
Lobo, F., Lima, C., Michalewicz, Z. (eds.): Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, vol. 54. Springer (2007)
Maturana, J., Fialho, A., Saubion, F., Schoenauer, M., Sebag, M.: Extreme compass and dynamic multi-armed bandits for adaptive operator selection. In: Proc. Congress on Evolutionary Computation, pp. 365–372. IEEE (2009)
Maturana, J., Lardeux, F., Saubion, F.: Autonomous operator management for evolutionary algorithms. Journal of Heuristics (2010). doi: 10.1007/s10732-010-9125-3
Maturana, J., Saubion, F.: A compass to guide genetic algorithms. In: Rudolph, G., et al. (eds.) Proc. Intl. Conference on Parallel Solving from Nature. LNCS, vol. 5199, pp. 256–265. Springer (2008)
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd edn. Springer, New York (1996)
Mitchell, M., Forrest, S., Holland, J.H.: The royal road for genetic algorithms: fitness landscapes and GA performance. In: Proc. European Conference on Artificial Life, pp. 245–254 (1992)
Nannen, V., Eiben, A.E.: Relevance estimation and value calibration of evolutionary algorithm parameters. In: Veloso, M. (ed.) Proc. Intl. Joint Conference on Artificial Intelligence, pp. 975–980 (2007)
Quick, R.J., Rayward-Smith, V.J., Smith, G.D.: The royal road functions: description, intent and experimentation. In: Selected Papers from AISB Workshop on Evolutionary Computing. LNCS, vol. 1143, pp. 223–235. Springer (1996)
Spears, W.: Adapting crossover in evolutionary algorithms. In: McDonnell, J.R., et al. (eds.) Proc. Conference on Evolutionary Programming, pp. 367–384. MIT (1995)
Stützle, T. (ed.): Proc. 3rd Intl. Conference on Learning and Intelligent Optimization. LNCS, vol. 5851. Springer (2009)
Thierens, D.: An adaptive pursuit strategy for allocating operator probabilities. In: Beyer, H.G. (eds.) Proc. Genetic and Evolutionary Computation Conference, pp. 1539–1546. ACM (2005)
Thierens, D.: Adaptive strategies for operator allocation. In: Lobo, F., Lima, C., Michalewicz, Z. (eds.): Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, vol. 54, pp. 77–90. Springer (2007)
Tuson, A., Ross, P.: Adapting operator settings in genetic algorithms. Evol. Comput. 6(2), 161–184 (1998)
Whitacre, J., Pham, T., Sarker, R.: Use of statistical outlier detection method in adaptive evolutionary algorithms. In: Keijzer, M. (ed.) Proc. Genetic and Evolutionary Computation Conference, pp. 1345–1352. ACM (2006)
Yu, T., Davis, D., Baydar, C., Roy, R. (eds.): Evolutionary Computation in Practice. Studies in Computational Intelligence, vol. 88. Springer (2008)
Yuan, B., Gallagher, M.: Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. In: Yao, X., et al. (eds.) Proc. Intl. Conference on Parallel Solving from Nature. LNCS, vol. 3242, pp. 172–181. Springer (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fialho, Á., Da Costa, L., Schoenauer, M. et al. Analyzing bandit-based adaptive operator selection mechanisms. Ann Math Artif Intell 60, 25–64 (2010). https://doi.org/10.1007/s10472-010-9213-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-010-9213-y