4

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.

Dilini
  • 777
  • 8
  • 22
  • 3
    Note that are [different types of Tabu](http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/index.html#tabuSearch). For example you can make the solution state tabu (ABCDEF), or the move (A goes before B) or the entities involved (A). Then simply don't accept any move that has the same tabu type (unless it gets aspirated). In my experiments, I get the best results with making the entities tabu. And making the solution state tabu is terrible: it doesn't scale. – Geoffrey De Smet Dec 06 '13 at 14:45
  • 1
    The link @GeoffreyDeSmet shared is just great! I think now I've understood the Tabu Search. Thanks a lot Geoffrey! Wish people like myself (who've desperately searched for a simple example to understand Tabu Search) could find that article from Google-search. – Dilini Dec 06 '13 at 16:18

2 Answers2

5

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 :))

Dan Prince
  • 29,491
  • 13
  • 89
  • 120
Wald
  • 1,063
  • 7
  • 13
  • Thank you very much Wald for your helpful answer!... So in the next iteration, we select another state **randomly**? And this state should not be Tabu...Am I correct? – Dilini Dec 04 '13 at 15:55
  • No the initial state is selected once then based on each neighbour it creates a canditate list: Neighbour (B,A, ...... ) His candidates can be all the other cities shifted in an order. If this isn't present in the current tabo list it enteres the candidates list if it does it's skipped ( for now depends on the threshold of the algorithm ). – Wald Dec 04 '13 at 17:09
  • "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." So we do not accept worse solutions ? How do we escape local optimas ? I think this statement is not true. – Kasper Ziemianek Dec 29 '14 at 18:18
4

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

Hill Climbing (source: OptaPlanner User Guide)

Tabu Search

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].

Community
  • 1
  • 1
Dilini
  • 777
  • 8
  • 22