tabu search

God not only plays dice. He also sometimes throws the dice where they cannot be seen Stephen Hawking

General optimisation/AI resources

Special topics

Selected articles | References | Software

The fields of tabu search and simulated annealing are relatively sparse in comparison with genetic algorithms.

Selected articles

The names Fred Glover and Manuel Laguna occur frequently in tabu search. Their paper Tabu Search forms an good and informal introduction to the topic.

Also of interest is their paper comparing three metaheuristic algorithms, consisting of Evolver, Genocop and their own product, Optquest. Evolver is highlighted in the genetic algorithm section of this website, Genocop is also a genetic algorithm and Optquest is a tabu/scatter search module of Crystal Ball, referred to below.

An interesting paper is Characterising search spaces for tabu search, which investigates which algorithm - tabu search or GA - is more efficient when applied to the location–allocation and the quadratic assignment problems. (We found GAs dramatically better for portfolio optimisation when comparing two very specific software appications of these two algorithms.)

One refinement of the tabu algorithm is reactive tabu search, developed by Roberto Battiti and described in the article The Reactive Tabu Search.

Although it is not applied to an investment problem, the paper Design and Evaluation of Tabu Search Algorithms for Multiprocessor Scheduling by Arne Thesen nevertheless provides some interesting insights on the general characteristics of tabu search.

Designing Portfolios Of Financial Products Via Integrated Simulation and Optimisation Models does exactly that. Tabu search is just one aspect of solving the problem.

to the top

References

The book Tabu Search by Glover and Laguna provides a pragmatic introduction to the topic.

Providing a more general overview of tabu search in the context of other metaheuristic approaches is Michalewicz, Z. (1994) Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, New York, NY, Second Edition.

to the top

Software

Decisioneering supplies Crystal Ball, an integrated simulation/optimisation/risk management product which contains Optquest, the tabu/scatter search module. We have used Crystal Ball and Optquest and recommend them highly, although Optquest did not work well on a (large, 100-stock) portfolio optimisation problem.

There are some interesting articles covering various applications on the site, as well as papers on Optquest. Should you wish for a version of Optquest specifically tailored to institutional asset allocation, go to OptTek Systems.

Genocop is a genetic algorithm-based program for constrained and unconstrained optimisation developed by Michalewicz in the book above. The software can be picked up from various sources, or go to the author's website to get the latest version. His website also offers some useful references.

to the top