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

摘要

This paper proposes a combinatorial optimization method, which utilizes ideal asynchronous spatiotem-poral chaotic dynamics for solution search in a high dimensional solution space. Such chaotic dynamics is generated by the Lebesgue spectrum filter, which has been applied to the chaotic CDMA in previous researches to minimize the cross-correlation among the sequences. In the proposed method, such a filter is applied to the output functions of optimization neural networks to realize an ideal chaotic search, which generates ideally complicated searching dynamics. The proposed scheme is applied to two combinatorial optimization approaches, the Hopfield-Tank neural network with additive noise and a simple heuristic 2-opt algorithm, which solve the Traveling Salesman Problems and the Quadratic Assignment Problems. The simulation results show that the proposed approach using the ideal chaotic dynamics simply improves the performance of the chaotic algorithms without searching appropriate parameter values even for large-scale problems.%組合せ最適化問題の非同期な探索解法に対して、理想的な時空間ダイナミクスを持たせるカオス的最適化手法を提案する。非同期な高次元探索アルゴリズムの各次元のダイナミクスに負の自己相関を持たせることで、次元間の相互相関を最小化させ、それによってローカルミニマムからの脱出を理想的に分散させる探索を実現する。負の自己相関を持つ時系列を用いることで、非同期な時系列間の相互相関を最小化させることが出来ることば、カオスCDMA における従来研究において理論的に示されている。また、非同期な探索解法の性能向上のためには、カオスノイズの負の自己相関であることを、これまでの我々の研究において示してきた。本稿では、そのような理想的な時空間ダイナミクスを実現するために、非同期な探索解法に負の自己相関を持たせるルベーグスペクトラムフィルタを導入する手法を提案する。提案手法を、ホップフィールドニューラルネットワークを用いた組合せ最適化問題の解法、および、2-opt法に適用し、それらのアルゴリズムの性能を向上できることを確認する。巡回セールスマン問題においては、1000 都市以上の大きな問題に対しても、提案アプローチが有効であることを示す。