Last active
October 4, 2015 22:47
-
-
Save sld/2711080 to your computer and use it in GitHub Desktop.
Ant Colony Algorithm / Муравьиный алгоритм
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# http://habrahabr.ru/post/105302/ | |
# http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D1%83%D1%80%D0%B0%D0%B2%D1%8C%D0%B8%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B | |
# http://myprograms.3dn.ru/load | |
# http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms | |
require 'set' | |
require 'graphviz' | |
class Node | |
attr_accessor :name | |
def initialize name | |
@name = name | |
end | |
def to_s | |
"Node #{name[0..7]}... " | |
end | |
end | |
class Edge | |
attr_accessor :from, :to, :weight, :intensity | |
def initialize( node1, node2, weight, intensity = nil ) | |
@from = node1 | |
@to = node2 | |
@weight = weight | |
# Инициализируем феромон небольшим начальным значением | |
@intensity = intensity || rand(weight) | |
end | |
def reversed | |
return Edge.new @to, @from, @weight, @intensity | |
end | |
def to_s(params={}) | |
if params[:with_brackets] | |
"(#{@from.name}, #{@to.name})" | |
else | |
"From #{@from.to_s} -- To #{@to.to_s} -- Weight #{@weight} -- Intensity #{@intensity}" | |
end | |
end | |
end | |
class Graph | |
attr_accessor :edges, :start_node | |
MAX_WEIGHT = 90000 | |
def initialize( edges, options = {} ) | |
@edges = edges | |
@start_node = @edges.first.from if @edges.first # Устанавливаем начальную ноду, откуда начинается решение TSP; отсюда также начинают муравьи | |
set_bidirectional if options[:bidirectional] | |
sort_edges if options[:sort_edges] | |
end | |
def sort_edges | |
current_edge = @edges.find{ |edge| !@edges.collect(&:to).include?(edge.from) } | |
@start_node = current_edge.from | |
next_edge = @edges.find{|edge| edge.from == current_edge.to } | |
sorted_edges = [current_edge] | |
while next_edge | |
current_edge = next_edge | |
sorted_edges << current_edge | |
next_edge = @edges.find{|edge| edge.from == current_edge.to } | |
end | |
@edges = sorted_edges | |
end | |
def set_bidirectional | |
reversed_edges = [] | |
@edges.each do |edge| | |
reversed_edges << edge.reversed | |
end | |
@edges += reversed_edges | |
end | |
def where_can_go_from( node, options = {} ) | |
if options[:in] | |
return [] if options[:in].first.class != Edge | |
return options[:in].select{ |edge| edge.from == node }.min_by{|edge| edge.weight}.to if options[:min] | |
return options[:in].select{ |edge| edge.from == node }.map{ |edge| edge.to } | |
else | |
return [] if @edges.first.class != Edge | |
return @edges.select{ |edge| edge.from == node }.map{ |edge| edge.to } | |
end | |
end | |
def edge( node1, node2 ) | |
@edges.select{ |edge| edge.from == node1 && edge.to == node2 }.first | |
end | |
def update_edge_intensity( edge, intensity ) | |
index = @edges.find_index{ |e| e==edge} | |
@edges[index].intensity = intensity | |
end | |
def sort_by_intensity | |
@edges.sort_by{ |edge| edge.intensity } | |
end | |
def nodes | |
tmp_edges = @edges | |
if tmp_edges.first.class == Edge | |
tmp_edges.map{ |edge| [edge.from, edge.to] }.flatten.uniq | |
else | |
return [] | |
end | |
end | |
def better_than( graph ) | |
@edges.inject(0){ |sum, edge| sum+=edge.weight} < graph.edges.inject(0){ |sum, edge| sum+=edge.weight} | |
end | |
def reachable_nodes_from(from_node, was_nodes=Set.new) | |
possible_nodes = where_can_go_from(from_node).to_set - was_nodes | |
was_nodes << from_node | |
possible_nodes.each do |possible_node| | |
reachable_nodes_from(possible_node, was_nodes) | |
end | |
return was_nodes | |
end | |
# Ноды из которых можно попасть во все ноды графа | |
def all_reaches_nodes | |
reaches_nodes = [] | |
nodes.each do |node| | |
reaches_nodes << node if reachable_nodes_from(node) == nodes.to_set | |
end | |
return reaches_nodes | |
end | |
def get_more_than_half_weight_edges | |
goode_edges = [] | |
@edges.each do |edge| | |
goode_edges << edge if ((edge.weight.abs > (edge.from.name.length / 2.0)) || (edge.weight.abs > (edge.to.name.length / 2.0))) | |
end | |
goode_edges | |
end | |
def to_s | |
str = "" | |
weight_sum=0 | |
@edges.each do |edge| | |
str += " #{edge.to_s} \n" | |
weight_sum += edge.weight | |
end | |
str += " Total weight sum is #{weight_sum}\n" | |
return str | |
end | |
def to_png | |
g = GraphViz.new( :G, :type => :digraph ) | |
nodes_hash = {} | |
edges.each do |edge| | |
nodes_hash[edge.from] ||= g.add_nodes( edge.from.to_s ) | |
nodes_hash[edge.to] ||= g.add_nodes( edge.to.to_s ) | |
g.add_edges( nodes_hash[edge.from], nodes_hash[edge.to] ) | |
end | |
g.output( :png => "graph.png" ) | |
end | |
def greedy_search | |
route = Graph.new [] | |
roads = @edges.clone | |
current_position = @start_node | |
while route.nodes.to_set != nodes.to_set | |
next_possible_edges = roads.select{ |edge| edge.from == current_position } | |
min_next_possible = next_possible_edges.min_by{|e| e.weight} | |
if next_possible_edges.collect(&:weight).count(min_next_possible.weight) == 1 | |
road = min_next_possible.clone | |
raise Exception if route.nodes.include?( min_next_possible.from ) | |
route.edges << road | |
current_position = min_next_possible.to | |
else | |
print ["????? in greedy_search", next_possible_edges.collect(&:weight).count(min_next_possible.weight)] | |
raise Exception | |
end | |
end | |
return route | |
end | |
# Генериурем случайный маршрут, если задана опция то, по всем узлам иначе | |
# просто по двум вершинам. Может быть так что маршрут не построится, тогда его цена | |
# будет иметь очень большую величину | |
def generate_random_route_for( options = {} ) | |
route = Graph.new [] | |
roads = @edges.clone | |
current_position = roads.first.from | |
if options[:all_nodes] | |
while route.nodes != nodes | |
begin | |
next_possible_positions = where_can_go_from( current_position, :in => roads ) | |
rescue | |
print( "Cant build random route which includes all nodes; This route weight will be very big sum") | |
break | |
end | |
next_position = next_possible_positions.find_all{|e| !route.nodes.include?(e)}.sample # Выбираем следующую ноду для маршрута случайным образом | |
next_position ||= next_possible_positions.sample | |
road = edge(current_position, next_position).clone | |
if route.nodes.include?( road.to ) | |
road.weight = MAX_WEIGHT | |
break | |
end | |
route.edges << road | |
roads.delete( road ) | |
current_position = road.to | |
end | |
return route | |
else | |
return Graph.new [@edges.first] | |
end | |
end | |
end | |
class Ant | |
attr_accessor :place, :went_places, :went_nodes | |
def initialize( place=nil ) | |
@place = place | |
@went_places = [] | |
@went_nodes = [] | |
end | |
def went_places_goodness | |
goodness = 0 | |
@went_places.each do |went_place| | |
goodness += went_place.weight | |
end | |
return goodness | |
end | |
end | |
class AntAlgorithm | |
def initialize( graph, iteration_count, ants ) | |
@graph = graph | |
@alpha = 10 | |
@beta = 1 | |
@ro = 0.2 | |
@k = 10.0 | |
@iteration_count = iteration_count | |
@ants = ants | |
@route_length = @graph.nodes.count-1 | |
@best_route = @graph.generate_random_route_for :all_nodes => true | |
#print @best_route.to_s | |
end | |
def set_ants_place | |
@ants.each do |ant| | |
ant.place = @graph.start_node | |
ant.went_nodes = [ant.place] | |
ant.went_places = [] | |
end | |
end | |
def run_algorithm debug=true | |
@iteration_count.times do |i| | |
set_ants_place | |
@ants.each do |ant| | |
track = create_track( ant ) | |
if debug | |
print track.to_s | |
print "\n-------- | |
-----------\n" | |
end | |
if track.better_than( @best_route ) && track.nodes.count == @route_length | |
@best_route = track | |
end | |
end | |
@graph.edges.each do |edge| | |
mark_in_edge = mark_in_edge( @ants, edge ) | |
edge.intensity = ( 1.0 - @ro )*edge.intensity + (@k / mark_in_edge) | |
end | |
end | |
output_results | |
return @best_route | |
end | |
def output_results | |
p "Ants count is #{@ants.count}" | |
p "Iteration count is #{@iteration_count}" | |
p "Algorithm parameters:" | |
print " | |
alpha=#{@alpha}\n | |
beta=#{@beta} \n | |
ro=#{@ro}\n | |
k=#{@k}\n | |
" | |
# p "Initial Graph" | |
# print @graph.to_s | |
p "---------" | |
p "Best found route:" | |
print @best_route.to_s | |
end | |
# След оставляемый муравьями в пройденном ребре | |
# Эвристика | |
def mark_in_edge( ants, edge ) | |
m = 0.01 | |
ants.each do |ant| | |
if ant.went_places.include?(edge) | |
m += edge.weight | |
else | |
m += rand( @k ) | |
end | |
end | |
return m | |
end | |
def create_track( ant ) | |
edges = [] | |
current_position = ant.place | |
node_probability_hash = calculate_probabilities( current_position ) | |
while !node_probability_hash.empty? | |
current_position = ant.place | |
next_position = select_next_position( node_probability_hash ) | |
break if ant.went_nodes.include?( next_position ) | |
ant.place = next_position | |
edges << @graph.edge( current_position, next_position ) | |
ant.went_places << @graph.edge( current_position, next_position ) | |
ant.went_nodes << next_position | |
current_position = next_position | |
node_probability_hash = calculate_probabilities( current_position ) | |
end | |
return Graph.new edges | |
end | |
# Считаем вероятности для каждой возможной вершины | |
def calculate_probabilities( current_position ) | |
probabilities = {} | |
next_possible_positions = @graph.where_can_go_from( current_position ) | |
return {} if next_possible_positions.empty? | |
denominator = ant_sum( current_position, next_possible_positions ) # Знаменатель по-русски | |
next_possible_positions.each do |node| | |
edge = @graph.edge( current_position, node ) | |
probabilities[node] = ( ( edge.intensity**@alpha + 1.0/( edge.weight**@beta ) ) / denominator ) | |
end | |
return probabilities | |
end | |
def select_next_position( node_probability_hash ) | |
random_value = rand | |
if random_value.between?(0.4, 1.0) | |
return node_probability_hash.max_by{ |k, v| v}.first | |
elsif random_value.between?(0.2, 0.39) | |
return node_probability_hash.sort_by{ |k, v| v}[node_probability_hash.count-2].flatten.first | |
else | |
return node_probability_hash.keys.sample | |
end | |
end | |
def ant_sum( position, nodes ) | |
sum = 0 | |
nodes.each do |node| | |
edge = @graph.edge( position, node ) | |
sum += edge.intensity**@alpha + 1.0 / ( edge.weight**@beta ) | |
end | |
return sum | |
end | |
end | |
class Application | |
def self.run | |
example1 | |
ant_algorithm = AntAlgorithm.new( @graph, 560, @ants ) | |
ant_algorithm.run_algorithm | |
# gets | |
# example2 | |
# ant_algorithm = AntAlgorithm.new( @graph, 1560, @ants ) | |
# ant_algorithm.run_algorithm | |
end | |
def self.example1 | |
@ants = [Ant.new,Ant.new,Ant.new,Ant.new,Ant.new,Ant.new,Ant.new] | |
@nodes = [ Node.new("1"), Node.new("2"), Node.new("3"), Node.new("4"), Node.new("5")] | |
@edges = [Edge.new( @nodes[0], @nodes[1], 5 ), | |
Edge.new( @nodes[0], @nodes[2], 7 ), | |
Edge.new( @nodes[0], @nodes[3], 4 ), | |
Edge.new( @nodes[1], @nodes[2], 6 ), | |
Edge.new( @nodes[2], @nodes[3], 10 ), | |
Edge.new( @nodes[2], @nodes[4], 2 ), | |
Edge.new( @nodes[3], @nodes[4], 3 ) ] | |
@graph = Graph.new( @edges, :bidirectional => true ) | |
end | |
def self.example2 | |
@ants = [Ant.new,Ant.new,Ant.new,Ant.new,Ant.new,Ant.new,Ant.new] | |
@nodes = [ Node.new("1"), Node.new("2"), Node.new("3"), Node.new("4"), Node.new("5")] | |
@edges = [Edge.new( @nodes[0], @nodes[1], 13 ), | |
Edge.new( @nodes[0], @nodes[2], 17 ), | |
Edge.new( @nodes[0], @nodes[3], 11 ), | |
Edge.new( @nodes[0], @nodes[4], 12 ), | |
Edge.new( @nodes[1], @nodes[2], 16 ), | |
Edge.new( @nodes[1], @nodes[3], 10 ), | |
Edge.new( @nodes[1], @nodes[4], 17 ), | |
Edge.new( @nodes[2], @nodes[3], 12 ), | |
Edge.new( @nodes[2], @nodes[4], 21 ), | |
Edge.new( @nodes[3], @nodes[4], 13 ) ] | |
@graph = Graph.new( @edges, :bidirectional => true ) | |
p @graph.all_reaches_nodes | |
end | |
end | |
#Application.run |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Yay Ruby!!