Solving Travelling Salesman with Tabu Search

Question

I'm trying to understand the Tabu Search by using it with Hill Climbing algorithm, to solve the travelling salesman problem.

I understand the 'pure' Hill Climbing Algorithm, but how Tabu Search changes this algorithm is not very clear to me.

Hill Climbing Demonstration:

Let us say, we are given 6 cities A,B,C,D,E,F, and we randomly pick an initial state: (A,B,C,D,E,F) with travelling cost of 120.

Then I'm going to select a set of neighboring states (by swapping 1st element with 2nd, 3rd, 4th and so on), and calculate the travelling cost of each:

(B,A,C,D,E,F) = 110   /* <120; mark as optimal */
(C,B,A,D,E,F) = 127
(D,B,C,A,E,F) = 145
(E,B,C,D,A,F) = 102   /* <110; mark as optimal */
(F,B,C,D,E,A) = 80    /* <102; mark as optimal */

Now we have found a local optimum: (F,B,C,D,E,A).

How does Tabu Search alter the above algorithm? If you could demonstrate one or two iterations, I would be very much thankful.

Answer 1

Disclaimer: This answer is based on the link [Reference-1] shared by Geoffrey De Smet, in his comment, pointed here. Credits should go to him.

The two images, shown below, helped me to understand how Tabu Search alters the Hill Climbing algorithm.

Hill Climbing

(source: OptaPlanner User Guide)

Tabu Search

(source: OptaPlanner User Guide)

Reference:

[Reference-1] JBoss.org Community Documentation. OptaPlanner User Guide. [ONLINE] Available at: http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/index.html. [Accessed 07 December 13].

Answer 2

The difference with the Tabu Search ( TS ) is the tabu list it is keeping. And how it affects the search. The simplest way to generate such a tabu list is by keeping track of recent searches and including them into the tabu list in order for the algorithm to 'explore' different possibilities. An example for tabu list heuristic is: if from city D you've went to city E less than 'n' iterations ago where 'n' is the number of previous solutions to be stored it's added into the tabu list ( elements in the tabu list have expiration ).

The steps it performs are pretty much the same as the hill climbing:

1. It choses an initial state ( may be at random ) and set it as the best option.

2. It enters in a loop checking if a condition to break given by the user is met ( can be threshold or traveling cost for this example ).

3. It creates an empty candidate list. Each of the candidates in a given neighbour which does not contain a tabu element are added to this empty candidate list.

4. It finds the best candidate on this list and if it's cost is better than the current best it's marked as a solution.

5. If the number of tabus on the tabu list have reached the maximum number of tabus ( you are defining the number ) a tabu expires. The tabus on the list expires in the order they have been entered .. first in first out.

And this process repeats itself until the threshold defined by the user is met. Hope this helps understanding how it works :))