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 Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(opts) ⇒ SimulatedAnnealing

Example:

obj = MySimulatedAnnealingObject.new

SimulatedAnnealing.new(
  :support             => obj,
  :global_threshold    => 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
)



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/algorithms/simulated_annealing.rb', line 33

def initialize ( opts )
  @support = opts[:support]
  @global_threshold = opts[:global_threshold] ||
     opts[:global_thresold] # :) backward compatibility
  @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]
  @iteration_max = opts[:iteration_max] || (1.0 / 0.0) # Infinity
  @progression = ' '
  @diff_cost = 0
  @iteration = 0
  @probability_threshold = 0
  @argmin = @support.copy_of_the_current_solution
  @min = @cur_cost
end

Instance Attribute Details

#argmin ⇒ Object (readonly) Also known as: best

Returns the value of attribute argmin.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def argmin
  @argmin
end

#diff_cost ⇒ Object (readonly)

Returns the value of attribute diff_cost.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def diff_cost
  @diff_cost
end

#generator ⇒ Object (readonly)

Returns the value of attribute generator.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def generator
  @generator
end

#global_threshold ⇒ Object (readonly)

Returns the value of attribute global_threshold.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def global_threshold
  @global_threshold
end

#initial_cost ⇒ Object (readonly)

Returns the value of attribute initial_cost.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def initial_cost
  @initial_cost
end

#initial_temperature ⇒ Object (readonly)

Returns the value of attribute initial_temperature.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def initial_temperature
  @initial_temperature
end

#iteration ⇒ Object (readonly)

Returns the value of attribute iteration.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def iteration
  @iteration
end

#iteration_max ⇒ Object (readonly)

Returns the value of attribute iteration_max.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def iteration_max
  @iteration_max
end

#iteration_modulus ⇒ Object (readonly)

Returns the value of attribute iteration_modulus.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def iteration_modulus
  @iteration_modulus
end

#output ⇒ Object (readonly)

Returns the value of attribute output.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def output
  @output
end

#probability_threshold ⇒ Object (readonly)

Returns the value of attribute probability_threshold.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def probability_threshold
  @probability_threshold
end

#step_modulus ⇒ Object (readonly)

Returns the value of attribute step_modulus.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def step_modulus
  @step_modulus
end

#step_multiplicator ⇒ Object (readonly)

Returns the value of attribute step_multiplicator.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def step_multiplicator
  @step_multiplicator
end

#support ⇒ Object (readonly)

Returns the value of attribute support.



12
13
14
 
# File 'lib/algorithms/simulated_annealing.rb', line 12

def support
  @support
end

Instance Method Details

#choose_probability(generator = nil) ⇒ Object 



138
139
140
 
# File 'lib/algorithms/simulated_annealing.rb', line 138

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

#disp(output = @output) ⇒ Object 



111
112
113
114
115
116
117
118
119
 
# File 'lib/algorithms/simulated_annealing.rb', line 111

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 



132
133
134
135
 
# File 'lib/algorithms/simulated_annealing.rb', line 132

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

#reset ⇒ Object 



55
56
57
58
 
# File 'lib/algorithms/simulated_annealing.rb', line 55

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

#run ⇒ Object 



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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/algorithms/simulated_annealing.rb', line 61

def run
  reset
  @output.puts '---'
  while @cur_cost > @global_threshold and @iteration < @iteration_max
    # 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
    if @cur_cost < @min
      @min = @cur_cost
      @argmin = @support.copy_of_the_current_solution
    end
  end
end

#summary ⇒ Object 



122
123
124
125
126
127
128
129
 
# File 'lib/algorithms/simulated_annealing.rb', line 122

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