Class: Algorithms::SimulatedAnnealing

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithms/simulated_annealing.rb

Defined Under Namespace

Modules: Support

Constant Summary collapse

@@zeros = 
[0.0] * 8

Instance Method Summary collapse

Constructor Details

#initialize(opts) ⇒ SimulatedAnnealing

Example:

obj = MySimulatedAnnealingObject.new

SimulatedAnnealing.new(
  :support             => obj,
  :global_thresold     => 200,
  :step_multiplicator  => 0.63,
  :initial_temperature => 10,
  :initial_cost        => obj.cost,
  :iteration_modulus   => 500,      # display status once a 500
  :step_modulus        => 5000      # change the temperature once a 5000
)



26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/algorithms/simulated_annealing.rb', line 26

def initialize ( opts )
  @support = opts[:support]
  @global_thresold = opts[:global_thresold]
  @step_multiplicator = opts[:step_multiplicator]
  @temperature = opts[:initial_temperature]
  @cur_cost = opts[:initial_cost]
  @output = opts[:output] || STDOUT
  @iteration_modulus = opts[:iteration_modulus] || 1
  @step_modulus = opts[:step_modulus] || 1
  @generator = opts[:generator]
  @progression = ' '
  @diff_cost = 0
  @iteration = 0
  @probability_threshold = 0
end

Instance Method Details

#choose_probability(generator = nil) ⇒ Object 



123
124
125
 
# File 'lib/algorithms/simulated_annealing.rb', line 123

def choose_probability ( generator=nil )
  1.0.choose(generator)
end

#disp(output = @output) ⇒ Object 



96
97
98
99
100
101
102
103
104
 
# File 'lib/algorithms/simulated_annealing.rb', line 96

def disp ( output=@output )
  args = [ @up, @same, @down, @reject, @temperature,
           @proba_mean / @proba_mean_count,
           @threshold_mean / @threshold_mean_count, @cur_cost ]
  fmt = '- { "+%-5d|=%-5d|-%-5d|x%-5d", temp: %-4f, ' +
            'prob: %-7f, thres: %-7f, cost: %-5s }'
  output.puts fmt % args
  reset
end

#progression(x) ⇒ Object 



117
118
119
120
 
# File 'lib/algorithms/simulated_annealing.rb', line 117

def progression ( x )
  @progression = x
  disp if (@iteration % @iteration_modulus).zero?
end

#reset ⇒ Object 



44
45
46
47
 
# File 'lib/algorithms/simulated_annealing.rb', line 44

def reset
  @up, @down, @same, @reject, @proba_mean, @proba_mean_count,
  @threshold_mean, @threshold_mean_count = @@zeros
end

#run ⇒ Object 



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/algorithms/simulated_annealing.rb', line 50

def run
  reset
  @output.puts '---'
  while @cur_cost > @global_thresold
    # puts "Iteration(#{it}) #{@cur_cost}"
    @transition = @support.choose_transition(@generator)
    @diff_cost = @support.transition_cost(@cur_cost, @transition)

    @iteration += 1
    if (@iteration % @step_modulus).zero?
      @temperature *= @step_multiplicator
    end

    if @diff_cost > 0
      @probability_threshold = Math.exp(- @diff_cost.to_f / @temperature)
      @proba = choose_probability(@generator)
      @proba_mean += @proba
      @proba_mean_count += 1
      @threshold_mean += @probability_threshold
      @threshold_mean_count += 1
      if @proba < @probability_threshold
        progression '+'
        @up += 1
      else
        progression ' '
        @reject += 1
        next
      end
    else
      @probability_threshold = 1
      @proba = 1
      if @diff_cost.zero?
        @same += 1
        progression '='
      else
        @down += 1
        progression '-'
      end
    end

    @support.apply_transition(@transition)
    @cur_cost += @diff_cost
  end
end

#summary ⇒ Object 



107
108
109
110
111
112
113
114
 
# File 'lib/algorithms/simulated_annealing.rb', line 107

def summary
  @output.puts %Q[
    |---
    |Found a mininum: #@cur_cost
    |Temperature at the end: #@temperature
    |Nb iterations: #@iteration
  ].head_cut!
end