Clever Algorithms

Home | About Us | Contact Us | Privacy

Books: Nature Inspired | Machine Learning | Further Reading




Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD.

Tabu Search

Tabu Search, TS, Taboo Search.

Taxonomy

Tabu Search is a Global Optimization algorithm and a Metaheuristic or Meta-strategy for controlling an embedded heuristic technique. Tabu Search is a parent for a large family of derivative approaches that introduce memory structures in Metaheuristics, such as Reactive Tabu Search and Parallel Tabu Search.

Strategy

The objective for the Tabu Search algorithm is to constrain an embedded heuristic from returning to recently visited areas of the search space, referred to as cycling. The strategy of the approach is to maintain a short term memory of the specific changes of recent moves within the search space and preventing future moves from undoing those changes. Additional intermediate-term memory structures may be introduced to bias moves toward promising areas of the search space, as well as longer-term memory structures that promote a general diversity in the search across the search space.

Procedure

Algorithm (below) provides a pseudocode listing of the Tabu Search algorithm for minimizing a cost function. The listing shows the simple Tabu Search algorithm with short term memory, without intermediate and long term memory management.

Input: $TabuList_{size}$
Output: $S_{best}$
$S_{best}$ $\leftarrow$ ConstructInitialSolution()
TabuList $\leftarrow \emptyset$
While ($\neg$ StopCondition())
    CandidateList $\leftarrow \emptyset$
    For ($S_{candidate}$ $\in$ $Sbest_{neighborhood}$)
        If ($\neg$ ContainsAnyFeatures($S_{candidate}$, TabuList))
            CandidateList $\leftarrow$ $S_{candidate}$
        End
    End
    $S_{candidate}$ $\leftarrow$ LocateBestCandidate(CandidateList)
    If (Cost($S_{candidate}$) $\leq$ Cost($S_{best}$))
        $S_{best}$ $\leftarrow$ $S_{candidate}$
        TabuList $\leftarrow$ FeatureDifferences($S_{candidate}$, $S_{best}$)
        While (TabuList > $TabuList_{size}$)
            DeleteFeature(TabuList)
        End
    End
End
Return ($S_{best}$)
Pseudocode for Tabu Search.

Heuristics

  • Tabu search was designed to manage an embedded hill climbing heuristic, although may be adapted to manage any neighborhood exploration heuristic.
  • Tabu search was designed for, and has predominately been applied to discrete domains such as combinatorial optimization problems.
  • Candidates for neighboring moves can be generated deterministically for the entire neighborhood or the neighborhood can be stochastically sampled to a fixed size, trading off efficiency for accuracy.
  • Intermediate-term memory structures can be introduced (complementing the short-term memory) to focus the search on promising areas of the search space (intensification), called aspiration criteria.
  • Long-term memory structures can be introduced (complementing the short-term memory) to encourage useful exploration of the broader search space, called diversification. Strategies may include generating solutions with rarely used components and biasing the generation away from the most commonly used solution components.

Code Listing

Listing (below) provides an example of the 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 Berli52 instance is 7542 units.

The algorithm is an implementation of the simple Tabu Search with a short term memory structure that executes for a fixed number of iterations. The starting point for the search is prepared using a random permutation that is refined using a stochastic 2-opt Local Search procedure. The stochastic 2-opt procedure is used as the embedded hill climbing heuristic with a fixed sized candidate list. The two edges that are deleted in each 2-opt move are stored on the tabu list. This general approach is similar to that used by Knox in his work on Tabu Search for symmetrical TSP [Knox1994] and Fiechter for the Parallel Tabu Search for the TSP [Fiechter1994].

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?(permutation, tabu_list)
  permutation.each_with_index do |c1, i|
    c2 = (i==permutation.size-1) ? permutation[0] : permutation[i+1]
    tabu_list.each do |forbidden_edge|
      return true if forbidden_edge == [c1, c2]
    end
  end
  return false
end

def generate_candidate(best, tabu_list, cities)
  perm, edges = nil, nil
  begin
    perm, edges = stochastic_two_opt(best[:vector])
  end while is_tabu?(perm, tabu_list)
  candidate = {:vector=>perm}
  candidate[:cost] = cost(candidate[:vector], cities)
  return candidate, edges
