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

# Greedy Randomized Adaptive Search

Greedy Randomized Adaptive Search Procedure, GRASP.

## Taxonomy

The Greedy Randomized Adaptive Search Procedure is a Metaheuristic and Global Optimization algorithm, originally proposed for the Operations Research practitioners. The iterative application of an embedded Local Search technique relate the approach to Iterative Local Search and Multi-Start techniques.

## Strategy

The objective of the Greedy Randomized Adaptive Search Procedure is to repeatedly sample stochastically greedy solutions, and then use a local search procedure to refine them to a local optima. The strategy of the procedure is centered on the stochastic and greedy step-wise construction mechanism that constrains the selection and order-of-inclusion of the components of a solution based on the value they are expected to provide.

## Procedure

Algorithm (below) provides a pseudocode listing of the Greedy Randomized Adaptive Search Procedure for minimizing a cost function.

Input: $\alpha$
Output: $S_{best}$
$S_{best}$ $\leftarrow$ ConstructRandomSolution()
While ($\neg$ StopCondition())
$S_{candidate}$ $\leftarrow$ GreedyRandomizedConstruction($\alpha$)
$S_{candidate}$ $\leftarrow$ LocalSearch($S_{candidate}$)
If (Cost($S_{candidate}$) < Cost($S_{best}$))
$S_{best}$ $\leftarrow$ $S_{candidate}$
End
End
Return ($S_{best}$)
Pseudocode for the GRASP.

Algorithm (below) provides the pseudocode the Greedy Randomized Construction function. The function involves the step-wise construction of a candidate solution using a stochastically greedy construction process. The function works by building a Restricted Candidate List (RCL) that constraints the components of a solution (features) that may be selected from each cycle. The RCL may be constrained by an explicit size, or by using a threshold ($\alpha \in [0,1]$) on the cost of adding each feature to the current candidate solution.

Input: $\alpha$
Output: $S_{candidate}$
$S_{candidate}$ $\leftarrow \emptyset$
While ($S_{candidate}$ $\neq$ ProblemSize)
$Feature_{costs}$ $\leftarrow \emptyset$
For ($Feature_{i}$ $\notin$ $S_{candidate}$)
$Feature_{costs}$ $\leftarrow$ CostOfAddingFeatureToSolution($S_{candidate}$, $Feature_{i}$)
End
RCL $\leftarrow \emptyset$
$Fcost_{min}$ $\leftarrow$ MinCost($Feature_{costs}$)
$Fcost_{max}$ $\leftarrow$ MaxCost($Feature_{costs}$)
For ($F_{i}cost$ $\in$ $Feature_{costs}$)
If ($F_{i}cost$ $\leq$ $Fcost_{min} + \alpha \cdot (Fcost_{max} - Fcost_{min})$ )
RCL $\leftarrow$ $Feature_{i}$
End
End
$S_{candidate}$ $\leftarrow$ SelectRandomFeature(RCL)
End
Return ($S_{candidate}$)
Pseudocode the GreedyRandomizedConstruction function.

## Heuristics

• The $\alpha$ threshold defines the amount of greediness of the construction mechanism, where values close to 0 may be too greedy, and values close to 1 may be too generalized.
• As an alternative to using the $\alpha$ threshold, the RCL can be constrained to the top $n\%$ of candidate features that may be selected from each construction cycle.
• The technique was designed for discrete problem classes such as combinatorial optimization problems.

## Code Listing

Listing (below) provides an example of the Greedy Randomized Adaptive Search Procedure 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 stochastic and greedy step-wise construction of a tour involves evaluating candidate cities by the the cost they contribute as being the next city in the tour. The algorithm uses a stochastic 2-opt procedure for the Local Search with a fixed number of non-improving iterations as the stopping condition.

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.size-1) ? perm[0] : perm[i+1]
distance += euc_2d(cities[c1], cities[c2])
end
return distance
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 local_search(best, cities, max_no_improv)
count = 0
begin
candidate = {:vector=>stochastic_two_opt(best[:vector])}
candidate[:cost] = cost(candidate[:vector], cities)
count = (candidate[:cost] < best[:cost]) ? 0 : count+1
best = candidate if candidate[:cost] < best[:cost]
end until count >= max_no_improv
return best
end

