Reactive Tabu Search

Reactive Tabu Search, RTS, R-TABU, Reactive Taboo Search.

Taxonomy

Reactive Tabu Search is a Metaheuristic and a Global Optimization algorithm. It is an extension of Tabu Search and the basis for a field of reactive techniques called Reactive Local Search and more broadly the field of Reactive Search Optimization.

Strategy

The objective of Tabu Search is to avoid cycles while applying a local search technique. The Reactive Tabu Search addresses this objective by explicitly monitoring the search and reacting to the occurrence of cycles and their repetition by adapting the tabu tenure (tabu list size). The strategy of the broader field of Reactive Search Optimization is to automate the process by which a practitioner configures a search procedure by monitoring its online behavior and to use machine learning techniques to adapt a techniques configuration.

Procedure

Algorithm (below) provides a pseudocode listing of the Reactive Tabu Search algorithm for minimizing a cost function. The Pseudocode is based on the version of the Reactive Tabu Search described by Battiti and Tecchiolli in [Battiti1995a] with supplements like the IsTabu function from [Battiti1994]. The procedure has been modified for brevity to exude the diversification procedure (escape move). Algorithm (below) describes the memory based reaction that manipulates the size of the ProhibitionPeriod in response to identified cycles in the ongoing search. Algorithm (below) describes the selection of the best move from a list of candidate moves in the neighborhood of a given solution. The function permits prohibited moves in the case where a prohibited move is better than the best know solution and the selected admissible move (called aspiration). Algorithm (below) determines whether a given neighborhood move is tabu based on the current ProhibitionPeriod, and is employed by sub-functions of the Algorithm (below) function.

Heuristics

• Reactive Tabu Search is an extension of Tabu Search and as such should exploit the best practices used for the parent algorithm.
• Reactive Tabu Search was designed for discrete domains such as combinatorial optimization, although has been applied to continuous function optimization.
• Reactive Tabu Search was proposed to use efficient memory data structures such as hash tables.
• Reactive Tabu Search was proposed to use an long-term memory to diversify the search after a threshold of cycle repetitions has been reached.
• The increase parameter should be greater than one (such as 1.1 or 1.3) and the decrease parameter should be less than one (such as 0.9 or 0.8).

Code Listing

Listing (below) provides an example of the Reactive Tabu Search algorithm implemented in the Ruby Programming Language. The algorithm is applied to the Berlin52 instance of the Traveling Salesman Problem (TSP), taken from the TSPLIB. The problem seeks a permutation of the order to visit cities (called a tour) that minimizes the total distance traveled. The optimal tour distance for Berlin52 instance is 7542 units.

The procedure is based on the code listing described by Battiti and Tecchiolli in [Battiti1995a] with supplements like the IsTabu function from [Battiti1994]. The implementation does not use efficient memory data structures such as hash tables. The algorithm is initialized with a stochastic 2-opt local search, and the neighborhood is generated as a fixed candidate list of stochastic 2-opt moves. The edges selected for changing in the 2-opt move are stored as features in the tabu list. The example does not implement the escape procedure for search diversification.

def euc_2d(c1, c2)
  Math.sqrt((c1[0] - c2[0])**2.0 + (c1[1] - c2[1])**2.0).round
end

def cost(perm, cities)
  distance = 0
  perm.each_with_index do |c1, i|
    c2 = (i==perm.size-1) ? perm[0] : perm[i+1]
    distance += euc_2d(cities[c1], cities[c2])
  end
  return distance
end

def random_permutation(cities)
  perm = Array.new(cities.size){|i| i}
  perm.each_index do |i|
    r = rand(perm.size-i) + i
    perm[r], perm[i] = perm[i], perm[r]
  end
  return perm
end

def stochastic_two_opt(parent)
  perm = Array.new(parent)
  c1, c2 = rand(perm.size), rand(perm.size)
  exclude = [c1]
  exclude << ((c1==0) ? perm.size-1 : c1-1)
  exclude << ((c1==perm.size-1) ? 0 : c1+1)
  c2 = rand(perm.size) while exclude.include?(c2)
  c1, c2 = c2, c1 if c2 < c1
  perm[c1...c2] = perm[c1...c2].reverse
  return perm, [[parent[c1-1], parent[c1]], [parent[c2-1], parent[c2]]]
end

def is_tabu?(edge, tabu_list, iter, prohib_period)
  tabu_list.each do |entry|
    if entry[:edge] == edge
      return true if entry[:iter] >= iter-prohib_period
      return false
    end
  end
  return false
end

def make_tabu(tabu_list, edge, iter)
  tabu_list.each do |entry|
    if entry[:edge] == edge
      entry[:iter] = iter
      return entry
    end
  end
  entry = {:edge=>edge, :iter=>iter}
  tabu_list.push(entry)
  return entry
end

def to_edge_list(perm)
  list = []
  perm.each_with_index do |c1, i|
    c2 = (i==perm.size-1) ? perm[0] : perm[i+1]
    c1, c2 = c2, c1 if c1 > c2
    list << [c1, c2]
  end
  return list
end

def equivalent?(el1, el2)
  el1.each {|e| return false if !el2.include?(e) }
  return true
end

def generate_candidate(best, cities)
  candidate = {}
  candidate[:vector], edges = stochastic_two_opt(best[:vector])
  candidate[:cost] = cost(candidate[:vector], cities)
  return candidate, edges
