2011 International Workshop on Nonlinear Circuits,Communication and Signal Processing
NCSP'11, Tianjin, China, March 1-3, 2011

Search of Good Solutions of QAPs by Hopfield Neural Networkwith Chaos Noise to Matrix Elements
Yasuyuki Yoshida† , Shuichi Aono‡ , Yoko Uwate† and Yoshifumi Nishio††Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470 FAX:+81-88-656-7471
Email: {yasu0824, uwate, nishio}@ee.tokushima-u.ac.jp‡Shizuoka University
3-5-1 Johoku Naka Hamamatsu, Japan
Phone:+81-53-478-1237 FAX:+81-53-478-1269
Email: aono@tzasai7.sys.eng.shizuoka.ac.jp

Abstract

avoid local minima and achieves a good solution of the QAPs.
In addition, we investigate the eﬀect of chaos noise comparIn this study, we propose a novel algorithm pouring the chaos ing to random noise.
noise to the matrix elements for solving the quadratic assignment problems (QAPs). We investigate the eﬀect of chaos
2. Solve to QAP with Hopfield NN
noise poured in the matrix elements with Hopfield Neural
Network (NN). In addition, we investigate comparing chaos
The QAP of N-element is expressed by two N ×N matrices,noise and random noise. By carrying out computer simula- the distance matrix D and the flow matrix F. The objective
tions for various problems, we confirm that the chaos noise function C(p) is given as follows;
has a good eﬀect to avoid local minima and achieves to aN ∑Ngood solution of the QAPs.
∑C(p) =(1)Di j F p(i)p( j) ,i=1 j=1

1. Introduction
Although it would be possible to solve combinatorial optimization problems with a huge number of elements if we haveinfinite long time, it does not make any sense for practicalproblems. In several approximation methods, the solutions
are trapped into local minima and do not escape. In order toavoid this critical problem, technical methods to escape fromlocal minima are required. Many researchers have proposedthat the approximation method with the chaos noise [1][2].
The chaos noise is directly poured to the algorithm in these
proposed methods.
In this study, we propose an algorithm that pouring thechaos noise to the matrix elements of quadratic assignment
problems (QAPs). It supports to find good solutions andavoid local minima. In the past study, we have investigatedthe eﬀect of chaos noise poured in the city placement of traveling salesman problems (TSPs) with 2-opt algorithm [3][4].
From results of the past study, we confirmed that the chaosnoise supports to find the good solutions and avoid the localminima.
The QAP belongs to a class of NP-hard in the computational complexity. Solving for QAPs, it is reported that thegood solution is achieved to used by neural network as othereﬃcient method [5][6].
By carrying out computer simulations for various problems, we confirm that the chaos noise has a good eﬀect towhere Di j and Fi j is the (i, j)-th elements of D and F, p(i) isthe (i)-th element of vector p, N is the size of problem, respectively. A good solution becomes close to the minimum
value of C(p). One example of QAP is to find the arrangement of factories to make a cost the minimum. The cost is
given by the distance between cities and the flow of products between factories. Because the QAP is very diﬃcult, it
is almost impossible to solve the optimal solutions in large
problems.
For solving N-element QAP by Hopfield NN, N × N neurons are required. The energy function is following Eq. (2).
E=N ∑N∑i,m=1 j,n=1N∑

wim , x jn +θim , xim .

(2)

i,m=1

The neurons are coupled each other with following weight
between the (i, m)-th neuron and the (i, n)-th neuron andthreshold the (i, m)-th neuron are described by:{}
Di j Fmn
wim; jn = −2 A(1 − δmn )δi j + Bδmn (1 − δi j ) +,qθim = A + B,(3)(4)

where A and B are positive constants and δi j is the Kronecker’s delta. The states of N × N neurons are asyn-- 300 -chronously updated as following Eq. (5).
xim (t + 1) = fN(∑

4. Simulation Results)
wim; jn xim (t)x jn (t) − θim + βzim (t) ,(5)4.1. Simulation 1j,n=1

