Class: TabooSearch::TabooSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/taboo_search.rb

Instance Method Summary collapse

Instance Method Details

#candidate(best, taboo_list, cities) ⇒ Object

candidate



57
58
59
60
61
62
63
64
65
 
# File 'lib/taboo_search.rb', line 57

def candidate(best, taboo_list, cities)
  shake, edges = nil, nil
  begin
    shake, edges = two_opt(best[:vector])
  end while is_taboo?(shake, taboo_list)
  candidate = {:vector => shake}
  candidate[:cost] = cost(candidate[:vector], cities)
  return candidate, edges
end

#cost(shake, cities) ⇒ Object

gets distance between two cities



11
12
13
14
15
16
17
18
19
 
# File 'lib/taboo_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

#euc_2d(c1, c2) ⇒ Object

gets distance between cities



6
7
8
 
# File 'lib/taboo_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

#is_taboo?(shake, taboo_list) ⇒ Boolean

is taboo

Returns:

  • (Boolean) 


46
47
48
49
50
51
52
53
54
 
# File 'lib/taboo_search.rb', line 46

def is_taboo?(shake, taboo_list)
  shake.each_with_index do |c1, i|
    c2 = (i == (shake.size - 1)) ? shake[0] : shake[i + 1]
    taboo_list.each do |forbidden_edge|
      return true if forbidden_edge == [c1, c2]
    end
  end
  false
end

#search(cities, taboo_list_size, candidate_list_size, max_iter) ⇒ Object

search



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/taboo_search.rb', line 68

def search(cities, taboo_list_size, candidate_list_size, max_iter)
  current = {:vector => shake(cities)}
  current[:cost] = cost(current[:vector], cities)
  best = current
  taboo_list = Array.new(taboo_list_size)
  max_iter.times do |iter|
    candidates = Array.new(candidate_list_size) do |i|
      candidate(current, taboo_list, cities)
    end
    candidates.sort!{|x, y| x.first[:cost] <=> y.first[:cost]}
    best_candidate = candidates.first[0]
    best_candidate_edges = candidates.first[1]
    if best_candidate[:cost] < current[:cost]
      current = best_candidate
      best = best_candidate if best_candidate[:cost] < best[:cost]
      best_candidate_edges.each{|edge| taboo_list.push(edge)}
      taboo_list.pop while taboo_list.size > taboo_list_size
    end
    puts " > iteration #{(iter + 1)}, best #{best[:cost]}"
  end
  best
end

#shake(cities) ⇒ Object

shake



22
23
24
25
26
27
28
29
 
# File 'lib/taboo_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

#two_opt(shake) ⇒ Object

gets reverse in range



32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/taboo_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