def construct_randomized_greedy_solution(cities, alpha)
candidate = {}
candidate[:vector] = [rand(cities.size)]
allCities = Array.new(cities.size) {|i| i}
while candidate[:vector].size < cities.size
candidates = allCities - candidate[:vector]
costs = Array.new(candidates.size) do |i|
euc_2d(cities[candidate[:vector].last], cities[i])
end
rcl, max, min = [], costs.max, costs.min
costs.each_with_index do |c,i|
rcl << candidates[i] if c <= (min + alpha*(max-min))
end
candidate[:vector] << rcl[rand(rcl.size)]
end
candidate[:cost] = cost(candidate[:vector], cities)
return candidate
end

def search(cities, max_iter, max_no_improv, alpha)
best = nil
max_iter.times do |iter|
candidate = construct_randomized_greedy_solution(cities, alpha);
candidate = local_search(candidate, cities, max_no_improv)
best = candidate if best.nil? or candidate[:cost] < best[:cost]
puts " > iteration #{(iter+1)}, best=#{best[:cost]}"
end
return best
end

## Bibliography

 [Bard1996] J. F. Bard and T. A. Feo and S. Holland, "A GRASP for scheduling printed wiring board assembly", I.I.E. Trans., 1996. [Feo1989] T. A. Feo and M. G. C. Resende, "A probabilistic heuristic for a computationally difficult set covering problem", Operations Research Letters, 1989. [Feo1991] T. A. Feo and K. Venkatraman and J. F. Bard, "A GRASP for a difficult single machine scheduling problem", Computers & Operations Research, 1991. [Feo1993] T. A. Feo and J. Bard and S. Holland, "A GRASP for scheduling printed wiring board assembly", Technical Report TX 78712-1063, Operations Research Group, Department of Mechanical Engineering, The University of Texas at Austin, 1993. [Feo1994] T. A. Feo and K. Sarathy and J. McGahan, "A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties", Technical Report TX 78712-1063, Operations Research Group, Department of Mechanical Engineering, The University of Texas at Austin, 1994. [Feo1995] T. A. Feo and M. G. C. Resende, "Greedy randomized adaptive search procedures", Journal of Global Optimization, 1995. [Feo1996] T. A. Feo and K. Sarathy and J. McGahan, "A grasp for single machine scheduling with sequence dependent setup costs and linear delay penalties", Computers & Operations Research, 1996. [Festa2002] P. Festa and M. G. C. Resende, "GRASP: An annotated bibliography", in Essays and Surveys on Metaheuristics, pages 325–367, Kluwer Academic Publishers, 2002. [Hart1987] J. P. Hart and A. W. Shogan, "Semi–greedy heuristics: An empirical study", Operations Research Letters, 1987. [Pardalos1995] P. M. Pardalos and L. S. Pitsoulis and M. G. C. Resende, "A parallel GRASP implementation for the quadratic assignment problems", in Parallel Algorithms for Irregularly Structured Problems (Irregular’94), 1995. [Pitsoulis2002] L. Pitsoulis and M. G. C. Resende, "Greedy randomized adaptive search procedures", in Handbook of Applied Optimization, pages 168–181, Oxford University Press, 2002. [Prais2000] M. Prais and C. C. Ribeiro, "Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment", INFORMS Journal on Computing, 2000. [Resende2003] M. G. C. Resende and C. C. Ribeiro, "Greedy randomized adaptive search procedures", in Handbook of Metaheuristics, pages 219–249, Kluwer Academic Publishers, 2003.

### Free Course

Get one algorithm per week...
• ...delivered to your inbox
• ...described in detail
• ...to read at your own pace
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?
Buy the book now.