バイナリー2次計画問題に対する高速k-opt局所探索法を用いた遺伝的局所探索法

本研究の目的は,組合せ最適化問題の一つであるバイナリー2次計画問題(BQP)を取り上げ,既発表のBQPに対する効率的なk-opt法(高速k-opt法)拡張版として,各問題例の性質を取り入れ,より最適なパラメータ設定を行う高速k-opt法を提案することと,BQPに対する高速k-opt法を用いた遺伝的局所探索法(GLS)の提案として,GLSの局所探索法(LS)部分に高速k-opt法を用い,遺伝的アルゴリズム(GA)の遺伝的操作(選択,交叉,突然変異)の考慮も含めた,BQPに対する強力なGLSを提案することである.BQPに対する高速k-opt法を用いたGLSを提案するために,BQPに対して知られているLSの中でも,最も有効なk-opt局所探索法(k-opt法)に焦点をあてた.BQPに対してk-opt法を用いたGLSを施行し,突然変異の効果を検討し成果発表を行った.さらに,高速k-opt法を用いた場合の突然変異についても検討を行い成果発表を行った.具体的には,多くの研究者らによって用いられているBQPのベンチマーク問題に対して,既存のk-opt法を組み込んだGLSを施行する実験を行った.実験結果から,計算時間,適した突然変異確率は問題サイズに依存することを示した.また,高速k-opt法を用いたGLSにおいては適した突然変異確率を使用することによって,既存のk-opt法を用いたGLSよりも多くの問題例で解質を向上させながら探索時間を大幅に短縮できることを示した.

本研究の目的は,組合せ最適化問題の一つであるバイナリー2次計画問題(BQP)を取り上げ,既発表のBQPに対する効率的なk-opt法(高速k-opt法)拡張版として,各問題例の性質を取り入れ,より最適なパラメータ設定を行う高速k-opt法を提案することと,BQPに対する高速k-opt法を用いた遺伝的局所探索法(GLS)の提案として,GLSの局所探索法(LS)部分に高速k-opt法を用い,遺伝的アルゴリズム(GA)の遺伝的操作(選択,交叉,突然変異)の考慮も含めた,BQPに対する強力なGLSを提案することである.BQPに対する高速k-opt法を用いたGLSを提案するために,BQPに対して知られているLSの中でも,最も有効なk-opt局所探索法(k-opt法)に焦点をあてた.BQPに対してk-opt法を用いたGLSを施行し,突然変異の効果を検討し成果発表を行った.さらに,高速k-opt法を用いた場合の突然変異についても検討を行い成果発表を行った.具体的には,多くの研究者らによって用いられているBQPのベンチマーク問題に対して,既存のk-opt法を組み込んだGLSを施行する実験を行った.実験結果から,計算時間,適した突然変異確率は問題サイズに依存することを示した.また,高速k-opt法を用いたGLSにおいては適した突然変異確率を使用することによって,既存のk-opt法を用いたGLSよりも多くの問題例で解質を向上させながら探索時間を大幅に短縮できることを示した.