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 impro...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2018
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/51615/ |
| _version_ | 1848798533225807872 |
|---|---|
| author | Jackson, Warren G. Özcan, Ender John, Robert I. |
| author_facet | Jackson, Warren G. Özcan, Ender John, Robert I. |
| author_sort | Jackson, Warren G. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T20:21:17Z |
| format | Article |
| id | nottingham-51615 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:21:17Z |
| publishDate | 2018 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-516152020-05-04T19:49:54Z https://eprints.nottingham.ac.uk/51615/ Move acceptance in local search metaheuristics for cross-domain search Jackson, Warren G. Özcan, Ender John, Robert I. 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. Elsevier 2018-11-01 Article PeerReviewed Jackson, Warren G., Özcan, Ender and John, Robert I. (2018) Move acceptance in local search metaheuristics for cross-domain search. Expert Systems with Applications, 131 . pp. 131-151. ISSN 0957-4174 Combinatorial Optimization Parameter Control Stochastic Local Search Trajectory Methods Search Algorithms https://www.sciencedirect.com/science/article/pii/S0957417418302835 doi:10.1016/j.eswa.2018.05.006 doi:10.1016/j.eswa.2018.05.006 |
| spellingShingle | Combinatorial Optimization Parameter Control Stochastic Local Search Trajectory Methods Search Algorithms Jackson, Warren G. Özcan, Ender John, Robert I. Move acceptance in local search metaheuristics for cross-domain search |
| title | Move acceptance in local search metaheuristics for cross-domain search |
| title_full | Move acceptance in local search metaheuristics for cross-domain search |
| title_fullStr | Move acceptance in local search metaheuristics for cross-domain search |
| title_full_unstemmed | Move acceptance in local search metaheuristics for cross-domain search |
| title_short | Move acceptance in local search metaheuristics for cross-domain search |
| title_sort | move acceptance in local search metaheuristics for cross-domain search |
| topic | Combinatorial Optimization Parameter Control Stochastic Local Search Trajectory Methods Search Algorithms |
| url | https://eprints.nottingham.ac.uk/51615/ https://eprints.nottingham.ac.uk/51615/ https://eprints.nottingham.ac.uk/51615/ |