end

def get_candidate_entry(visited_list, permutation)
  edgeList = to_edge_list(permutation)
  visited_list.each do |entry|
    return entry if equivalent?(edgeList, entry[:edgelist])
  end
  return nil
end

def store_permutation(visited_list, permutation, iteration)
  entry = {}
  entry[:edgelist] = to_edge_list(permutation)
  entry[:iter] = iteration
  entry[:visits] = 1
  visited_list.push(entry)
  return entry
end

def sort_neighborhood(candidates, tabu_list, prohib_period, iteration)
  tabu, admissable = [], []
  candidates.each do |a|
    if is_tabu?(a[1][0], tabu_list, iteration, prohib_period) or
       is_tabu?(a[1][1], tabu_list, iteration, prohib_period)
      tabu << a
    else
      admissable << a
    end
  end
  return [tabu, admissable]
end

def search(cities, max_cand, max_iter, increase, decrease)
  current = {:vector=>random_permutation(cities)}
  current[:cost] = cost(current[:vector], cities)
  best = current
  tabu_list, prohib_period = [], 1
  visited_list, avg_size, last_change = [], 1, 0
  max_iter.times do |iter|
    candidate_entry = get_candidate_entry(visited_list, current[:vector])
    if !candidate_entry.nil?
      repetition_interval = iter - candidate_entry[:iter]
      candidate_entry[:iter] = iter
      candidate_entry[:visits] += 1
      if repetition_interval < 2*(cities.size-1)
        avg_size = 0.1*(iter-candidate_entry[:iter]) + 0.9*avg_size
        prohib_period = (prohib_period.to_f * increase)
        last_change = iter
      end
    else
      store_permutation(visited_list, current[:vector], iter)
    end
    if iter-last_change > avg_size
      prohib_period = [prohib_period*decrease,1].max
      last_change = iter
    end
    candidates = Array.new(max_cand) do |i|
      generate_candidate(current, cities)
    end
    candidates.sort! {|x,y| x.first[:cost] <=> y.first[:cost]}
    tabu,admis = sort_neighborhood(candidates,tabu_list,prohib_period,iter)
    if admis.size < 2
      prohib_period = cities.size-2
      last_change = iter
    end
    current,best_move_edges = (admis.empty?) ? tabu.first : admis.first
    if !tabu.empty?
      tf = tabu.first[0]
      if tf[:cost]<best[:cost] and tf[:cost]<current[:cost]
        current, best_move_edges = tabu.first
      end
    end
    best_move_edges.each {|edge| make_tabu(tabu_list, edge, iter)}
    best = candidates.first[0] if candidates.first[0][:cost] < best[:cost]
    puts " > it=#{iter}, tenure=#{prohib_period.round}, best=#{best[:cost]}"
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  berlin52 = [[565,575],[25,185],[345,750],[945,685],[845,655],
   [880,660],[25,230],[525,1000],[580,1175],[650,1130],[1605,620],
   [1220,580],[1465,200],[1530,5],[845,680],[725,370],[145,665],
   [415,635],[510,875],[560,365],[300,465],[520,585],[480,415],
   [835,625],[975,580],[1215,245],[1320,315],[1250,400],[660,180],
   [410,250],[420,555],[575,665],[1150,1160],[700,580],[685,595],
   [685,610],[770,610],[795,645],[720,635],[760,650],[475,960],
   [95,260],[875,920],[700,500],[555,815],[830,485],[1170,65],
   [830,610],[605,625],[595,360],[1340,725],[1740,245]]
  # algorithm configuration
  max_iter = 100
  max_candidates = 50
  increase = 1.3
  decrease = 0.9
  # execute the algorithm
  best = search(berlin52, max_candidates, max_iter, increase, decrease)
  puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}"
end

References

Primary Sources

Reactive Tabu Search was proposed by Battiti and Tecchiolli as an extension to Tabu Search that included an adaptive tabu list size in addition to a diversification mechanism [Battiti1994]. The technique also used efficient memory structures that were based on an earlier work by Battiti and Tecchiolli that considered a parallel tabu search [Battiti1992]. Some early application papers by Battiti and Tecchiolli include a comparison to Simulated Annealing applied to the Quadratic Assignment Problem [Battiti1994a], benchmarked on instances of the knapsack problem and N-K models and compared with Repeated Local Minima Search, Simulated Annealing, and Genetic Algorithms [Battiti1995a], and training neural networks on an array of problem instances [Battiti1995b].

Learn More

Reactive Tabu Search was abstracted to a form called Reactive Local Search that considers adaptive methods that learn suitable parameters for heuristics that manage an embedded local search technique [Battiti1995] [Battiti2001]. Under this abstraction, the Reactive Tabu Search algorithm is a single example of the Reactive Local Search principle applied to the Tabu Search. This framework was further extended to the use of any adaptive machine learning techniques to adapt the parameters of an algorithm by reacting to algorithm outcomes online while solving a problem, called Reactive Search [Battiti1996]. The best reference for this general framework is the book on Reactive Search Optimization by Battiti, Brunato, and Mascia [Battiti2008]. Additionally, the review chapter by Battiti and Brunato provides a contemporary description [Battiti2009].

Bibliography