Tabu SearchTabu Search, TS, Taboo Search. TaxonomyTabu Search is a Global Optimization algorithm and a Metaheuristic or Metastrategy 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. StrategyThe 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 intermediateterm memory structures may be introduced to bias moves toward promising areas of the search space, as well as longerterm memory structures that promote a general diversity in the search across the search space. ProcedureAlgorithm (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}$)Heuristics
Code ListingListing (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 2opt Local Search procedure. The stochastic 2opt procedure is used as the embedded hill climbing heuristic with a fixed sized candidate list. The two edges that are deleted in each 2opt 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.size1) ? 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.sizei) + 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.size1 : c11) exclude << ((c1==perm.size1) ? 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[c11], parent[c1]], [parent[c21], parent[c2]]] end def is_tabu?(permutation, tabu_list) permutation.each_with_index do c1, i c2 = (i==permutation.size1) ? 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 Download: tabu_search.rb.
ReferencesPrimary SourcesTabu 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 twopart journal article, the first part of which introduced the algorithm and reviewed thenrecent applications [Glover1989], and the second which focused on advanced topics and open areas of research [Glover1990]. Learn MoreGlover provides a highlevel 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 indepth 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 
Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...

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

Do you like Clever Algorithms? Buy the book now. 