Solving Ability of Hopﬁeld Neural Networkwith Scale-Rule Noise for QAP
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— One of the applications of neural network is solving
combinatorial optimization problems. In our past study, thesolving ability of the Hopfield Neural Network with noise forquadratic assignment problem is investigated. However, even if
we injected the noise to the network, the optimal solution cannotoccasionally be found. In this study, we propose the method
adding scale-rule noise to the Hopfield Neural Network to achieve
better performance. By computer simulations solving quadratic
assignment problem, we evaluate the performance of the method.

I. I NTRODUCTION

978-1-4244-1684-4/08/$25.00 ©2008 IEEEFig. 1.

Scale-free network model.

characterized by power law distributions (Fig. 2). Because
scale-rules emerge in many areas and disciplines of science(e.g. engineering, economics, social sciences and so on), weexpect that also in the development of neural networks, they
will play an important role.

number of links

Hopﬁeld 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 Hopﬁeld NN. However, in a lot of cases,
the network ﬁnds 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 theHopﬁeld NN. Hayakawa and Sawada pointed out the chaos
near the three-periodic window of the logistic map gains thebest performance as noise [2]. They concluded that the goodresult might be obtained by a property of the chaos noise;
short time correlations of the time-sequence. Hasegawa et al.
investigated solving abilities of the Hopﬁeld NN with various
surrogate noise, and they concluded that the effects of thechaotic sequence for solving optimization problems can bereplaced by stochastic noise with similar autocorrelation [3].
In our past study, we proposed the method to change theamplitude of the chaos noise according to the state; Hoppingchaos [4]. By using this method, the network could searchmany good solutions. However, this method was not still
effective to ﬁnd near optimal solutions for difﬁcult problems.
Since the scale-free network were discovered by Barabasi etal. [5], studies assessing the inﬂuence of this property on theefﬁciency of networks have been carried out in various ﬁelds.
Figure 1 shows the scale-free network model. In the scalefree 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 arenumber of nodes

Fig. 2.

Scale-free distribution.

In this study, we propose a method to add noise of different
amplitudes determined by a scale-rule. Adding the noise iseffective for the solution to escape from the local minimum,
but at the same time it may obstruct the energy decentprinciple. If the noise with a small amplitude is injected
to important neurons and the noise with a large amplitude105

is injected to unimportant neurons, the solution may search
only around the global optimum without wandering away. We
investigate solving ability of the Hopﬁeld NN with the scalerule noise for QAP. We conﬁrm that the method is effective
to solve QAP by computer simulations.
II. S OLVING QAP WITH H OPFIELD NN
Various methods are proposed for solving QAP which
is one of the NP-hard combinatorial optimization problems.
We explain QAP with a factory arrangement problem. Theproblem is given by two matrices, distance matrix C denoting
the distances between the factories and ﬂow matrix D denoting
the ﬂow of the products between the factories, and is to ﬁnd
the permutation P which corresponds to the minimum valueof the objective function f (P ) in Eq. (1).
f (P ) =NN Cij Dp(i)p(j),(1)

i=1 j=1

where Cij and Dij are the (i,j)-th elements of C and D,
respectively, p(i) is the i-th element of vector P , and N is thesize of the problem. There are many real applications which
are formulated by Eq. (1). Other examples are the placement oflogical modules in an IC chip and the distribution of medical
services in large hospital.
Because the QAP is very difﬁcult, it is almost impossible
to solve the optimum solution in large problems. The largest
problem which is solved by deterministic methods may be only
24 in recent study. Further, computation times is very longto obtain the exact optimum solution. Therefore, it is usual
to develop heuristic methods which search nearly optimal
solutions in reasonable time.
For solving N -element QAP by the Hopﬁeld NN, N ×N
neurons are required and the following energy function isdeﬁned to ﬁre (i,j)-th neuron at the optimal position:
E=N

N


wim;jn xim xjn +i,m=1 j,n=1

Nzim is additional noise injected to the network, and β limits
amplitude of the noise.
III. C HAOS NOISE
In this section, we describe chaos noise injected to theHopﬁeld NN. The logistic map is used to generate the chaosnoise:ˆlim (t + 1) = αl (t)(1 − ˆlim (t)).
(7)
Varying parameter αl , Eq. (7) behaves chaotically via aperiodic-doubling cascade. Further, it is well known that themap produces intermittent bursts just before periodic-windows
appear. Figure 3 shows an example of the intermittency chaos
near the three-periodic window obtained from Eq. (7) for
αl = 3.8274. As we can see from the ﬁgure, the chaotic
time series could be divided into two phases; laminar parts ofperiodic behaviour with period three and burst parts of spread
points over the invariant interval. As increasing αl , the ratio of
the laminar parts becomes larger and ﬁnally the three-periodic
window appears.
We use the intermittency chaos after the following normalization.
lim (t + 1) =l̂im (t) − ȳσl(8)where l̄ and σl are the average and the standard deviation ofl̂(t), respectively.
l̂
1

0.9

0.8

0.7

0.6

0.5

θim xim .

(2)

0.4

i,m=10.3

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 Dmnwim;jn = −2 A(1−δmn)δij +Bδmn (1−δij)+(3)qθim = A + B(5)where f is sigmoidal function deﬁned as follows:
f (x) =1
1 + exp − x

0.1
0100

200

300

400

500

600

700

800

900

1000

tFig. 3.

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

(4)

where A and B are positive constant, and δij is Kroneker’s
delta. The state of N ×N neurons are asynchronously updated
due to the following difference equation:
 Nxim (t + 1) = fwim;jn xim (t)xjn (t) − θim + βzim (t)j,n=10.2(6)

