class AntColony::Colony

Constants

DEFAULT_PHERO

Attributes

alpha[R]
beta[R]
graph[R]
ph[R]
pop[R]
q[R]

Public Class Methods

new(graph, alpha: 0.8, beta: 0.4, ph: 0.3, q: 500, pop: 200) click to toggle source
# File lib/ant_colony.rb, line 9
def initialize(graph, alpha: 0.8, beta: 0.4, ph: 0.3, q: 500, pop: 200)
  method(__method__).parameters.each do |_, name|
    instance_variable_set(:"@#{name}", binding.local_variable_get(name))
  end
  set_default_tau
end

Public Instance Methods

find_path(*roadmap) click to toggle source
# File lib/ant_colony.rb, line 16
def find_path(*roadmap)
  loop do
    city = graph[roadmap.last] # current point(city) ant located

    sum_paths = city.reduce(0.0) do |sum, (_, path)|
      sum + (path[:tau]**alpha).to_f / (path[:length]**beta)
    end

    proposed_paths = city.each_with_object({}) do |(direction, path), paths|
      unless roadmap.include? direction
        paths[direction] = (((path[:tau]**alpha).to_f / path[:length])**beta) / sum_paths
      end
    end

    roadmap << best_path_of(proposed_paths)
    break unless roadmap.length < graph.size
  end

  roadmap
end
length_of(path) click to toggle source
# File lib/ant_colony.rb, line 46
def length_of(path)
  [*path, path.first].each_cons(2).reduce(0.0) do |sum, (cur, nxt)|
    sum + graph[cur][nxt][:length]
  end
end
solve() click to toggle source
# File lib/ant_colony.rb, line 37
def solve
  graph.size.times do |i|
    pop.times do
      path = find_path(i + 1)
      increase_tau_for path
    end
  end
end

Private Instance Methods

best_path_of(paths) click to toggle source
# File lib/ant_colony.rb, line 62
def best_path_of(paths)
  paths.max_by { |_, v| v }.first
end
increase_tau_for(path) click to toggle source
# File lib/ant_colony.rb, line 66
def increase_tau_for(path)
  [*path, path.first].each_cons(2) do |cur, nxt|
    tau_next = (1.0 - ph) * graph[cur][nxt][:tau] + q.to_f / length_of(path)
    graph[cur][nxt][:tau] = graph[nxt][cur][:tau] = tau_next
  end
end
set_default_tau() click to toggle source
# File lib/ant_colony.rb, line 54
def set_default_tau
  graph.each do |_, roads|
    roads.each do |_, props|
      props[:tau] = DEFAULT_PHERO
    end
  end
end