Department of Measurement and Instrument Engineering
Technical University of Budapest
H-1521 Budapest, Hungary
Email: strausz@mmt.bme.hu
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.