Move acceptance in local search metaheuristics for cross-domain search

Metaheuristics provide high-level instructions for designing heuristic optimisation algorithms and have been successfully applied to a range of computationally hard real-world problems. Local search metaheuristics operate under a single-point based search framework with the goal of iteratively improving a solution in hand over time with respect to a single objective using certain solution perturbation strategies, known as move operators, and move acceptance methods starting from an initially generated solution. Performance of a local search method varies from one domain to another, even from one instance to another in the same domain. There is a growing number of studies on `more general' search methods referred to as cross-domain search methods, or hyperheuristics, that operate at a high-level solving characteristically different problems, preferably without expert intervention. This paper provides a taxonomy and overview of existing local search metaheuristics along with an empirical study into the effects that move acceptance methods, as components of singlepoint based local search metaheuristics, have on the cross-domain performance of such algorithms for solving multiple combinatorial optimisation problems. The experimental results across a benchmark of nine different computationally hard problems highlight the shortcomings of existing and well-known methods for use as components of cross-domain search methods, despite being re-tuned for solving each domain