Solving the Steiner tree problem in graphs using the chaotic neural network

点击翻译按钮获取中文摘要

グラフ的シュタイナー木問題は，電子回路の自動配線や省エネルギーな通信網・電力網の設計などへの応用が期待されている重要な組合せ最適化問題の一つである．グラフ的シュタイナー木問題はNP困難な組合せ最適化問題であり，厳密に最適な解を現実的な時間で求めるのは難しいと考えられている．そこで本研究は，グラフ的シュタイナー木問題に対する効率的な近似解法を開発することを目的とする．近年，巡回セールスマン問題や二次割当問題などの様々な組合せ最適化問題に対して，カオスニューラルネットワークが効率的な解探索を実現できることが知られている．このことから昨年度は，カオスニューラルネットワークを用いたグラフ的シュタイナー木問題の解法を開発した．また，数値実験により，カオスニューラルネットワークが有力な従来手法の一つであるタブーサーチよりもグラフ的シュタイナー木問題に対して高い解探索性能を発揮することを確認した．本年度は，カオスニューラルネットワークのどのような特徴が効率的な解の発見に寄与するのかを明らかにすべく，解探索中の目的関数値の変化の時系列を解析した．カオスニューラルネットワークとタブーサーチの結果を比較したところ，カオスニューラルネットワークのほうが多様な目的関数値の解に移動していることが分かった．このことから，グラフ的シュタイナー木問題の解法としては，様々な目的関数値の解に積極的に移動することが，より良い解の発見に寄与すると考えられる．