Linear genetic programming of parsimonious metaheuristics

Abstract

We use a form of grammar-based linear Genetic Programming (GP) as a hyperheuristic, i.e., a search heuristic on the space of heuristics. This technique is guided by domain- specific languages that one designs taking inspiration from elementary components of specialised heuristics and metaheuristics for a domain. We demonstrate this approach for traveling- salesperson problems for which we test different languages, including one containing a looping construct. Experimentation with benchmark instances from the TSPLIB shows that the GP hyperheuristic routinely and rapidly produces parsimonious metaheuristics that find tours whose lengths are highly competitive with the best real-valued lengths from literature.