Iterated local search: framework and applications
The key idea underlying iterated local search is to focus the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm, typically a local search heuristic. The resulting search behavior can be characterized as iteratively building a...
| Authors: | ; ; |
|---|---|
| Format: | Book chapter |
| Status: | Accepted version |
| Publication date: | 2019 |
| Country: | España |
| Institution: | Universitat Pompeu Fabra |
| Repository: | Repositorio Digital de la UPF |
| OAI Identifier: | oai:repositori.upf.edu:10230/69330 |
| Online Access: | http://hdl.handle.net/10230/69330 http://dx.doi.org/10.1007/978-3-319-91086-4_5 |
| Access Level: | Open access |
| Keyword: | Optimització combinatòria Investigació operativa Informàtica -- Matemàtica |
| _version_ | 1878736563222872064 |
|---|---|
| author | Ramalhinho-Lourenço, Helena |
| author2 | Martin, Olivier C. Stützle, Thomas |
| author2_role | author author |
| author_browse | Martin, Olivier C. Ramalhinho-Lourenço, Helena Stützle, Thomas |
| author_facet | Ramalhinho-Lourenço, Helena Martin, Olivier C. Stützle, Thomas |
| author_role | author |
| collection | Repositorio Digital de la UPF |
| description | The key idea underlying iterated local search is to focus the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm, typically a local search heuristic. The resulting search behavior can be characterized as iteratively building a chain of solutions of this embedded algorithm. The result is also a conceptually simple metaheuristic that nevertheless has led to state-of-the-art algorithms for many computationally hard problems. In fact, very good performance is often already obtained by rather straightforward implementations of the metaheuristic. In addition, the modular architecture of iterated local search makes it very suitable for an algorithm engineering approach where, progressively, the algorithm’s performance can be further optimized. Our purpose here is to give an accessible description of the underlying principles of iterated local search and a discussion of the main aspects that need to be taken into account for a successful application of it. In addition, we review the most important applications of this method and discuss its relationship with other metaheuristics. |
| eu_rights_str_mv | openAccess |
| format | bookPart |
| id | ES_913dd2ee0bfa42676f851687f4ecccec |
| institution | Universitat Pompeu Fabra |
| instname_str | Universitat Pompeu Fabra |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:repositori.upf.edu:10230/69330 |
| publishDate | 2019 |
| publishDateSort | 2019 |
| publisher | SpringerNature |
| publisherStr | SpringerNature |
| reponame_str | Repositorio Digital de la UPF |
| spelling | Iterated local search: framework and applications Ramalhinho-Lourenço, Helena Martin, Olivier C. Stützle, Thomas Optimització combinatòria Investigació operativa Informàtica -- Matemàtica The key idea underlying iterated local search is to focus the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm, typically a local search heuristic. The resulting search behavior can be characterized as iteratively building a chain of solutions of this embedded algorithm. The result is also a conceptually simple metaheuristic that nevertheless has led to state-of-the-art algorithms for many computationally hard problems. In fact, very good performance is often already obtained by rather straightforward implementations of the metaheuristic. In addition, the modular architecture of iterated local search makes it very suitable for an algorithm engineering approach where, progressively, the algorithm’s performance can be further optimized. Our purpose here is to give an accessible description of the underlying principles of iterated local search and a discussion of the main aspects that need to be taken into account for a successful application of it. In addition, we review the most important applications of this method and discuss its relationship with other metaheuristics. Helena Ramalhinho Lourenço acknowledges support from the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT), and Thomas Stützle acknowledges support from the F.R.S.-FNRS, of which he is a research director. This work received support from the COMEX project P7/36 within the Interuniversity Attraction Poles Programme of the Belgian Science Policy Office. SpringerNature http://hdl.handle.net/10230/69330 http://dx.doi.org/10.1007/978-3-319-91086-4_5 |
| spellingShingle | Iterated local search: framework and applications Ramalhinho-Lourenço, Helena Optimització combinatòria Investigació operativa Informàtica -- Matemàtica |
| status_str | acceptedVersion |
| title | Iterated local search: framework and applications |
| title_full | Iterated local search: framework and applications |
| title_fullStr | Iterated local search: framework and applications |
| title_full_unstemmed | Iterated local search: framework and applications |
| title_short | Iterated local search: framework and applications |
| title_sort | Iterated local search: framework and applications |
| topic | Optimització combinatòria Investigació operativa Informàtica -- Matemàtica |
| topic_facet | Optimització combinatòria Investigació operativa Informàtica -- Matemàtica |
| url | http://hdl.handle.net/10230/69330 http://dx.doi.org/10.1007/978-3-319-91086-4_5 |