Description of the Tabu Search implementation

mck- edited this page Mar 14, 2012 · 4 revisions

Tabu Search is a local search technique that allows for non-improving moves to overcome local optima. These moves are in turn declared tabu for a number of iterations (tenure) in order to prevent cycling from happening.

alt Iterator

Tabu Search is implemented using the Iterator. It is defined in TS.lisp, but depends on TS-classdef.lisp, TS-utils.lisp, iterator.lisp, tools.lisp, best-insertion.lisp and greedy-best-insertion.lisp.

(make-instance 'tabu-search) will create a Tabu Search algo object with default values, as defined in TS-classdef.lisp. Here are the slots that you could define for your Tabu Search.

  • :iterations sets how many iterations to run. Note that if a stopping-condition is defined, the run may stop prematurely. Once the run is stopped, you may call iterate-more to keep searching.

  • :tabu-tenure defines how long the tabu-list is. Lowering this number might facilitate the search in a narrow direction, but it may get trapped easily. A higher number might prevent useful moves from occurring for a long time, but it is necessary in order to escape a local optimum. Default value is set to 15, which works pretty well for the solomon100 test-case, but may be too high for smaller test cases. Researchers have spent a lot of time determining the right value, so make sure you choose wisely. They have also devised mechanisms such as a Reactive Tabu Search, which adjusts the tenure value dynamically; when plenty of good moves are found, reduce tenure, but when no new best solution has been found for a number of iterations, increase the tenure value. This has not yet been implemented in Open-VRP.

  • :tabu-parameter-f holds the function that will be called on a move that is unimproving. The value this function returns will be saved on the :tabu-list. This function defines what parameters of the move will be used for identification. For instance, by default it's set to #'ts-pars-n (defined in TS-utils) which only returns the node-ID. Once a move with node-ID x has been declared tabu, then all potential moves that involve moving node x around are tabu. This may seem too inhibiting (especially for a small number of customers and large tenure value), so you could also use multiple parameters, say the node-id and the vehicle-id: #'ts-pars-nv. Or define/set your own #'(lambda (mv) (list ...)).

  • :move-type holds the symbol of the move. By default, uses TS-best-insertion-move. Adjust this if you are defining your own moves.

  • :init-heur holds the symbol that defines the algo to be used to create an initial solution. By default, uses Greedy Best Insertion to generate an initial solution. Adjust this if you want to write your own algo to create an initial solution.

  • :aspirationp is a boolean slot, setting the use of the aspiration criteria. Whenever a new best solution is found through a move that is on the tabu list, we override the tabu list when the aspiration criteria is set to T. Without such an aspiration criteria, we risk that better solutions are not found. By default, set to T.

  • :elite-listp is a boolean slot, setting the use of elite candidate lists. Normally, during each iteration, we assess all possible moves and only select the best (non-tabu) move to perform. In the following iteration, we will again assess all possible moves and probably find the same moves that were found during the previous iteration, resulting in double computation. The elite candidate list records all improving moves, which will then be used during the next iteration (once all related or affected moves are discarded). This may speed up the search significantly at the beginning, when there are plenty of possible improving moves. By default, set to T.

  • :stopping-condition holds a function that takes one algo argument and tests whether the stopping condition has been met or not. Before each iteration, the algo object is passed to this function and when this function returns T, the algo run gets interrupted. By default refers to #'stopping-conditionp which is implemented in TS-utils and makes use of algo-best-iteration which is set every time a new best solution is found. It stops when the number of iterations that no new best solution has been found exceeds triple the tenure value (with a minimum of 20, in case tenure is lower than 7). Beware Although in many cases it means that the search is stuck in a local optimum, this might stop the search prematurely! Set stopping condition to NIL instead (or call iterate-more to keep searching). It is only useful in combination with multi-run, in which case we perform multiple searches. The time spend stuck in a local optimum might in that case may be spend in a new area of the search space, which might result in a better global optimum.

Neighbourhood structure

A fancy term for talking about what solutions we may reach from a solution, or in short, what defines a move. Currently, we have defined only one move, i.e. TS-best-insertion-move which holds two parameters. move-node-id and move-vehicle-id.

A move with move-node-id = 1 and move-vehicle-id = 2, simply means that we will remove node 1 from whichever vehicle that has it on its route, and insert it in vehicle 2 in the most optimal index (which is achieved by calling get-best-insertion-move-in-vehicle, see best-insertion) This also implies that intra-route moves are also possible, e.g. when originally vehicle 2 has node 1 already, but in a non-optimal spot.

This is a very basic (almost minimalistic) neighbourhood structure which is fast and works pretty well in most times, but it might not be strong enough in some cases to escape local optima. You may use multi-run to diversify your search, or implement more complex (expensive) moves that will get triggered when it deemed stuck.

For a little visual demo on how Tabu Search proceeds, you may run:

(solve-prob solomon25 (make-instance 'tabu-search :animate T))

and follow the search iteration per iteration as it plots in run-frames/ folder.