Tabu Search Modern Heuristic Techniques for Combinatorial Problems

TabzlSearch / 57
a distinction between y and x since there may not be a one-one association between thl~m.) Time records identifying the quality of outcomes produced by recent firings, and identifying the frequency particular attribute assignments produce the highest quality firing outcomes, yield a basis for delaying changes in certain weight assignments and for encouraging changes in others. The concept of influence, in the form introduced in tabu search, should be considered in parallel with quality of outcomes.

Attribute creation and vocabulary building strategies as discussed in Section 3 have a significant potential for contributing to the issue of adaptive network design. An element notably lacking in neural networks at present is a systematic means to generate concepts, as where a chess player evolves an ability to detect and treat a particular configuration (class of positions) as a single unit Vocabulary building yields a direct way to generate new units from existing ones. Applied to neural networks, such a process may operate to find embedded configurations of states that correspond to good firing outcomes, and assemble them into larger units. More particularly, starting with a set of previous firing states and weightings, represented by assignments in which y ranges over a set Y(S), attribute creation processes can be used to identify and integrate significant components (subvectors). Copying and segregating these components permits associated neural connections to be treated as hardwired, i.e., locked in. This corresponds to treating the unit as a single new attribute. Activating the unit (as by setting Yj = P for appropriate j andp) thus automatically activates the full associated system of firings. The duplication of components of Y segregated from the original structure permits the "original components" to continue to evolve without the hardwiring limitation. This occurs in the same way that created attributes in vocabulary building processes exist side by side with separate insuLnces of the attributes that gave rise to them.

As noted in Table 1 of Section 4, elements of tabu search have already been incorporated into neural networks in the work of de Werra and Hertz (1989) and Beyer and Ogier (1991). These applications, which respectively treat visual pattern identification and nonconvex optiInization, are reported to significantly reduce training times and increase the reliability of outcomes g;enerated. In addition, TS principles also have been integrated into a special variant of neural networks making use of constructions called ghost images in (Glover, 1991b).
The preceding observations suggest that TS concepts and strategies offer a variety of fruitful possibilities for creating hybrid methods in combination with other approaches. Beyond this, many opportunities exist to expand the frontiers of tabu search itself. We have undertaken to point out some of the areas likely to yield particular benefits. As shown in Section 4, TS appears to be opening the door to new advances in many settings, encompassing production scheduling, routing, design, network planning, expert systems, and a variety of other areas. Tabu search methods present opportunities for future research both in developing new applications and in creating improved methodology. The exploration of these realms may afford a chance to make a useful impact on the solution of practical combinatorial problems.
58 / GLOVERandLAGUNA
Acknowledgemen t
This work was supported in part by the Joint Air Force Office of Scientific Research and Office of Naval Research Contract No. F49620-90-C-OO33 at the University of Colorado.
6.
Bibliography

Beyer, D. and R. Ogier (1991) "Tabu Learning: A Neural Network Search Method for Solving Nonconvex

Optimization Problems," Proceedings of the International Joint Conference on Neural Networks. IEEE and INNS, Singapore.

Bovet, J., C. Constantin, and D. de Werra (1991) "A Convoy Scheduling Problem," to appear in Discrete Applied Mathematics.

Chakrapani, J. and J. Skorin-Kapov (1993) "Massively Parallel Tabu Search for the Quadratic Assignment Problem," Annals of Operations Research. 41, 327-342.
Dammeyer, F. and S. VoS (1993) "Dynamic Tabu List Management Using the Reverse Elimination Method," Annals of Operations Research, 41, 31-46.
Daniels, R. L. and J. B. Mazzola (1993) "A Tabu Search Heuristic for dIe Flexible-Resource Flow Shop Scheduling Problem," Annals of Operations Research, 41, 207-230.
Davis, L. (ed.) (1991) Handbook 01 Genetic Algorithms, Van Nostrand Reinhold.
Dell' Amico, M. and M. Trubian (1993) "Applying Tabu Search to the Job-Shop Scheduling Proble,m," Annals of