Class: GreedyRaAlgorithm::GreedyRaAlgorithm

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

Instance Method Summary collapse

Instance Method Details

#cost(shake, cities) ⇒ Object

gets distance between two cities



11
12
13
14
15
16
17
18
19
 
# File 'lib/greedy_ra_algorithm.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/greedy_ra_algorithm.rb', line 6

def euc_2d(c1, c2)
  Math.sqrt((c2[0] - c1[0]) ** 2.0 + (c2[1] - c1[1]) ** 2.0).round
end

#local_search(best, cities, max_no_improv) ⇒ Object

does two opt



36
37
38
39
40
41
42
43
44
45
 
# File 'lib/greedy_ra_algorithm.rb', line 36

def local_search(best, cities, max_no_improv)
  count = 0
  begin
    candidate = {:vector => two_opt(best[:vector])}
    candidate[:cost] = cost(candidate[:vector], cities)
    count = (candidate[:cost] < best[:cost]) ? 0 : count + 1
    best = candidate if candidate[:cost] < best[:cost]
  end until count >= max_no_improv
  best
end

#randomized_greedy_solution(cities, greedy) ⇒ Object

get solution



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/greedy_ra_algorithm.rb', line 48

def randomized_greedy_solution(cities, greedy)
  candidate = {}
  candidate[:vector] = [rand(cities.size)]
  allCities = Array.new(cities.size){|i| i}
  while candidate[:vector].size < cities.size
    candidates = allCities - candidate[:vector]
    costs = Array.new(candidates.size) do |i|
      euc_2d(cities[candidate[:vector].last], cities[i])
    end
    rcl, max, min = [], costs.max, costs.min
    costs.each_with_index do |cost, i|
      rcl << candidates[i] if cost <= (min + greedy * (max - min))
    end
    candidate[:vector] << rcl[rand(rcl.size)]
  end
  candidate[:cost] = cost(candidate[:vector], cities)
  candidate
end

#search(cities, max_iter, max_no_improv, greedy) ⇒ Object

search



68
69
70
71
72
73
74
75
76
77
 
# File 'lib/greedy_ra_algorithm.rb', line 68

def search(cities, max_iter, max_no_improv, greedy)
  best = nil
  max_iter.times do |iter|
    candidate = randomized_greedy_solution(cities, greedy)
    candidate = local_search(candidate, cities, max_no_improv)
    best = candidate if best.nil? or candidate[:cost] < best[:cost]
    puts " > iteration #{(iter + 1)}, best #{best[:cost]}"
  end
  best
end

#two_opt(shake) ⇒ Object

gets reverse in range



22
23
24
25
26
27
28
29
30
31
32
33
 
# File 'lib/greedy_ra_algorithm.rb', line 22

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
  perm
end