社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

スケーリング則を利用した
ノイズ注入型 Hopﬁeld NN による組合せ最適化問題の解法
多田佳史†

上手洋子†

西尾芳文†

† 徳島大学工学部 電気電子工学科 〒 770-8506 徳島市南常三島 2-1
E-mail: †{y-tada,uwate,nishio}@ee.tokushima-u.ac.jp
あらまし

組合せ最適化問題は、問題の規模が大きくなると、解の総数が指数関数的に増加し、総解を求める方法を用いると、計算時間が長くなり、実質的には計算不可能である。組合せ最適化問題の解法のひとつとして、Hopﬁeld

NN を用いる方法が提案されている。しかし、この方法を用いると、ネットワークは局所解に陥ってしまい、最適解を求めることができない。ネットワークの局所解脱出のために、ニューロンにノイズを注入する方法が提案されている。本研究では、解探索能力の向上のために、スケーリング則を利用したノイズ注入型 Hopﬁeld NN を提案する。コンピュータシミュレーションを用いて、提案手法による二次割り当て問題の解探索能力について調査を行う。
キーワード

Hopﬁeld NN, Chaos noise, QAP, Scaling law

Hopﬁeld NN Using Scaling Law for Quadratic Assignment Problem
Yoshifumi TADA† , Yoko UWATE† , and Yoshifumi NISHIO†† Faculty of Engineering, Tokushima University, 2-1 Minami-Josanjima, Tokushima, 770-8506 Japan
E-mail: †{y-tada,uwate,nishio}@ee.tokushima-u.ac.jp
Abstract If the scale of the combinatrial optimization problem becomes large, the problem can not be solvedby method of searching all solutions. Hopﬁeld Neural Network is one of the important tool of solving combinatorial optimization problem. However, the network ﬁnds a local minimum, and can not escape from there. Many
researchers proposed the method adding some kinds of noises to the Hopﬁeld Neural Network. In this study, we
propose the injecting scaling law noise to Hopﬁeld Neural Network for improvement of the ability. We investigate
eﬀective search with Hopﬁeld Neural Network using scaling law for quadratic assignment problem.
Key words Hopﬁeld NN, Chaos noise, QAP, Scaling law1. ま え が きにおいて最適解を求めるには有効ではない。
スケールフリーネットワークは Barabasi らによって発見さ組合せ最適化問題の解法として、Hopﬁeld Neural Network

れ [4]、ネットワークの性質を評価する研究が多岐の分野にわ(abbr. NN) [1] を用いる方法が提案されている。この方法はたり行われた。図 1 にスケールフリーネットワークモデルを示

Hopﬁeld NN のエネルギー最小化原理にしたがい最適解を求めす。スケールフリーネットワークにおいて、多くのノードは少ることができる。しかし、多くの場合、解が局所解に陥ってし数のリンクしか存在せず、少数のノードのみが多くのリンクをまい、局所解から脱出することができず最適解を求めることが持っているネットワークである。つまり、少数の重要なノードできない。この問題を回避するために Hopﬁeld NN にさまざまが多くのリンクを持っている。このノード数とリンク数の関係なノイズを注入する方法が提案されている。早川と澤田らはロを図 2 に示す。数学的にはスケールフリーネットワークはべきジスティック写像より得られる 3 周期窓付近のインターミッテ法則によって特徴づけられる。スケールフリーネットワークはンシーカオスノイズを用いると最も良い性能を示すと報告して多くの研究分野 (工学、経済学、社会科学等) で確認されていいる [2]。我々は過去の研究において Hopping chaos と呼ばれる。我々は同様にニューラルネットワーク分野の発展に重要なる一定の場所に留まるとノイズの振幅が変化するノイズを提案役割を果たすと期待している。

した [3]。この方法を用いることにより、ネットワークは多くの本研究ではスケーリング則に乗っ取った振幅の異なるノイズ最良解を求めることができた。しかし、この方法は難しい問題を Hopﬁeld NN に注入する方法を提案する。ノイズを注入す

—1—

E=NN
∑
∑

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

N∑θim xim .

(2)

i,m=1

ニューロン間は互いにシナプス結合によって結合されている。

(i,m) 番目のニューロンと (i,n) 番目のニューロンの結合係数、(i,m) 番目の閾値は以下の式 (3) で記述される。

{Cij Dmn
wim;jn = −2 A(1 − δmn )δij + Bδmn (1 − δij ) +q}(3)
θim = A + B

図 1 スケールフリーネットワークモデル(4)

ここで、A と B は正の定数。δij はクロネッガーのデルタであnumber of links

る。N ×N ニューロンの状態の非同期更新は以下の式 (5) で表される。

(N∑

xim (t + 1) = f)wim;jn xim (t)xjn (t) − θim + βzim (t)j,n=1(5)f はシグモイド関数で式 (6) で示される。

number of nodes

f (x) =

図 2 スケールフリー分布