end

def search(cities, tabu_list_size, candidate_list_size, max_iter)
  current = {:vector=>random_permutation(cities)}
  current[:cost] = cost(current[:vector], cities)
  best = current
  tabu_list = Array.new(tabu_list_size)
  max_iter.times do |iter|
    candidates = Array.new(candidate_list_size) do |i|
      generate_candidate(current, tabu_list, cities)
    end
    candidates.sort! {|x,y| x.first[:cost] <=> y.first[:cost]}
    best_candidate = candidates.first[0]
    best_candidate_edges = candidates.first[1]
    if best_candidate[:cost] < current[:cost]
      current = best_candidate
      best = best_candidate if best_candidate[:cost] < best[:cost]
      best_candidate_edges.each {|edge| tabu_list.push(edge)}
      tabu_list.pop while tabu_list.size > tabu_list_size
    end
    puts " > iteration #{(iter+1)}, 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
  tabu_list_size = 15
  max_candidates = 50
  # execute the algorithm
  best = search(berlin52, tabu_list_size, max_candidates, max_iter)
  puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}"
end
Tabu Search in Ruby
Download: tabu_search.rb. Unit test available in the github project

References

Primary Sources

Tabu Search was introduced by Glover applied to scheduling employees to duty rosters [Glover1986a] and a more general overview in the context of the TSP [Glover1986], based on his previous work on surrogate constraints on integer programming problems [Glover1977]. Glover provided a seminal overview of the algorithm in a two-part journal article, the first part of which introduced the algorithm and reviewed then-recent applications [Glover1989], and the second which focused on advanced topics and open areas of research [Glover1990].

Learn More

Glover provides a high-level introduction to Tabu Search in the form of a practical tutorial [Glover1990a], as does Glover and Taillard in a user guide format [Glover1993]. The best source of information for Tabu Search is the book dedicated to the approach by Glover and Laguna that covers the principles of the technique in detail as well as an in-depth review of applications [Glover1998]. The approach appeared in Science, that considered a modification for its application to continuous function optimization problems [Cvijovic1995]. Finally, Gendreau provides an excellent contemporary review of the algorithm, highlighting best practices and application heuristics collected from across the field of study [Gendreau2003].

Bibliography

[Cvijovic1995] D. Cvijovic and J. Klinowski, "Taboo Search: An Approach to the Multiple Minima Problem", Science, 1995.
[Fiechter1994] C–N. Fiechter, "A parallel tabu search algorithm for large traveling salesman problems", Discrete Applied Mathematics, 1994.
[Gendreau2003] M. Gendreau, "2: An Introduction to Tabu Search", in Handbook of Metaheuristics, pages 37–54, Springer, 2003.
[Glover1977] F. Glover, "Heuristics for integer programming using surrogate constraints", Decision Sciences, 1977.
[Glover1986] F. Glover, "Future paths for integer programming and links to artificial intelligence", Computers and Operations Research, 1986.
[Glover1986a] F. Glover and C. McMillan, "The general employee scheduling problem: an integration of MS and AI", Computers and Operations Research, 1986.
[Glover1989] F. Glover, "Tabu Search – Part I", ORSA Journal on Computing, 1989.
[Glover1990] F. Glover, "Tabu Search – Part II", ORSA Journal on Computing, 1990.
[Glover1990a] F. Glover, "Tabu Search: A Tutorial", Interfaces, 1990.
[Glover1993] F. Glover and E. Taillard, "A user's guide to tabu search", Annals of Operations Research, 1993.
[Glover1998] F. W. Glover and M. Laguna, "Tabu Search", Springer, 1998.
[Knox1994] J. Knox, "Tabu search performance on the symmetric traveling salesman problem", Computers & Operations Research, 1994.
Clever Algorithms: Nature-Inspired Programming Recipes

Paperback

Lulu
Amazon.com
Barnes & Noble


PDF

Download


Contribute

Fork on github.com


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



© Copyright 2013. All Rights Reserved.