Class: AntTsp::AntTsp

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

Instance Method Summary collapse

Instance Method Details

#cost(sh, cities) ⇒ Object

cost, of the tour



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

#decay_pheromone(pheromone, decay_factor) ⇒ Object

decay, pheromone



76
77
78
79
80
81
82
 
# File 'lib/ant_tsp.rb', line 76

def decay_pheromone(pheromone, decay_factor)
  pheromone.each do |array|
    array.each_with_index do |p, i|
      array[i] = (1.0 - decay_factor) * p
    end
  end
end

#euc_2d(c1, c2) ⇒ Object

distance, between two cities



6
7
8
 
# File 'lib/ant_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_choices(cities, last_city, skip, pheromone, c_heur, c_hist) ⇒ Object

choices, get them



37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/ant_tsp.rb', line 37

def get_choices(cities, last_city, skip, pheromone, c_heur, c_hist)
  choices = []
  cities.each_with_index do |position, i|
    next if skip.include?(i)
    prob = {:city => i}
    prob[:history] = pheromone[last_city][i] ** c_hist
    prob[:distance] = euc_2d(cities[last_city], position)
    prob[:heuristic] = (1.0 / prob[:distance]) ** c_heur
    prob[:prob] = prob[:history] * prob[:heuristic]
    choices << prob
  end
  choices
end

#search(cities, max_it, num_ants, decay_factor, c_heur, c_hist) ⇒ Object

search



96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/ant_tsp.rb', line 96

def search(cities, max_it, num_ants, decay_factor, c_heur, c_hist)
  best = {:vector => shake(cities)}
  best[:cost] = cost(best[:vector], cities)
  pheromone = setup_phero_matrix(cities.size, best[:cost])
  max_it.times do |iter|
    solutions = []
    num_ants.times do
      candidate = {}
      # +++ get tour
      candidate[:vector] = stepwise_const(cities, pheromone, c_heur, c_hist)
      candidate[:cost] = cost(candidate[:vector], cities)
      best = candidate if candidate[:cost] < best[:cost]
      solutions << candidate
    end
    # +++ decay phero
    decay_pheromone(pheromone, decay_factor)
    # +++ update phero
    update_pheromone(pheromone, solutions)
    puts " > iteration #{(iter + 1)}, best #{best[:cost]}"
  end
  best
end

#select_next_city(choices) ⇒ Object

next city



52
53
54
55
56
57
58
59
60
61
 
# File 'lib/ant_tsp.rb', line 52

def select_next_city(choices)
  sum = choices.inject(0.0) {|sum, element| sum + element[:prob]}
  return choices[rand(choices.size)][:city] if sum == 0.0
  v = rand()
  choices.each_with_index do |choice, i|
    v -= (choice[:prob] / sum)
    return choice[:city] if v <= 0.0
  end
  return choices.last[:city]
end

#setup_phero_matrix(num_cities, naive_score) ⇒ Object

setup, pheromone matrix



31
32
33
34
 
# File 'lib/ant_tsp.rb', line 31

def setup_phero_matrix(num_cities, naive_score)
  v = num_cities.to_f / naive_score
  return Array.new(num_cities){|i| Array.new(num_cities, v)}
end

#shake(cities) ⇒ Object

shake, cities



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

#stepwise_const(cities, phero, c_heur, c_hist) ⇒ Object

next city, add them up



64
65
66
67
68
69
70
71
72
73
 
# File 'lib/ant_tsp.rb', line 64

def stepwise_const(cities, phero, c_heur, c_hist)
  shake = []
  shake << rand(cities.size)
  begin
    choices = get_choices(cities, shake.last, shake, phero, c_heur, c_hist)
    next_city = select_next_city(choices)
    shake << next_city
  end until shake.size == cities.size
  shake
end

#update_pheromone(pheromone, solutions) ⇒ Object

update, pheromone



85
86
87
88
89
90
91
92
93
 
# File 'lib/ant_tsp.rb', line 85

def update_pheromone(pheromone, solutions)
  solutions.each do |other|
    other[:vector].each_with_index do |x, i|
      y = (i == (other[:vector].size - 1)) ? other[:vector][0] : other[:vector][i + 1]
      pheromone[x][y] += (1.0 / other[:cost])
      pheromone[y][x] += (1.0 / other[:cost])
    end
  end
end