Tabu Search

Tabu search (or taboo search) improves self-avoiding random walks by generalising the forbidden (tabu/taboo) moves. Rather than just forbidding repetition, tabu search can impose other arbitrary limitations. To keep things simple and general, I'll stick to just forbidding previously visited solutions. Note that this would seem to give us exactly the self-avoiding random walk, but actually the forbidden list in tabu search must be finite; in other words, we forget old locations once our memory limit is reached. This allows the search to keep going as long as necessary, unlike the self-avoiding random walk, and it reduces the potential for getting trapped (forming a ring of visited solutions around ourself). Once again, we keep going until we find a solution that's "good enough".

In this example, like with the other random walks, the fitness of a particular location is shown by how light the grey colour is. This is randomly generated when the page loads.

Each (x, y) point in the square is a solution, and our goal is to find the best (lightest). We start in the centre and move a set distance at a random angle at each step. If the location is in our tabu list (once again, rounded to the nearest pixel) then we keep choosing new angles until we find a non-tabu location. Once we've moved to a new location, we add it to our tabu list, and we shift off an item from the start of the list if it's over a certain length. Like the standard random walk, I've made the edges wrap around. Note that if you choose a step size of 1 then the trails will only be removed once they leave the tabu list. This allows the tabu areas to be seen (we couldn't do this for larger step sizes, as it's only the end points that are chosen, not the line in-between).