自 己 組 織 化 す る、­、-圃‘ューラノレネ、ソ松山

トと最適化問題
泰男

￨111
川
11川
11川
11川
11111
川
川
11川
11川|川
11 川
11川
11川
11川
11川
11川|川
11 川
11川
11川
11川
11川
11川
11川
11川|川
11 川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11l川|川
川
11川
11川
11川
11川
11川
11川
11川
11川|川
11 川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11川
11川
11川
11川
11川|川
11 川
11l川
川
11川
11川
11川
11川
11川
11川
11川
11川|川
11 川
11川
11川
11川
11川
11川
11111
川
川
111111
川
川|川
11 川
11川
11川
11川
11川
11川川
11l目1刊111
川
l川
川
11川
11川
11111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11111
川
川
11川
11川
11川
11川
111111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
11川
11川11川
11川
11川
11川川
11山
1'， M ー 1 ;s===O ， … ， t) ， k=O ， … ， K ー1.

はじめに

(3)

は加法的なペナルティであり，

h叫 =hnL(x削 lDm ， X'; n=O ， … ， Nー 1 ;m=O ,ニユ}ロコンビュテーションにおいては，数多くの計., M-I ;s=O , …, t) , I=O , …, L- 1.

算素子が一体となって l つの問題を解く.この計算素子(4)は多入力・ 1I主力多分岐であり，互いに結合されてネッは乗法的なペナルティである.

トワークを構成する.各素子は(人工)ニューロンと呼は，ばれ，価である.もし，非一様な場合には確率に従った重みを生理学的ニューロンとの類似性は実に多様である.各ニューロンが数学モテ.ルとして非常に抽象化されE (・)に等かける.ている場合にはむしろエージェント[ 1]という，より3. 競合，広い意味の用語が適切となる.
本稿で、は，ニューロコンビュテーションのうち，特に(2) 式における Z い)

データが一様に与えられる場合には ，協調，自己組織化

いま第 t 回目の学習において，データベクトルが=自己組織化を最適化問題に当てはめることを行ない，事Sη がネットワークに提示されたとする.

例を与える.以下での内容はいずれもここで初めて与え対して各ニューロンは競合 (competition) を起こし，るものである.

次のような最優位ニューロン(勝者，W m ( ω= argminDn
0 孟， m<M

コストを最小化するように学習を行なう.このコストはまず第 11こニューロンによができる(競合学習).

W~ln)=w~ω 十 AWm(n)fn=f(x n , Wm)(1)

ここに Sη (n=O ， …， N-I) は学習に用いられるデー

wm(m=O ,"', M-I)

(6)

この AWm(n) は最適化の手法によりいろいろなものがあるが，ここでは最急降下法を用いる.

はニューロンの状態(重み)ベクトルで、ある.すなわち，ニューロ(5)

この最優位ニューロンは，自分の状態を更新することるデータの近似度を反映する.

タベクトルであり ，winner) が決定される.

2. ペナルティのあるコストニユ}ラルネット全体は，このデータに

