class AntTsp::AntTsp
Public Instance Methods
cost(sh, cities)
click to toggle source
cost, of the tour
# 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)
click to toggle source
decay, pheromone
# 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)
click to toggle source
distance, between two cities
# 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)
click to toggle source
choices, get them
# 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)
click to toggle source
search
# 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)
click to toggle source
next city
# 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)
click to toggle source
setup, pheromone matrix
# 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)
click to toggle source
shake, cities
# 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)
click to toggle source
next city, add them up
# 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)
click to toggle source
update, pheromone
# 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