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
search(cities, max_iterations, t)
click to toggle source
search
# File lib/extremal_opt_tsp.rb, line 141 def search(cities, max_iterations, t) current = {:vector => shake(cities)} current[:cost] = cost(current[:vector], cities) best = current max_iterations.times do |iter| candidate = {} candidate[:vector] = new_shake(cities, t, current[:vector]) candidate[:cost] = cost(candidate[:vector], cities) current = candidate best = candidate if candidate[:cost] < best[:cost] puts " > iter #{(iter + 1)}, best #{best[:cost]}" end best 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