ることは局所解脱出に対し有効である。しかし、同時にエネル
ギー最小化原理のじゃまをしていると考えられる。もし、振幅の小さいノイズを重要なニューロンに注入し、振幅の大きなノイズを重要ではないニューロンに注入すると、最適解付近を効率良く探索することができると考えられる。本研究ではスケーリング則に乗っ取ったノイズを注入した Hopﬁeld NN によるQAP の解探索能力について調査を行う。コンピュータシミュ

1()
1 + exp − x²

(6)

3. ノイズの生成
この節では、Hopﬁeld NN に注入するカオスノイズについて説明する。本研究ではロジスティック写像 式 (7) により生成される 3 周期窓付近のインターミッテンシーカオスノイズを使用する。

ˆlim (t + 1) = αl (t)(1 − ˆlim (t)).

(7)

レーションを用いて提案手法が QAP の解法として有効である
コントロールパラメータ αl を変化させると式 (7) は周期倍分ことを確認する。

岐を経てカオス的にふるまう。さらに、ロジスティック写像は2. QAP を解く Hopﬁeld NN

よく知られているように周期窓の直前にインタ−ミッテンシー

NP-困難な組合せ最適化問題である QAP を解くためのさまカオスと呼ばれる間欠性のバーストを作り出す。図 3 に 3 周期ざまな方法が提案されている。工場配置問題を例にして QAP窓直前のインターミッテンシーカオスの例を示す。図 3 より、を説明する。この問題は各工場を各都市にどのように配置すれカオス時系列はほぼ 3 周期の周期的なふるまいをするラミナーば最も効率が良いかを求める問題である。条件は distance 行列部と分布が不変区間にひろがるバースト部から構成されている

D と ﬂow 行列 F の二つの行列によって与えられ、順列 P はことがわかる。コントロールパラメータ αl の値を少しずつ大式 (1) の関数 f (p) の値を小さくすることに該当する。

きくしていくとラミナー部の占める割合が増えていき最後にはf (P ) =N ∑N∑

3 周期窓が表れる。
Cij Dp(i)p(j) ,(1)i=1 j=1

Cij と Dij は C,D 行列の i,j 番目の要素、p(i) はベクトル p のi 番目のニューロン、N は問題のサイズである。これらは式 によって公式化され、多くの現実問題に応用されている。Hopﬁeld

NN で要素数 N の QAP を解くには N ×N のニューロンが必要である。この時のエネルギー関数は以下の式 (2) で定義される。

インターミッテンシーカオスを注入する時は、式 (8) の正規化を行う。

lim (t + 1) =ˆlim (t) − ȳσl(8)¯l と σl は ˆl(t) の平均と標準偏差である。

4. スケーリング則ノイズ
QAP を解く場合、与えられた問題に応じて重要な都市とあまり重要ではない都市が存在するのではないかと考えられる。

—2—

110.90.9

Linear function

0.80.80.70.7β0.60.6

Scale-rule

0.50.50.40.40.30.30.20.20.1

13...........

5N-1NnC
0100200300400500

600700800900

1000

図5

スケール則に従ったノイズの振幅t
図 3 インターミッテンシーカオス時系列 (αl = 3.8274)

は、各更新において、最初に発火するニューロンの存在する列を記憶する。何度か更新を行い、最も最初に発火するニューロ

つまり、各問題を解くにあたりいくつかの重要となる都市が存ンが多く発生した列を右から一列目に並べ替える。次に、多く在し、それをうまく配置することがより良い解を求めるのに重最初に発火するニューロンが発生した列を右から二番目の列に要だと考えられる。ノイズを注入することにより、ネットワー並べ替える。この作業を続けると、右側から最初に発火するクの最小化原理を妨げると考えられ、重要な都市を示すニューニューロンの発生頻度が多い順番に列が入れ換わる。

ロンには大きな振幅のノイズを注入しないほうが良いと考えられる。本研究では、スケーリング則と重要な都市をコンセプト

5. シミュレーション結果にスケーリング則ノイズを注入する方法を提案する。図 4 に N

この節では 12 要素の QAP へのスケーリング則ノイズを注

要素の QAP を解く Hopﬁeld NN モデルを示す。各列のニュー入した Hopﬁeld NN のシミュレーション結果を示す。問題はロンは各都市を示す。ニューロンに注入するスケーリング則ノ

QAP LIB より N ug12 という問題を選択した。この問題の最イズの振幅は式 (9) によって決定する。

β=U適解は 578 である。Hopﬁeld NN のパラメータは A = 0.9,nC(9)B = 0.9, q = 140, ε = 0.2 に設定した。シミュレーション結果
は 10000 回更新を 100 回行い、その平均を示す。従来の方法のU は 0 から 1 の間の定数であり、nC は列の数である。線形関ノイズの振幅を調節するパラメータは β0 = 0.6 である。ロジ数との比較のために、式 (9) より得られる最大値 βmax は線形

