Effective Search with Hopping Chaos
for Hopfield Neural Networks Solving 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— Many people propose the method adding chaosnoise to Hopfield Neural Network for solving combinatorial
optimization problems. In our past study, we solved Quadratic
Assignment Problem by Hopfield neural network with various
chaotic noises. However, the solution of the network is sometimes
trapped in a certain area and can not find a good solution,
especially for relatively larger problems. In this study, we
propose a method changing the amplitude of the chaos noise. We
investigate the performance of Hopfield Neural Network with the
hopping chaos for Quadratic Assignment Problem.

Neural Network for Quadratic Assignment Problem.
II. S OLVING QAP WITH H OPFIELD NN
Various methods are proposed for solving the QAP which isone of the NP-hard combinatorial optimization problems.The
QAP is expressed as follow: given two matrices, distancematrix C and flow matrix D, and find the permutation P whichcorresponds to the minimum value of the objective function
f (p) in Eq. (1).

I. I NTRODUCTION
Solving combinatorial optimization problem is one of theapplication of the Neural Network (abbr.NN). If we choose
connection weights between neurons appropriately according
to given problems, we can obtain a good solution by theenergy minimization principle. However, the solutions areoften trapped into a local minimum and do not reach the global
minimum. In order to avoid this critical problem, several
people proposed the method adding some kinds of noise forsolving traveling salesman problems (TSP) with the Hopfield
NN [1]. Hayakawa and Sawada pointed out the chaos near
the three-periodic window of the logistic map gains the best
performance [2]. They concluded that the good result might
be obtained by a property of the chaos noise; short timecorrelations of the time-sequence. Hasegawa et al. investigatedsolving abilities of the Hopfield NN with various surrogate
noise, and they concluded that the effects of the chaotic
sequence for solving optimization problems can be replaced bystochastic noise with similar autocorrelation [3]. We have alsostudied the reason of the good performance of the Hopfield
NN with chaotic noise. We imitated the intermittency chaosnoise by the burst noise generated by the Gilbert [4] modelwith 2 states; a laminar state and a burst state. We concluded
that the irregular switching of laminar part and burst part isone of the reasons of the good performance of the chaotic
noise [5]-[7]. However, we often observed that only a verysmall number of solutions are found. We consider that finding
a lot of nearly optimal solutions is important than finding the
optimal solution for difficult problems.
In this study, we propose a method changing the amplitudeof the chaos noise to escape from the area where the network
have almost finished searching. By using this method named as
the hopping chaos, we investigate the performance of Hopfield
1-4244-0921-7/07 $25.00 © 2007 IEEE.

f (P ) =N N

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 ith element of vector P, and N is thesize of the problem. There are many real applications which
are formulated by Eq. (1). One example of QAP is find an
arrangement of the factories to make a cost the minimum. The
cost is given by the distance between the factories and flowof the products between the factories. Other examples are theplacement of logical modules in a IC chip, the distribution of
medical services in large hospital.
Because the QAP is very difficult, it is almost impossible
to solve the optimum solutions in large problems. The largest
problem which is solved by deterministic methods may be
only 24 in recent study. Further, computation times is very
long to obtain the exact optimum solution. Therefore, it isusual to develop heuristic which search near optimal solutions
in reasonable time.
For solving N -element QAP by Hopfield NN, N ×N neurons are required and the following energy function is defined
to fire (i, j)-th neuron at the optimal position:
E=

N
N


i,m=1 i,n=1

wim;jn xim xjn +Nθim xim ,

(2)

i,m=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 ) +
q
(3)
(4)
θim = A + B

1783

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

(5)
where f is sigmoidal function defined as follows:
f (x) =1

