2004 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'04)
Hawaii, USA, Mar. 5-7, 2004.

Search of Many Good Solutions of QAP by Connected Hopfield NNs with Chaos Noise
Yoko Uwate and Yoshifumi Nishio
Dept. of Electrical and Electronics Engineering,
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470
FAX:+81-88-656-7471
Email: {uwate,nishio}@ee.tokushima-u.ac.jp

1. Introduction
Combinatorial optimization problems have an ability todescribe various actual problems mathematically. However,there is a large disparity between to describe problems mathematically and to solve them. In order to solve a very difficult
problem, it takes a long time (e.g. more than the cosmos age)by current computer system. That makes no sense actually.
The method using the Hopfield Neural Network (NN) [1]has been proposed for combinatorial optimization problems
as an approximate mean based on search. In this method,
if we choose connection weights between neurons appropriately according to given problems, we can obtain a good solution by the energy minimization principle. However, thesolutions are often trapped into a local minimum and do notreach the global minimum. In order to avoid this criticalproblem, several people proposed the method adding somekinds of noise to the Hopfield NN. Many researchers suggested that intermittency chaos near the three-periodic window of the logistic map gains the best performance [2]. In order to make clear the reason why intermittency chaos is better
than fully developed chaos, we have investigated the performance with the burst noise generated by the Gilbert modelfor traveling salesman problems [3, 4] and quadratic assignment problems(QAP) said to be one of most difficult to solvein the combinatorial optimization problems [5]. In those results, we have confirmed that the Hopfield NN with noise canfind a lot of various solutions. It is very important to find a
lot of various solutions when the networks do not know theoptimal solution. However, the Hopfield NN with noise hassome problems: “The solution of the network keeps staying
at the same state during a certain period.” “The solution ofthe network comes into the states found before a number oftimes.” By avoiding these problems, the network could find a
lot of nearly optimal solutions.
In this study, we connect some Hopfield NNs with chaosnoise like hierarchical networks in order to find a lot of nearly
optimal solutions. The weights of neurons are configured as
the same and each network operates by itself. We propose amethod connecting some Hopfield NNs with chaos noise andevaluate this method by solving QAP. In the simulated results,
we confirm that the connected Hopfield NNs with chaos noise
can search a broad range of energy function and find manynearly optimal solutions.

2. Solving QAP with Hopfield NN
Various methods are proposed for solving QAP which isone of the NP-hard combinatorial optimization problems.
QAP is expressed as follow: given two matrices, distance matrix C and flow matrix D, and find the permutation p whichcorresponds to the minimum value of the objective function
f (p) in Eq. (1).
f (p) =N NCij 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 the vector p, and N
is the size of the problem. There are many real applications
which are formulated by Eq. (1). One example of QAP is tofind an arrangement of factories to make a cost the minimum.
The cost is given by the distance between the cities and theflow of the products between the factories.
Other examples are the placement of logical modules in anIC chip, the distribution of medical services in a large hospital, and so on.
Because the QAP is very difficult, it is almost impossible tosolve the optimum solutions in larger problems. The largestproblem whose optimal solution can be obtained may be only
36 in recent study [6]. Further, computation time is very longto obtain the exact optimum solutions. Therefore, it is usual
to develop heuristic methods which search nearly optimal solutions in reasonable time.
For solving an N -element QAP by the Hopfield NN,
N ×N neurons are required and the following energy func-- 145 -tion is defined:
E=1.5

NN



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

θim xim .

(2)

0.5i,m=1

θimz(t)0The neurons are coupled each other with the synaptic connection weight. Suppose that the weight between (i, m)-thneuron and (j, n)-th neuron and the threshold of the (i, m)-thneuron are described by:wim;jn = −2 A(1 − δmn )δij
Cij Dmn(3)+Bδmn (1 − δij ) +q-0.5-1-1.5

-2
0

100

200

300

400

500

600

700

800

900

1000

tFigure 1: Chaos noise. α=3.8274.

= A+B

