Abstract
The performance of an evolutionary algorithm strongly depends on the design of its operators and on the management of these operators along the search; that is, on the ability of the algorithm to balance exploration and exploitation of the search space. Recent approaches automate the tuning and control of the parameters that govern this balance. We propose a new technique to dynamically control the behavior of operators in an EA and to manage a large set of potential operators. The best operators are rewarded by applying them more often. Tests of this technique on instances of 3-SAT return results that are competitive with an algorithm tailored to the problem.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bader-El-Den, M., Poli, R.: Generating sat local-search heuristics using a gp hyper-heuristic framework. In: 8th International Conference, Evolution Artificielle, EA 2007, Tours, France. Lecture Notes in Computer Science, vol. 4926, pp. 37–49. Springer, Berlin (2008)
Battiti, R., Brunato, M.: Learning and Intelligent Optimization Second International Conference, LION 2007 II. Lecture Notes in Computer Science, vol. 5313. Springer, Berlin (2008)
Battiti, R., Brunato, M.: Reactive search optimization: learning while optimizing, In: Handbook of Metaheuristics, 2nd edn. Springer, Berlin (2009, in press)
Battiti, R., Brunato, M., Mascia, F.: Reactive Search and Intelligent Optimization. Operations Research/Computer Science Interfaces, vol. 45. Springer, Berlin (2008)
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, Amsterdam (2009)
Burke, E.K., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology. In: Handbook of Meta-Heuristics, pp. 457–474. Kluwer Academic, Dordrecht (2003)
Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Qu, R.: A survey of hyper-heuristics. Technical Report No. NOTTCS-TR-SUB-0906241418-2747, School of Computer Science and Information Technology, University of Nottingham, Computer Science (2009a)
Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.: A classification of hyper-heuristics approaches. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research and Management Science. Springer, Berlin (2009b, in press)
Cowling, P., Soubeiga, E.: Neighborhood structures for personnel scheduling: a summit meeting scheduling problem (abstract). In: Burke, E.K., Erben, W. (eds.) Proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, Constance, Germany (2000)
Cowling, P.I., Kendall, G., Soubeiga, E.: Hyperheuristics: a tool for rapid prototyping in scheduling and optimisation. In: Applications of Evolutionary Computing, EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN. Lecture Notes in Computer Science, vol. 2279, pp. 1–10. Springer, Berlin (2002)
Crowston, W., Glover, F., Thompson, G., Trawick, J.: Probabilistic and parametric learning combinations of local job shop scheduling rules. Technical Report, ONR Research Memorandum No. 117, GSIA, Carnegie-Mellon University, Pittsburg, PA (1963)
Da Costa, L., Schoenauer, M.: GUIDE, a graphical user interface for evolutionary algorithms design. In: Moore, J.H. (ed.) GECCO Workshop on Open-Source Software for Applied Genetic and Evolutionary Computation (SoftGEC). ACM, New York (2007). Software available at http://guide.gforge.inria.fr/
Davis, L.: Adapting operator probabilities in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 61–69, San Francisco, CA, USA, 1989. Morgan Kaufmann, San Mateo (1989)
De Jong, K.A.: Evolutionary Computation: A Unified Approach. MIT Press, Cambridge (2006)
De Jong, K.A., Spears, W.M.: Using genetic algorithm to solve NP-complete problems. In: Proc. of the 3rd International Conference on Genetic Algorithms (ICGA’89), pp. 124–132, Virginia, USA (1989)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing. Natural Computing Series. Springer, Berlin (2003)
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: Parameter Setting in Evolutionary Algorithms, Computational Intelligence, vol. 54, pp. 19–46. Springer, Berlin (2007)
Fialho, A., Da Costa, L., Schoenauer, M., Sebag, M.: Extreme value based adaptive operator selection. In: Rudolph, G., et al. (eds.) Parallel Problem Solving from Nature—PPSN X, 10th International Conference. Lecture Notes in Computer Science, vol. 5199, pp. 175–184. Springer, Berlin (2008)
Fisher, H., Thompson, L.: Probabilistic learning combinations of local job-shop scheduling rules. In: Industrial Scheduling. Prentice Hall, New York (1963)
Fleurent, C., Ferland, J.A.: Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. In: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 619–652 (1996)
Fukunaga, A.: Automated discovery of local search heuristics for satisfiability testing. Evol. Comput. 16(1), 31–61 (2008)
Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Glover, F., Kochenberger, G.: Handbook of Metaheuristics. International Series in Operations Research & Management Science. Springer, Berlin (2003)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley/Longman, Reading/Harlow (1989)
Goldberg, D.E.: Probability matching, the magnitude of reinforcement, and classifier system bidding. Mach. Learn. 5(4), 407–425 (1990)
Gottlieb, J., Voss, N.: Adaptive fitness functions for the satisfiability problem. In: Parallel Problem Solving from Nature—PPSN VI 6th International Conference. Lecture Notes in Computer Sscience, vol. 1917. Springer, Berlin (2000)
Hamadi, Y., Monfroy, E., Saubion, F.: Special issue on autonomous search. Contraint Program. Lett. 4 (2008a)
Hamadi, Y., Monfroy, E., Saubion, F.: What is autonomous search? Technical Report MSR-TR-2008-80, Microsoft Research (2008b)
Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. University of Michigan Press, Ann Arbor (1975)
Hutter, F., Hamadi, Y., Hoos, H., Brown, K.L.: Performance prediction and automated tuning of randomized and parametric algorithms. In: Twelfth International Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, vol. 4204, pp. 213–228. Springer, Berlin (2006)
Hutter, F., Hoos, H.H., Stützle, T.: Automatic algorithm configuration based on local search. In: Proc. of the Twenty-Second Conference on Artifical Intelligence (AAAI’07), pp. 1152–1157 (2007)
Julstrom, B.A.: What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp. 81–87. Morgan Kaufmann, San Mateo (1995)
Lardeux, F., Saubion, F., Hao, J.-K.: Recombination operators for satisfiability problems. In: Artificial Evolution, 6th International Conference, Evolution Artificielle. Lecture Notes in Computer Science, vol. 2936, pp. 103–114. Springer, Berlin (2004)
Lardeux, F., Saubion, F., Hao, J.-K.: GASAT: a genetic local search algorithm for the satisfiability problem. Evol. Comput. 14(2), 223–253 (2006)
Le Berre, D., Roussel, O., Simon, L.: The SAT2007 competition. Technical Report, Tenth International Conference on Theory and Applications of Satisfiability Testing, May 2007
Lobo, F.G., Goldberg, D.E.: Decision making in a hybrid genetic algorithm. In: IEEE International Conference on Evolutionary Computation, pp. 121–125. IEEE Press, New York (1997)
Lobo, F., Lima, C., Michalewicz, Z. (eds.): Parameter Setting in Evolutionary Algorithms. Studies in Computational Intelligence, vol. 54. Springer, Berlin (2007)
Marchiori, E., Rossi, C.: A flipping genetic algorithm for hard 3-SAT problems. In: Proc. of the Genetic and Evolutionary Computation Conference, vol. 1, pp. 393–400 (1999)
Maturana, J., Saubion, F.: On the design of adaptive control strategies for evolutionary algorithms. In: Proc. Int. Conf. on Artificial Evolution. Lecture Notes in Computer Science, vol. 4926. Springer, Berlin (2007a)
Maturana, J., Saubion, F.: Towards a generic control strategy for EAs: an adaptive fuzzy-learning approach. In: Proceedings of IEEE International Conference on Evolutionary Computation (CEC), pp. 4546–4553 (2007b)
Maturana, J., Saubion, F.: A compass to guide genetic algorithms. In: Rudolph, G., et al. (eds.) Parallel Problem Solving from Nature—PPSN X, 10th International Conference Dortmund, Germany, 13–17 September, 2008. Lecture Notes in Computer Science, vol. 5199, pp. 256–265. Springer, Berlin (2008)
Maturana, J., Fialho, A., Saubion, F., Schoenauer, M., Sebag, M.: Compass and dynamic multi-armed bandits for adaptive operator selection. In: Proceedings of IEEE Congress on Evolutionary Computation CEC (2009)
Meyer-Nieberg, S., Beyer, H.G.: Self-Adaptation in Evolutionary Computation, pp. 47–76. Springer, Berlin (2007)
Nannen, V., Smit, S.K., Eiben, A.E.: Costs and benefits of tuning parameters of evolutionary algorithms. In: Parallel Problem Solving from Nature—PPSN X, 10th International Conference Dortmund, Germany, 13–17 September, 2008. Lecture Notes in Computer Science, vol. 5199, pp. 528–538. Springer, Berlin (2008)
Pareto, V.: Cours d’économie politique. In: Oeuvres Complètes. Droz, Genève (1896)
Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)
Rossi, C., Marchiori, E., Kok, J.N.: An adaptive evolutionary algorithm for the satisfiability problem. In: Proc. of the ACM Symposium on Applied Computing (SAC’00), pp. 463–470. ACM, New York (2000)
Sais, L.: Problème SAT: Progrès et Défis. Collection Programmation par Contraintes. Hermès, Paris (2008)
Simon, L., Le Berre, D.: The SAT2005 competition. Technical Report, Eighth International Conference on the Theory and Applications of Satisfiability Testing, June 2005
Smit, S., Eiben, G.: Comparing parameter tuning methods for evolutionary algorithms. In: Proceedings of the IEEE Congress on Evolutionary Computation (2009)
Smith-Miles, A.K.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1), 1–25 (2008)
Sywerda, G.: Uniform crossover in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 2–9. San Francisco, CA, USA. Morgan Kaufmann, San Mateo (1989)
Thierens, D.: An adaptive pursuit strategy for allocating operator probabilities. In: Beyer, H.-G. (ed.) Proc. GECCO’05, pp. 1539–1546. ACM, New York (2005)
Thierens, D.: Adaptive strategies for operator allocation. In: Lobo, F.G., Lima, C.F., Michalewicz, Z. (eds.) Parameter Setting in Evolutionary Algorithms, pp. 77–90. Springer, Berlin (2007)
Tuson, A., Ross, P.: Adapting operator settings in genetic algorithms. Evol. Comput. 6(2), 161–184 (1998)
Whitacre, J.M., Pham, T.Q., Sarker, R.A.: Use of statistical outlier detection method in adaptive evolutionary algorithms. In: GECCO’06: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 1345–1352. ACM, New York (2006)
Wong, Y.-I., Lee, K.-H., Leung, K.-S., Ho, C.-W.: A novel approach in parameter adaptation and diversity maintenance for GAs. Soft. Comput. 7(8), 506–515 (2003)
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Satzilla: portfolio-based algorithm selection for sat. J. Artif. Intell. Res. 32, 565–606 (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Maturana, J., Lardeux, F. & Saubion, F. Autonomous operator management for evolutionary algorithms. J Heuristics 16, 881–909 (2010). https://doi.org/10.1007/s10732-010-9125-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-010-9125-3