Tabu Search - Pseudo-code

Pseudo-code

The following pseudocode, adapted from, presents the tabu search algorithm as described above. This implementation has the required short-term memory, but contains no intermediate or long-term memory structures.

1: s ← s0
2: sBest ← s
3: tabuList ← null
4: while (not stoppingCondition)
5: candidateList ← null
6: for(sCandidate in sNeighborhood)
7: if(not containsTabuElements(sCandidate, tabuList))
8: candidateList ← candidateList + sCandidate
9: end
10: end
11: sCandidate ← LocateBestCandidate(candidateList)
12: if(fitness(sCandidate) > fitness(sBest))
13: tabuList ← featureDifferences(sCandidate, sBest)
14: sBest ← sCandidate
15: while(size(tabuList) > maxTabuListSize)
16: ExpireFeatures(tabuList)
17: end
18: end
19: end
20: return(sBest)

Lines 1-3 represent some initial setup, respectively creating an initial solution (possibly chosen at random), setting that initial solution as the best seen to date, and initializing an empty tabu list. In this example, the tabu list is simply a short term memory structure that will contain a record of the elements of the states visited.

The proper algorithm starts in line 4. This loop will continue searching for an optimal solution until a user-specified stopping condition is met (two examples of such conditions are a simple time limit or a threshold on the fitness score. In line 5, an empty candidate list is initialized. The neighboring solutions are checked for tabu elements in line 7. If the solution does not contain elements on the tabu list, it is added to the candidate list (line 8).

The best candidate on the candidate list is chosen in line 11 (generally, solutions are evaluated according to a provided mathematical function, which returns a fitness score). If that candidate has a higher fitness value than the current best (line 12), its features are added to the tabu list (line 13) and it is set as the new best (line 14). At this point, if the tabu list is full (line 15), some elements will be allowed to expire (line 16). Generally, elements expire from the list in the same order they are added.

This process continues until the user specified stopping criterion is met, at which point, the best solution seen during the search process is returned (line 20).