Distance-guided local search

Daniel Porumbel () and Jin-Kao Hao ()
Additional contact information
Daniel Porumbel: Conservatoire National des Arts et Métiers
Jin-Kao Hao: Université d’Angers

Journal of Heuristics, 2020, vol. 26, issue 5, No 4, 741 pages

Abstract: Abstract We present several techniques that use distances between candidate solutions to achieve intensification in Local Search (LS) algorithms. An important drawback of classical LS is that after visiting a very high-quality solution the search process can “forget about it” and continue towards very different areas. We propose a method that works on top of a given LS to equip it with a form of memory so as to record the highest-quality visited areas (spheres). More exactly, this new method uses distances between candidate solutions to perform a coarse–grained recording of the LS trajectory, i.e., it records a number of discovered spheres. The (centers of the) spheres are kept sorted in a priority queue in which new centers are continually inserted as in insertion-sort algorithms. After thoroughly investigating a sphere, the proposed method resumes the search from the first best sphere center in the priority queue. The resulting LS trajectory is no longer a continuous path, but a tree-like structure, with closed branches (already investigated spheres) and open branches (as-yet-unexplored spheres). We also explore several other techniques relying on distances, e.g., in Section 2.3, we show how to use distance information to prevent the search from looping indefinitely on large (quasi-)plateaus. Experiments on three problems based on different encodings (partitions, vectors and permutations) confirm the intensification potential of the proposed ideas.

Keywords: Meta-heuristic methodologies; Local search; Distance between solutions; Intensification (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-020-09446-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:26:y:2020:i:5:d:10.1007_s10732-020-09446-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-020-09446-w

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().