Variable Neighborhood SearchVariable Neighborhood Search, VNS. TaxonomyVariable Neighborhood Search is a Metaheuristic and a Global Optimization technique that manages a Local Search technique. It is related to the Iterative Local Search algorithm. StrategyThe strategy for the Variable Neighborhood Search involves iterative exploration of larger and larger neighborhoods for a given local optima until an improvement is located after which time the search across expanding neighborhoods is repeated. The strategy is motivated by three principles: 1) a local minimum for one neighborhood structure may not be a local minimum for a different neighborhood structure, 2) a global minimum is a local minimum for all possible neighborhood structures, and 3) local minima are relatively close to global minima for many problem classes. Procedure
Algorithm (below) provides a pseudocode listing of the Variable Neighborhood Search algorithm for minimizing a cost function.
The Pseudocode shows that the systematic search of expanding neighborhoods for a local optimum is abandoned when a global improvement is achieved (shown with the Input :
Neighborhoods
Output :
$S_{best}$
$S_{best}$ $\leftarrow$ RandomSolution ()While ($\neg$ StopCondition ())For ($Neighborhood_{i}$ $\in$ Neighborhoods )$Neighborhood_{curr}$ $\leftarrow$ CalculateNeighborhood ($S_{best}$, $Neighborhood_{i}$)$S_{candidate}$ $\leftarrow$ RandomSolutionInNeighborhood ($Neighborhood_{curr}$)$S_{candidate}$ $\leftarrow$ LocalSearch ($S_{candidate}$)If (Cost ($S_{candidate}$) < Cost ($S_{best}$))$S_{best}$ $\leftarrow$ $S_{candidate}$ Break End End End Return ($S_{best}$)Heuristics
Code ListingListing (below) provides an example of the Variable Neighborhood Search algorithm implemented in the Ruby Programming Language. The algorithm is applied to the Berlin52 instance of the Traveling Salesman Problem (TSP), taken from the TSPLIB. The problem seeks a permutation of the order to visit cities (called a tour) that minimizes the total distance traveled. The optimal tour distance for Berlin52 instance is 7542 units. The Variable Neighborhood Search uses a stochastic 2opt procedure as the embedded local search. The procedure deletes two edges and reverses the sequence inbetween the deleted edges, potentially removing 'twists' in the tour. The neighborhood structure used in the search is the number of times the 2opt procedure is performed on a permutation, between 1 and 20 times. The stopping condition for the local search procedure is a maximum number of iterations without improvement. The same stop condition is employed by the higherorder Variable Neighborhood Search procedure, although with a lower boundary on the number of nonimproving iterations. def euc_2d(c1, c2) Math.sqrt((c1[0]  c2[0])**2.0 + (c1[1]  c2[1])**2.0).round end def cost(perm, cities) distance =0 perm.each_with_index do c1, i c2 = (i==perm.size1) ? perm[0] : perm[i+1] distance += euc_2d(cities[c1], cities[c2]) end return distance end def random_permutation(cities) perm = Array.new(cities.size){i i} perm.each_index do i r = rand(perm.sizei) + i perm[r], perm[i] = perm[i], perm[r] end return perm end def stochastic_two_opt!(perm) c1, c2 = rand(perm.size), rand(perm.size) exclude = [c1] exclude << ((c1==0) ? perm.size1 : c11) exclude << ((c1==perm.size1) ? 0 : c1+1) c2 = rand(perm.size) while exclude.include?(c2) c1, c2 = c2, c1 if c2 < c1 perm[c1...c2] = perm[c1...c2].reverse return perm end def local_search(best, cities, max_no_improv, neighborhood) count = 0 begin candidate = {} candidate[:vector] = Array.new(best[:vector]) neighborhood.times{stochastic_two_opt!(candidate[:vector])} candidate[:cost] = cost(candidate[:vector], cities) if candidate[:cost] < best[:cost] count, best = 0, candidate else count += 1 end end until count >= max_no_improv return best end def search(cities, neighborhoods, max_no_improv, max_no_improv_ls) best = {} best[:vector] = random_permutation(cities) best[:cost] = cost(best[:vector], cities) iter, count = 0, 0 begin neighborhoods.each do neigh candidate = {} candidate[:vector] = Array.new(best[:vector]) neigh.times{stochastic_two_opt!(candidate[:vector])} candidate[:cost] = cost(candidate[:vector], cities) candidate = local_search(candidate, cities, max_no_improv_ls, neigh) puts " > iteration #{(iter+1)}, neigh=#{neigh}, best=#{best[:cost]}" iter += 1 if(candidate[:cost] < best[:cost]) best, count = candidate, 0 puts "New best, restarting neighborhood search." break else count += 1 end end end until count >= max_no_improv return best end if __FILE__ == $0 # problem configuration berlin52 = [[565,575],[25,185],[345,750],[945,685],[845,655], [880,660],[25,230],[525,1000],[580,1175],[650,1130],[1605,620], [1220,580],[1465,200],[1530,5],[845,680],[725,370],[145,665], [415,635],[510,875],[560,365],[300,465],[520,585],[480,415], [835,625],[975,580],[1215,245],[1320,315],[1250,400],[660,180], [410,250],[420,555],[575,665],[1150,1160],[700,580],[685,595], [685,610],[770,610],[795,645],[720,635],[760,650],[475,960], [95,260],[875,920],[700,500],[555,815],[830,485],[1170,65], [830,610],[605,625],[595,360],[1340,725],[1740,245]] # algorithm configuration max_no_improv = 50 max_no_improv_ls = 70 neighborhoods = 1...20 # execute the algorithm best = search(berlin52, neighborhoods, max_no_improv, max_no_improv_ls) puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}" end Download: variable_neighborhood_search.rb.
ReferencesPrimary SourcesThe seminal paper for describing Variable Neighborhood Search was by Mladenovic and Hansen in 1997 [Mladenovic1997], although an early abstract by Mladenovic is sometimes cited [Mladenovic1995]. The approach is explained in terms of three different variations on the general theme. Variable Neighborhood Descent (VND) refers to the use of a Local Search procedure and the deterministic (as opposed to stochastic or probabilistic) change of neighborhood size. Reduced Variable Neighborhood Search (RVNS) involves performing a stochastic random search within a neighborhood and no refinement via a local search technique. Basic Variable Neighborhood Search is the canonical approach described by Mladenovic and Hansen in the seminal paper. Learn MoreThere are a large number of papers published on Variable Neighborhood Search, its applications and variations. Hansen and Mladenovic provide an overview of the approach that includes its recent history, extensions and a detailed review of the numerous areas of application [Hansen2003]. For some additional useful overviews of the technique, its principles, and applications, see [Hansen1998] [Hansen2001a] [Hansen2002]. There are many extensions to Variable Neighborhood Search. Some popular examples include: Variable Neighborhood Decomposition Search (VNDS) that involves embedding a second heuristic or metaheuristic approach in VNS to replace the Local Search procedure [Hansen2001], Skewed Variable Neighborhood Search (SVNS) that encourages exploration of neighborhoods far away from discovered local optima, and Parallel Variable Neighborhood Search (PVNS) that either parallelizes the local search of a neighborhood or parallelizes the searching of the neighborhoods themselves. Bibliography

Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...


Please Note: This content was automatically generated from the book content and may contain minor differences. 

Do you like Clever Algorithms? Buy the book now. 