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 2018 : 3 citations
Nyathi, T., & Pillay, N. (2018). Comparison of a genetic algorithm to grammatical evolution for automated design of genetic programming classification algorithms. Expert Systems with Applications, 104, 213-234.
Pillay, N., & Qu, R. Hyper-Heuristics: Theory and Applications.
Sevaux, M., Sörensen, K., & Pillay, N. (2018). Adaptive and multilevel metaheuristics. Handbook of Heuristics, 1-19.
Year 2017 : 3 citations
D?az, X. F. C. S. (2017). School of Engineering and Sciences (Doctoral dissertation, Instituto Tecnológico y de Estudios Superiores de Monterrey).
Ryser-Welch, P. (2017). Evolving comprehensible and scalable solvers using CGP for solving some real-world inspired problems (Doctoral dissertation, University of York).
Mariani, T., Guizzo, G., Vergilio, S. R., & Pozo, A. T. Automatic Design of Algorithms Applied to the Multi-Objective TSP Problem.
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 : 3 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.
Martin, M. A. (2015). Hyper-heuristics for the automated design of black-box search algorithms.
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)
