Guided Local SearchGuided Local Search, GLS. TaxonomyThe Guided Local Search algorithm is a Metaheuristic and a Global Optimization algorithm that makes use of an embedded Local Search algorithm. It is an extension to Local Search algorithms such as Hill Climbing and is similar in strategy to the Tabu Search algorithm and the Iterated Local Search algorithm. StrategyThe strategy for the Guided Local Search algorithm is to use penalties to encourage a Local Search technique to escape local optima and discover the global optima. A Local Search algorithm is run until it gets stuck in a local optima. The features from the local optima are evaluated and penalized, the results of which are used in an augmented cost function employed by the Local Search procedure. The Local Search is repeated a number of times using the last local optima discovered and the augmented cost function that guides exploration away from solutions with features present in discovered local optima. ProcedureAlgorithm (below) provides a pseudocode listing of the Guided Local Search algorithm for minimization. The Local Search algorithm used by the Guided Local Search algorithm uses an augmented cost function in the form $h(s)=g(s)+\lambda\cdot\sum_{i=1}^{M}f_i$, where $h(s)$ is the augmented cost function, $g(s)$ is the problem cost function,$\lambda$ is the 'regularization parameter' (a coefficient for scaling the penalties), $s$ is a locally optimal solution of $M$ features, and $f_i$ is the $i$'th feature in locally optimal solution. The augmented cost function is only used by the local search procedure, the Guided Local Search algorithm uses the problem specific cost function without augmentation. Penalties are only updated for those features in a locally optimal solution that maximize utility, updated by adding 1 to the penalty for the future (a counter). The utility for a feature is calculated as $U_{feature}=\frac{C_{feature}}{1+P_{feature}}$, where $U_{feature}$ is the utility for penalizing a feature (maximizing), $C_{feature}$ is the cost of the feature, and $P_{feature}$ is the current penalty for the feature. Input :
$Iter_{max}$, $\lambda$
Output :
$S_{best}$
$f_{penalties}$ $\leftarrow \emptyset$ $S_{best}$ $\leftarrow$ RandomSolution ()For ($Iter_{i}$ $\in$ $Iter_{max}$)$S_{curr}$ $\leftarrow$ LocalSearch ($S_{best}$, $\lambda$, $f_{penalties}$)$f_{utilities}$ $\leftarrow$ CalculateFeatureUtilities ($S_{curr}$, $f_{penalties}$)$f_{penalties}$ $\leftarrow$ UpdateFeaturePenalties ($S_{curr}$, $f_{penalties}$, $f_{utilities}$)If (Cost ($S_{curr}$) $\leq$ Cost ($S_{best}$))$S_{best}$ $\leftarrow$ $S_{curr}$ End End Return ($S_{best}$)Heuristics
Code ListingListing (below) provides an example of the Guided Local 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 implementation of the algorithm for the TSP was based on the configuration specified by Voudouris in [Voudouris1997]. A TSPspecific local search algorithm is used called 2opt that selects two points in a permutation and reconnects the tour, potentially untwisting the tour at the selected points. The stopping condition for 2opt was configured to be a fixed number of nonimproving moves. The equation for setting $\lambda$ for TSP instances is $\lambda = \alpha\cdot\frac{cost(optima)}{N}$, where $N$ is the number of cities, $cost(optima)$ is the cost of a local optimum found by a local search, and $\alpha\in (0,1]$ (around 0.3 for TSP and 2opt). The cost of a local optima was fixed to the approximated value of 15000 for the Berlin52 instance. The utility function for features (edges) in the TSP is $U_{edge}=\frac{D_{edge}}{1+P_{edge}}$, where $U_{edge}$ is the utility for penalizing an edge (maximizing), $D_{edge}$ is the cost of the edge (distance between cities) and $P_{edge}$ is the current penalty for the edge. def euc_2d(c1, c2) Math.sqrt((c1[0]  c2[0])**2.0 + (c1[1]  c2[1])**2.0).round 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(permutation) perm = Array.new(permutation) 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 augmented_cost(permutation, penalties, cities, lambda) distance, augmented = 0, 0 permutation.each_with_index do c1, i c2 = (i==permutation.size1) ? permutation[0] : permutation[i+1] c1, c2 = c2, c1 if c2 < c1 d = euc_2d(cities[c1], cities[c2]) distance += d augmented += d + (lambda * (penalties[c1][c2])) end return [distance, augmented] end def cost(cand, penalties, cities, lambda) cost, acost = augmented_cost(cand[:vector], penalties, cities, lambda) cand[:cost], cand[:aug_cost] = cost, acost end def local_search(current, cities, penalties, max_no_improv, lambda) cost(current, penalties, cities, lambda) count = 0 begin candidate = {:vector=> stochastic_two_opt(current[:vector])} cost(candidate, penalties, cities, lambda) count = (candidate[:aug_cost] < current[:aug_cost]) ? 0 : count+1 current = candidate if candidate[:aug_cost] < current[:aug_cost] end until count >= max_no_improv return current end def calculate_feature_utilities(penal, cities, permutation) utilities = Array.new(permutation.size,0) permutation.each_with_index do c1, i c2 = (i==permutation.size1) ? permutation[0] : permutation[i+1] c1, c2 = c2, c1 if c2 < c1 utilities[i] = euc_2d(cities[c1], cities[c2]) / (1.0 + penal[c1][c2]) end return utilities end def update_penalties!(penalties, cities, permutation, utilities) max = utilities.max() permutation.each_with_index do c1, i c2 = (i==permutation.size1) ? permutation[0] : permutation[i+1] c1, c2 = c2, c1 if c2 < c1 penalties[c1][c2] += 1 if utilities[i] == max end return penalties end def search(max_iterations, cities, max_no_improv, lambda) current = {:vector=>random_permutation(cities)} best = nil penalties = Array.new(cities.size){ Array.new(cities.size, 0) } max_iterations.times do iter current=local_search(current, cities, penalties, max_no_improv, lambda) utilities=calculate_feature_utilities(penalties,cities,current[:vector]) update_penalties!(penalties, cities, current[:vector], utilities) best = current if best.nil? or current[:cost] < best[:cost] puts " > iter=#{(iter+1)}, best=#{best[:cost]}, aug=#{best[:aug_cost]}" end 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_iterations = 150 max_no_improv = 20 alpha = 0.3 local_search_optima = 12000.0 lambda = alpha * (local_search_optima/berlin52.size.to_f) # execute the algorithm best = search(max_iterations, berlin52, max_no_improv, lambda) puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}" end Download: guided_local_search.rb.
ReferencesPrimary SourcesGuided Local Search emerged from an approach called GENET, which is a connectionist approach to constraint satisfaction [Wang1991] [Tsang1992]. Guided Local Search was presented by Voudouris and Tsang in a series of technical reports (that were later published) that described the technique and provided example applications of it to constraint satisfaction [Voudouris1994], combinatorial optimization [Voudouris1995b] [Voudouris1995], and function optimization [Voudouris1995a]. The seminal work on the technique was Voudouris' PhD dissertation [Voudouris1997]. Learn MoreVoudouris and Tsang provide a highlevel introduction to the technique [Voudouris1998], and a contemporary summary of the approach in Glover and Kochenberger's 'Handbook of metaheuristics' [Glover2003a] that includes a review of the technique, application areas, and demonstration applications on a diverse set of problem instances. Mills et al. elaborated on the approach, devising an 'Extended Guided Local Search' (EGLS) technique that added 'aspiration criteria' and random moves to the procedure [Mills2003], work which culminated in Mills' PhD dissertation [Mills2002]. Lau and Tsang further extended the approach by integrating it with a Genetic Algorithm, called the 'Guided Genetic Algorithm' (GGA) [Lau1998], that also culminated in a PhD dissertation by Lau [Lau1999]. 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. 