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