International Symposium on Nonlinear Theory and its Applications
Xi’an, PRC, October 7–11, 2002

Comparison between Chaotic Noise and Iterative Simulated Annealing for
Combinatorial Optimization Problems
Tohru Kawabe∗, Tetsushi Ueta∗∗ and Yoshifumi Nishio∗∗∗∗∗

University of Tsukuba
Tsukuba, 305-8573, Japan
Phone/Fax: +81-298-53-5507
Email: kawabe@is.tsukuba.ac.jp

Abstract
In this paper, we investigate the solving ability of Hopﬁeld neural network with iterative simulated annealing noise for traveling salesman problems (TSPs) andquadratic assignment problems (QAPs) by comparing
with chaotic noise. From several numerical experiments,
we can conﬁrm that the solving ability of iterative simulated annealing noise is almost same as chaotic one.
Key words
Hopﬁeld neural network, Iterative simulated annealing
noise, Chaotic noise, TSP, QAP
1. Introduction

University of Tokushima
Tokushima, 770-8506, Japan
Email: tetsushi@is.tokushima-u.ac.jp,nishio@ee.tokushima-u.ac.jp

ﬁnd the cause of the good performance of chaotic noisefor QAPs. They also indicated that the chaotic noise
could be replaced by the stochastic one whose statisticalcharacteristic is similar to the chaotic one[6, 7, 8, 9].
On the other hand, there is a general agreement that
SA is eﬀective for escaping local minima. But, in ourprevious research, the solving ability of H-NN with simple SA noise is inferior to H-NN with chaotic one[10].
Then we have developed the H-NN with iterative SA
noise and conﬁrmed that the searching ability of global
minimum of iterative SA noise is almost same as chaotic
one, and searching performance for detecting local minima is superior to chaotic one in the case of some small
TSPs[11]. In this paper, therefore, we investigate thesolving ability of iterative SA noise for larger TSPs andsome QAPs by comparing with the chaotic one. By computing simulations we conﬁrm that the iterative SA noise
is eﬀective and can pick up larger number of local minima than chaotic one in both problems. Thus, we cansay that this is superior property of iterative SA noisefor practical use.

One of the key application of Hopﬁeld neural network (H-NN)[1] is combinatorial problems, such as traveling salesman problems (TSPs) and quadratic assignment problems (QAPs). Since there are generally many
local minima in such problems, the state of the H-NN
is often trapped into these local minima. It remains,therefore, an unsettled question how to escape easily
from them and reach global minimum. Many methods to try to overcome this problem have been pro- 2. H-NN with Noise
posed, for examples, Boltzmann machine[2], chaotic neural network[3], simulated annealing (SA)[4], neural netThe dynamics of the H-NN is given as:work with noise[5] and so on. These methods couldbe classiﬁed into two categories from their dynamicalN Nbehaviors[8]. First category is ‘autonomous method’. Inxik (t + 1) = f ωikjl xjl (t) + θik + ε(1)this method, by modifying the characteristic of dymanj=1 l=1
ics of each neuron to stochastic or chaotic one, then thenetwork can search every candidate of global minimum
itself. Boltzmann machine and chaos neural network are where ε is an additional noise. And f is a sigmoidal
included in this category. The other category is ‘nonautonomous method’. By adding noise to each neuron,
the network can avoid to trap the local minima. The
amplitude of noise should be controlled appropriately.
Exmaples in this category are SA, neural network withnoise and so on. Recently, for second category, chaotic
time series which is generated from the logistic map ispaid great attention as a good noise candidates [6, 7].
Hayakawa et al. [6] pointed out that H-NN with the inεtermittent chaos noise near the period-3 window of thelogistic map is more eﬀective for traveling salesman probFigure 1: Neuron modellem(TSP)s. Ueta et al. [8] mentioned that period-5 and
7 are also eﬀective for TSPs. Uwate et al. [9] tried to-447-

