C++ Neural Networks and Fuzzy Logic by Valluru B. Rao M&T Books, IDG Books Worldwide, Inc. ISBN: 1558515526   Pub Date: 06/01/95

Tabu Neural Network

Tabu search, popularized by Fred Glover with his contributions, is a paradigm that has been used successfully in many optimization problems. It is a method that can steer a search procedure from a limited domain to an extended domain, so as to seek a solution that is better than a local minimum or a local maximum.

Tabu search (TS), suggests that an adaptive memory and a responsive exploration need to be part of an algorithm. Responsive exploration exploits the information derivable from a selected strategy. Such information may be more substantial, even if the selected strategy is in some sense a bad strategy, than what you can get even in a good strategy that is based on randomness. It is because there is an opportunity provided by such information to intelligently modify the strategy. You can get some clues as to how you can modify the strategy.

When you have a paradigm that incorporates adaptive memory, you see the relevance of associating a neural network:. a TANN is a Tabu neural network. Tabu search and Kohonen’s self-organizing map have a common approach in that they work with “neighborhoods.” As a new neighborhood is determined, TS prohibits some of the earlier solutions, as it classifies them as tabu. Such solutions contain attributes that are identified as tabu active.

Tabu search, has STM and LTM components as well. The short-term memory is sometimes called recency-based memory. While this may prove adequate to find good solutions, the inclusion of long-term memory makes the search method much more potent. It also does not necessitate longer runs of the search process.

Some of the examples of applications using Tabu search are:

•  Training neural nets with the reactive Tabu search

•  Tabu Learning: a neural network search method for solving nonconvex optimization problems

•  Massively parallel Tabu search for the quadratic assignment problem

•  Connection machine implementation of a Tabu search algorithm for the traveling salesman problem

•  A Tabu search procedure for multicommodity location/allocation with balancing requirements

Summary

The traveling salesperson problem is presented in this chapter as an example of nonlinear optimization with neural networks. Details of formulation are given of the energy function and its evaluation. The approaches to the solution of the traveling salesperson problem using a Hopfield network and using a Kohonen self-organizing map are presented. C++ programs are included for both approaches.

The output with the C++ program for the Hopfield network refers to examples of four- and five-city tours. The output with the C++ program for the Kohonen approach is given for a tour of five cities, for illustration. The solution obtained is good, if not optimal. The problem with the Hopfield approach lies in the selection of appropriate values for the parameters. Hopfield’s choices are given for his 10-city tour problem. The same values for the parameters may not work for the case of a different number of cities. The version of this approach given by Anzai is also discussed briefly.

Use of neural networks for nonlinear optimization as applied to portfolio selection is also presented in this chapter. You are introduced to Tabu search and its use in optimization with neural computing.