ホップフィールドネットワークのパラメータ空間における山登り学習法に基づく巡回セールスマン問題の解法

摘要

本論文では，ホップフィールドネットワークのパラメータ空間において，故意にエネルギーを上昇させ，局所最小値から脱出を計る最急上昇（山登り）学習法を提案する．更に本学習を巡回セールスマン問題に適用し，その有効性を示す．本学習法は，ホップフィールドネットワークが時間空間における状態更新によって，いったん局所的最小値に陥った状態に対して，故意にエネルギーを上昇させるように，パラメータ空間においてパラメータを修正した後に，再び時間空間に戻って状態更新することを繰り返すことにより，局所的最小値から脱出させる学習方法である．本学習法により，ホップフィールドネットワークが初期状態に依存した局所的最小値から脱出できることをシミュレーションにより示す．まず，9都市及び20都市に対してシミュレーション実験を行い，その有効性を明らかにする．更に，より実用的任意都市数の巡回セールスマン問題，例えば数百都市巡回セールスマン問題に対し，全都市配置を部分都市群に分割し，各部分都市群の最適解により全都市配置の最適解または準最適解を計る．最後に，本手法を用いて，100都市の巡回セールスマン問題に対してシミュレーションを行い，その有効性を明らかにする．