Class: Algorithm::LocalSearch::TabuSearch

Inherits:
Object
  • Object
show all
Defined in:
lib/opt_alg_framework/algorithm/local_search/tabu_search.rb

Instance Method Summary collapse

Constructor Details

#initialize(params) ⇒ TabuSearch

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.



8
9
10
11
12
13
14
15
 
# File 'lib/opt_alg_framework/algorithm/local_search/tabu_search.rb', line 8

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

Instance Method Details

#encapsulate_solution(solution) ⇒ Object

A solution is a hash, with the keys :solution and :fitness.



39
40
41
42
43
44
 
# File 'lib/opt_alg_framework/algorithm/local_search/tabu_search.rb', line 39

def encapsulate_solution(solution)
  hash = Hash.new
  hash[:solution] = solution
  hash[:fitness] = @problem.fitness(tasks_sequence: solution)
  hash
end

#start ⇒ Object

Main method.



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/opt_alg_framework/algorithm/local_search/tabu_search.rb', line 18

def start
  s = encapsulate_solution(@problem.default_solution.dup)
  best = s.dup
  @tabu_list << s[:solution]
  @iterations.times do
    @tabu_list.shift if @tabu_list.size == @list_max_size
    r = encapsulate_solution(@tweak_operator.tweak(s[:solution]))
    (@tweak_number - 1).times do
      w = encapsulate_solution(@tweak_operator.tweak(s[:solution]))
      r = w.dup if !@tabu_list.include?(w) && w[:fitness] < r[:fitness] || @tabu_list.include?(r[:solution])
    end
    if !@tabu_list.include?(r[:solution])
      s = r.dup
      @tabu_list << r
    end
    best = s.dup if s[:fitness] < best[:fitness]
  end
  best
end