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

Solving Ability of Hopfiend NN with Chaos Noise for Maximum Independent Set Problems
Junko Hamao, Yoko Uwate, Takashi Shimamoto and Yoshifumi Nishio
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470,Fax:+81-88-656-7471
Email: jun@ee.tokushima-u.ac.jp

and U3 = {1, 3, 4, 6} are independent sets. U2 and U3 arelocal maximum independent set and U3 is maximum indeIn a certain graph, it is very usuful to find a maximum inde- pendent set.
pandent set because we can apply the maximum independent
set to various engineering problems. However, Maximum
Independent Set Problems is so-called NP-difficult problems
4
5that we can’t solve the problems in time polynomial in nodes.
3
In consequense, we need to find some kind of solving method2that can solve the problems effectively. Today,it has con6
firmed that GA contrast favorably with a heuristics method in1
DIMACS Bench Mark graph. In this study, we use Hopfield
Neural Network (Hopfield NN) with chaos noise in MaxiFigure 1: example graph .
mum Independent Set Problems and confirm the validity, because Hopfield NN with chaos noise achieved concrete results in areas like combinational optimization problems sucu
as TSP and QAP. By computer simulations, we confirm that 3. Method of Maximum Independet Set Problems byHopfield NN with chaos noise can find some good solutions Hopfield NN
better than GA.
In this method, N neurons are needed in the graph that
has N nodes because we related neurons to each nodes and2. Maximum Independent Set Problems
we made these work. And we decided limiting condition andobjective functions for Hopfield NN with chaos noise. TheMaximum Independent Set Problems is one of the combilimiting condition is Eq.(1) because fire neurons don’t havenational optimization problems. The Maximum IndependentEdges. Objective functions are Eq.(2) and Eq.(3) because
Set Problems are finding the largest subset of vertices of asum of firing neurons is to the maximization and the neuron
graph such that none of these vertices are connected by anhas few Edges fire. there is those equations follow. (di,j isedge (i.e., all vertices are independent of each other). If weincidence matrix that is expressed if there is a Edge between
define what Maximum Independent Set Problems is in graphi node and j node 1，if not 0.)
theory, we can say as follows.
N
First, universal set G = (V, E) is defined as undirectedAdi,j xi xj ⇒ 0(1)graph that is formed N -nodes. Where, set V is set of nodes
2 i,jand E is set of Edges. In subset U of V , when there is noEdges in between two nodes that belong to U . Set U is indeNpendent set of G. When set U is independent set and U is notB(1 − xi )2 ⇒ 0(2)contained by another independent sets in G, U is local maxii
mum independent set. If the local maximum independent setN
has maximum nodes, it is maximum independent set.
Cdegree[i] xi ⇒ min(3)In following figure (Fig 1), U1 = {1, 3, 4}, U2 = {2, 6}
i1. Introduction- 331 -

By adove equations, the energy function is Eq.(4) in Hopfield

0.50.4NN with chaos noise.

0.3

0.2

N(4)

chaos noiseNA
E=−di,j xi xj − Bx2i
2 i,jiN −2B + C · degree[i] xi+0.1

0-0.1

i-0.2-0.3

And the energy function in Hopfield NN is following Eq.(5).

-0.4
0

100

200

300

400

500

600

700

800

900

1000

t

N

E=−N


1 
ωij xi xj −θi xi
2 i,ji(5)Compare Eq.(4) and Eq.(5),coupling coefficient ωij andthreshold value θi are discribed such as follow equation.
ωij = −Adi,j (1 − δij ) − B(6)θi = 2B − C · degree[i](7)And, internal state of neurons update asynchronously byEq.(8). In this equation, f is a sigmoid function (Eq.(9)), andzi is chaos noise.
xi (t + 1) = fN
ωij xj (t) + θi + βzi

1
1 + exp(−x/)

(8)

(9)