function deﬁned as follows:
1xf (x) =1 + tanh
2µTable 1: Scheduling parameters for SA noise
Iteration
T0µ0ρ
1
100.0 100.0 38.0
5100.0 100.0 26.7
10100.0 100.0 16.0(2)where µ is a constant in chaotic noise, but it’s a variable
parameter in SA noise. Fig. 1 shows a conceptual neuronmodel for this H-NN. The decision method of neuron’sstate, ﬁre or not, is used the method in [6, 8].

where T0 is the initial value of temperature and µ0 is
the initial value of µ. And where c is a loop counter and2.1. H-NN with Chaotic Noiseρ is a descent parameter. From former results [10], weFor chaotic noise, we generate a time series by the know the solving ability of H-NN with simple SA noise
is not good and inferior to H-NN with chaotic noise. We
logistic map:
consider one of the reasons for this fact is that chaoticzik (t + 1) = azik (t)(1 − zik (t))(3) noise is always injected all the simulation time but theamplitude of SA noise is decreased as the temperature iswhere a is a bifurcating parameter of the logistic map. reducing. We, therefore, propose the iterative SA-noise
Then the dynamics of H-NN with chaotic noise is given for improving normal SA noise. In the iterative SA noise,when the temperature becomes zero, it is initialized andas :repeated procedure of simulated annealing till terminal
condition is satisﬁed. Hence, annealing is done moreNN xik (t+1) = fωikjl xjl (t) + θik + βzik (t) (4) than twice per one trial. Thus, we call this noise iterative
SA noise. Fig. 3 indicates time serieses of iterativej=1 l=1
10 SA noise, and scheduling parameters of iterative SA
noise are shown in Table 1.
where β is amplitude of noise which is design parameter.
Fig. 2 shows an example of the periodic-3 intermittent
chaotic noise (t = 1 ∼ 1000).
252015The value of noise

101.5
10.5

0-5-10-150z(t)5-20-0.5-25200-1-1.5-2400

c600

800

1000

Figure 3: Time serieses of iterative-10 SA noises
200400t

600

8001000

Figure 2: Time series of periodic-3 intermittent chaos
3. Simulation results and discussion
3.1. Results of TSP
For solving N -city TSP, N × N neurons are required
andthe following energy function is deﬁned to ﬁre (i, j)
H-NN with SA is also based on sigmoidal function andneuron
at the optimal position:
has a noise term (ε) depends on Gaussian distributionof which mean is 0 and standard deviation is δ/πT .
N NNWhere δ is a empirical parameter and T is a control
E =wi,k,j,l xi.j xk,l −θi,j xi,j(6)parameter, called temperature, which tends to zero aci,j k,li,jcording to a diterministic “annealing schedule”.
The value of µ which is a parameter of sigmoidal func- where wi,k,j,l is a weight coeﬃcient between (i, j) andtion is determined by “sharpening schedule”. As the (k, l) neurons. They are deﬁned asvalue of ε is closer to 1, neuron’s input-output function iswi,k,j,l = −A{δi,j (1 − δk,l ) + δk,l (1 − δi,j )}closer to step function. We employ annealing and sharpening schedules as follows:−Bδi,j (δl,k+1 + δl,k−1 )(7)
2.2. H-NN with iterative SAT= T0 exp−cρ, µ = µ0 exp−cρ

where A > 0, B > 0, δ is Kroneker’s delta and θi,j :=(5) A + B is the thresholdi,jvalue.

-448-

11

"10-city"

0.8

0.6

0.6

the performance between SA noise and chaotic one, wesee that performance about γ between iterative SA noiseand chaotic one are almost same. On the other hand,values of σ are diﬀerent between chaotic and iterative
SA noises. Iterative SA noise can pick up local minima
more than chaotic one. We can say that this is superior
property of iterative SA noise for practical use.

"22-city"

yy

0.8

0.4

0.4

0.2

0.2

00

0.2

0.4

x

0.6

0.8

1000.2

0.4

x

0.6

0.8

1

Figure 4: 10-city and 22-city TSPs

CityNo.

Table 3: Results of TSP
iterative SA noise
Chaotic noise
Itera. γ (%)σPeriod. γ (%)
σ1089
14.0
7847.5586
10.2
581
8.8
162
6.4
391
13.1
1047
8.2
760
8.3
549
8.6
553
8.8
120
4.3
350
10.3