1 + exp − xε(6)zim is additional noise, and β limits amplitude of the noise.
We use the method proposed by Sato et al. to decide firingof neurons [8].
III. C HAOS N OISE
In this section, we describe chaos noise injected to the
Hopfield 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 1 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 figure, the chaotic
time series could be divided into two phases; laminar parts ofperiodic behavior 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 finally the three-periodic
window appears. We use the intermittency chaos time series
after the following normalization.
lim (t + 1) =ˆlim (t) − ȳσlIV. A LGORITHM OF H OPPING C HAOSThe Hopfield NN with the noises can find various solutions.
However, the state of the Hopfield NN sometimes stays around
one solution or a group of several solution. We consider thatsuch a behavior is not useful to find the optimal or nearly
optimal solution. So, we propose the algorithm to find manykinds of solutions in large solution space by hopping chaos. If
the network finds the same solution, our proposed algorithm
makes the network search another area by changing the noise
amplitude β. Namely, searching area moves to a new area andthe network searches many different solutions. We denote thestandard value of β as β0 and the bigger β as βjump . The
conceptual figure of searching in solution space is shown in
Fig. 2. If the network finds the same solution as one found
before, β value is changed to βjump . If the network finds a
new solution just after jumping, β value returns back to β0
from βjump . While if the network still find the same solution
after jumping, we increase β according to the following update
equation;β = βjump + (βjump − β0 )(n − 1)(9)where n is the number of times that the network finds the same
solution continuously after jump. Namely, if the network can
not find a new solution, the amplitude β of additional noise
becomes bigger and bigger. We consider that the networkwith constant amplitude chaos noise, the network can notsearch large solution area, on the other hand, the network
search larger area in the solution space by using the proposed
algorithm of hopping chaos.

(8)

where ¯l and σl are the average and the standard deviation of
ˆl(t), respectively

Solution Space(a) Chaos noise.

1

0.9

0.8

0.7

0.6

0.5

0.4

Solution Space
0.3(b) Algorithm of hopping chaos.

0.2

Fig. 2.

0.1
0

100

200

300

400

500

600

700

800

900

1000

Searching in solution space.

αl = 3.8274.
Fig. 1.

Time series obtained from logistic map.

V. S IMULATION R ESULTS
In this section, the simulated results of the Hopfield NN for
QAP with the proposed algorithm are shown.

1784

The first target problem is named as “Nug12” chosen fromthe site QAPLIB [9]. The number of the elements is 12 andthe optimal solution is known as 578. The parameters of the
Hopfield NN are fixed as A = 0.9, B = 0.9, q = 140, andε = 0.02 and the amplitude of the injected noise is fixed as
β0 = 0.55. The iteration number Niteration of the network isfixed as 10000.

800

800

700

700

600

600

500

500

400

400

300

300

200

200

100

100

0
500

600

700

800

900

1000

0
500

1100

600

700

(a) Constant β (conventional).

A. Frequency Distribution
We examine frequency distribution of the obtained solutions. First, we explain how to accept the solutions. The Hopfield NN with the noises can find various solutions. However,the state of the Hopfield NN sometimes stays around one
solution or a group of several solutions. We consider that sucha behavior is not useful to find the optimal or nearly optimal
solutions. So, we take the only-different-solutions method.
Namely, we take into account only the solutions whose firing
patterns have not found ever in each trial. In other words, we
accept only the first time if the completely same firing patterns
appear more than once in each trial.
The results of the frequency distribution when the value of
βjump is changed are shown in Fig. 3. The frequency means
the number of the accepted solutions with the corresponding
costs found during 10000 iterations. We can see that a lot ofsolutions are found for the cases of the proposed algorithm(Fig. 3(b)-(f)). On the other hand, only a very small numberof the solutions are found for the network without proposed
algorithm (Fig. 3(a)). Furthermore, we confirm the performance of the random search network is shown in Fig. 4. The
random search network find many solution, however almostof the solved solutions are very bad. From these results, we
can say that the proposed hopping chaos method is effective
for solving QAP.

800

700

700

600

600

500

500

400

400

300

300

200

200

0
500

1000

1100

100

600

700

800

900

1000

0
500

1100

(c) βjump = 0.65.

600

700

800

900

1000

1100

1000

1100

(d) βjump = 0.7.

800

800

700

700

600

600

500

500

400

400

300

300

200

200

100

0
500

900

(b) βjump = 0.6.

800

100

800

100

600

700

800

900

1000

0
500

1100

(e) βjump = 1.0.
Fig. 3.

600

700

800

900

(f) βjump = 1.5.

Frequency distribution of solutions for Nug12.

800

700

600

500

B. Depth [7]400Many people have evaluated the performance of the Hopfield NN with noises by using only the best solution foundin each trial; time to find the optimal solution, frequency offinding the optimal solution during a given time, average of theminimum cost in each trial, and so on. However, such methods
are not sufficient to reflect the number of the obtained solutions
as shown in the previous subsection. Further, when the network
can not find the optimal solution, the methods using only
the optimal solution do not give a correct evaluation of the
network. Namely, for very difficult problems, we consider that
it is more important to find a lot of nearly optimal solutions
than to happen to find the optimal solution. Therefore, we haveproposed two evaluation methods to appreciate finding a lotof nearly optimal solutions.
1) Depth 1: The first evaluation method Depth 1 is defined asn2Depth 1 ={f (pk ) − D∞ }
(10)

