The GRASP involves alternating a greedy adaptive solution construction procedure with a local search algorithm to refine the coarser search result. The approach was designed for combinatorial problems where the individual components of a candidate solution can be discriminated in the context of the goal (such as cost). This greedy step-wise construction involves the preparation of Restricted Candidate List (RCL) of components from which to select from, and the random selection of a component from the RCL to add to the growing solution. This process continues until a viable candidate solution is constructed and can be passed onto a local search procedure for evaluation.
The power of GRASP is in the preparation of the RCL. Typically the value of individual components to a final solution is used to restrict entry to the list (a threshold). Alternative approaches involve a fixed RCL size (of the top components), and an adaptive threshold or size over time. Management of the RCL requires careful attention, ensuring sufficient flexibility in the selection of components for a solution, whilst biasing the search towards a global optimum supplemented with a local search technique. It is interesting to note that the use of a strict RCL that selects the best component during each step of construction will result in a greedy search.
Greedy randomized adaptive search procedure
This guide provide a demonstration of the GRASP applied to a standard instance of the Traveling Salesman Problem. This classical combinatorial optimization provides a good example for the step-wise construction technique used by the GRASP.
The Berlin52TSP class provides an implementation of a small sized TSP with 52 cities. The problem data is stored as constants within the class. The COORDINATES constant provides a 2D array of city coordinates and the OPTIMAL_TOUR constant stores a representation of the optimal tour (permutation) of cities that used in the algorithms termination criterion. The initialize() constructor in turn calls the build_distance_matrix method to pre-calculate a matrix of the Euclidean distance between all combinations of cities. The city-to-city distance calculation represents the most expensive aspect of candidate solution evaluations which is eased via the pre-calculation requiring only a lookup of city ID's to determine the intervening distance. The evaluate(permutation) makes use of this pre-calculation via the dist(c1, c2) method, evaluating candidate solutions in the form a 51-city permutation where each city ID is specified between 1 and 52 inclusively.
class Berlin52TSPThe Solution class provides a generic container for candidate solutions. Problem specific solution data (in this case permutations) are stored in the immutable @data instance variable, and a mutable solution costing is stored in the @score instance variable.
OPTIMAL_TOUR = [1,49,32,45,19,41,8,9,10,43,33,51,11,52,14,13,47,26,
27,28,12,25,4,6,15,5,24,48,38,37,40,39,36,35,34,44,46,16,29,50,20,
23,30,2,7,42,21,17,3,18,31,22]
COORDINATES = [[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]]
attr_reader :num_cities
def initialize()
@num_cities = COORDINATES.length
@distance_matrix = Array.new(@num_cities) {Array.new(@num_cities)}
build_distance_matrix
@optimal_tour_length = evaluate(OPTIMAL_TOUR) # calculate
end
def build_distance_matrix
# symmetrical matrix along the diag
puts "pre-calculating the TSP distance matrix"
@distance_matrix.each_with_index do |row, i|
row.each_index do |j|
row[j] = euc_2d(COORDINATES[i], COORDINATES[j])
end
end
end
def evaluate(permutation)
dist = 0
permutation.each_with_index do |c1, i|
c2 = (i==@num_cities-1) ? permutation[0] : permutation[i+1]
dist += dist(c1,c2)
end
return dist
end
# expects city numbers [1,52]
def dist(c1, c2)
@distance_matrix[c1-1][c2-1]
end
def euc_2d(c1, c2)
# As defined in TSPLIB'95 (EUC_2D)
Math::sqrt((c1[0] - c2[0])**2 + (c1[1] - c2[1])**2).round
end
def is_optimal?(scoring)
scoring == optimal_score
end
def optimal_score
@optimal_tour_length
end
# true if s1 is better score than s2
def is_better?(s1, s2)
s1 < s2 # minimizing
end
end
class SolutionThe GRASP class provides an implementation of the Greedy Randomized Adaptive Search Procedure. The initialize(max_iterations) constructor for the algorithm sets up the maximum number of iterations for the algorithms termination criteria, as well as the algorithm specific @max_rcl_size that defines the maximum size of the Restricted Candidate List each step during construction, defaulted to 5 components. The search(problem) method provides the entry point to the search that executes the main loop until the termination criterion should_stop?(curr_it, problem) returns true. The main loop involves first a call to greedy_randomized_solution(current, problem) to construct a candidate solution, followed by a call to local_search_solution(candidate, problem) to refine the result.
attr_reader :data
attr_accessor :score
def initialize(data)
@data = data
@score = 0.0/0.0 # NaN
end
def to_s
"[#{@data.inspect}] (#{@score})"
end
end
The greedy_randomized_solution(solution, problem) provides a simplistic realization of the GRASP with a fixed size RCL. The construction starts with a random city and proceeds by first preparing a set of viable (unused) cities to which to connect. The candidates are ordered by their distance from the 'current' city, the list is trimmed to be no longer than the @max_rcl_size instance variable, and finally a random component from the list is selected and appended to the permutation.
The local search algorithm defined in the local_search_solution(solution, problem) method involves the application of the classical TSP local search called 2-opt (the two_opt_solution(solution) method) where two cities are selected and reconnected. This procedure is repeated 15 times as an approximation of locating the local optimum for the provided candidate solution.
class GRASPThe algorithm can be executed by first creating an instance of the problem, the algorithm, and passing the problem to the algorithms search method. The algorithm will displaying its progress during the search and return the best result found. The global random number generated is seeded with a fixed number to ensure a consistent sequence of random numbers are used which can prove useful during testing.
attr_accessor :max_iterations, :max_rcl_size
attr_reader :best_solution
def initialize(max_iterations)
@max_iterations = max_iterations
@max_rcl_size = 5 # default
end
# execute the algorithm
def search(problem)
# initialize the search
@best_solution = nil
current = generate_initial_solution(problem)
evaluate_candidate_solution(current, problem)
curr_it = 0
begin
# greedy randomized solution
candidate = greedy_randomized_solution(current, problem)
evaluate_candidate_solution(candidate, problem) # eval
# local search
candidate = local_search_solution(candidate, problem)
# greedy acceptance
current = candidate if problem.is_better?(candidate.score, current.score)
curr_it += 1
end until should_stop?(curr_it, problem)
return @best_solution
end
def should_stop?(curr_it, problem)
(curr_it >= @max_iterations) or problem.is_optimal?(best_solution.score)
end
def generate_initial_solution(problem)
all = Array.new(problem.num_cities) {|i| (i+1)}
permutation = Array.new(all.length) {|i| all.delete_at(rand(all.length))}
return Solution.new(permutation)
end
def greedy_randomized_solution(solution, problem)
# construct a valid perm
perm = []
perm << rand(problem.num_cities) + 1 # random starting point
last = perm[0]
while perm.length < problem.num_cities
# create restricted candidate list for components
all = Array.new(problem.num_cities) {|i| (i+1)}
# ensure we can only add unused components
rcl = all - perm
# order by distance, asc (best have smallest distance)
rcl.sort! {|i,j| problem.dist(last, i) <=> problem.dist(last, j)}
# trim to fixed size
rcl.pop until rcl.length <= @max_rcl_size
# select random
last = rcl[rand(rcl.length)]
perm << last
end
return Solution.new(perm)
end
def local_search_solution(solution, problem)
# greedy iterated 2-opt
15.times do
candidate = two_opt_solution(solution)
evaluate_candidate_solution(candidate, problem)
if problem.is_better?(candidate.score, solution.score)
solution = candidate
end
end
return solution
end
def two_opt_solution(solution)
perm = Array.new(solution.data) # copy
# select a sub-sequence
c1, c2 = rand(perm.length), rand(perm.length)
c2 = rand(perm.length) while c1 == c2
# ensure c1 is low and c2 is high
c1, c2 = c2, c1 if c2 < c1
# reverse sub-sequence
perm[c1...c2] = perm[c1...c2].reverse
return Solution.new(perm)
end
def evaluate_candidate_solution(solution, problem)
solution.score = problem.evaluate(solution.data)
# keep track of the best solution found
if @best_solution.nil? or
problem.is_better?(solution.score, @best_solution.score)
@best_solution = solution
puts "> new best: #{solution.score}"
end
end
end
srand(1) # set the random number seed to 1The demonstrated GRASP provides much opportunity for extension. One may modify the implementation of the TSP problem instance to provide a class that can load problems form definition files provided by the TSPLIB. The size of the RCL list may be tuned to vary the greediness of solution construction. Further, the preparation of the RCL may be modified to make use of the current working solution passed into the function, perhaps using existing selected components to bias the selection of those components during construction. Finally, adaptive RCL management procedures may be adopted as well as alternative local search procedures for the TSP.
algorithm = GRASP.new(500) # limit to 500 iterations
problem = Berlin52TSP.new # create a problem
best = algorithm.search(problem) # execute the search
puts "Best Solution: #{best}" # display the best solution
Source Code
Download: GRASP.rb
Further Reading
Papers
- T. A. Feo and M. G. C. Resende. Greedy randomized adaptive search procedures. (pre-print) Journal of Global Optimization, 6, 109-133, 1995.
- M. G. C. Resende and C. C. Ribeiro Greedy randomized adaptive search procedures (pre-print). In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, Springer, pages. 219-249, 2003.
- L. Pitsoulis and M. G. C. Resende Greedy randomized adaptive search procedures (pre-print). In P. M. Pardalos and M. G. C. Resende, editors, Handbook of Applied Optimization, Oxford University Press, pages. 168-181, 2002
Have you found a bug? Know of a great reference? Got an idea for a guide? Please send an email to jasonb@InspiredAlgorithms.com.
Need Help? Want to discuss this post? Please visit the Inspired Algorithms User Group.
