2007 IEEE Workshop on Nonlinear Circuit Networks
NCN'07, Tokushima, Japan, Dec 7--8, 2007

Performance of Quadratic Assignment Problemby Hopfield NN with Scale Law
Yoshifumi Tada, Yoko Uwate and Yoshifumi Nishio
Department of Electrical and Electronic Engineering, Tokushima University,
2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN
Email:{y-tada, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract— In our past study, the solving ability of the Hopfield
Neural Network with noise for quadratic assignment problem
is investigated. However, even if we injected the noise to thenetwork, the optimal solution cannot occasionally be found. In
this study, we propose the method adding noise with scale law
to the Hopfield Neural Network to achieve better performance.

I. I NTRODUCTION
Hopfield Neural Network (abbr. NN) [1] is one of theimportant tools of solving combinatorial optimization problems. The global minimum can be searched by energy decent
principle of the Hopfield NN. However, in a lot of cases,
the network finds a local minimum, and can not escape fromthere. In order to avoid this critical problem, many researchers
proposed the method adding some kinds of noises to theHopfield NN. Hayakawa and Sawada pointed out the chaos
near the three-periodic window of the logistic map gains thebest performance as noise [2].
Figure 1 shows the scale-free network model. In the scale-investigate solving ability of adding the noise with scale law
the Hopfield NN for QAP. We confirm that the method iseffective to solve QAP by computer simulations.
II. S OLVING QAP WITH H OPFIELD NN
For solving N -element QAP by the Hopfield NN, N ×N
neurons are required and the following energy function isdefined to fire (i,j)-th neuron at the optimal position:
NNNXXXθim xim .
(1)
wim;jn xim xjn +E=i,m=1i,m=1 j,n=1

The neurons are coupled each other with weight between(i,m)-th neuron and (j,n)-th neuron and the threshold of the(i,m)-th neuron are described by:
Cij Dmn
wim;jn = −2 A(1−δmn )δij +Bδmn (1−δij)+(2)qθim = A + B(3)
where A and B are positive constant, and δij is Kroneker’sdelta. The state of N ×N neurons are asynchronously updated
due to the following difference equation:!
NX
xim (t + 1) = f
wim;jn xim (t)xjn (t) − θim + βzim (t)
j,n=1

(4)
where f is sigmoidal function.zim is additional noise injectedto the network, and β limits amplitude of the noise.

Fig. 1. Scale freeFig. 2. Scale-free destribution.
network model.
free network, a lot of nodes have only few connections, somenodes (marked in black) act as highly connected hubs. So, thesmall number of important nodes have a lot of connections.
This distinction is captured in a more quantitative way by thedistribution of the number of links vs. the number of nodes,
as shown in Fig. 2. Mathematically, scale-free network arecharacterized by power law distributions (Fig.2).
In this study, we propose a method to add noise of different
amplitudes determined by a scale law. Adding the noise iseffective for the solution to escape from the local minimum,
but at the same time it may obstruct the energy decent
principle. If the noise with a small amplitude is injected
to important neurons and the noise with a large amplitude
is injected to unimportant neurons, the solution may search
only around the global optimum without wandering away. We- 72 -III. C HAOS NOISE
In this section, we describe chaos noise injected to theHopfield NN. The logistic map is used to generate the chaosnoise:
ˆlim (t + 1) = αl (t)(1 − ˆlim (t)).
(5)
Figure III shows an example of the intermittency chaos near
the three-periodic window obtained from Eq. (5) for αl =3.8274.
10.9
0.8
0.7l̂

0.6
0.5
0.4
0.3
0.2

tFig.3. Time series obtained
from logistic map for αl = 3.8274.
0.10100200300

4005006007008009001000

IV. NOISE WITH SCALE LAW
We consider that there are some important cities and unimportant cities in a given problem. In other words, there exist
some key cities in many problems, whose arrangements should
be decided prior to the others to find better solutions. In order
to avoid to obstruct the steepest decent principle of the neurons
corresponding to such important cities, it may be better not toinject noise with a large amplitude to such neurons. In thisstudy, we propose the method to add noise with scale law
based on the concept of the important city and the scale law.
Figure 4 shows the Hopfield NN model for N -element QAP.
The neuron of each column expresses the city. The noisewith scale law is injected to all the neurons. However, theiramplitudes are determined by the column number nC of theneurons. Namely,
β = U nC
(6)
where U is the constant between 0 and 1, and nC is the column
number.
For the purpose of the comparison, we consider the casethat the amplitude is determined by a linear function with thesame maximum value.
Further, in order to compare them with the conventional
method, the average value of the functions is set up to β0 ofthe conventional method.
12CityN
110.9

Linear function

0.8

factory

20.7

β0.6

Scale-rule

0.5

TABLE IP LOBREM AND PARAMETERS .
Problem name
Global minimum
β0βmaxUA,Bq

Nug12578
0.6
1.0
0.6
0.9
140
0.2

Tai12a224416
0.5
1.3
0.5
0.9
16000
0.02

TABLE IIS OLVING ABILITIES FOR N UG 12.
Iteration
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

Conventional
632.96623.30619.82616.18613.56612.68611.74610.48610.30609.96

Scale law617.96613.32608.50605.78603.02600.94598.84597.82596.74595.84

Linear623.86616.12612.54609.68607.54606.20604.94604.12603.24602.36TABLE IIIS OLVING ABILITIES FOR TAI 12 A .
Iteration
4000
8000
12000
16000
20000
24000
28000
32000
36000
40000

Conventional
252624.44251337.90
250291.38
249638.16
249520.72
249495.62
249458.04
249335.58
249228.40
249225.84

Scale law242148.18
239571.98
238373.66
237750.34
237236.76
236733.68
236347.96
236021.02
235834.22
235549.42

Linear244849.92
242123.36
240738.44
239504.80
238803.02
238198.66
237838.76
237469.98
237209.98
237121.14

0.4

0.3

N0.2

135...........

N-1

NnCFig. 4. Neuron of Hopfild NN
Fig.5. Amplitude
model for N-element QAP.
of noise with scale law.
However, which is important city? Usually, we cannot know
how important is each city. Hence, we combine a rearranging
the column with the method. In this algorithm, we memorize
the column with the first fired neuron. The first fired neuronmeans the largest output value among the all neurons. So, thecolumn is rearranged to the last (right in Fig. 4). Next, thecolumn with the second fired neuron is the rearranged to thenext to the last. In this way, we rearrange the columns in theorder of frequency of the firing.
V. S IMULATION RESULTS
In this section, the simulated results of the Hopfield NN
with the noise with scale law for 12-elements of QAP areshown. The problems and parameters are shown as Table 1.
Tables 2 and 3 show the average values of the best solutions
obtained during a given iteration numbers for Nug12 andTai12a, respectively. From these results, the proposed method
gains better performance than the conventional method, andthe noise with scale law is better than the linear function noise.

- 73 -VI. C ONCLUSIONSIn this study, we proposed the method to add noise withscale law based on the concept of the important city and thescale law. By combining the method with the rearrangement of
the columns, we could inject the noise with a large amplitude
to unimportant neurons and the noise with a small amplitude toimportant neurons. By computer simulations, we investigated
the solving ability of adding the noise with scale law to theHopfield NN for QAP.
VII. ACKNOWLEDGMENTS
This research is supported by the found of Open ResearchCenter Project from MEXT of Japanese Government (20072011).
R EFERENCES[1] J.J. Hopfield, “Neurons with graded response have collective computational properties like those of two-state neurons,” Proc. Natl. Acad. Sci.
USA, vol.81, pp.3088–3092, 1984.
[2] Y. Hayakawa and Y. Sawada, “Effects of the chaotic noise on theperformance of a neural network model for optimization problems,”
Physical Review E, vol.51, no.4, pp.2693–2696, Apr. 1995.