300

200

100

0
500

Fig. 4.

600

700

800

900

1000

1100

Frequency distribution of solutions of random search for Nug12.

solutions and the cost f (pk ) is calculated by Eq. (1) using the
permutation pk corresponding to the k-th accepted solution.
2) Depth 2: The second evaluation method Depth 2 isdefined as
Depth 2 =

n

k∈kg

−

k=0

where D∞ is a constant which is large enough to include
the costs of all solutions, n is the number of the accepted

1785

2

{f (pk ) − Dth }n2{f (pk ) − Dth }

k∈k
/ g

where

kg = {k | f (pk ) ≤ Dth }.

(11)

3.5e+07

This evaluation has an advantage such that we can set thethreshold Dth according to the requirement. We consider thatfinding a lot of bad solutions makes the performance of the
network worse. However, the value of Depth 1 increases even
if the obtained solution is very bad. Hence, in this evaluation,
we not only set up a threshold but give a penalty according
to the cost. Namely, if the network finds a solution with thecost more than a given threshold value, the value of Depth 2
is reduced.
The calculated results of Depth 1 and Depth 2 and thenumber of the solved solution during 10000 iterations areshown in Figs. 5, 6 and 7. The horizontal axis is the valueof βjump . The data at βjump = 0.55 means the networkwith constant amplitude chaos noise. We confirm that the
proposed algorithm gains better performance than the networkwith constant amplitude chaos noise. We also noticed that the
Depth 2 becomes worse as βjump increases. This is because
the network becomes close to the random search network
finding a lot of bad solutions.
Next, we compare the hopping chaos and the hopping
random noise which is the method obtained by replacing theintermittency chaos by uniform random noise. In the result of
the solved solutions, the hopping random noise obtains more
solutions than hopping chaos around βjump =0.6. However, thehopping chaos gains slightly better performance of Depth 2
than the hopping random noise. We consider that the chaotic
nature is important but the hopping concept makes its effectsmaller.

chaos
3e+07

Depth_2

2.5e+07
random2e+07

1.5e+07

1e+07

5e+06

0
0.5

0.55

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

β_jumpFig. 6.

Simulated result of Depth2 (Dth = 812).

8000

number of solution

7000
random
6000

5000
chaos
4000

3000

2000

1000

0
0.5

0.55

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

β_jump4.5e+08

Fig. 7.

Simulated result of number of solved solutions.

4e+08
random3.5e+08

Depth_1

3e+08

2.5e+08
chaos
2e+08

1.5e+08

1e+08

5e+07

0
0.5

0.55

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

β_jumpFig. 5.

Simulated result of Depth1 (D∞ = 1000).

VI. C ONCLUSION
In this study, we proposed the hopping chaos method which
is changing the amplitude of the chaos noise injected to
Hopfield Neural Network to escape from the area where
the network have almost finished searching. By computer
simulation, we confirmed that the network with the proposed
algorithm can find many good solutions.

[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] M.C. Jeruchim, P. Balaban and K.S. Shanmugan, Simulation of Communication Systems, pp.245–247, Plenum Press, New York, 1992.
[5] T. Ueta, Y. Nishio and T. Kawabe, “Comparison between Chaotic Noiseand Burst Noise on Solving Ability of Hopfield Neural Networks,” Proc.
NOLTA’97, vol. 1, pp. 409-412, Nov. 1997.
[6] Y. Uwate, Y. Nishio and A. Ushida, ”Markov Chain Modeling of Intermittency Chaos and its Application to Hopfield NN,” IEICE Transactions
on Fundamentals, vol. E87-A, no. 4, pp. 774-779, Apr. 2004.
[7] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T. Ikeguchi, “Performanceof Chaos and Burst Noise Injected to the Hopfield NN for Quadratic
Assignment Problems,” IEICE Transactions on Fundamentals, vol. E87A, no. 4, pp. 937-943, Apr. 2004.
[8] K. Sato, T. Ikeguchi, M. Hasegawa and K. Aihara, “An optimization method for quadratic assignment problems by chaotic dynamics
and its characterization by Lyapunov dimensions,” IEICE Tech. Rep.,
vol.NLP64-13, pp.13–20, 2001 (in Japanese).
[9] R.E. Berkard, S.E. Karisch and F. Rendl, “QAPLIB – a quadratic
assignment problem library,”

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.

1786

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