バイナリー二次計画問題に対する効率的な近似解法の開発

点击翻译按钮获取中文摘要

バイナリー2次計画問題(BQP)に対するさまざまな近似解法(メタ戦略)の開発を行った.以下では各アルゴリズム別に,アルゴリズム概要,結果,明らかになった事項などを簡潔に示す.1.ランダムk-opt局所探索法(ランダムk-opt法)新たに開発したランダムk-opt法は,ランダム性を巧妙に導入した可変深度探索により実現され,従来法よりも平均的に良好な局所最適解を算出可能であることが明らかになった.2.シミュレーティッドアニーリング法新たに開発したシミュレーティッドアニーリング法(SA)は,巧妙な再加熱および近傍解のゲイン値を高速に計算可能なデータ構造を採用することで,大規模なBQPに対しても効率的に良好な結果を算出できることが明らかになった.なお,ORLIBに準備されているBQPの幾つかの大規模問題例において新しい最良解が本SAにより極めて短時間で発見された.現在これらは既知の最良解となっている.3.遺伝的局所探索法1.で示したランダムk-opt法を組み込むことにより新たに開発した遺伝的局所探索法(GLS)は,2.で示したSAよりもある程度計算時間を必要とするが,既知の最良解を頻繁に算出可能であることが明らかになった.4.反復局所探索法1.のランダムk-opt法を用いて新たに開発した反復局所探索法(ILS)は,対象とする問題例に依存するが,2.で示したSAおよび3.のGLSよりも,効率的に既知の最良解を頻繁に算出できることが明らかになった.本ILSでは,局所最適解からの脱出時に幾つかのビットの反転を行うが,ランダムk-opt法を組み込んだILSの場合は,他の局所探索法を組み込むよりも少ないビット反転で十分な性能を発揮することが観測された.これは,上記したメタ戦略(近似解法)の改良版を考慮する際にも貴重な観測結果であるとともに,局所探索過程を含む近似解法全般において重要な特長であると考えられる.