where A and B are positive constants, q is a normalization parameter to correspond given problems, and δ ij is theKronecker’s delta. The states of N ×N neurons are asynchronously updated due to the following difference equation:
N
xim (t + 1) = g wim;jn xjn (t)j,n=1(4)4. Connected Hopfield NNs

In this study, we connect some Hopfield NNs with chaosnoise like hierarchical networks in order to find a lot of nearly
optimal solutions. We consider that the connected Hopfield
NNs with chaos noise can search a broad range of energyfunction.
The connected Hopfield NNs with chaos noise is shown in− θim + βzim (t)Fig. 2. In this figure, ● show the firing neuron, ⊗ show theconnection neuron. The weights of neurons are configured as
the same and each network operates by itself. We consider
where g is a sigmoidal function defined as follows:that reflecting the firing pattern of one network to the firing1
 x
g(x) =(5) pattern of the next network by connecting with the neurons
between the two networks is important. The K-th network
1 + exp −εselects one neuron from the firing neurons of the (K-1)-thnetwork
at random, and we connect the selected neuron withzim is an additional noise, and β limits the amplitude of thetheneuron
at the same position as the selected neuron in thenoise.
K-thnetwork.
The output of the connected neuron in the KAlso, we use the method suggested by Sato et al. (1.1 inthnetwork
issetto zero.
[7]) to decide firing of neurons.
3. Chaos Noises
In this section, we describe chaos noise injected to the Hopfield NN. The logistic map is used to generate chaos noise:ẑim (t + 1) = αẑim (t)(1 − ẑim (t)).

(6)

Varying parameter α, Eq. (6) behaves chaotically via aperiod-doubling cascade. When we inject chaos noise to theHopfield NN, we normalize ẑ im by Eq. (7).
zim (t + 1) =ẑim (t) − z̄σz(7)Where z̄ is the average of ẑ(t), and σ z is the standard deviation of ẑ(t). Figure 1 shows an example of the time series of
the chaos noise.

- 146 -(K-1)-th
networkK-th
network

Nn-th
network

Figure 2: Connected Hopfield NNs.

140
1 network120

2 networks
3 networks

Frequency

100

12 networks

80
60
40
200
240000260000280000
Cost

300000320000Figure 3: Frequency distribution of solutions.
5. Simulated Results
The problem used here was chosen from the site QAPLIB
which collects the bench mark problems. We carried out computer simulation for “Tai12a” using connected 2 〜20 Hopfield NNs with chaos noise. The global minimum of thisproblem is known as 224416. The parameters of the Hopfield NN are fixed as A = 0.94, B = 0.94, q = 30000 and
ε = 0.02 and the amplitude of the injected chaos noise isfixed as β = 0.5. The total number of updating the network
is 12000. For example, the case of connecting 4 networks, thenumber of updating the per 1 network is 3000, and the total
number of updating the 4 networks is 12000.
Next, we explain how to accept solutions. The connected
Hopfield NNs with the chaos noise searches various solutions. However, the state of the Hopfield NN sometimes stays
around a group of several solutions. We consider that such abehavior is not useful to find the optimal or nearly optimalsolutions. So, we take the only-different-solutions method.
Namely, we take into account the solutions which have notfound ever.
5.1. Frequency distribution
The results of the frequency distribution when the someHopfield NNs with chaos noise are connected is shown inFig. 3. For comparison, the result of the only 1-Hopfield NN
with chaos noise is shown in this figure. The horizontal axis iscost calculated by Eq. (1) and vertical axis is frequency. The

frequency means the number of the accepted solutions withthe corresponding costs found during 12000 iterations. We
can see that a lot of the nearly optimal solutions are found forthe case of connected some Hopfield NNs with chaos noise.
When the number of connection Hopfield NNs with chaosnoise is large, the networks can find many good solutions.
On the other hand, only a small number of the nearly optimalsolutions are found for the only 1-Hopfield NN with chaosnoise.
5.2. Depth 1
Until now, we have proposed two methods [8] to appreciatefinding a lot of nearly optimal solutions.
The first evaluation method Depth 1 is defined as
Depth 1 =n

