Effective Simulation of Dynamic Neural Network

Gyorgy Strausz

Department of Measurement and Instrument Engineering
Technical University of Budapest
H-1521 Budapest, Hungary
Email: strausz@mmt.bme.hu

Mean-field neural networks are efficient tools for finding low-cost solutions of optimization problems. The success of the search process mainly depend on the effectiveness of the problem coding and also on the simulation method chosen. Neural network simulations are usually of high calculation need. The proper simulation method mainly depends on how it can utilize the known structure and the hidden relations in the used coding.

In this paper a method is presented how to map constraint satisfaction problem onto dynamic Hopfield type neural network in order to achieve fast, optimal or near optimal solution. The application task has been solved is the Radio Link Frequency Assignment Problem (RLFAP). In this problem we have to assign frequencies from a finite domain to several radio connections in such a way that the result should meet numerous inequality constraints.

Methods and results of spin-glass theory have been recently applied to study stochastic recurrent neural network behavior [1]. Solving optimization problem we are investigating the global minima of the energy function associated to the network. In order to avoid local minima mean field technique was used to relax the system into the desired state.

The problem is mapped onto the network such that a neuron being on corresponds to a certain decision. Each unit indicates whether a variable of the problem is taking a given value. Constraints are embedded in the connection weights such that the global minima of the network's energy function belongs to the state when no constraint is violated. In order to restrict the space of allowed states graded units were used that forces exactly 1 unit to be in active state in each group. It automatically guarantees that each variable takes exactly one value in the solution. This leads to the Potts glass model [2], where the usual nonlinear transfer function modifies to the vector generalization of a sigmoidal function.

The method was tested on 12 large size (900 variables, 30000 constraints) problems where good quality results were received. Another advantage of the approach is the direct hardware implementation possibility as the mean field equations are isomorphic to the RC equations of the VLSI circuit.

  1. Peterson, K. and Soderberg, B. (1989): A new method for mapping optimization problems onto neural networks, International Journal of Neural Systems, Vol. 1, No. 1, pp.3-22.

  2. Kanter, I. and Sompolinsky H. (1987): Graph optimization problems and the Potts glass, Journal of Physics A20 (1987), pp. L673-L679.

  3. Hopfield, J.J. (1982): Neural networks and physical systems with emergent collective computational abilities, Proc. National Academy of Sciences of the USA 81, pp.3088- 3092.