class Algorithmically::Stochastic::GuidedLocalSearch

Public Class Methods

new(max_iterations, berlin52, max_no_improv, lambda) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 6
def initialize(max_iterations, berlin52, max_no_improv, lambda)
  @berlin52 = berlin52
  @max_iterations = max_iterations
  @max_no_improv = max_no_improv
  alpha = 0.3
  local_search_optima = 12000.0
  lambda = alpha * (local_search_optima/berlin52.size.to_f)
  @lambda = lambda
  best = search(@max_iterations, @berlin52, @max_no_improv, lambda)
  puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}"
end

Public Instance Methods

augmented_cost(permutation, penalties, cities, lambda) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 43
def augmented_cost(permutation, penalties, cities, lambda)
  distance, augmented = 0, 0
  permutation.each_with_index do |c1, i|
    c2 = (i==permutation.size-1) ? permutation[0] : permutation[i+1]
    c1, c2 = c2, c1 if c2 < c1
    d = euc_2d(cities[c1], cities[c2])
    distance += d
    augmented += d + (lambda * (penalties[c1][c2]))
  end
  [distance, augmented]
end
calculate_feature_utilities(penal, cities, permutation) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 72
def calculate_feature_utilities(penal, cities, permutation)
  utilities = Array.new(permutation.size, 0)
  permutation.each_with_index do |c1, i|
    c2 = (i==permutation.size-1) ? permutation[0] : permutation[i+1]
    c1, c2 = c2, c1 if c2 < c1
    utilities[i] = euc_2d(cities[c1], cities[c2]) / (1.0 + penal[c1][c2])
  end
  utilities
end
cost(cand, penalties, cities, lambda) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 55
def cost(cand, penalties, cities, lambda)
  cost, acost = augmented_cost(cand[:vector], penalties, cities, lambda)
  cand[:cost], cand[:aug_cost] = cost, acost
end
euc_2d(c1, c2) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 18
def euc_2d(c1, c2)
  Math.sqrt((c1[0] - c2[0])**2.0 + (c1[1] - c2[1])**2.0).round
end
random_permutation(cities) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 22
def random_permutation(cities)
  perm = Array.new(cities.size) { |i| i }
  perm.each_index do |i|
    r = rand(perm.size-i) + i
    perm[r], perm[i] = perm[i], perm[r]
  end
  perm
end
stochastic_two_opt(permutation) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 31
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
  perm
end
update_penalties!(penalties, cities, permutation, utilities) click to toggle source
# File lib/Algorithmically/Stochastic/guided_local_search.rb, line 82
def update_penalties!(penalties, cities, permutation, utilities)
  max = utilities.max()
  permutation.each_with_index do |c1, i|
    c2 = (i==permutation.size-1) ? permutation[0] : permutation[i+1]
    c1, c2 = c2, c1 if c2 < c1
    penalties[c1][c2] += 1 if utilities[i] == max
  end
  penalties
end