[ Home | Docs | News | Resources | Download] |

GAUL Documentation: Tabu-Search |

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.
- Start with the
**current**solution. - If the
**current**solution better than the**best**solution so far, store it as the new**best**solution. - Add the
**current**solution to the Tabu list, remove the oldest item on the Tabu list if it contains more than**N**items. - Apply the local move
**M**times to generate**M****putative**solutions. - Rank the
**putative**solutions by fitness. - If the highest ranked
**putative**solution is the better than the**current**solution and jump to step 8. - Eliminate those
**putative**solutions which satisfy the Tabu conditions, unless they also satisfy the aspiration conditions. - Select the highest ranked
**putative**solution that was not eliminated as the new**current**solution, unless all**putative**solutions where eliminated. - If the terminantion criterion is not satisfied, repeat from step 2.
In the above algorithm,
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 The third and fourth parameters should be selected on a problem-by-problem basis to facilitate efficient, but effective, optimisation. They relate to 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. |

[ BACK TO TOP | NEXT SECTION OF TUTORIAL ]

[ Home | Docs | News | Resources | Download] |

Hosted by: |

© 2002-2003, "Stewart Adcock" <stewart@linux-domain.com> All rights reserved. |

All trademarks on this page are probably owned by their respective companies. You can insert you own favourite disclaimer here. |