Multiobjective Tabu Search

Research Theme: Computational Design

The design of engineering systems involves the simultaneous consideration of multiple criteria or objectives. Often some of these objectives will be in conflict. Thus, a trade-off exists, which can be investigated by using multiobjective optimisation methods.

In such a problem, no single optimal solution exists, rather there is a set of equally valid optimal solutions, known as the Pareto-optimal set. The solutions in this set show the designer what is possible, allowing them to make a fully informed choice.

Motivation

There is widespread interest within the Engineering Design community in applying Multiobjective Genetic Algorithms (MOGAs) to real-world engineering design problems. However, MOGAs can experience difficulties on highly constrained problems. Tabu Search (TS), because of the local search heuristic at its heart, can navigate highly constrained search spaces successfully. A multiobjective variant of TS would therefore be a valuable tool for Engineering Design.

Objectives

  • To develop a multiobjective Tabu Search (MOTS) algorithm variant.
  • To develop enhancements to the MOTS algorithm to improve its performance,including the exploitation of parallel computing environments.
  • To test and validate the MOTS algorithm on benchmark and real-world problems.

Method

An existing single-objective TS implementation for problems with continuous design variables, based around the Hooke & Jeeves local search method, is being adapted for multiobjective optimisation. It is being tested on a variety of established benchmark problems and on real-world Engineering Design problems.

Findings

The initial MOTS implementation has been shown to be competitive with other current state-of-the-art multiobjective optimisers on benchmark problems. It has been applied successfully to a variety of real-world problems.

A number of possible algorithm enhancements have been identified, implemented and tested, and this work is continuing through the Undergraduate Research Opportunities Programme.

Details

Tabu Search operates in a sequential, iterative manner: the search starts at a given point and the algorithm selects a new point in the search space to be the next current point. The basic search pattern in our implementation is a modified version of Hooke & Jeeves (H&J) search.

Recently visited points are stored in the Short Term Memory (STM) on a first-in-first-out basis and are tabu – the search is not allowed to revisit these points.

The Medium Term Memory (MTM) maintains a record of the Pareto-optimal points found thus far during search, and its contents are the primary output at the end of the optimisation.

An Intensification Memory (IM) stores locally Pareto-optimal points that have not been selected as part of the H&J search pattern; the IM is used to select points for search intensification, focusing the search on areas of the search space with known good objective function values.

The Long Term Memory (LTM) records the regions of the search space which have been explored, and is used on diversification, directing the search to regions which are under-explored.

A local iteration counter is used, and reset upon a successful addition to the MTM. When this counter reaches user-specified values, the algorithm will diversify or intensify the search, or reduce the search step size and restart the search from a randomly selected point from the MTM. Thus, TS combines a systematic local search with a stochastic element and an intelligent coverage of the entire search space.

Acknowledgements

Support for this project was provided by the EPSRC.

Selected Publications

  • JAEGGI, D.M., PARKS, G.T., KIPOUROS, T. and CLARKSON, P.J. (2006) 'Thedevelopment of a multi-objective tabu search algorithm for continuous optimisationproblems' in European Journal of Operations Research feature issueon Adaptation of Discrete Metaheuristics for Continuous Optimization (forthcoming)
  • JAEGGI, D.M., PARKS, G.T., KIPOUROS, T. and CLARKSON, P.J. (2005) 'A multi-objectiveparallel tabu search algorithm for constrained optimisation' in The 3rdInternational Conference of Evolutionary Multi-Criterion Optimisation,Guanajuato, Mexico, 3410, 490-504
  • JAEGGI, D.M., ASSELIN-MILLER, C.S., PARKS, G.T., KIPOUROS, T., BELL, T.and CLARKSON, P.J. (2004) 'Multi-objective parallel tabu search' in The8th International Conference on Parallel Problem Solving from Nature (PPSN),Birmingham, UK, 3242, 732-741