In this section, the simulation results of Hopfield NN with
two kinds method of the chaos noise to matrix elements aresummarized in Tables 1 and 2. Here, the problems used from1QAPLIB [7] are “Nug12” and “Nug15”. The optimal solution
f (x) =,(6)1 + exp(− ϵx )of “Nug12” is known “578” and “Nug15” is known “1150”.
zim is additional chaos noise, β limits the amplitude of noise. The number of iterations is from 1000 to 10000 times. TheIn this study, we use the noise poured to matrix elements of results are shown by the values of total cost. The parameterof Hopfield NN is A = 0.9, B = 0.9, β = 0.7, q = 140 andQAP.
ϵ = 0.02.
In these tables, the conventional method is Hopfield NN
3. Chaos Noise
with chaos noise only for state Eq. (5). The propsed method
In this study, we use the time series of the chaos generated 1 is the chaos noise poured to matrix elements once before
by the logistic map as a noise. The logistic map is given as executing Hopfield NN. The propsed method 2 is the chaosnoise poured to matrix elements when the neurons of Hopfollowing equation.
field NN are updated. The states of the neurons are updated
xn (t + 1) = αxn (t)(1 − xn (t)).
(7) many times. Then, the chaos noise is poured to the original
matrix elements at every time. In the proposed methods 1
The chaotic sequence is normalized byand 2, the chaos noise is poured to distance matrix and flow
matrix.
xn (t) − x̄x̂n (t) =,(8)σxTable 1: The result for Nug12.
where x̄ is the average of xn and σ x is the standard division of xn . In this study, we use the bifurcation parameter
Iteration Conventional Proposed Proposed
α = 3.828. The bifurcation parameter α = 3.828 is the inmethod
method 1 method 2termittency chaos near the three-periodic window obtained
1000
643.8
706.4
638.4
from the logistic map. It is reported that the intermittency
5000
631.6
684.6
624.6
chaos near the three-periodic window obtained from the lo10000
629.6
680.0
620.6
gistic map gains good performance for combinatorial optimization problems [1]. The chaotic sequence is shown in Fig.
1.
The initial conditions are diﬀerence when the noise ispoured to the Hopfield NN or matrix elements.
Table 2: The result for Nug15.
where f is sigmodal functions following Eq. (6).

1.5

Iteration

1

1000
5000
10000x(t)0.5Conventional
method1273.81240.81240.8Proposedmethod 1
1321.41304.81304.8Proposedmethod 2
1281.21255.01241.8

0-0.5

-1

-1.5

0

100

200

300

400

500

600

700

800

900

t

Figure 1: The time series of logistic map (α = 3.828).

1000

From Table 1, we can confirm that the proposed method 2
is better performance than the conventional method and theproposed method 1. This means that the chaos noise is eﬀective to avoid the local minima. From Table 2, we can confirm
that the result of the proposed method 2 is similar to the conventional method.
4.2. Simulation 2- 301 -In this section, the simulation results of comparing the proposed method 2 to random noise for two QAPs are summarized in Tables 3 - 6. Here, we use two problems “Nug12”
and “Nug15” from QAPLIB [7]. The result of “Nug12” issummarized in Tables 3 and 4 and “Nug15” is summarizedin Tables 5 and 6. The simulation conditions are the same as“Simulation 1”.
In these tables, Chaos noise 1 is Hopfield NN with chaosnoise poured to two matrices, 2 is Hopfield NN with chaosnoise poured to distance matrix, 3 is Hopfield NN with chaosnoise poured to flow matrix, Random noise 1 is Hopfield NN
with random noise poured to two matrices, 2 is Hopfield NN
with random noise poured to distance matrix, 3 is Hopfield
NN with random noise poured to flow matrix.

Table 6: Solving for Nug15 with random noise.
Iteration
1000
5000
10000

Table 3: Solving for Nug12 with chaos noise.
Iteration
1000
5000
10000

Chaos
noise 1638.4
624.6
620.6

Chaos
noise 2623.6
617.4
614.8

Chaosnoise 3
627.0
618.4
616.2

Randomnoise 11322.01288.01274.6

