A generic module for performing simulated annealing optimizations

simulated_annealing.rb

# Include this in a class and define your own #variation method that
# makes returns a new instance that might be better.
#
# Use #add_annealing_constraint to add constraints
module SimulatedAnnealing
  def self.included(base) base.extend(ClassMethods) end

  module ClassMethods
    def annealing_constraints
      @annealing_constraints  ||= {}
    end
    def annealing_constraint_descriptions
      @annealing_constraint_descriptions ||= {}
    end
    def annealing_constraint_default_weights
      @annealing_constraint_default_weights ||= Hash.new(1)
    end
    def add_annealing_constraint( key, default_weight=nil, description=nil, &calculator )
      annealing_constraints[key] = calculator
      annealing_constraint_default_weights[key] = default_weight || 1
      annealing_constraint_descriptions[key] = description
    end    
    attr_reader :annealing_preconstraint
    def add_annealing_preconstraint( &lambda )
      @annealing_preconstraint = lambda
    end
  end

  def initialize( *args )
    use_default_annealing_constraint_weights
  end

  def use_default_annealing_constraint_weights
    @annealing_constraint_weights = self.class.annealing_constraint_default_weights.dup
  end
  
  # Set the weights for all constraints to 0
  def use_no_annealing_constraints
    @annealing_constraint_weights.each{ |key,_| @annealing_constraint_weights[key] = 0 }
  end
  
  def use_annealing_constraint_weights( constraint_weights=Hash.new(0) )
    use_no_annealing_constraints
    @annealing_constraint_weights.merge( constraint_weights )
  end
  
  attr_reader :annealing_constraint_weights
  
  attr_reader :anneal_best, :anneal_best_cost
  attr_accessor :anneal_state, :anneal_cost
  attr_accessor :anneal_max_temp, :anneal_max_passes, :anneal_good_enough
  attr_reader :anneal_percent_done, :anneal_pass, :anneal_temp
  def anneal( attribute, max_passes=50_000, max_temp=500, good_enough=0 )
    @anneal_attribute   = :"@#{attribute}"
    @anneal_state       = instance_variable_get( @anneal_attribute )
    @anneal_cost        = annealing_cost( @anneal_state )
    @anneal_max_passes  = max_passes
    @anneal_max_temp    = max_temp
    @anneal_good_enough = good_enough
    if !@anneal_best_cost || @anneal_best_cost > @anneal_cost
      @anneal_best      = @anneal_state
      @anneal_best_cost = @anneal_cost
    end
    simulate_annealing
  end
  
  def simulate_annealing
    @anneal_max_passes.times do |pass|
      @anneal_pass      = pass
      @anneal_test      = variation( @anneal_state )
      @anneal_test_cost = annealing_cost( @anneal_test )
      if @anneal_test_cost < @anneal_best_cost
        @anneal_best      = @anneal_test
        @anneal_best_cost = @anneal_test_cost
        break if @anneal_best_cost < @anneal_good_enough
      end
      @anneal_percent_done = (pass+1.0) / @anneal_max_passes 
      @anneal_temp = temperature( @anneal_percent_done, @anneal_max_temp )
      chance       = probability( @anneal_cost, @anneal_test_cost, @anneal_temp, @anneal_max_temp )
      if rand < chance
        @anneal_state = @anneal_test
        @anneal_cost  = @anneal_test_cost
      end
    end
    instance_variable_set( @anneal_attribute, @anneal_best )
  end
  
  def annealing_cost( state )
    if cost = state.instance_variable_get( :@annealing_cost )
      cost
    else
      cost  = 0
      stats = {}
      self.class.annealing_preconstraint[state,self] if self.class.annealing_preconstraint
      weights = self.annealing_constraint_weights
      self.class.annealing_constraints.each do |key,calculator|
        if weights[key] != 0
          piece = calculator[state,self]
          cost += piece * weights[key]
          stats[key] = piece
        else
          stats[key] = nil
        end
      end
      state.instance_variable_set( :@annealing_stats, stats )
      state.instance_variable_set( :@annealing_cost,  cost  )
    end
  end
  
  def annealing_stats( state )
    state.instance_variable_get( :@annealing_stats ) || (annealing_cost && state.instance_variable_get( :@annealing_stats ))
  end
  
  # Simple linear interpolation from max_temp to 0; override in your own class for a better function
  def temperature( percent_done, max_temp )
    max_temp - max_temp * percent_done
  end
  
  def probability( current_cost, test_cost, current_temp, max_temp )
    test_cost <= current_cost ? 1.0 : Math.exp( (current_cost - test_cost) / current_temp )
  end
end