4. Chaos NoiseIn these years, it is studied that chaos is used effective.
Recently, there are the study using Hopfield NN with chaosnoise for combinational optimization problems as TSP andQAP. And those given good results. Reason, we use the Hopfield NN with chaos noise for Maximum Independent Set
Problems. We show time series of chaos noise the following
figure (Fig 2). Here we adopt the logistick map as an exampleof chaos noise, which is described as follows:zi (t + 1) = αzi (t)(1 − zi (t))
where α is a bifurcation parameter.

5. Graph Normalization
In this study, we propose graph normalization to fix theparameters of Hopfield NN and we tyr to improve the performance of Hopfield NN with chaos noise. We consider thatthe graph characteristics must be an important factor and wenormalized the graphs for fix the parameters. The more eachnode’s Edges abounding, the factors both primary and secondary are added. Moreover, for the parameters independent
the graphs, we divide the factors both primary and secondary
by maximum order of the graph.
6. Analysis Resultif (x) =Figure 2: chaos noise.

(10)

In this study, the problems used here was chosen from thesite DIMACS which collects the bench mark problems. We
carried out computer simulation for brock800 1, brock800 2,brock800 3 and brock800 4. The parameters of Hopfield NN
are fixed as A=2, B=1, C=1 and ε=0.81. The bifurcation parameter of chaos noise is fixed as α=3.828, and the amplitudeof the injected chaos noise is fixed as β=6.12. We had confirme that these graphs are made for hard to find maximum independent set in the graph, and those maximum independent
sets have a much lower rate of nodes than aggregate numberof the graph’s nodes. We show analysis results in Table 1.
(Edges is sum of Edges in the graph, Opt. is the graph’s maximum independent set, Best is best solution in 10 loops, Avg.
is 10 loops average, [1] is thebibliography[1]’s solution andOur is Hopfield NN with chaos noise’s solutions.) We can seethat the case of the Hopfield NN with caoth noise has muchbetter performance than the case of GA both Best and Avg..
embrace that sequence better than another methods both best
and 10 loops average. In this occasion, we decided the bifurcation parameter α=3.828.

- 332 -Table 1

Analysis Result for DIMACS benchmark graphs

DataEdges

Opt.

brock800-1
brock800-2
brock800-3
brock800-4

20750520816620733320764323242526Best
1920
19
19

[1]Avg.
18.7
18.8
18.7
18.5

ourBest Avg.
21 21.0
21 21.0
22 20.7
21 20.7

with Chaotic Noise and Burst Noise for Quadratic Assignment Problem,” Proc. ISCAS’02, vol. 3, pp. 465-468,
May 2002.

7. Conclusions
In this study, we solved Maximum Independent Set Problems by Hopfield NN with chaos noise. And we confirmedthat conclusion in brock800 1, brock800 2, brock800 3 andbrock800 4 (DIMACS benchmark graph) are better. As tasks
for the future, we make consideration Graph Normalizationgraph independent and more effective objective function.
Acknowledgement
This work was party supported by Kayamori Foundation ofInformational Science Advancement’s Resarch Grant.
References[1] Takashi SHIMAMOTO, Seishi KITAYAMA, Manabu
HASHIMOTO and Akio SAKAMOTO “A Genetic Approach with Multi-Decoding for Maximum Indepemdemt
Set Problems,” IEICE Trans. Fundamentals, vol.J83-A,
No.12, pp. 1505-1512, DECEMBER 2000 (in Japanese)[2] J. J. Hopfield, “Neurons with Graded Response Have
Collective Computational Properties like Those of TwoState Neurons,” Proc. Natl. Acad. Sci. USA, vol. 81,
pp. 3088-3092, 1984.
[3] Y. Hayakawa and Y. Sawada, “Effects of Chaotic Noiseon the Performance of a Neural Network Model,” IEICE Tech. Rep., vol. NLP94-39, pp. 47-52, 1994 (inJapanese).
[4] T. Ueta, Y. Nishio and T. Kawabe, “Comparison Between
Chaotic Noise and Burst Noise on Solving Ability ofHopfield Neural Network,” Proc. of NOLTA’97, vol. 1,
pp. 409-412, 1997.
[5] 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.
[6] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T.
Ikeguchi, “Solving Ability of Hopfield Neural Network- 333 -- 334 -