Learning a stopping criterion for local search
Loading...
Files
Accepted Version
Date
2016-12-01
Authors
Arbelaez, Alejandro
O’Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature Ltd.
Published Version
Abstract
Local search is a very effective technique to tackle combinatorial problems in multiple areas ranging from telecommunications to transportations, and VLSI circuit design. A local search algorithm typically explores the space of solutions until a given stopping criterion is met. Ideally, the algorithm is executed until a target solution is reached (e.g., optimal or near-optimal). However, in many real-world problems such a target is unknown. In this work, our objective is to study the application of machine learning techniques to carefully craft a stopping criterion. More precisely, we exploit instance features to predict the expected quality of the solution for a given algorithm to solve a given problem instance, we then run the local search algorithm until the expected quality is reached. Our experiments indicate that the suggested method is able to reduce the average runtime up to 80% for real-world instances and up to 97% for randomly generated instances with a minor impact in the quality of the solutions.
Description
Keywords
Local search , Problem instance , Travel salesman problem , Local search algorithm , Average runtime
Citation
Arbelaez, A. and O’Sullivan, B. (2016) 'Learning a stopping criterion for local search', in Festa, P., Sellmann, M. and Vanschoren, J. (eds.) Learning and Intelligent Optimization. LION 2016, pp. 3-16. Lecture Notes in Computer Science, 10079. Springer, Cham. https://doi.org/10.1007/978-3-319-50349-3_1
Link to publisher’s version
Copyright
© 2016, Springer International Publishing Switzerland. This version of the paper has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-319-50349-3_1