平成22年度電気関係学会四国支部連合大会

309

18-10
Eﬀect of Chaos Noise to Matrix Elements withHopﬁeld Neural Network for QAP
Yasuyuki Yoshida
Shuichi Aono
Yoko Uwate
Yoshifumi Nishio(Tokushima University) (Shizuoka University) (Tokushima University) (Tokushima University)

Although it would be possible to solve combinatorial optimization problems with a huge number of elements if wehave inﬁnite long time, it does not make any sense for practical problems. The Hopﬁeld Neural Network (NN) is usedby many researchers for solving combinatorial optimizationproblems [1]. However, the solutions are trapped into thelocal minima. To obtain an optimal soltion, the solution
needs to avoid the local minima.
In this study, we propose an algorithm that pouringchaos noise to matrix elements of quadratic assignment
problem (QAP) with Hopﬁeld NN. It supports to avoid
local minima and to ﬁnd good solutions. By carrying out
computer simulations, we conﬁrm that the chaos noise has
a good eﬀect to avoid local minima and achieves a good
performance to ﬁnd a good solution of QAP.

2 Solve to QAP with Hopﬁeld NN
The QAP of N -element is expressed by two N × N matrixes, the distance matrix D and the ﬂow matrix F . The
objective function C(p) is given as follows;
C(p) =NN∑∑

Dij Fp(i)p(j) ,(1)i=1 j=1

where Dij and Fij is the (i, j)-th elements of D and F ,p(i) is the (i)-th element of vector p, N is the size of problem, respectively. A good solution becomes close to theminimum value of C(p).
For solving N -element QAP by Hopﬁeld NN, N × N
neurons are required. The states of N × N neurons are
asynchronously updated as following Eq. (2).
xim (t + 1) = f (N∑wim;jn xim (t)xjn (t) − θim + βzim (t)),

j,n=1(2)where zim is additionnal chaos noise, β limits the amplitude
of noise. In this study, we use the noise poured to matrix
elements of QAP.

3 Chaos noise
In this study, we use the time series of the chaos generated by the logistic map as a noise. The logistic map isgiven as following equation.
xn (t + 1) = αxn (t)(1 − xn (t)),
The chaotic sequence is normalized byxn (t) − x̄,x̂n (t) =σx(3)(4)where x̄ is the average of xn and σx is the standard devision of xn . In this study, we use the bifurcation parameter
α = 3.828. The bifurcation parameter α = 3.828 is the intermittency chaos near the three-periodic window obtained
from the logistic map. It is reported that the intermittency chaos near the three-periodic window obtained fromthe logistic map gains good performance for combinatorial
optimization problems [2]. The chaotic sequence is shownin Fig. 1.

The initial conditions are diﬀerence when the noise ispoured to the Hopﬁeld NN or matrix elements.
1.5

10.5x(t)1 Introduction

0-0.5-1-1.5

0100

200300400500600

700800

900

1000

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

4 Simulated results
In this study, we use the problem, “Nug12” fromQAPLIB. The optimal solution of this problem is known“578”. The results are summarized in Table 1. Here, thenumber of iterations is from 1000 to 5000 times. The results are average values of 10 trials. The prameter of Hopﬁeld NN is A = 0.9, B = 0.9, q = 140 and ϵ = 0.02.
In Table 1, the conventional method is Hopﬁeld NN withchaos noise only for state (2). The proposed method 1 isHopﬁeld NN with chaos noise poured to two matrixes. The
proposed method 2 is Hopﬁeld NN with chaos noise poured
to distance matrix.

Table 1: Solving to “Nug12 .
Iteration
1000
2000
3000
4000
5000

Conventional
method
643.8
640.6
635.6
633.8
631.6

Proposedmethod 1
638.4
628.6
628.0
625.6
624.6

Proposedmethod 2
623.6
623.2
620.2
620.2
617.4

From this table, we can conﬁrm that the proposed algorithm exhibits better performance than the conventional
method and the distance matrix with chaos noise is thebest performance at every iterations.

5 Conclusions
We have investigated the eﬀect of chaos noise poured
to the matrix elements with Hopﬁeld NN for the QAP. By
carrying out computer simulations, we have conﬁrmed thatthe chaos noise had a good eﬀect to avoid local minimum
problems and achieved a good performance to ﬁnd goodsolutions of the QAP.
As the future subject, we will investigate the eﬀect topour diﬀerent noises to the elements.

References[1] Y. Uwate and Y. Nishio, “Search of Many Good Solutions of QAP by Connected Hopﬁeld NNs with Chaos
Noise,” P roc.of N CSP ′ 04, pp. 145-148, Mar. 2004.
[2] Y. Hayakawa and Y. Sawada, “Eﬀects of the chaotic
noise on the performance of a neural network model foroptimization problems,” Physical Review E, vol.51, no.4,
pp.2693-2696, 1995.