Very Brief Tabu-Search Primer

The Tabu search has been proven effective at solving many search and optimisation problems. It is a heuristic method which guides a local search procedure to explore the search space in such a way that entrapment in local minima is avoided. Unlike simple hill-climbing search techniques, but like simulated annealling, the Tabu search often moves from a current solution to one which is worse, with the expectation that this move will eventually lead to an even better solution. The basic Tabu search algorithm is illustrated below, along with a number of important terms:

• Local move: The process of generating a feasible solution to the problem which is related to the current solution.
• Tabu list: A list of previous solutions.
• Tabu conditions: A set of rules which are used to derive, from the Tabu list, regions of the search space from which any solutions are forbidden.
• Aspiration conditions: A set of rules which override the Tabu conditions, to ensure that certian favourable local moves are accepted.

1. Start with the current solution.
2. If the current solution better than the best solution so far, store it as the new best solution.
3. Add the current solution to the Tabu list, remove the oldest item on the Tabu list if it contains more than N items.
4. Apply the local move M times to generate M putative solutions.
5. Rank the putative solutions by fitness.
6. If the highest ranked putative solution is the better than the current solution and jump to step 8.
7. Eliminate those putative solutions which satisfy the Tabu conditions, unless they also satisfy the aspiration conditions.
8. Select the highest ranked putative solution that was not eliminated as the new current solution, unless all putative solutions where eliminated.
9. If the terminantion criterion is not satisfied, repeat from step 2.

In the above algorithm, N and M are both adjustable parameters.

Further Information About Tabu-Search

A Google search.

Tabu-Search Implemented in GAUL

The Tabu search is implemented in GAUL and demonstrated in examples/pingpong_tabu.c and examples/pingpong_tabu2.c.

The fitness evaluation function defined for use by the evolutionary algorithms is also utilised by the Tabu search routine. The local moves are generated by using the mutation operator. Note that performance may be enhanced greatly if this mutation operator contains a local search procedure, but this must be implemented by the programmer if desired. The additional parameters that are required are specified using the "ga_population_set_tabu_parameters()" function. The optimisation is initiated by the "ga_tabu()" function.

  ga_population_set_tabu_parameters(
       pop,                     /* population           *pop */
       ga_tabu_check_integer,   /* GAtabu_accept        tabu acceptance criterion */
       50,                      /* const int            tabu list length */
       20                       /* const int            tabu neighbourhood search count */
         );

The "GAtabu_accept" parameter is a function that applies the Tabu and aspiration criteria, given a single putative solution and single tabu solution. Simple functions are provided by GAUL for its built-in chromosome types. The use of custom, problem specific, versions is strongly recommended.

The third and fourth parameters should be selected on a problem-by-problem basis to facilitate efficient, but effective, optimisation. They relate to M and N, respectively, in the above algorithm.

ga_tabu(
       pop,                     /* population           *pop */
       solution,                /* entity               *initial */
       50                       /* const int            max_iterations */
         );

"ga_tabu()" takes a single entity as its second argument. This is used as the initial solution. Passing NULL is valid; a NULL entity parameter causes a random solution to be generated by applying the seed operator. The initial solution will be overwritten by the results of the Tabu search procedure.