負の自己相関を持つカオスダイナミクスを用いた組合せ最適化手法の有効性

摘要

組合せ最適化問題の非同期な探索解法に対して、理想的な時空間ダイナミクスを持たせるカオス的最適化手法を提案する。非同期な高次元探索アルゴリズムの各次元のダイナミクスに負の自己相関を持たせることで、次元間の相互相関を最小化させ、それによってローカルミニマムからの脱出を理想的に分散させる探索を実現する。負の自己相関を持つ時系列を用いることで、非同期な時系列間の相互相関を最小化させることが出来ることは、カオスCDMAにおける従来研究において理論的に示されている。また、非同期な探索解法の性能向上のためには、カオスノイズの負の自己相関であることを、これまでの我々の研究において示してきた。本稿では、そのような理想的な時空間ダイナミクスを実現するために、非同期な探索解法に負の自己相関を持たせるルベーグスペクトラムフィルタを導入する手法を提案する。提案手法を、ホップフィールドニューラルネットワークを用いた組合せ最適化問題の解法、および、2-opt法に適用し、それらのアルゴリズムの性能を向上せきることを確認する。巡回セールスマン問題においては、1000都市以上の大きな問題に対しても、提案アプローチが有効であることを示す。