Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

Home | Read Online

This is the ad-supported version of the book. Buy it now if you like it.

Reactive Tabu Search

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


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.


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.


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.

Input: $Iteration_{max}$, Increase, Decrease, ProblemSize
Output: $S_{best}$
$S_{curr}$ $\leftarrow$ ConstructInitialSolution()
$S_{best}$ $\leftarrow$ $S_{curr}$
TabuList $\leftarrow \emptyset$
ProhibitionPeriod $\leftarrow$ 1
For ($Iteration_{i}$ $\in$ $Iteration_{max}$)
    MemoryBasedReaction(Increase, Decrease, ProblemSize)
    CandidateList $\leftarrow$ GenerateCandidateNeighborhood($S_{curr}$)
    $S_{curr}$ $\leftarrow$ BestMove(CandidateList)
    TabuList $\leftarrow$ $Scurr_{feature}$
    If (Cost($S_{curr}$) $\leq$ Cost($S_{best}$))
        $S_{best}$ $\leftarrow$ $S_{curr}$
Return ($S_{best}$)
Pseudocode for Reactive Tabu Search.
Input: Increase, Decrease, ProblemSize
If (HaveVisitedSolutionBefore($S_{curr}$, VisitedSolutions))
    $Scurr_{t}$ $\leftarrow$ RetrieveLastTimeVisited(VisitedSolutions, $S_{curr}$)
    RepetitionInterval $\leftarrow$ $Iteration_{i}$ – $Scurr_{t}$
    $Scurr_{t}$ $\leftarrow$ $Iteration_{i}$
    If (RepetitionInterval < 2 $\times$ ProblemSize)
        $RepetitionInterval_{avg}$ $\leftarrow$ 0.1 $\times$ RepetitionInterval + 0.9 $\times$ $RepetitionInterval_{avg}$
        ProhibitionPeriod $\leftarrow$ ProhibitionPeriod $\times$ Increase
        $ProhibitionPeriod_{t}$ $\leftarrow$ $Iteration_{i}$
    VisitedSolutions $\leftarrow$ $S_{curr}$
    $Scurr_{t}$ $\leftarrow$ $Iteration_{i}$
If ($Iteration_{i}$ – $ProhibitionPeriod_{t}$ > $RepetitionInterval_{avg}$)
    ProhibitionPeriod $\leftarrow$ Max(1, ProhibitionPeriod $\times$ Decrease)
    $ProhibitionPeriod_{t}$ $\leftarrow$ $Iteration_{i}$
Pseudocode for the MemoryBasedReaction function.
Input: ProblemSize
Output: $S_{curr}$
$CandidateList_{admissible}$ $\leftarrow$ GetAdmissibleMoves(CandidateList)
$CandidateList_{tabu}$ $\leftarrow$ CandidateList – $CandidateList_{admissible}$
If (Size($CandidateList_{admissible}$) < 2)
    ProhibitionPeriod $\leftarrow$ ProblemSize – 2
    $ProhibitionPeriod_{t}$ $\leftarrow$ $Iteration_{i}$
$S_{curr}$ $\leftarrow$ GetBest($CandidateList_{admissible}$)
$Sbest_{tabu}$ $\leftarrow$ GetBest($CandidateList_{tabu}$)
If (Cost($Sbest_{tabu}$) < Cost($S_{best}$) $\wedge$ Cost($Sbest_{tabu}$) < Cost($S_{curr}$) )
    $S_{curr}$ $\leftarrow$ $Sbest_{tabu}$
Return ($S_{curr}$)
Pseudocode for the BestMove function.
Output: Tabu
Tabu $\leftarrow$ False
$Scurr_{feature}^{t}$ $\leftarrow$ RetrieveTimeFeatureLastUsed($Scurr_{feature}$)
If ($Scurr_{feature}^{t}$ $\geq$ $Iteration_{curr}$ – ProhibitionPeriod)
    Tabu $\leftarrow$ True
Return (Tabu)
Pseudocode for the IsTabu function.


  • 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

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])
  return distance

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

def stochastic_two_opt(parent)
  perm =
  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]]]

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
  return false

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

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]
  return list

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

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

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

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

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
      admissable << a
  return [tabu, admissable]

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
      store_permutation(visited_list, current[:vector], iter)
    if iter-last_change > avg_size
      prohib_period = [prohib_period*decrease,1].max
      last_change = iter
    candidates = do |i|
      generate_candidate(current, cities)
    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
    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
    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]}"
  return best

if __FILE__ == $0
  # problem configuration
  berlin52 = [[565,575],[25,185],[345,750],[945,685],[845,655],
  # 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}"
Reactive Tabu Search in Ruby


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].


[Battiti1992] R. Battiti and G. Tecchiolli, "Parallel Biased Search for Combinatorial Optimization: genetic algorithms and TABU", Microprocessors and Microsystems, 1992.
[Battiti1994] R. Battiti and G. Tecchiolli, "The reactive tabu search", ORSA Journal on Computing, 1994.
[Battiti1994a] R. Battiti and G. Tecchiolli, "Simulated annealing and tabu search in the long run: a comparison on qap tasks", Computer and Mathematics with Applications, 1994.
[Battiti1995] R. Battiti and M. Protasi, "Reactive local search for the Maximum Clique problem", Technical Report TR-95-052, International Computer Science Institute, Berkeley, CA, 1995.
[Battiti1995a] R. Battiti and G. Tecchiolli, "Local search with memory: Benchmarking RTS", Operations Research Spektrum, 1995.
[Battiti1995b] R. Battiti and G. Tecchiolli, "Training neural nets with the reactive tabu search", IEEE Transactions on Neural Networks, 1995.
[Battiti1996] R. Battiti, "Machine learning methods for parameter tuning in heuristics", in 5th DIMACS Challenge Workshop: Experimental Methodology Day, 1996.
[Battiti2001] R. Battiti and M. Protasi, "Reactive local search for the Maximum Clique problem", Algorithmica, 2001.
[Battiti2008] R. Battiti and M. Brunato and F. Mascia, "Reactive Search and Intelligent Optimization", Springer, 2008.
[Battiti2009] R. Battiti and M. Brunato, "Reactive Search Optimization: Learning while Optimizing", in Handbook of Metaheuristics, Springer Verlag, 2009.
Clever Algorithms: Nature-Inspired Programming Recipes

Free Course

Get one algorithm per week...
  • ...delivered to your inbox
  • ...described in detail
  • read at your own pace
Sign-up Now

Own A Copy

This 438-page ebook has...
  • ...45 algorithm descriptions
  • practice usage
  • ...pseudo code
  • ...Ruby code
  • ...primary sources
Buy Now

Please Note: This content was automatically generated from the book content and may contain minor differences.

Clever Algorithms: Nature-Inspired Programming Recipes

Do you like Clever Algorithms?
Buy the book now.

© Copyright 2015. All Rights Reserved. | About | Contact | Privacy