Although detection for the global mimimum is impor10
tant for solving TSP, it should be added that how many
minima are detected within a reasonable trial time isalso important, because the dynamics of this H-NN with
22
noise is nonautonomous and the network is not converge
to the local minima and global minimum. We, therefore,
use two performance criterion for investigating the solving abilities of H-NN with iterative SA noise and choatic3.2. Results of QAP
one as follows:
Results of QAP In this section, simulation results ofQAP are shown. The QAP is one of the most diﬃcult
number of success trials
γ :=× 100 (%)(8) combinatorial problem and it is to ﬁnd the permutation
total trial numbervector p which minimize the objective function f (p) under given distance matrix C and ﬂow matrix D. The
σ := average number of detected local minima
objective function of QAP is deﬁned as(9)NN 
f (p) :=
Ci,j Dp(i).p(j)(10)
where ”success trials” means the trial that could detectglobal minimum. One trial is deﬁned as 1000 times of
i=1 j=1transfer of every neurons’ input-output signal and total
trial number is 100. We investigate solving abilities of where Ci,j and Di,j are the (i, j)-th elements of C andabove mentiond two type of noise for TSPs indicated in D respectively, and p(i) is the i th element of p.
The QAP’s energy function for H-NN could be exﬁg. 4 from the points of the two performance criteriapressedas TSP’s, eq. (6), the weight, wi,k,j,l , is a bit
mentiond above eqs. (8) and (9). The values of parameters for chaotic noise, a and β in eqs. (3) and (4), are diﬀerent. It’s described astuned as shown in table 2. The initial values of all neuCi,j Dk,lrons and noises are chosen at random, and the value of wi,k,j,l = −2 Aδi,j (1 − δk,l ) + Bδk,l (1 − δi,j ) +q
parameters of energy function are tuned adequetly ac(11)cording to simulation conditions.
where A > 0, B > 0 and q > 0 are constants, and δi,jis Kroneker’s delta. And where θi,j := A + B is thethreshold value. Two problems, “Nug5” and “Nug12”,
Table 2: Values of parameters for chaotic noiseare chosen here from QAPLIB[12].
CityPeriodicParameters
numbernumber
1. [Nug 5]
7a = 3.7001, β = 0.47
 0 4 3 5 2 
105a = 3.7379, β = 0.47
3a = 3.8250, β = 0.47
 4 0 6 2 1 
7a = 3.7001, β = 0.47
C =  3 6 0 5 7 
225a = 3.7379, β = 0.45
5 2 5 0 33a = 3.8252, β = 0.42
2 1 7 3 0
 0 3 1 2 4  3 0 2 1 4 
Table 3 shows the best solving abilities of H-NN withD =  1 2 0 5 3 
iterative SA noise and H-NN with chaotic noise respec2 1 5 0 1
tively. From table 3, we can see that solving abilities
4 4 3 1 0of iterative-5 and 10 SA noise are more eﬀective thaniterative-1 SA noise which is a normal SA method in The global optimum is known as 158.
both performace criteria, γ and σ. When we compare-449-

2. [Nug 12]
C0
 1
 2

 3

 1

 2=  3

 4

 2

 3
 45
0
 5
 2

 4

 1

 0=  0

 6

 2

 1
 1
11012212332
3450
3022204500

4. Conclusion
2101321243232
30000055222

3 1 2 32 2 1 2
1 3 2 10 4 3 2
4 0 1 23 1 0 12 2 1 01 3 2 15 1 2 34 2 1 2
3 3 2 12 4 3 241002200005250 10
2 10 020510 010010555145104 2 3 43 3 2 32 4 3 2
1 5 4 33 1 2 32 2 1 21 3 2 10 4 3 2
4 0 1 23 1 0 12 2 1 01 3 2 10622040552 10 000051
10 10 5
10 00500200
35 10
30 10


54 
3 
2 

4 

3 2 

1 
3 
2 1 0
1 15 0
2 20 55 15 42 30 50 50 55 00 2

