Editing Tabu search (section)

== Pseudocode ==

The following [[pseudocode]] presents a simplified version of the tabu search algorithm as described above. This implementation has a rudimentary short-term memory, but contains no intermediate or long-term memory structures. The term "fitness" refers to an evaluation of the candidate solution, as embodied in an objective function for mathematical optimization.

<syntaxhighlight lang="pascal" line="">
sBest ← s0
sCurr ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(sCurr)
    bestCandidateFitness ← -∞
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) 
            and (fitness(sCandidate) > bestCandidateFitness) )
            bestCandidate ← sCandidate
            bestCandidateFitness ← fitness(bestCandidate)
        end
    end
    if (bestCandidateFitness is -∞)
        break;
    end
    sCurr ← bestCandidate
    if (bestCandidateFitness > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest
</syntaxhighlight>

Lines 1–4 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 a tabu list with this initial solution. 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 core algorithmic loop starts in line 5. 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). The neighboring solutions are checked for tabu elements in line 9. Additionally, the algorithm keeps track of the best solution in the neighbourhood, that is not tabu.

The fitness function is generally a mathematical function, which returns a score or the aspiration criteria are satisfied — for example, an aspiration criterion could be considered as a new search space is found.<ref name="ise.ncsu.edu"/> If the best local candidate has a higher fitness value than the current best (line 18), it is set as the new best (line 19). The local best candidate is always added to the tabu list (line 21), and if the tabu list is full (line 22), some elements will be allowed to expire (line 23). Generally, elements expire from the list in the same order they are added. The procedure will select the best local candidate (even if it has worse fitness than the current best) in order to escape the local optimal.

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 26).