class Annealer
Attributes
logger[RW]
Public Class Methods
new(opts = {})
click to toggle source
# File lib/annealer.rb, line 2 def initialize(opts = {}) max_iter = (opts[:max_iter] || 1000) @cooling_func = opts[:cooling_func] || lambda do |iter_count| Math.exp(-iter_count / (opts[:cooling_time] || max_iter * 1000)) end @transition_probability = opts[:transition_probability] || lambda do |e0, e1, temp| Math.exp((e0 - e1) / temp) end @stop_condition = opts[:stop_condition] || lambda do |iter_count, best_energy| iter_count > max_iter end @repetition_count = opts[:repetition_count] || 1 @logger = opts[:logger] || Class.new do def initialize(log_to) @log_to = log_to end def info(msg) @log_to.puts(msg) if @log_to end end.new(opts[:log_to]) @log_progress_frequency = opts[:log_progress_frequency] || 5000 end
Public Instance Methods
anneal(start_state)
click to toggle source
Given a (probably random) starting state, returns a state that approximately minimizes an arbitrary “energy” metric.
The given start_state must implement two methods:
- *energy*: Returns the metric you want to optimize. - *random_neighbor*: Returns a randomly selected new state which differs slightly from this one. This method _must not modify_ the original state, but instead return a clean copy. You must ensure that the entire state space you want to search is reachable by hopping from neighbor to neighbor. Ideally, the new state should be likely to have similar energy (i.e. "neighbors" should be small changes); at the same time, you don't want it to require too many hops between any two states.
# File lib/annealer.rb, line 48 def anneal(start_state) energy = start_state.energy best_state = start_state best_energy = energy logger.info "Starting state:" logger.info best_state.inspect @repetition_count.times do |rep| logger.info "Repetition #{rep}..." if @repetition_count > 1 state = best_state iter_count = 0 while !@stop_condition.call(iter_count, best_energy) temperature = @cooling_func.call(iter_count) new_state = state.random_neighbor new_energy = new_state.energy logger.info "Iteration #{iter_count} (energy = #{new_energy})..." if iter_count % @log_progress_frequency == 0 if best_state.nil? || @transition_probability.call(energy, new_energy, temperature) > rand state, energy = new_state, new_energy if new_energy < best_energy best_state, best_energy = state, energy logger.info "New best solution on rep #{rep}, iter #{iter_count} with energy #{energy}:" logger.info state.inspect end end iter_count += 1 end end best_state end
info(msg)
click to toggle source
# File lib/annealer.rb, line 24 def info(msg) @log_to.puts(msg) if @log_to end