相互結合形NNの最安定解をTSPの最適解に一致させる為のコスト関数置換え方式の改善

概要

論文の詳細を見る
TSPは、複数の都市を巡回する為の最短経路を求める問題で、2値状態でのコスト関数を最小化する組合わせ最適化問題の一種である。相互結合形ニューラルネット(RNN)は、この種の組合わせ最適化問題の解法に利用される。しかし、相互結合形ニューラルネットには、複数のローカルミニマムがあるため、グローバルな最適解を検出することは難しい。このため、初期値制御の様な決定論的改善策やシミュレーテッドアニーリングの様な確率的探索法等が考案されてきた。本稿では、対角項を操作することによって、最適解の検出確率を向上させる方法について検討する。対角項操作とは、次式のように、エネルギー関数に頂点でのエネルギー値を変えずに関数形を変化させる項aΣx_1(x_1-1)を加えることによって、頂点への収束性を制御する方法である。E(x)=1/2x^tW_0x+θ^t_0x+aΣx_i(x_i-1)ここで、添え字tは、ベクトル及び行列の転値を表わす。W_0は、初期結合行列で対称な実数行列とする。θ_0は、初期しきい値ベクトルである。組合わせ最適化問題は、この初期結合行列と初期しきい値ベクトルとして、RNNに与えられる。
社団法人電子情報通信学会の論文
1996-09-18