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