class AntColonyTsp::AntColonyTsp
Public Instance Methods
cost(sh, cities)
click to toggle source
cost, of the tour
# File lib/ant_colony_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
euc_2d(c1, c2)
click to toggle source
distance, between cities
# File lib/ant_colony_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
where to go next
# File lib/ant_colony_tsp.rb, line 36 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
get_phero_matrix(num_cities, init_pher)
click to toggle source
phero matrix, get it
# File lib/ant_colony_tsp.rb, line 31 def get_phero_matrix(num_cities, init_pher) return Array.new(num_cities){|i| Array.new(num_cities, init_pher)} end
get_tour(cities, phero, c_heur, c_greed)
click to toggle source
get tour +++
# File lib/ant_colony_tsp.rb, line 68 def get_tour(cities, phero, c_heur, c_greed) sh = [] sh << rand(cities.size) begin choices = get_choices(cities, sh.last, sh, phero, c_heur, 1.0) greedy = rand() <= c_greed next_city = (greedy) ? select_city_greedy(choices) : select_city(choices) sh << next_city end until sh.size == cities.size sh end
search(cities, max_it, num_ants, decay, c_heur, c_local_phero, c_greed)
click to toggle source
search
# File lib/ant_colony_tsp.rb, line 101 def search(cities, max_it, num_ants, decay, c_heur, c_local_phero, c_greed) best = {:vector => shake(cities)} best[:cost] = cost(best[:vector], cities) init_phero = 1.0 / (cities.size.to_f * best[:cost]) phero = get_phero_matrix(cities.size, init_phero) max_it.times do |iter| num_ants.times do cand = {} cand[:vector] = get_tour(cities, phero, c_heur, c_greed) cand[:cost] = cost(cand[:vector], cities) best = cand if cand[:cost] < best[:cost] update_phero_local(phero, cand, c_local_phero, init_phero) end update_phero_global(phero, best, decay) puts " > iteration #{iter + 1}, best #{best[:cost]}" end best end
select_city(choices)
click to toggle source
select city, next
# File lib/ant_colony_tsp.rb, line 51 def select_city(choices) sum = choices.inject(0.0) {|sum, item| sum + item[: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
select_city_greedy(choices)
click to toggle source
select city, greedy
# File lib/ant_colony_tsp.rb, line 63 def select_city_greedy(choices) return choices.max{|a, b| a[:prob] <=> b[:prob]}[:city] end
shake(cities)
click to toggle source
shake, cities
# File lib/ant_colony_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
update_phero_global(phero, candidate, decay)
click to toggle source
update phero, global
# File lib/ant_colony_tsp.rb, line 81 def update_phero_global(phero, candidate, decay) candidate[:vector].each_with_index do |row, i| col = (i == candidate[:vector].size - 1) ? candidate[:vector][0] : candidate[:vector][i + 1] value = ((1 - decay) * phero[row][col]) + (decay * (1 / candidate[:cost])) phero[row][col] = value phero[col][row] = value end end
update_phero_local(phero, candidate, c_local_phero, init_phero)
click to toggle source
update phero, local
# File lib/ant_colony_tsp.rb, line 91 def update_phero_local(phero, candidate, c_local_phero, init_phero) candidate[:vector].each_with_index do |row, i| col = (i == candidate[:vector].size - 1) ? candidate[:vector][0] : candidate[:vector][i + 1] value = (1.0 - c_local_phero) * phero[row][col] + (c_local_phero * init_phero) phero[row][col] - value phero[col][row] = value end end