スティック写像のコントロールパラメータは αl = 3.8274 であ関数と同じ値になるように設定する。さらに、従来の方法と比る。スケーリング則と線形関数の最大値 βmax = 1.0 に設定し較を行うために、スケーリング則の平均値と従来の方法の振幅た。スケーリング則のパラメータは U = 0.6 に固定した。

β0 をそろえる。
表 1 シミュレーション結果 (Nug12)
12City更新回数
N

1factory

2N

従来スケール則

線形1000 632.96

617.96623.86

2000 623.30

613.32616.123000 619.82

608.50612.544000 616.18

605.78609.685000 613.56

603.02607.546000 612.68

600.94606.207000 611.74

598.84604.94

8000 610.48597.82604.12

9000 610.30596.74603.24

10000 609.96595.84602.36

次に、T ai12a という問題に挑戦した。この問題の最適解は224416 である。Hopﬁeld NN のパラメータは A = 0.9, B = 0.9,
図 4 N 要素の QAP を解く Hopﬁeld NN モデル.

q = 16000, ε = 0.02 である。この問題では 40000 回更新を 100回行い、その平均をシミュレーション結果として示している。ましかし、QAP を解くにあたり、どの都市が重要な都市なのか? 我々にはどの都市が重要な都市なのか知る方法がない。そこで、各列を並び替える方法を提案する。このアルゴリズムでた、Hopﬁeld NN 以外のパラメータは β0 = 0.5, αl = 3.82676,βmax = 1.3, U = 0.5 である。
表 1,2 に N ug12 と T ai12a の各更新回数において、求めら—3—

シミュレーション結果 (Tai12a)
従来

250000スケール則線形4000 252624.44

242148.18

244849.92

8000 251337.90

239571.98

242123.36

12000 250291.38

238373.66

240738.44

16000 249638.16

237750.34

239504.80

20000 249520.72

237236.76

238803.02

24000 249495.62

236733.68

238198.66

28000 249458.04

236347.96

237838.76

32000 249335.58

236021.02

237469.98

36000 249228.40

235834.22

237209.98248000

Average of solutions

表2
更新回数

Conventional

246000244000242000240000Linear function

238000236000

23400000.1

0.20.340000 249225.84 235549.42 237121.14
図80.40.5

U0.60.70.80.91

シミュレーション結果 (Tai12a)

れた最も良い解の平均値を示す。これらの結果より、提案手法は従来の方法より良い結果を得ることができた。また、スケー

くなり線形関数に相似するあたり以外では線形関数より良い性

リング則ノイズは線形ノイズよりも良い結果を得ることができ能を示している。また U = 1.0 は線形関数と同様の意味を示した。N ug12 ではすべての方法で最適解を求めることができた。ている。

しかし T ai12a については従来の方法では最適解を求めること

6. ま と めはできなかったが、提案手法ではスケーリング則、線形ノイズ
本研究では、重要な都市とスケーリング則を元に提案したス共に最適解を求めることができた。
最後にスケーリング則の勾配を変化させた性能を確認する。

ケーリング則ノイズを Hopﬁeld NN に注入する手法を提案し

図 6 より U を変化させ U の値が大きくなるにつれて、スケーた。また、ニューロンの各列を並び替える方法を組み合わせる

リング則は線形関数に類似することが確認できる。

ことにより、重要な都市には振幅の小さなノイズ、あまり重要ではない都市には振幅の大きなノイズを注入した。コンピュー1タシミュレーションを用いて QAP をスケーリング則ノイズを0.9注入した Hopﬁeld NN を用いて解探索能力の調査を行った。提0.8

案手法が QAP を解く手法として有効であることを確認した。

0.7

文

β 0.6

U = 0.1
U = 0.3
U = 0.50.5

U = 0.70.40.3

U = 0.90.20.1

linear123456789101112

Number of city

図 6 U を変化させたノイズの振幅

610

Conventional

Average of solutions

608

献[1] J.J. Hopﬁeld, “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, “Eﬀects of the chaotic noise on
the performance of a neural network model for optimization
problems,” Physical Review E, vol.51, no.4, pp.2693–2696,
Apr. 1995.
[3] Y. Tada, Y. Uwate and Y. Nishio, “Eﬀective search withhopping chaos for Hopﬁeld neural networks solving QAP,”
Proc. ISCAS’07, pp.1783-1786, May 2007.
[4] Barabasi, Albert-Laszlo and A. Reka, “Emergence of scaling
in random networks,” Science, 286:509-512, Oct. 1999.
[5] R.E. Berkard, S.E. Karisch and F. Rendl, “QAPLIB – aquadratic assignment problem library,”
http://www.opt.math.tu-graz.ac.at/qaplib

606

Linear function

604
602
600
598
596
594
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.91

U

図 7 シミュレーション結果 (Nug12)

図 7、8 の結果より、スケーリング則において U の値が大き—4—