In this paper, we propose the H-NN with iterative SA
noise and investigate the solving abilities of this H-NN
for TSPs and QAPs. Then we conﬁrm that H-NN with
iterative SA noise is as eﬀective as H-NN with chaotic
noise in these combinatorial problems. As future works,
suitable parameter set of energy function for iterative
SA noise is required to ﬁnd. In addition to this we needto analyze the solving abilities of iterative SA noise andchaotic one with a theoretical approach.
References[1] J.J. Hopﬁeld and D.W. Tank, “Neural computation
on decisions in optimization problems”, Biological
1Cybernetics, Vol.52, pp.147-152, 1985.
0 [2]D.H. Ackley, G.E. Hinton and T.J. Sejnowski, “A2 
learning
algorithm for boltzmann machines”, Cog
5 
nitive Science, Vol.9, pp.147-169, 1985.
1 
0  [3] K. Aihara, “Chaotic neural networks”, in H.
DKawakami (Ed.), Bifurcation phenomena in non3 linearsystems and theory of dynamical systems,0 (World Scientiﬁc), pp.143-161, 1997.
0 
0  [4] S. Kirkpartick, C.D. Gelatt, Jr. and M.P. Vecchi,
2 
Optimization by Simulated Annealing, SCIENCE,
0Vol.220, No.4598, pp.671-680, 1983.
[5] K. Onodera, T. Kamio, H. Ninomiya and H. Asai,“Application of hopﬁeld neural networks with exterThe global optimum is known as 578.
nal noises to TSPs”, Proc. NOLTA’95, pp.275-378,
1995.
In these problems, we do not only use γ but Av which[6]M. Hayakawa and Y. Sawada, “Eﬀects of the chaotic
means the average value of every minimum costs foundnoise on the performance of a neural networkin trials[9]. The results of H-NN with iterative SA noisemodel”, Tech. repo. IEICE, Vol.NLP94, No.39,
are summarized in Table 4. The results of H-NN with
pp.47-52,
1994 (in Japanese).
the periodic-3 intermittent chaos noise (a = 3.8276) are[7] M. Hasegawa, T. Ikeguti, T. Matozaki, K. Aihara,
also shown for comparison.
“An analysis on adding eﬀects of nonlinear dynamics for combinatorial optimization”, IEICE Trans.
Fundamentals, Vol. E80-A, No.1, pp.206-213, 1997.
Table 4: Results of QAP[8] T. Ueta, E. Okahisa, T. Kawabe and Y. Nishio,“Construction of eﬀective noise for TSP”, Proc.
Nug
iterative SA noise
Chaotic noise
IECON2000, pp.2135-2140, 2000.
No.
Itera. γ (%)
Av
γ (%)
Av
[9] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T.
1070
159.2
Ikeguchi, “Solving ability of hopﬁeld neural network
5562
160.6
72
158.9
with chaotic noise and burst noise for quadratic as1
8198.3signment problem”, Proc. IEEE ISCAS2002, Vol.3,
106597.3
pp.465-468, 2002.
1253609.9
3612.010–[10] K. Shimoji, T. Kawabe, T. Ueta and Y. Nishio,“Solving abilities of hopﬁeld neural network withchaotic noise versus with simulated annealing for
traveling salesman problem”, Proc. AFSS2000,
pp.909-913, 2000.
From table 4, we can also say that solving abilitiesof iterative-5 and 10 SA noise are more eﬀective than [11] T. Kawabe, T. Ueta and Y. Nishio, “Iterative simulated annealing for hopﬁeld neural network”, Proc.
iterative-1. From comparison with the chaotic noise, theIASTED MS2002, pp. 59-62, 2002.
performance of iterative SA noise and chaotic one are almost same. But, it is remains the room for improvement [12] R.E. Berkard, S.E. Karisch and F. Rendl,of solving ability of iterative SA noise. We need to ﬁnd“QAPLIB - A quadratic assignment problem lia suitable parameter set of energy function for iterativebrary”, http://www.opt.math.tu-graz.ac.at/qaplib
SA noise. To settle this diﬃculty is a future problem.
-450-