class Algorithm::LocalSearch::SimulatedAnnealing
Public Class Methods
new(params)
click to toggle source
Initialize specifying the cooling rate percentage (@cooling_rate), number of iterations in each temperature (@max_iterations) and passing an instantiated problem and tweak operator class.
# File lib/opt_alg_framework/algorithm/local_search/simulated_annealing.rb, line 9 def initialize(params) @cooling_rate = params[:cooling_rate] @problem = params[:problem] @tweak_operator = params[:tweak_operator] @max_iterations = params[:max_iterations] @temperature = initial_temperature end
Public Instance Methods
start()
click to toggle source
solution_b = best solution solution_n = neighbor solution solution_c = current solution
# File lib/opt_alg_framework/algorithm/local_search/simulated_annealing.rb, line 20 def start solution_b = encapsulate_solution(@problem.default_solution.shuffle) solution_c = solution_b.dup temperature = @temperature while temperature > 1 do iteration = 1 while iteration < @max_iterations do solution_n = encapsulate_solution(@tweak_operator.tweak(solution_c[:solution])) solution_c = solution_n.dup if accept?(solution_c[:fitness], solution_n[:fitness], temperature) solution_b = solution_c.dup if solution_c[:fitness] < solution_b[:fitness] iteration += 1 end temperature *= 1 - @cooling_rate end solution_b end
Private Instance Methods
accept?(fitness, neighbor_fitness, temperature)
click to toggle source
Calculate the acceptance probability, if and only if the neighbor fitness is worst than the current fitness.
# File lib/opt_alg_framework/algorithm/local_search/simulated_annealing.rb, line 61 def accept?(fitness, neighbor_fitness, temperature) return true if neighbor_fitness < fitness probability = E ** - ((fitness - neighbor_fitness).abs.fdiv(temperature)) # E is the Euller number r = Random.rand(0.0..1) if r < probability return true else false end end
encapsulate_solution(solution)
click to toggle source
A solution is a hash, with the keys :solution and :fitness.
# File lib/opt_alg_framework/algorithm/local_search/simulated_annealing.rb, line 52 def encapsulate_solution(solution) hash = Hash.new hash[:solution] = solution hash[:fitness] = @problem.fitness(solution) hash end
initial_temperature()
click to toggle source
Calculate the initial temperature, generating N neighbors of an initial solution and setting as initial temperature the neighbor with the worst fitness.
# File lib/opt_alg_framework/algorithm/local_search/simulated_annealing.rb, line 41 def initial_temperature solution = encapsulate_solution(@problem.default_solution.shuffle) max = solution @max_iterations.times do neighbor = encapsulate_solution(@tweak_operator.tweak(solution[:solution])) max = neighbor if neighbor[:fitness] > max[:fitness] end max[:fitness] end