超大規模組合せ最適化問題における新パラダイムの構築とその応用

本研究の目的は、従来扱うことができなかった超大規模な組合せ最適化問題に対する革新的なアルゴリズムを開発し、様々な問題に適用することでこの分野における新しいパラダイムを構築することである。本年度は、我々が提案した最大多様性問題(Maximum Diversity Problem)に対する初期近傍探索法における、局所探索法についての検討を行った。最大多様性問題は、与えられたn個の要素からm個の要素を選ぶとき、できるだけ多様性を有するように要素を選択する組み合わせ最適化問題であり、ネットワーク設計やVLSI設計など応用範囲の広い問題として知られている。最大多様性問題にはｍ個の要素を選択するという制約条件があるが、本手法ではこの制約条件を満たさない解空間の探索も行うことで、これまでとは別の探索経路で解探索を行うことができ、従来手法よりもより評価値の良い解を発見できることを示した。また、バイナリー２次計画問題(Quadratic Assignment Problem)に対して、Opposition-Based Learningを組み入れたMemetic Aligotithmにおける局所探索法についての検討を行った。バイナリー2次計画問題は、NP困難な問題に含まれる組み合わせ最適化問題の一つであり、マシンスケジューリング問題やCAD問題など大規模な計算を要する問題の応用例として知られている。本研究では、制約付き近傍やk-opt局所探索法など様々な局所探索を組み入れることにつての検討を行い、k-opt局所探索法を用いることが最も良い結果を得られることを示した。

本研究の目的は、従来扱うことができなかった超大規模な組合せ最適化問題に対する革新的なアルゴリズムを開発し、様々な問題に適用することでこの分野における新しいパラダイムを構築することである。本年度は、我々が提案した最大多様性問題(Maximum Diversity Problem)に対する初期近傍探索法における、局所探索法についての検討を行った。最大多様性問題は、与えられたn個の要素からm個の要素を選ぶとき、できるだけ多様性を有するように要素を選択する組み合わせ最適化問題であり、ネットワーク設計やVLSI設計など応用範囲の広い問題として知られている。最大多様性問題にはｍ個の要素を選択するという制約条件があるが、本手法ではこの制約条件を満たさない解空間の探索も行うことで、これまでとは別の探索経路で解探索を行うことができ、従来手法よりもより評価値の良い解を発見できることを示した。また、バイナリー２次計画問題(Quadratic Assignment Problem)に対して、Opposition-Based Learningを組み入れたMemetic Aligotithmにおける局所探索法についての検討を行った。バイナリー2次計画問題は、NP困難な問題に含まれる組み合わせ最適化問題の一つであり、マシンスケジューリング問題やCAD問題など大規模な計算を要する問題の応用例として知られている。本研究では、制約付き近傍やk-opt局所探索法など様々な局所探索を組み入れることにつての検討を行い、k-opt局所探索法を用いることが最も良い結果を得られることを示した。