CISUC

The Importance of the Learning Conditions in Hyper-Heuristics

Authors

Abstract

Evolutionary Algorithms are problem solvers inspired by na- ture. The effectiveness of these methods on a specific task usually depends on a non trivial manual crafting of their main components and settings. Hyper-Heuristics is a re- cent area of research that aims to overcome this limitation by advocating the automation of the optimization algorithm design task. In this paper, we describe a Grammatical Evo- lution framework to automatically design evolutionary algo- rithms to solve the knapsack problem. We focus our atten- tion on the evaluation of solutions that are iteratively gen- erated by the Hyper-Heuristic. When learning optimization strategies, the hyper-method must evaluate promising candi- dates by executing them. However, running an evolutionary algorithm is an expensive task and the computational bud- get assigned to the evaluation of solutions must be limited. We present a detailed study that analyses the effect of the learning conditions on the optimization strategies evolved by the Hyper-Heuristic framework. Results show that the computational budget allocation impacts the structure and quality of the learned architectures. We also present exper- imental results showing that the best learned strategies are competitive with state-of-the-art hand designed algorithms in unseen instances of the knapsack problem.

Conference

Genetic and Evolutionary Computation Conference (GECCO 2013), July 2013

PDF File


Cited by

Year 2016 : 5 citations

 Ortiz-Bayliss, José Carlos, Hugo Terashima-Marín, and Santiago Enrique Conant-Pablos. "A Neuro-evolutionary Hyper-heuristic Approach for Constraint Satisfaction Problems." Cognitive Computation 8.3 (2016): 429-441.

 Martin, Matthew Allen. "Hyper-heuristics for the automated design of black-box search algorithms.".

 Mariani, T., Guizzo, G., Vergilio, S. R., & Pozo, A. T. "Automatic Design of Algorithms Applied to the Multi-Objective TSP Problem".

 Mariani, Thainá, Giovani Guizzo, Silvia R. Vergilio, and Aurora TR Pozo. "Grammatical Evolution for the Multi-Objective Integration and Test Order Problem." Proceedings of the 2016 on Genetic and Evolutionary Computation Conference. ACM, 2016.

 Mariani, Thainá, Giovani Guizzo, Silvia R. Vergilio, and Aurora TR Pozo. "A grammatical evolution hyper-heuristic for the integration and test order problem." GECCO. ACM, 2016.

Year 2015 : 2 citations

 Martin, Matthew A., and Daniel R. Tauritz. "Hyper-Heuristics: A Study On Increasing Primitive-Space." Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference. ACM, 2015.

 Matthew A. Martin and Daniel R. Tauritz. 2014. A problem configuration study of the robustness of a black-box search algorithm hyper-heuristic. In Proceedings of the 2014 conference companion on Genetic and evolutionary computation companion (GECCO Comp '14)