Ant Colony Algorithm / Муравьиный алгоритм

graph_and_ant_colony.rb

# 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

Yay Ruby!!