7.5 The DAM as a Gradient Net and its Application to Combinatorial Optimization

In the above presentation, the DAM is generally viewed as a stable monlinear dynamical system which performs associative retrievals of stored vectors/memories from noisy initial states. The fundamental idea is to store a set of desired memories as local minima of an energy function which is minimized by the DAM's dynamics. Memory storage is achieved by using recording recipes which result in the proper synthesis of DAM parameters (weights).

The notion of minimizing an energy function by a dynamical system (especially a physically realizable one) has important implications to the solution of optimization problems. Here, a stable dynamical system is designed whose energy function E(x) matches the cost/objective function J of a given optimization problem. Then, this dynamical system is initialized at a random state x(0) and is allowed to relax to a solution x*. This solution may be viewed as a solution to the optimization problem. The degree of optimality of the solution x* does not depend on the initial state x(0) if the dynamical system used has global search capability. Unfortunately, no design methodology is available for designing such a stable dynamical system for optimization problems of practical significance.

Gradient dynamical systems are often used to generate solutions to optimization problems (Cichocki and Unbehauen, 1993) because of their potential realization via physical systems and their intrinsic stability. However, gradient systems are only capable of local (gradient-based) search and thus the quality of the solutions they generate depends greatly on the initial state of the system. This problem may be partially treated if fast analog hardware (or a fast parallel computer) is used to implement the gradient system; this leads to fast convergence time ranging from nanoseconds to microseconds and allows running the system many times from different initial conditions, within a short period of time, and may eventually lead to high quality solutions.

One particular class of optimization problems frequently encountered in many branches of science and technology consists of problems with combinatorial complexity. Such problems have a finite set of possible solutions but which scales exponentially or factorially in problem size n (dimension of x). Because of the combinatorial nature of these problems the time needed to solve any one of them scales exponentially, thus making the solution intractable for large n (for an example, the reader is referred to the traveling salesman problem described at the end of Section 3.5.3. See also Problem 7.5.3). These problems are known as nondeterministic polynomial-time-complete (NP-complete) for which no algorithm is known which provides the global minimal solution in a polynomial computational time (Papadimitriou and Steiglitz, 1982; Garey and Johnson, 1979). Heuristic algorithms with polynomial-time complexity have been developed which provide sub-optimal solutions to NP-complete problems (e.g., see Simeone, 1989). Unfortunately, these heuristic algorithms are problem-specific and their sequential search nature prevents their implementation on fast parallel computers or in hardware.

Many combinatorial optimization problems can be cast as a problem of minimizing the sum of a cost term and a constraints satisfaction term according to

J = (cost term) + (constraints satisfaction terms) (7.5.1)

Furthermore, for a wide range of practical problems, the objective function J can be put in the form of or approximated by the quadratic function (Hopfield and Tank, 1985)

(7.5.2)

where W is a symmetric zero-diagonal real-valued matrix and  = [I1 I2 ... In]T is a bias vector. Here, W and are determined by the optimization problem to be solved. The vector x usually has binary components, x  {-1, +1}n (or {0, 1}n), reflecting the combinatorial nature of the problem.

