class TabooReactiveSearch::TabooReactiveSearch

Public Instance Methods

cost(shake, cities) click to toggle source

cost

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

same

# File lib/taboo_reactive_search.rb, line 81
def equivalent(el1, el2)
  el1.each {|e| return false if el2.nil? || !el2.include?(e)}
  true
end
euc_2d(c1, c2) click to toggle source

get distance between cities

# File lib/taboo_reactive_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
get_candidate(best, cities) click to toggle source

get candidate

# File lib/taboo_reactive_search.rb, line 87
def get_candidate(best, cities)
  candidate = {}
  candidate[:vector], edges = two_opt(best[:vector])
  candidate[:cost] = cost(candidate[:vector], cities)
  return candidate, edges
end
get_candidate_entry(visited_list, shake) click to toggle source

get entry

# File lib/taboo_reactive_search.rb, line 95
def get_candidate_entry(visited_list, shake)
  edge_list = to_edge_list(shake)
  visited_list.each do |entry|
    return entry if equivalent(edge_list, entry[:edge_list])
  end
  nil
end
is_taboo?(edge, taboo_list, iter, prohib_period) click to toggle source

is taboo

# File lib/taboo_reactive_search.rb, line 46
def is_taboo?(edge, taboo_list, iter, prohib_period)
  taboo_list.each do |entry|
    if entry[:edge] = edge
      return true if entry[:iter] >= iter - prohib_period
      return false
    end
  end
  false
end
make_taboo(taboo_list, edge, iter) click to toggle source

make taboo

# File lib/taboo_reactive_search.rb, line 57
def make_taboo(taboo_list, edge, iter)
  taboo_list.each do |entry|
    if entry[:edge] == edge
      entry[:iter] = iter
      return entry
    end
  end
  entry = {:edge => edge, :iter => iter}
  taboo_list.push(entry)
  entry
end
shake(cities) click to toggle source

shake

# File lib/taboo_reactive_search.rb, line 22
def shake(cities)
  shake = Array.new(cities.size){|i| i}
  shake.each_index do |i|
    r = rand(shake.size - 1) + 1
    shake[i], shake[r] = shake[r], shake[i]
  end
  shake
end
sort_neighborhood(candidates, taboo_list, prohib_period, iteration) click to toggle source

sort hood

# File lib/taboo_reactive_search.rb, line 114
def sort_neighborhood(candidates, taboo_list, prohib_period, iteration)
  taboo, admissable = [], []
  candidates.each do |a|
    if is_taboo?(a[1][0], taboo_list, iteration, prohib_period) or
      is_taboo?(a[1][1], taboo_list, iteration, prohib_period)
      taboo << a
    else
      admissable << a
    end
  end
  return [taboo, admissable]
end
store_shake(visited_list, shake, iteration) click to toggle source

store shake

# File lib/taboo_reactive_search.rb, line 104
def store_shake(visited_list, shake, iteration)
  entry = {}
  entry[:entry_list] = to_edge_list(shake)
  entry[:iter] = iteration
  entry[:visits] = 1
  visited_list.push(entry)
  entry
end
to_edge_list(shake) click to toggle source

to edge list

# File lib/taboo_reactive_search.rb, line 70
def to_edge_list(shake)
  list = []
  shake.each_with_index do |c1, i|
    c2 = (i == (shake.size - 1)) ? shake[0] : shake[i + 1]
    c1, c2 = c2, c1 if c2 < c1
    list << [c1, c2]
  end
  list
end
two_opt(shake) click to toggle source

reverse in range

# File lib/taboo_reactive_search.rb, line 32
def two_opt(shake)
  perm = Array.new(shake)
  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
  return perm, [[shake[c1 - 1], shake[c1]], [shake[c2 - 1], shake[c2]]]
end