class SimAnnealing::SimAnnealing

Public Instance Methods

cost(sh, cities) click to toggle source

cost, of the path

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

distance, between cities

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

get neighbor

# File lib/sim_annealing.rb, line 43
def get_neighbor(current, cities)
  candidate = {}
  candidate[:vector] = Array.new(current[:vector])
  two_opt(candidate[:vector])
  candidate[:cost] = cost(candidate[:vector], cities)
  candidate
end
shake(cities) click to toggle source

shake, cities

# File lib/sim_annealing.rb, line 21
def shake(cities)
  sh = Array.new(cities.size){|i| i}
  sh.each_index do |i|
    r = rand(sh.size - i) + i
    sh[r], sh[i] = sh[i], sh[r]
  end
  sh
end
should_accept?(candidate, current, temp) click to toggle source

accept, ?

# File lib/sim_annealing.rb, line 52
def should_accept?(candidate, current, temp)
  return true if candidate[:cost] <= current[:cost]
  return Math.exp((current[:cost] - candidate[:cost]) / temp) > rand()
end
two_opt(sh) click to toggle source

shake, cities in range

# File lib/sim_annealing.rb, line 31
def two_opt(sh)
  c1, c2 = rand(sh.size), rand(sh.size)
  skip = [c1]
  skip << ((c1 == 0) ? sh.size - 1 : c1 - 1)
  skip << ((c1 == sh.size - 1) ? 0 : c1 + 1)
  c2 = rand(sh.size) while skip.include?(c2)
  c1, c2 = c2, c1 if c2 < c1
  sh[c1...c2] = sh[c1...c2].reverse
  sh
end