class IteratedLocalSearch::IteratedLocalSearch

Public Instance Methods

cost(permutation, cities) click to toggle source

gets distance between two cities

# File lib/iterated_local_search.rb, line 11
def cost(permutation, cities)
  distance = 0
  permutation.each_with_index do |c1, i|
    c2 = (i == (permutation.size - 1)) ? permutation[0] : permutation[i + 1]
    # +++ get distance between two cities
    distance += euc_2d cities[c1], cities[c2]
  end
  distance
end
double_bridge_move(permutation) click to toggle source

rejoins array

# File lib/iterated_local_search.rb, line 48
def double_bridge_move(permutation)
  pos1 = 1 + (permutation.size / 4)
  pos2 = pos1 + 1 + rand(permutation.size / 4)
  pos3 = pos2 + 1 + rand(permutation.size / 4)
  p1 = permutation[0...pos1] + permutation[pos3...permutation.size]
  p2 = permutation[pos2...pos3] + permutation[pos1...pos2]
  p1 + p2
end
euc_2d(c1, c2) click to toggle source

gets distance between cities

# File lib/iterated_local_search.rb, line 6
def euc_2d(c1, c2)
  Math.sqrt((c2[0] - c1[0]) ** 2.0 + (c2[1] - c1[1]) ** 2.0).round
end
perturbation(cities, best) click to toggle source

does double bridge

# File lib/iterated_local_search.rb, line 58
def perturbation(cities, best)
  candidate = {}
  candidate[:vector] = double_bridge_move best[:vector]
  candidate[:cost] = cost candidate[:vector], cities
  candidate
end
random_permutation(cities) click to toggle source

gets random permutation

# File lib/iterated_local_search.rb, line 22
def random_permutation(cities)
  perm = Array.new(cities.size){|i| i}

  perm.each_index do |i|
    # +++ stays withing range, +- cancel each other
    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

gets reverse in range

# File lib/iterated_local_search.rb, line 34
def stochastic_two_opt(permutation)
  perm = Array.new(permutation)
  c1, c2 = rand(perm.size), rand(perm.size)
  collection = [c1]
  collection << ((c1 == 0 ? perm.size - 1 : c1 - 1))
  collection << ((c1 == perm.size - 1) ? 0 : c1 + 1)
  c2 = rand(perm.size) while collection.include? (c2)
  c1, c2 = c2, c1 if c2 < c1
  # +++ reverses in range
  perm[c1...c2] = perm[c1...c2].reverse
  perm
end