The algorithm works by first selecting a starting point for the search either randomly or via a domain specific construction heuristic. The starting position is then optimized to an approximation of the local optimum using a local search strategy. The algorithm loop involves three steps: a perturbation of the current position, the application of the local search to the perturbation, and an acceptance decision of whether or not the locally optimizing candidate solution should replace the current working position for the search.
A good starting point is important for shorter algorithm runs, whereas this importance degrades as the length of the run is increased because the algorithm is given more opportunity to improve. The Iterative Local Search algorithm resembles random restart of a local search technique, although out-performs this technique given the dependence between each new starting position of the search. The perturbation of the current working position provides long jumps in the search space that are further refined by the local search. If the jumps are too large, performance degrades as the behaviors resembles random restart. If the jumps are too small in the search space, the broader search technique resembles the local search algorithm.
The goal is to find a balance between the perturbation and local search mechanisms within the algorithm such that the local search technique cannot easily undo the longer jumps made by the perturbations. There is a relationship between the perturbations and the acceptance criteria for replacing the current working position. Always accepting improved points may result in a greedy algorithm that only accepts small steps and cannot explore distant regions of the search space. Longer jumps made by the perturbation mechanism may require a more flexible (less greedy) acceptance criteria for the search to progress.
Iterated Local Search of the Traveling Salesman Problem
The Iterated Local Search algorithm is suited to problem domains where the good solutions in the search space are clustered. The approach is more commonly applied to combinatorial optimization problems like the Traveling Salesman Problem (TSP) where this clustering of good solutions is manifest as the sharing of common edges. This guide demonstrates the application of the Iterated Local Search algorithm applied to a standardized instance of the TSP from the TSP library (TSPLIB).
The Berlin52TSP class contains a the city coordinate data and optimal tour data as COORDINATES and OPTIMAL_TOUR constants respectively, taken from the TSPLIB definition files for the Berlin52 problem instance. The initialize() constructor sets the accessible @num_cities instance variable and calculates the @optimal_tour_length used by the is_optimal?(scoring) method for assessing scores to see if an optimal tour has been discovered. The evaluate(permutation)method calculates the distance of a given tour permutation which is an array of non-repeating integers that specify cities between 1 and 52 inclusively. Evaluation involves calculating the Euclidean distance for each of the city pairs using the problem definition coordinates. The euc_2d(c1, c2) method matches the Euclidean calculation specified by the TSPLIB documentation, most notably involving the rounding of calculated distances to integers for this symmetrical TSP instance.
class Berlin52TSPThe Solution class is a classical container for candidate solutions, holding a TSP permutation in the immutable @data instance variable and managing a mutable permutation scoring 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
@optimal_tour_length = evaluate(OPTIMAL_TOUR) # calculate
end
def evaluate(permutation)
dist = 0
permutation.each_with_index do |c1, i|
c2 = (i==@num_cities-1) ? permutation[0] : permutation[i+1]
dist += euc_2d(COORDINATES[c1-1], COORDINATES[c2-1])
end
return dist
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 IteratedLocalAlgorithm class is quite large. The search(problem) method is generalized and executes the iterated local search algorithm on the provided problem definition. It starts by calling generate_initial_solution(problem) to prepare a starting point for the search and refining it with a call to local_search_solution(current, problem). The algorithms main loop is a text book implementation involving repeated rounds of generating a perturbed versions of the current working solution, refining it with a local search procedure, and in this case using a greedy (candidate must be better) acceptance criteria.
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 meat of the algorithm are specific to TSP permutations. The generate_initial_solution(problem) generates a random permutation as the starting point of the search. The perturb_solution(solution) method generates a 4-opt variation of a given permutation, also known as a double-bridge move. Basically the permutation is split into 4 pieces and reordered. This function may be called repeatedly if more drastic perturbations are desired, perhaps on large problem instances. The local_search_solution(solution, problem) method is an iterative application of the 2-opt procedure, that evaluates generated solutions and greedily maintains the best candidate solution discovered. The 2-opt procedure involves breaking the tour permutation into two parts (two break points) and reconnecting the tour back together by switching the end points (reversing the sequence between the break points). This is a classical and fast local search procedure for TSP and here it is repeated 30 times.
class IteratedLocalAlgorithmThe demonstration of the algorithm involves first seeding the global random number generator to one, and constructing both an instance of the problem and the algorithm. The algorithm is executed on the problem instance and the algorithm stop condition is triggered if the optimal solution is discovered or a maximum of 2000 iterations of the main algorithm loop are completed.
attr_accessor :max_iterations
attr_reader :best_solution
def initialize(max_iterations)
@max_iterations = max_iterations
end
# execute a iterated local search on the provided problem
def search(problem)
# random starting point
current = generate_initial_solution(problem)
@best_solution = current
evaluate_candidate_solution(current, problem)
# local search
local_best = local_search_solution(current, problem)
current = local_best if problem.is_better?(local_best.score, current.score)
curr_it = 0
begin
# generate perturbation
pert_solution = perturb_solution(current)
evaluate_candidate_solution(pert_solution, problem)
# local search
local_best = local_search_solution(pert_solution, problem)
# greedy acceptance
current = local_best if problem.is_better?(local_best.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 perturb_solution(solution)
data = solution.data
length = data.length
# double-bridge move (4-opt), break into 4 parts (a,b,c,d)
pos1 = 1 + rand(length / 4)
pos2 = pos1 + 1 + rand(length / 4)
pos3 = pos2 + 1 + rand(length / 4)
# put it back together (a,d,c,b)
perm = data[0...pos1] + data[pos3...length] +
data[pos2...pos3] + data[pos1...pos2]
return Solution.new(perm)
end
def local_search_solution(solution, problem)
# greedy iterated 2-opt
30.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 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 1There is plenty of room for extension of this interesting guide. The problem definition may be made generic such that it loads problem instance descriptions and optimal tours from TSPLIB files. The problem class may be made computationally more efficient by pre-calculating the city distance matrix on construction and looking up these distance evaluations in the evaluate method. The use of a randomly generated starting point for the search suggests that the algorithm may need to be executed for a long time to approximate the global optima (longer than 2000 iterations). The algorithm may be adjusted to use a deterministically generated nearest-neighbor solution as the starting point of the search that expected to be a much better quality solution. Finally, more advanced local search procedures exist for the TSP (such as Lin-Kernighan), which may be integrated into the algorithm.
algorithm = IteratedLocalAlgorithm.new(1000) # limit to 1000 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: IteratedLocalSearch.rb
Further Reading
Papers
- Helena Ramalhinho-Lourenço, Olivier C. Martin, Thomas Stützle, Iterated Local Search. (pre-print) Handbook of Metaheuristics, pages 320-353. Springer. 2003
- Thomas Stützle, Iterated local search for the quadratic assignment problem. (pre-print) European Journal of Operational Research. 174(3), pages 1519-1539. 2006
- David S. Johnson, Local optimization and the Traveling Salesman Problem. Automata, Languages and Programming, pages 446-461. 1990
- Local search (optimization). Wikipedia
- Hill climbing. Wikipedia
- TSPLIB
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.
