Distance-guided local search
- PDF / 701,617 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 218 Views
Distance-guided local search Daniel Porumbel1
· Jin-Kao Hao2,3
Received: 6 March 2017 / Revised: 10 January 2020 / Accepted: 8 May 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 highestquality 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
B
Daniel Porumbel [email protected] Jin-Kao Hao [email protected]
1
CEDRIC, Conservatoire National des Arts et Métiers, 292, rue Saint Martin, Paris, France
2
LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France
3
Institut Universitaire de France, 1, rue Descartes, 75231 Paris Cedex 05, France
123
D. Porumbel, J.-K. Hao
1 Introduction Local Search (LS) is one of the most popular methods for solving large and hard optimization problems in many fields of science. A drawback of many classical LS algorithms is that they lack a “global vision” over the search trajectory and evolution. Typically, even if an LS algorithm visits a very high-quality solution s at a given moment, it might often not intensify the search in the proximity of s, thus easily missing better solutions close to s. This paper proposes Distance-Guided Local Search (DGLS), an algorithmic framework that operates on top of a given LS; the goal is to improve the underlying LS by introducing different intensification techniques that rely on a distance measure defined over the space of candidate solutions. The distance between two solutions s1 and s2 is measured as the minimum number of neighborhood transitions (moves) required to reach s2 from s1 . Using such a met
Data Loading...
