class GuidedLocalSearch::GuidedLocalSearch
Public Instance Methods
augmented_cost(shake, penalties, cities, modifier)
click to toggle source
get augmented cost
# File lib/guided_local_search.rb, line 34 def augmented_cost(shake, penalties, cities, modifier) distance, augmented = 0, 0 shake.each_with_index do |c1, i| c2 = (i == (shake.size - 1)) ? shake[0] : shake[i + 1] c1, c2 = c2, c1 if c2 < c1 d = euc_2d cities[c1], cities[c2] distance += d augmented += d + (modifier * penalties[c1][c2]) end [distance, augmented] end
cost(cand, penalties, cities, modifier)
click to toggle source
get shake cost
# File lib/guided_local_search.rb, line 47 def cost(cand, penalties, cities, modifier) cost, acost = augmented_cost cand[:vector], penalties, cities, modifier cand[:cost], cand[:aug_cost] = cost, acost end
euc_2d(c1, c2)
click to toggle source
get line distance between cities
# File lib/guided_local_search.rb, line 6 def euc_2d(c1, c2) Math.sqrt((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2).round end
feature_utilities(penal, cities, shake)
click to toggle source
get utilities
# File lib/guided_local_search.rb, line 53 def feature_utilities(penal, cities, shake) utilities = Array.new(shake.size, 0) shake.each_with_index do |c1, i| c2 = (i == (shake.size - 1)) ? shake[0] : shake[i + 1] c1, c2 = c2, c1 if c2 < c1 # +++ metric utilities utilities[i] = euc_2d(cities[c1], cities[c2]) / (1.0 + penal[c1][c2]) end utilities end
local_search(current, cities, penalties, max_no_improv, modifier)
click to toggle source
do local search
# File lib/guided_local_search.rb, line 77 def local_search(current, cities, penalties, max_no_improv, modifier) cost current, penalties, cities, modifier count = 0 begin candidate = {:vector => stochastic_two_opt(current[:vector])} cost candidate, penalties, cities, modifier 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 current end
random_permutation(cities)
click to toggle source
shake cities (random permute)
# File lib/guided_local_search.rb, line 11 def random_permutation(cities) shake = Array.new(cities.size){|i| i} shake.each_index do |i| r = rand(shake.size - i) + i shake[r], shake[i] = shake[i], shake[r] end shake end
search(max_iterations, cities, max_no_improv, modifier)
click to toggle source
do search
# File lib/guided_local_search.rb, line 90 def search(max_iterations, cities, max_no_improv, modifier) 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, modifier utilities = 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 best end
stochastic_two_opt(shake)
click to toggle source
shake in range
# File lib/guided_local_search.rb, line 21 def stochastic_two_opt(shake) sh = Array.new(shake) c1, c2 = rand(sh.size), rand(sh.size) pool = [c1] pool << ((c1 == 0) ? sh.size - 1 : c1 + 1) pool << ((c1 == (sh.size - 1)) ? 0 : c1 - 1) c2 = rand(sh.size) while pool.include? c2 c1, c2 = c2, c1 if c2 < c1 sh[c1...c2] = sh[c1...c2].reverse sh end
update_penalties(penalties, cities, shake, utilities)
click to toggle source
update penalties
# File lib/guided_local_search.rb, line 65 def update_penalties(penalties, cities, shake, utilities) max = utilities.max() shake.each_with_index do |c1, i| c2 = (i == (shake.size - 1)) ? shake[0] : shake[i + 1] c1, c2 = c2, c1 if c2 < c1 # +++ metric penalties penalties[c1][c2] += 1 if utilities[i] = max end penalties end