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