ホップフィールドネットワーク(7)
ホップフィールドネットワーク(+α)に最適化問題を解かせる一例に巡回セールスマン問題があります。巡回セールスマン問題は、複数の場所(都市)を巡る距離を最小にする問題で、どの場所も1回しか訪れず、全ての場所を必ず訪問する、という制限がかかっています。2つの場所の間には距離が設定されています。このような問題がホップフィールドネットワークで解くことが出来るそうです。これからそれについて考えていきます。
簡単にするために、場所は5か所とします。まず、巡回セールスマン問題の解をニューラルネットワークの状態として表すことを考えます。場所の名前をA,B,C,D,Eとします。解は、例えば、B→D→A→E→Cかもしれません。そこで、5×5のマス目を考え、縦(行)が場所を回る順番を示し、横(列)が場所(A,B,C,D,E)を示すとします。
このような表し方では、先ほどの例のB→D→A→E→Cは、下の図のように表されます。
このマス目の1つ1つをそれぞれ1個のニューロンに対応させることにします。そしてマス目が黒いことをニューロンの出力が「1」、白いことを「−1」で示すことにします。ニューロンの番号は下の図のように付けます。
1つの行には「1」は1つしか存在しません。1つの列にも「1」は1つしか存在しません。これを式で表すと「1」でないところは皆「−1」なので1つの行に「1」が1つしか存在しないことを数式で表すと、
- ・・・・(15)
- ・・・・(16)
- ・・・・(17)
- ・・・・(18)
- ・・・・(19)
これらの式を最小化の条件に変換するには、それぞれの式の右辺を左辺に移項して、全体を2乗します。
- ・・・・(20)
- ・・・・(21)
- ・・・・(22)
- ・・・・(23)
- ・・・・(24)
これらの式がそれぞれ最小になる時(実数の2乗なので最小は0)に上の(15)〜(19)の式が成り立つことは明らかです。(20)〜(24)の式を全て足したものを最小にすることは、(20)〜(24)の式をそれぞれ最小にすることに等しいです。よって
-
- ・・・・(25)
とした場合、を最小にするという条件は、1つの行には「1」は1つしか存在しない、という条件に等しいことになります。(25)を展開すると
- ・・・・(26)
の形になっていることが分かります。よって、の値を適切に設定することにより式(25)はエネルギー
- ・・・・(14)
の形に変換することが出来ます。ということは、このようにして定めたシナプス係数を持つホップフィールドネットワーク(+α)は、図9において1つの行には「1」は1つしか存在しない状態で安定することになります。