# Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

This is the ad-supported version of the book. Buy it now if you like it.

# Guided Local Search

Guided Local Search, GLS.

## Taxonomy

The 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.

## Strategy

The 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.

## Procedure

Algorithm (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}$)
Pseudocode for Guided Local Search.

## Heuristics

• The Guided Local Search procedure is independent of the Local Search procedure embedded within it. A suitable domain-specific search procedure should be identified and employed.
• The Guided Local Search procedure may need to be executed for thousands to hundreds-of-thousands of iterations, each iteration of which assumes a run of a Local Search algorithm to convergence.
• The algorithm was designed for discrete optimization problems where a solution is comprised of independently assessable 'features' such as Combinatorial Optimization, although it has been applied to continuous function optimization modeled as binary strings.
• The $\lambda$ parameter is a scaling factor for feature penalization that must be in the same proportion to the candidate solution costs from the specific problem instance to which the algorithm is being applied. As such, the value for $\lambda$ must be meaningful when used within the augmented cost function (such as when it is added to a candidate solution cost in minimization and subtracted from a cost in the case of a maximization problem).

## Code Listing

Listing (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 TSP-specific local search algorithm is used called 2-opt that selects two points in a permutation and reconnects the tour, potentially untwisting the tour at the selected points. The stopping condition for 2-opt was configured to be a fixed number of non-improving 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 2-opt). 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.size-i) + 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.size-1 : c1-1)
exclude << ((c1==perm.size-1) ? 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.size-1) ? 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.size-1) ? 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.size-1) ? 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

Guided Local Search in Ruby

## References

### Primary Sources

Guided 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].

Voudouris and Tsang provide a high-level 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

 [Glover2003a] C. Voudouris and E. P. K. Tsang, "7: Guided Local Search", in Handbook of Metaheuristics, pages 185-218, Springer, 2003. [Lau1998] T. L. Lau and E. P. K. Tsang, "The guided genetic algorithm and its application to the general assignment problems", in IEEE 10th International Conference on Tools with Artificial Intelligence (ICTAI'98), 1998. [Lau1999] L. T. Lau, "Guided Genetic Algorithm", [PhD Thesis] Department of Computer Science, University of Essex, 1999. [Mills2002] P. Mills, "Extensions to Guided Local Search", [PhD Thesis] Department of Computer Science, University of Essex, 2002. [Mills2003] P. Mills and E. Tsang and J. Ford, "Applying an Extended Guided Local Search on the Quadratic Assignment Problem", Annals of Operations Research, 2003. [Tsang1992] E. P. K. Tsang and C. J. Wang, "A Generic Neural Network Approach For Constraint Satisfaction Problems", in Neural network applications, 1992. [Voudouris1994] C. Voudouris and E. Tsang, "The Tunneling Algorithm for Partial CSPs and Combinatorial Optimization Problems", Technical Report CSM-213, Department of Computer Science, University of Essex, Colchester, C04 3SQ, UK, 1994. [Voudouris1995] C. Voudouris and E. Tsang, "Guided Local Search", Technical Report CSM-247, Department of Computer Science, University of Essex, Colchester, C04 3SQ, UK, 1995. [Voudouris1995a] C. Voudouris and E. Tsang, "Function Optimization using Guided Local Search", Technical Report CSM-249, Department of Computer Science University of Essex Colchester, CO4 3SQ, UK, 1995. [Voudouris1995b] E. Tsang and C. Voudouris, "Fast Local Search and Guided Local Search and Their Application to British Telecom's Workforce Scheduling Problem", Technical Report CSM-246, Department of Computer Science University of Essex Colchester CO4 3SQ, 1995. [Voudouris1997] C. Voudouris, "Guided local search for combinatorial optimisation problems", [PhD Thesis] Department of Computer Science, University of Essex, Colchester, UK, 1997. [Voudouris1998] C. Voudouris and E. P. K. Tsang, "Guided local search joins the elite in discrete optimisation", in Proceedings, DIMACS Workshop on Constraint Programming and Large Scale Discrete Optimisation, 1998. [Wang1991] C. J. Wang and E. P. K. Tsang, "Solving constraint satisfaction problems using neural networks", in Proceedings Second International Conference on Artificial Neural Networks, 1991.

### Free Course

Get one algorithm per week...
• ...described in detail
Sign-up Now

### Own A Copy

This 438-page ebook has...
• ...45 algorithm descriptions
• ...best practice usage
• ...pseudo code
• ...Ruby code
• ...primary sources

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

Do you like Clever Algorithms?