Skip to main content

Research Repository

Advanced Search

Move acceptance in local search metaheuristics for cross-domain search


Warren G. Jackson

Profile Image

Professor of Computer Science and Operational Research

Robert I. John


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.


Jackson, W. G., Özcan, E., & John, R. I. (2018). Move acceptance in local search metaheuristics for cross-domain search. Expert Systems with Applications, 131,

Journal Article Type Article
Acceptance Date May 7, 2018
Online Publication Date May 9, 2018
Publication Date Nov 1, 2018
Deposit Date May 8, 2018
Publicly Available Date May 10, 2019
Journal Expert Systems with Applications
Print ISSN 0957-4174
Electronic ISSN 0957-4174
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 131
Keywords Combinatorial Optimization, Parameter Control, Stochastic Local Search, Trajectory Methods, Search Algorithms
Public URL
Publisher URL


Move_Acceptance_Survey___Final___Accepted.pdf (1.1 Mb)

Copyright Statement
Copyright information regarding this work can be found at the following address:

You might also like

Downloadable Citations