class ExtremalOptTsp::ExtremalOptTsp

Public Instance Methods

cost(sh, cities) click to toggle source

cost, of the tour

# File lib/extremal_opt_tsp.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 two cities

# File lib/extremal_opt_tsp.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_city_fitness(sh, city_number, cities) click to toggle source

fitness, city

# File lib/extremal_opt_tsp.rb, line 56
def get_city_fitness(sh, city_number, cities)
  c1, c2 = get_edges_for_city(city_number, sh)
  neighbors = get_neighbor_rank(city_number, cities)
  n1, n2 = -1, -1
  neighbors.each_with_index do |neighbor, i|
    n1 = i + 1 if neighbor[:number] == c1
    n2 = i + 1 if neighbor[:number] == c2
  end
  return 3.0 / (n1.to_f + n2.to_f)
end
get_city_fitnesses(cities, sh) click to toggle source

fitnesses, cities

# File lib/extremal_opt_tsp.rb, line 68
def get_city_fitnesses(cities, sh)
  city_fitnesses = []
  cities.each_with_index do |city, i|
    city_fitness = {:number => i}
    city_fitness[:fitness] = get_city_fitness(sh, i, cities)
    city_fitnesses << city_fitness
  end
  return city_fitnesses.sort!{|x, y| x[:fitness] <=> y[:fitness]}
end
get_component_probs(ordered_comps, t) click to toggle source

probs, components

# File lib/extremal_opt_tsp.rb, line 79
def get_component_probs(ordered_comps, t)
  sum = 0.0
  ordered_comps.each_with_index do |component, i|
    component[:prob] = (i + 1.0) ** (-t)
    sum += component[:prob]
  end
  sum
end
get_edges_for_city(city_number, sh) click to toggle source

edges, for city

# File lib/extremal_opt_tsp.rb, line 43
def get_edges_for_city(city_number, sh)
  c1, c2 = nil, nil
  sh.each_with_index do |c, i|
    if c == city_number
      c1 = (i == 0) ? sh.last : sh[i - 1]
      c2 = (i == sh.size - 1) ? sh.first : sh[i + 1]
      break
    end
  end
  return [c1, c2]
end
get_longer_edge(edges, neighbor_distances) click to toggle source

longer edge, get

# File lib/extremal_opt_tsp.rb, line 123
def get_longer_edge(edges, neighbor_distances)
  n1 = neighbor_distances.find{|x| x[:number] = edges[0]}
  n2 = neighbor_distances.find{|x| x[:number] = edges[1]}
  return (n1[:distance] > n2[:distance]) ? n1[:number] : n2[:number]
end
get_neighbor_rank(city_number, cities, ignore=[]) click to toggle source

neighbors, get them ranked

# File lib/extremal_opt_tsp.rb, line 31
def get_neighbor_rank(city_number, cities, ignore=[])
  neighbors = []
  cities.each_with_index do |city, i|
    next if i == city_number or ignore.include?(i)
    neighbor = {:number => i}
    neighbor[:distance] = euc_2d(cities[city_number], city)
    neighbors << neighbor
  end
  return neighbors.sort!{|x, y| x[:distance] <=> y[:distance]}
end
new_shake(cities, t, sh) click to toggle source

new shake

# File lib/extremal_opt_tsp.rb, line 130
def new_shake(cities, t, sh)
  city_fitnesses = get_city_fitnesses(cities, sh)
  selected_city = select_maybe(city_fitnesses.reverse, t)
  edges = get_edges_for_city(selected_city, sh)
  neighbors = get_neighbor_rank(selected_city, cities)
  new_neighbor = select_maybe(neighbors, t, edges)
  long_edge = get_longer_edge(edges, neighbors)
  return vary_shake(sh, selected_city, new_neighbor, long_edge)
end
select(comps, sum_probs) click to toggle source

select

# File lib/extremal_opt_tsp.rb, line 89
def select(comps, sum_probs)
  selection = rand()
  comps.each_with_index do |comp, i|
    selection -= (comp[:prob] / sum_probs)
    return comp[:number] if selection <= 0.0
  end
  return comps.last[:number]
end
select_maybe(ordered_comps, t, skip = []) click to toggle source

select, city maybe

# File lib/extremal_opt_tsp.rb, line 99
def select_maybe(ordered_comps, t, skip = [])
  sum = get_component_probs(ordered_comps, t)
  selected_city = nil
  begin
    selected_city = select(ordered_comps, sum)
  end while skip.include?(selected_city)
  selected_city
end
shake(cities) click to toggle source

shake, cities

# File lib/extremal_opt_tsp.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
vary_shake(sh, selected, new, long_edge) click to toggle source

shake, vary

# File lib/extremal_opt_tsp.rb, line 109
def vary_shake(sh, selected, new, long_edge)
  _sh = Array.new(sh)
  c1, c2 = _sh.rindex(selected), _sh.rindex(selected)
  p1, p2 = (c1 < c2) ? [c1, c2] : [c2, c1]
  right = (c1 == _sh.size - 1) ? 0 : c1 + 1
  if _sh[right] == long_edge
    _sh[p1 + 1 ... p2] = _sh[p1 + 1 ... p2].reverse
  else
    _sh[p1 ... p2] = _sh[p1 ... p2].reverse
  end
  _sh
end