t1 w間〈 ω= 一 (6/2) (òDn/òwm( 川(7)各ニューロンは，自分が最優位となったときにあらかンの集合 {W眠}は，コスト L; ;:':Jfn を小さくするようじめ決められた自分のパートナーを活性化する(協調学にデータ集合 {x n } を近似する.このとき，このコスト習).の最小値に近い値を実現するエユーロン状態は多様であw 円ι=W tν/Y，~ {J Y {隅 (n)}m(n))+α ./Y (m(n)} t1w ν〆YN (m(n)}る.ここで，それらの内からさらに制約条件についても(8)これを小さい値として実現するものを選ぶ.
N‑lN‑lrK-l、 IL-l

ここに a、D =L; Dn=L;1 ん + L; ~nkgnd( r hnLJ(2H./Tlm(n)lは，学習パラメータである .

乗法的ハンディキャップ h nL はコンセプト(カテゴリ )[2]を扱うことを可能にする.すなわち，もし h九，
ηz

=∞なら

ここ tこt1w ﾁ/".

g叫 =gnk(Xn ， Wm ， X'; n=O ， ・・・ ， Nー 1; m=O ,=0 (implici
tconcept learning).

J Y (叫【 n)}(9)まつやまやすお茨城大学

工学部

干 316 日立市中成沢町 4ー 12-1
1992 年 7 月号

情報工学科とする.

これに対して，より強いコンセプト学習もある.
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(17)3311.
0t+，~.
A'"(m(nll=1.
0t，~

グ (m(n))‑<<' ，~

d1.
Oνグ 1m切))~- .
A'"Im(n))(explicitconcept learning) (10)

[Step 3J
都市集合 X の要素をランダムに l つ選び，これを Zπ上のような，競合・協調・カテゴリ分けによるニューとする.そして，ラルネット学習は教師なしの学習であり，この学習は制

1.
Om(n)

約条件と協調関係を満たすように進行する.これが自己組織化 (self-organization) であり，その構造はしばしばユークリッド空間に写影される.

このようなデータ圧縮された図形は特徴マップ (feature map) [3J ,[4J と呼ばれる.

通常これは，自己組織化の結果を視覚的に理解するため，あるいはその後段における決定過程のために生成される.次節ではこの特徴マップを，ユーグリッド空間における巡回セールスマン問題に適用することを行なう.

4.

=argmin ん+な)
O~玉 m<Mとなるニューロンを選択する.

[Step4J
Wm(n) および H=1 となるニューロン Wk に対して，t
Wi，+I=Wk+ ε ta(xη -Wι (n)) ‑a{wk+1(t)- 2W k (t) 十 Wk-1 (t)}とし、う更新を行なう.

[Step 5Jコストを計算し ，et.f( ・ ， t+1).<<t 刊に対して e t +1 .f(・ ， t+1 )， <<t +1を求め ，ユークリッド空間における巡回セー上のアルゴリズム中の関数は，次のように設定されてL 、る.

ルスマン問題
いま N個のデータはt=t+1 として Step 2 へ戻る.

[e の更新式]
2 次元平面上の国定された都市であり ， M個のニューロンは閉曲線上に配置されているとする.このとき，巡回セールスマン問題 (TSP ，lingsalesperson problem)

traveｭ

は，次のようなコストを競合学習により最小化する問題と解釈される.
lY'‑1

ft
>jt-1 , gt<gt-1 のとき ， e t + 1 = εヘ
上記以外のとき
ε t+1= 〆一行 (ft- ft‑1)/ft‑1.

(14)[.<の更新式](15)

ぷ +l=.<t+rl(gt-g ト 1)/gト 1

D =L:(fn+.<g)(11)

ん =f(x n ，1.0π)=llxη- 1.O m I1 2(12)n=Og( 1.Oo， ・， WM-1)=1filmm-W附111 2 ， (modM)(13)
このとき，学習アルゴリズムは次のようになる.

[その他の更新式]

f(k , t)=exp{ -k 2 /2 σ2 (t) )}(16)

L(t)=3 σ (t )，(17)

σ (t)= σ (O)(I-s)Lt/MJ

図 1 は，上の方法によりセールスマンの経路を自己組織化している過程である.その結果は，図 2 のようになる.この方法による解は ， e t とがとを前もって決めた[アルゴリズム TSPJ

方法で変化させる場合 [ 5J よりも良好な近似解を与え[Step 1Jる(表 1 ).

次のようなデータと初期値が与えられる.
・都市の集合X={xo , …, Xi , …, XN •}, XiER25̲

運搬車経路問題

運搬車経路問題 (VRP ，・ニューロンの状態ベクトルの集合
W(t)={wo (t)， … ， Wj(t) ， … ， WM_l(t) }， ωj( t)ER2

ただし各 Wj (t) は ， R2 における閉曲線上に配置し，vehicleroutingproblem)

は，より複雑な TSP と解釈される.

[VRPJ 複数台の運搬車に対して 1 つの発着都市が与j はその上での順番に対応しているとする.

えられている.また，一般の都市にはあらかじめ指定さ・初期学習率れた分量の荷物がある.このとき，運搬車の積載制限を。

・ベナノレティ項結合係数の初期値
・勝者分配重み
ここに ，.
<0a(k , t)H( Ikl 豆 L(t))

H( ・)は，インジケータ関数である.

学習により，各都市が互いに相異なる勝者をもつようにニューラルネットが構成されたら，学習を終了する.

332 (18)

この問題は相当に複雑であるが，ここではさらに込み入った問題(拡張された VRP) を扱う.

[EVRP1J 上の問題に対して各都市にラベル(コン[Step2J

そうでなければ Step 3 へゆく.

満たし，かつ総走行距離が最小となる経路を求めよ.

セプト[2 J) を与える.

各運搬車には，このラベルにより訪問できる都市と，そうでない都市が決められる.

[EVRP2J EVRP 1 に対して，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

さらに各運搬車のオベレーションズ・リサ}チ

図 1

自己組織化の過程 (t=20000)
表 1l

最適

解 [6 J

図 2

最終結果 (t=82042)

USA-532 セットに対する解と計算時間の比較

巡回距離|計算時間|

使用計算機

I8.7汚別o (伶0 蜘 I 5 時問粉 I CYBER_25
却
2お50 Super白r∞coompu叫te町r

Pr山

本手法 I 9 附 (2.8%)

1 4 時間28分

最大経路長を小さくする.

[EVRP3J EVRP 1 に対して，SunSPARCstation1を比較したものである.この表からわかるように運搬寧さらに各運搬車の当たりの経路長と積載荷量の均等化は，総経路長を犠牲のもとに可能となる.

積載荷量を均等化する.

[EVRP 4J EVRP1 に対して，さらに EVRP 2 とEVRP 3 の制約を課する.
この問題はアルゴリズム TSP を，運搬車の台数分だけのユユーロン環の自己組織化に置き換えることによって解ける.このとき，都市に与えられたラベルと最大経路長および最大積荷量の最小化は，1(4) 式の乗法的コストに反映させる.

6. 多重降下競合学習による最適化特徴
マップ
アルコリズム TSP におけるコストは，ハンディキャップを含んでいるが，全体としては 1 重の最適化である.これに対して，異質な最適化の合成となっている多重降下コストに関する競合学習がある[ 7]. このよう図 3 は EVRP 2 に対する自己組織化の結果である.

な多重降下競合学習においては，レベルの異なる複数種

運搬車 1 は， 0 の都市のみを通過できる.運搬車 2 は，類の特徴マップが自己組織化される.

O またはムの都市を通れる.残りの運搬車は， 0ム口のメントの最適グループ化により生成されるパターンであどの都市も通過できる.表 2 は各種 EVRP の計算結果

表 21 つはデータ且レ

EVRP 1-4 の実験結果の比較

lEVRP11EVRP21EVRP31EVRP4総巡回 I 10.2421 I
1.4
987I¥ 1I13.7066I13.3郎
経路長.l V."::;' ，，，，，.L

経路長 l経路長 2経路長 3

経路長 4荷物量 1
荷物量 2荷物量 3
図 31992 年 7 月号

EVRP2 の近似解荷物量 411.'....UIJ..J. I V V V¥0.
83852.
02944.
42002.
95422.
2
3892.
85973.
3
5203.
0
4813.
6
4
533.
1
5723.
4
2883.
4
7533.
53263.
10
993.
1
9793.
5193

118442304
612863598465595649668

41562
96806538161001© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

33(19)3

図 4る.またもう 1 つは，

図 5

CCITT の原画像最適化特徴マップのエッジを間ヲ I \，、た図グループ化によって得られたスーパーベクトルを学習データとしたときに生成される特徴マップである.このような 2 つの特徴マップを生成する
学習アルゴリズムは次のとおりである.
[多重降下競合学習アルゴリズム][Step 1J
トレ}ニングデータとグループ化の初期パターン

Uo ，そして重みのスーパーベクトノレ集合が与えられる.

[Step2J
グループ化されたデータの一部が学習機構に与えられる.

[Step 3J(部分最適化による最適化特徴マップの更新)
その部分に対して，コストがより小さくなるように再グループ化をする.

[Step4J(重みのスーパーベクトルの更新)
部分最適化の対象となったス}パーベクトルにより，重みを更新する.

情報庄縮された画像を変形した結果あらかじめ決めておいた繰り返し停止条件が満たされ

W::/n)=W~( 川 +et(y(v)-W~(n))'

v= 則的)

(18)
ここに

図 B

v はグループ化によって生成されたスーパーた場合には，学習を終了する，そうでなければ，各種の学習パラメータを更新して，Step 2 へゆく.

上のような多重降下競合学習アルゴリズムを画像処理

ベクトル ， w~(n) は競合の勝者である重みスーパーベに適用してみる.

クトノレ，そして U は形状の正規化である.にある原画 (8 bits/pix) である.図 5 は，最適化によ[Step4'J (重みスーパーベクトルの特徴マップの更るピクセルグループ化 (Step 3) により生じる特徴マッ新)

プから，さらに不要なエッジを問ヲ I \，、た図である.図 B

W~(n) の位相的近傍である重みスーパーベクトルには再生画像である

図 4 は CCITT の画像データベース(32.0 dBat0.
96 bits/pix).

ただ対しても(1 8) 式と同様な更新を行なう.

しこの図 6 においては，図 5 のパターンを用いて外部か[Step 5Jらの強制情報により変形を行なっている.すなわち，図334(20)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

4 の現画像においては口を開けているが，図 6 の再生画論とソフトウェア作成に感謝する.

像においては，ロを閉じている.これは，自己組織化と参考文献

外部知性との結合を行なった初めての例である.
多重降下競合学習アルゴリズムは，このほかには複数[1] Minsky , M.:The Societ
y ofM問d. Simonの「子 vehicleJ が地方をまわり， 1 台の「親 vehicleJandSchuster , New York , 1987 (安西祐一郎訳，がそれらの子をめぐるとし、う問題に当てはめることができる.

心の科学，産業図書，

1990)
.

[2] Natarajan , B.K.:MachineLearning.Morｭ7. 最小学習原理 (minimum leamingprinciple)
本稿では学習にもとづく最適化および自己組織化のう
ち，特に競合を用いるものを取り上けγこ・計算論的立場に立っと，学習とは Minsky [1]のように，r どのよ

うにして新しいユ且ーロン集合(エージェント集合)を991.
ganKaufmann , SanMateo , 1[3] Wilshaw , D.J.andMalsburg , C.vonder:
How patterned neuralconnections can be setoc. Lond.
up by self‑organization. Proc. R. SB. , Vo1.1
94 (1976) , 43 ト 445.

[4] Kohnen , T.:Self‑Organization and AssoｭciativeMemory. Springer , Berlin , 1
984.

作り，また古いニューロン集合を変えるのか」という見[5] 松山泰男:自己組織化できるニューラルネットと方になる.このとき，教師なし学習である競合学習の解

ユーグリッド空間におけるいろいろな巡回セールスマ

釈をもう少し進めてみると，次のことがし、える.

r 集団

において学習が進行する場合には，その最も適切な部分集団が学習を行ない，にとどめている J.

全体としての変更を必要最小限

このことは変分原理と共通であり，(2)式あるいは (1 1)式に反映されている.

パックプ

ロパゲーションのような教師ありの学習においても，やはり教師信号と比較される部分集団が学習を担当していン問題.電子情報通信学会論文誌，[6] Padberg , M.andRinaldi , G.:Optimizationofa532‑city symmetric traveling salesmanes. Let. ,problem by branch and cut. O r. R
V01.6., 1(1987).

[7] 松山泰男:多重降下競合アルゴリズムと並列部分最適化.

る.

[謝辞]黒津泰，森浮幸一，古屋貴子の諸氏による討

D-II , 3(1991)
.

416‑
425.

情報処理学会論文誌，

31 , 3 (1991) , 3
33‑

344.

『会員名簿』刊行についてのお願い
名簿刊行委員会1992年版の会員名簿を作成することになりました.会員原簿のコピーを，会員の方々にお送りいたしますので，変更事項につきましては赤字ご訂正ください.
ご変更の有無にかかわらず，原簿はすべて，学会事務局宛ご返送くださるようお願 L 内、たします.

なお，会員名簿は，会員の方々への限定刊行で，有料頒布となります.原簿返送の際，併せてご購入予約を頂ければ幸いです.年内刊行を予定いたしておりますのでどうぞよろしくお願 L 、 L 、たします.

1992 年 7 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(21)335