{f (pk ) − D∞ }2(8)k=0where D∞ is a constant which is large enough to include thecosts of all solutions, n is the number of the accepted solutions and the cost f (pk ) is calculated by Eq. (1) using thepermutation p k corresponding to the k-th accepted solution.
The calculated result of Depth 1 is shown in Fig. 4. The
horizontal axis is number of connected networks and verticalaxis is Depth 1. In this figure, Depth 1 becomes larger as
the number of the connected networks increases. We consider
that the connected Hopfield NNs with chaos noise can obtain
good performance to find a lot of solutions.

- 147 -

2e+105.5e+1205e+12-2e+104.5e+12-4e+10Depth_2

Depth_1

6e+124e+12-6e+103.5e+12-8e+103e+12-1e+11

2.5e+12-1.2e+112e+122468101214

1618-1.4e+1120

Number of networks{f (pk ) − Dth }2−{f (pk ) − Dth }2(9)k∈k/ g

where

8

10

12

14

16

18

20

results, the connection method got good performance to finda lot of nearly optimal solutions of QAP. We confirmed thatthe connected Hopfield NNs with chaos noise can search abroad range of energy function and find many nearly optimalsolutions.

The second evaluation method Depth 2 is defined ask∈kgn

6

Figure 5: Depth 2 for Tai12a (D th = 285000).

5.3. Depth 2n

4

Number of networks

Figure 4: Depth 1 for Tai12a (D ∞ = 340000).

Depth 2 =2

Acknowledgement
This works was partly supported by Kayamori Foundationof Informational Science Advancement’s Research Grant.

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

References

This evaluation has an advantage such that we can set thethreshold Dth according to the requirement. We consider
that finding a lot of bad solutions makes the performance ofthe 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 the cost more than a given threshold value, the value ofDepth 2 is reduced.
The calculated result of Depth 2 is shown in Fig. 5. The
horizontal axis is number of connected networks and verticalaxis is Depth 2. In this figure, Depth 2 becomes smaller as
the number of the connected networks increases. This resultshows that the networks find a lot of nearly optimal solutions
as well as far optimal solutions. From this result, we can seethat there is an appropriate number of connecting networks tofind only good solutions.
6. Conclusions
In this study, we connected some Hopfield NNs with chaosnoise like hierarchical networks in order to find a lot of nearly
optimal solutions. The weights of neurons are configured as
the same and each network operates by itself. We proposed
method connecting some Hopfield NNs with chaos noise andevaluated this method by simulating QAP. In the simulated[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 Chaotic Noise on thePerformance of a Neural Network Model,” IEICE Tech. Rep.,
vol. NLP94-39, pp. 47-52, 1994 (in Japanese).
[3] T. Ueta, Y. Nishio and T. Kawabe, “Comparison Between
Chaotic Noise and Burst Noise on Solving Ability of Hopfield Neural Network,” Proc. of NOLTA’97, vol. 1, pp. 409-412,1997.
[4] S. Baba, N. Urushihara, Y. Nishio, T. Kawabe and T. Ueta,“Solving Ability of the Hopfield NN with Burst Noise,” Proc.
of AFSS’00, vol. 2, pp. 914-917, 2000.
[5] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T. Ikeguchi, “Solving Ability of Hopfield Neural Network with Chaotic Noiseand Burst Noise for Quadratic Assignment Problem,” Proc. ISCAS’02, vol. 3, pp. 465-468, May 2002.
[6] R. E. Berkard, S. E. Karisch and F. Rendl, “QAPLIB – A
Quadratic Assignment Problem Library,”
http://www.opt.math.tu-graz.ac.at/qaplib[7] 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).
[8] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T. Ikeguchi, “Performance of Chaos Noise Injected to Hopfield NN for QuadraticAssignment Problem,” Proc. NOLTA’02, vol. 1, pp. 267-270,Oct 2002.

- 148 -