Randomnoise 21324.61284.01274.2

Randomnoise 31324.61284.01274.6

Errorave =Ave − Opt
× 100,Opt(9)

Errormin =Best − Opt
× 100,Opt(10)

where Opt shows the optimal solution of “Nug15” fromQAPLIB [7]. A known optimal total cost of “Nug15” is1150. The horizontal axis shows the iteration of Hopfield NN.
The vertical axis shows the error. The result of the conventional method is Fig. 2, the chaos noise to two matrices is Fig.
3, the chaos noise to flow matrix is Fig. 4, the random noise
to two matrices is 5, the random noise to flow matrix is Fig.
6.

Table 4: Solving for Nug12 with random noise.
Iteration
1000
5000
10000

Randomnoise 1
764.0
754.2
737.2

Randomnoise 2
752.4
751.2
759.2

Randomnoise 3
747.8
729.0
730.2

Table 5: Solving for Nug15 with chaos noise.
Iteration
1000
5000
10000

Chaos
noise 1
1281.21255.01241.8Chaos
noise 2
1281.21255.01241.8Figure 2: Conventional method.

Chaos
noise 3
1273.81240.81229.4From these figures, we can confirm that the Hopfield NN
with chaos noise exhibits better performance than the conventional method and Hopfield NN with random noise. Inaddition, we can also confirm that the Hopfield NN with
From these tables, we can confirm that the conventional chaos noise to matrix elements is able to avoid the local minmethod exhibits better performance than the random noise ima comparing the conventional method and the Hopfield NN
poured to matrices. However, we can confirm that the chaos with chaos noise.
noise is better performance than the random noise and theconventional method.
5. Conclusion
The simulation results of typical examples of the error with
iteration are shown in Figures 2 - 6. The errors show theWe have investigated the eﬀect of chaos noise poured to thevalues between the average or the minimum values and the matrix elements with Hopfield NN for the QAP. By carrying
optimal solution calculated by the following equations.
out computer simulations, we have confirmed that the chaos- 302 -

Figure 6: Random noise to flow matrix.

Figure 3: Chaos noise to two matrices.

Acknowledgment
This work was partly supported by JSPS Grant-in-Aid for
Scientific Research 22500203.
References[1] Y. Hayakawa and Y. Sawada, “Eﬀects of the chaotic noiseon the performance of a neural network model for optimization problems,” Physical Review E, vol. 51, no. 4,
pp. 2693-2696, 1995.
[2] T. Ueta, Y. Nishio and T. Kawabe, “Comparison between
Chaotic Noise and Burst Noise on Solving Ability ofHopfield Neural Networks,” Proc. of NOLTA’97, vol. 1,
pp. 409-412, 1997.

Figure 4: Chaos noise to flow matrix.

[3] Y. Yoshida, S. Aono and Y. Nishio, “Eﬀect of Chaos
Noise on City Placement by Using 2-Opt Algorithm forTSPs,” Proc. of NCSP’09, pp. 357-359, Mar. 2009.
[4] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D.
B. Shmoys, The traveling salesman problem, John Wileyand Sons, Chichester, 1985.
[5] Y. Tada, Y. Uwate and Y. Nishio “Solving Ability of Hopfield Neural Network with Scale-Rule Noise for QAP,”
Proc. of ISCAS’08, pp. 105-108, May 2008.
[6] Y. Uwate and Y. Nishio, “Search of Many Good Solutionsof QAP by Connected Hopfield NNs with Chaos Noise,”Proc. of NCSP’ 04, pp. 145-148, Mar. 2004.

Figure 5: Random noise to two matrices.

noise had a good eﬀect to avoid local minimum problems andachieved a good performance to find good solutions of theQAP.
As a future subject, we will investigate the eﬀect to pourdiﬀerent noises to the matrix elements and changing each parameter.

[7] R. E. Burkard, S. E. Karisch and F. Rendl,“QAPLIB-A Quadratic Assignment Problem Library,”
http://www.opt.math.tu-graz.ac.at/qaplib/- 303 -