Grammatical evolution of local search heuristics

Citation

Burke E, Hyde M & Kendall G (2012) Grammatical evolution of local search heuristics. IEEE Transactions on Evolutionary Computation, 16 (3), pp. 406-417. https://doi.org/10.1109/TEVC.2011.2160401

Abstract
Genetic programming approaches have been employed in the literature to automatically design constructive heuristics for cutting and packing problems. These heuristics obtain results superior to human-created constructive heuristics, but they do not generally obtain results of the same quality as local search heuristics, which start from an initial solution and iteratively improve it. If local search heuristics can be successfully designed through evolution, in addition to a constructive heuristic which initializes the solution, then the quality of results which can be obtained by automatically generated algorithms can be significantly improved. This paper presents a grammatical evolution methodology which automatically designs good quality local search heuristics that maintain their performance on new problem instances.

Keywords
bin packing; genetic algorithms; search problems

Journal
IEEE Transactions on Evolutionary Computation: Volume 16, Issue 3