The cost function J in Equation (7.5.2) has the same functional form as the energy function in Equation (7.1.24) minimized by the discrete Hopfield DAM. The cost function J is also approximately equal to the energy function of the continuous-time continuous-state Hopfield net (Equation (7.1.23) in the limit of large amplifier gain . This suggests that one may map the cost function in Equation (7.5.2) onto a Hopfield DAM and let the DAM relax to a local minimum of this cost function, hoping that such a local minimum is a good solution to the optimization problem at hand. In practice, the continuous model is more preferable than the discrete model since it can avoid some of the numerous poor local minima of J (located at vertices of the hypercube ) encountered by the discrete model. When the continuous Hopfield net is used, the amplifier gains are initially set to a value close to 1 so that sufficient time is given for the net to "explore" the solution space before converging to a vertex solution. After some time, though, the gains should be gradually increased in order to force all local minima of the network's energy to move to corners of the hypercube where the desired solutions are located. This gradual increase in gain is known as "hardware annealing" (Lee and Shen, 1991. Also see Section 8.4.1). Another technique is to add to the cost function J (and thus to the energy function E) an additional quadratic constraint satisfaction (penalty) term which is equal to zero only if xi  {-1, +1} for all i.

With finite gain, the continuous Hopfield net may be viewed as a gradient system in terms of the Energy function E(x) of Equation (7.1.23). Formally,

(7.5.3)

where , i > 0 are as defined in Section 7.1.2. Writing Equation (7.5.3) in terms of the cost function J to be minimized gives

(7.5.4)

Solving for the partial derivative term in Equation (7.5.4) leads to

(7.5.5)

Now, the time derivative of J(x) is

(7.5.6)

Where Equation (7.5.5) was used. The first term on the right hand side of Equation (7.5.6) is always positive. However, the second term can become positive and, therefore, may become positive. This means that Equation (7.5.3) is not a gradient system in J unless the decay terms are eliminated (Takefuji and Lee, 1991). This can be physically accomplished by assuming lossless amplifiers in the Hopfield net. With all i = 0, the Hopfield net's dynamics reduce to the stable gradient system

(7.5.7)

To summarize, the lossless amplifier Hopfield net whose energy function is exactly matched to a quadratic objective function J(x) is guaranteed to converge to a local minimum of J. It should be noted here that the cost and the constraint satisfaction terms comprising J compete with each other and may develop local minima in J which may violate one or more constraints (in which case the solution is not acceptable) or may satisfy all constraints at the expense of suboptimal solutions.

This section is concluded by an illustrative example of mapping an objective function representing a simple computational task onto a continuous Hopfield net. Problems 7.5.2 and 7.5.3 further explore the ideas of this section. A large body of research on, and applications of the Hopfield net have appeared since the original introduction of the idea of optimization via gradient neural-like nets by Hopfield and Tank (1985) ,(see also Tank and Hopfield, 1986). A good sample of this research can be found in the books by Hertz et al. (1991), and Cichocki and Unbehauen (1993). See also Watta (1994) for an extension of the Hopfield net idea to constrained mixed integer optimization problems.

Example 7.5.1: Design of a 2-bit A/D converter

The objective in this example is to demonstrate via a specific simple example the procedure for mapping a computational (optimization) task onto a continuous Hopfield net, thus resulting in a fast parallel analog implementation of the desired task. The computational task here is to convert a continuous analog signal into its 2-bit binary representation (x0x1) where x0 is the least significant bit. First, the problem is expressed in terms of a quadratic objective function J(x0x1). The main objective here is for the equivalent decimal value of the desired digital representation of z to be as close as possible to the analog value of z. In other words, it is desired to minimize the quantity . Furthermore, it is important that the variables x0 and x1 take on unipolar binary values. This can be accomplished by minimizing the constraint satisfaction terms x1(1 - x1) and x0(1 - x0). Therefore, a suitable objective function is given by (note the intentional quadratic nature of J)

(7.5.8)

Equation (7.5.8) should now be minimized. Expanding J gives

(7.5.9)

Since J should ultimately match a Hopfield net's energy function which has no and terms, the last two terms on the right-hand side of Equation (7.5.9) must vanish. This is accomplished by choosing and . The term is not a function of the states x0 and x1 and its presence only shifts J by a positive amount. Thus, the term can be deleted without affecting the local minima of J. Hence, the following alternative objective function may be used:

(7.5.10)

Because of the unipolar nature of x0 and x1, the transfer function of the Hopfield net amplifiers will be assumed to have the following unipolar sigmoidal form:

(7.5.11)

Now, by matching the net's energy function given by (here, w00 = w11 = 0, w01 = w10, and high amplifier gain are assumed):

(7.5.12)

to J in Equation (7.9.10), one gets w10 = w01 = -2, I0 = z - , and I1 = 2(z - 1). According to Equations (7.5.7) and (7.5.10), the network dynamics are given by (assuming )

(7.5.13)

Finally, a circuit realization of this system is given in Figure 7.5.1 (Actually, this circuit does not exactly model the dynamics in Equation (7.5.13). See Problem 7.5.1 for further exploration into this matter).


Figure 7.5.1. A circuit realization of the two-bit A/D converter in Example 7.5.1.

Back to the Table of Contents

Back to Main Menu