二次割当問題のカオスハイブリッド解法とその並列実装

摘要

カオスを用いた組合せ最適化手法の有効性が示されている．本稿では，GAを用いた大域的探索とカオス近傍探索法を組み合わせた解法を並列実装し，アルゴリズムの効率的な実行を試みる．このアルゴリズムの基盤となっているGAとタブーサーチを組み合わせたGenetic Hybrid法は，2次割当問題の複数のベンチマーク問題の既知最適解を発見した手法であり，これをカオスタブーサーチに拡張することで性能が向上することが従来研究で示されている．GAで発見した大域的に分布する多数の良解を保持しながら，各々の解の近傍を詳しくカオスサーチで探索する．シリアルな実行では，一つ一つの良解を順番にカオスサーチで改善するが，このカオスサーチによる改善は複数同時に実行することが可能であり，並列処理によって大幅に実行時間を短縮できる．CPUに実装して性能を評価し，探索実行時間当たりの解探索回数が大幅に増加し，良い解を探索可能であることを示す．