# Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

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.

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

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}$
End
End
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}$
End
Else
VisitedSolutions $\leftarrow$ $S_{curr}$
$Scurr_{t}$ $\leftarrow$ $Iteration_{i}$
End
If ($Iteration_{i}$ – $ProhibitionPeriod_{t}$ > $RepetitionInterval_{avg}$)
ProhibitionPeriod $\leftarrow$ Max(1, ProhibitionPeriod $\times$ Decrease)
$ProhibitionPeriod_{t}$ $\leftarrow$ $Iteration_{i}$
End
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}$
End
$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}$
End
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
End
Return (Tabu)
Pseudocode for the IsTabu 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)
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
end
end
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]}
prohib_period = cities.size-2
last_change = iter
end
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

Reactive Tabu Search in Ruby

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

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

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

### Free Course

Get one algorithm per week...
• ...described in detail
Sign-up Now

### Own A Copy

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

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

Do you like Clever Algorithms?