IV. S CALE - RULE NOISE
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 ﬁnd 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 scale-rule noise basedon the concept of the important city and the scale-rule.

106Figure 4 shows the Hopﬁeld NN model for N -element QAP.
The neuron of each column expresses the city. The scale-rulenoise is injected to all the neurons. However, their amplitudes
are determined by the column number nC of the neurons.
Namely,β = U nC
(9)
where U is the constant between 0 and 1, and nC is the columnnumber.
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.
City1

2

next to the last. In this way, we rearrange the columns in theorder of frequency of the ﬁring.
V. S IMULATION RESULTS
In this section, the simulated results of the Hopﬁeld NN
with the scale-rule noise for 12-elements of QAP are shown.
The problem was chosen from the site QAPLIB [6] named“Nug12”. The global minimum is known as 578. The parameters of the Hopﬁeld NN are ﬁxed as A = 0.9, B = 0.9,q = 140, and  = 0.2. We carried out 100 trails of 10000
iterations. The parameter corresponding to the noise amplitudeof the conventional method is ﬁxed as β0 = 0.6. The control
parameter of the logistic map is ﬁxed as αl = 3.8274. The
maximum value of the scale-rule and the linear functions are
set to βmax =1.0. The parameter of the scale-rule function isﬁxed as U = 0.6.

NTABLE I
S OLVING ABILITIES FOR N UG 12.

1

Iteration
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

factory

2

Conventional
632.96623.30619.82616.18
613.56612.68611.74610.48610.30609.96

Scale-rule617.96613.32608.50605.78603.02600.94598.84597.82596.74595.84

Linear623.86616.12612.54609.68607.54606.20604.94604.12603.24602.36

NFig. 4.

Next, we tried another problem, problem name is “Tai12a”.
The global minimum is 224416. The parameters of the Hopﬁeld NN are ﬁxed as A = 0.9, B = 0.9, q = 16000, and = 0.02. We carried out 100 trails of 40000 iterations. Otherparameters are β0 = 0.5, αl = 3.82676, βmax =1.3, and U =0.5.

Neurons of Hopﬁeld NN model for N -elemnt QAP.

10.9

TABLE II

Linear function

0.8

S OLVING ABILITIES FOR TAI 12 A .
0.7

βIteration
4000
8000
12000
16000
20000
24000
28000
32000
36000
40000

0.6

Scale-rule
0.5

0.4

0.3

0.2
13...........

5N-1NnC
Fig. 5.

Conventional
252624.44251337.90
250291.38
249638.16
249520.72
249495.62
249458.04
249335.58
249228.40
249225.84

Scale-rule242148.18
239571.98
238373.66
237750.34
237236.76236733.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

Amplitude of scale-rule noise.

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 ﬁrst ﬁred neuron. The ﬁrst ﬁred 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 ﬁred neuron is the rearranged to theTables 1 and 2 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 scale-rule noise is better than the linear function noise.
For Nug12, all the methods could ﬁnd the global minimum.
While, for Tai12a, the conventional method could not ﬁnd the107

250000

global minimum, but the proposed methods (both scale-ruleand linear) could ﬁnd it.
Finally, we investigate the performance against changing thedistribution of the scale-rule function (Fig. 6). As the value ofU increases, the scale-rule function becomes similar to thelinear function.

Average of solutions

24800010.9

Conventional

246000244000242000240000Linear function

2380000.82360000.7234000

β 0.6

00.1

0.2

0.5

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1U

U = 0.1
U = 0.3
U = 0.5

Fig. 8.

U = 0.7
0.4

Simulation result of Tai12a.

0.3

U = 0.9[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.
[3] M. Hasegawa, T. Ikeguchi, T. Matozaki and K. Aihara, “An analysis on
additive effects of nonlinear dynamics for combinatorial optimization,”
IEICE Trans. Fundamentals, vol.E80-A, no.1, pp.206–213, Jan. 1997.
[4] Y. Tada, Y. Uwate and Y. Nishio, “Effective search with hopping chaos for
Hopﬁeld neural networks solving QAP,” Proc. ISCAS’07, pp.1783-1786,May 2007.
[5] Barabasi, Albert-Laszlo and A. Reka, “Emergence of scaling in random
networks,” Science, 286:509-512, Oct. 1999.
[6] R.E. Berkard, S.E. Karisch and F. Rendl, “QAPLIB – a quadratic
assignment problem library,”

0.2

linear

0.1
12

3

4

567

8

9101112

Number of city

Value of changing U .

Fig. 6.

610

Conventional

Average of solutions

608606

http://www.opt.math.tu-graz.ac.at/qaplib

Linear function

604602600

598596

594
00.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1UFig. 7.

Simulation result of Nug12.

From the results of changing U (Figs. 7 and 8), we cansay that the scale-rule noise gains better performance than thelinear function for almost U . When U approaches to 1.0, theperformance becomes similar to the linear function.
VI. C ONCLUSIONSIn this study, we proposed the method to add scale-rulenoise based on the concept of the important city and the scalerule. By combining the method with the rearrangement of thecolumns, we could inject the noise with a large amplitude tounimportant neurons and the noise with a small amplitude toimportant neurons. By computer simulations, we investigated
the solving ability of the Hopﬁeld NN with the scale-rule for
QAP. We conﬁrmed that the proposed method is effective tosolve QAP.
R EFERENCES[1] J.J. Hopﬁeld, “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.

108