class Algorithm::LocalSearch::TabuSearch

Public Class Methods

new(params) click to toggle source

Initialize specifying as parameters the tabu list size (@list_max_size), number of tweaks in each current solution (@tweak_number), number of iteratiions to perform in the algorithm (@iterations) and an instantiated problem and tweak operator class.

# File lib/opt_alg_framework/algorithm/local_search/tabu_search.rb, line 9
def initialize(params)
  @tabu_list = []
  @list_max_size = params[:list_max_size]
  @tweak_number = params[:tweak_number]
  @iterations = params[:iterations]
  @tweak_operator = params[:tweak_operator]
  @problem = params[:problem]
end

Public Instance Methods

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/tabu_search.rb, line 42
def encapsulate_solution(solution)
  hash = Hash.new
  hash[:solution] = solution
  hash[:fitness] = @problem.fitness(solution)
  hash
end
start() click to toggle source

Main method.

# File lib/opt_alg_framework/algorithm/local_search/tabu_search.rb, line 19
def start
  solution_c = encapsulate_solution(@problem.default_solution.dup)
  solution_s = solution_c.dup
  @tabu_list << solution_c[:solution]
  @iterations.times do
    @tabu_list.shift if @tabu_list.size == @list_max_size
    solution_bn = solution_n1 = encapsulate_solution(@tweak_operator.tweak(solution_c[:solution]))
    (@tweak_number - 1).times do
      solution_n2 = encapsulate_solution(@tweak_operator.tweak(solution_c[:solution]))
      solution_bn = solution_n2.dup if !@tabu_list.include?(solution_n2) &&
                    solution_n2[:fitness] < solution_n1[:fitness] ||
                    @tabu_list.include?(solution_n1[:solution])
    end
    if !@tabu_list.include?(solution_bn[:solution])
      solution_c = solution_bn.dup
      @tabu_list << solution_n1
    end
    solution_s = solution_c.dup if solution_c[:fitness] < solution_s[:fitness]
  end
  solution_s
end