Qbsolvの問題分割アルゴリズム調査

Qbsolvの問題分割アルゴリズム調査

Qbsolvとは #

Qbsolvは「大規模な組み合わせ最適化問題に対する問題分割ソルバー」のアルゴリズム並びにそのライブラリです。 D-Wave社のBoothらによって提案されました1。 ソースコードはGitHub上で公開され、誰でも利用することができます。

わかりやすく #

先ほどの説明では少々専門的な言葉が多かったので、まずは「大規模な組み合わせ最適化問題に対する問題分割ソルバー」とはどういったものなのかについて説明します。 「大規模な組み合わせ最適化問題に対する問題分割ソルバー」をいくつかの単語に分けて解説しますので、意味がわからない部分だけ読んでみてください。

一覧 #

  1. 組み合わせ最適化問題
  2. 大規模な組み合わせ最適化問題
  3. 問題分割
  4. ソルバー

1. 組み合わせ最適化問題 #

組み合わせ最適化問題とは、たくさんの選択肢から最も理想的な選択肢の組み合わせを求める問題です。 理想とは何かは問題ごとに設定されます。 情報科学で扱うような言葉を使うならば、何らかの条件における変数の値の組み合わせのうち理想的な組み合わせを求めるという問題と言い換えることもできます。 一般的に、「何らかの条件」は関数（目的関数と呼びます）によって表現されます。そして「理想的な組み合わせ」は目的関数の値が最も小さい、もしくは最も大きい状態を指します。

さて、この問題はとても難しい問題です。 なぜなら組み合わせの数は変数が増えるにつれて指数関数的に増加するからです。 例えばYESかNOかの2択の選択肢が2個ある場合、そのYESとNOの組み合わせの数は \(2^2 = 4\) 個になります。 選択肢が \(N\) 個なら、 \(2^N\) 個です。 指数関数は見た目の単純さからするとはるかに恐ろしいものです。これが現れた瞬間、情報科学に携わる多くの人々は恐怖で震えだします。 試しに \(N=100\) としてみましょう。 \(2^{100}\) 個と書くと優しく見えますが、これは実に \(1,267,650,600,228,229,401,496,703,205,376\) 個にも及びます。

これだけ組み合わせが多くなると「全通り試せばいいじゃん！」という単純な方法で最適化問題を解こうとしても、現実的な時間やリソース（メモリやCPUなど）では終わりません。 様々な工夫を凝らす必要が出てきます。 この工夫の一つに量子コンピュータがあります。

組み合わせ最適化問題と量子コンピュータとの関わりについては、次のページでより詳しく解説しています。

量子アニーリング方式

2. 大規模な組み合わせ最適化問題 #

大規模な組み合わせ最適化問題とは、文字通り問題のサイズが大きい最適化問題のことです。

何をもって大きいとするのかということですが、ここでは変数の数で判断します。

具体的にどの程度の数が大規模かという基準はないのですが、例えば 1. 組み合わせ最適化問題 の例のように100個のYES/NOの組み合わせに関する問題は、大規模な問題であると言ってよいでしょう。

現実的な組み合わせ最適化問題はほとんどが大規模な問題です。 したがって、大規模な組み合わせ最適化問題をいかにして解くかということは重要なテーマとなっています。

しかしながら、計算にかかる時間やリソースを考慮すると、解ける問題のサイズが制限される必要があるアルゴリズムや手法は少なくありません。

また、ハードウェア的な制約で問題のサイズが制限されるケースがあります。 例えばアニーリングマシンと呼ばれるマシンを用いた最適化の場合、マシンの持つbit数やbit配置の幾何学的な構造によって扱える変数の数や組み合わせ方が制限されます。 アニーリングマシンや量子アニーリングについては、量子アニーリング方式やアニーリングマシンのプログラミングをご覧ください。

以上のことから、アルゴリズムやマシンによってはどうにかして問題のサイズを小さくしてやる必要があり、そのための一つのアプローチが問題を分割する手法です。3. 問題分割 にて説明します。

3. 問題分割 #

2. 大規模な組み合わせ最適化問題 ではアルゴリズムやマシンの制約上、大規模な問題をそのまま解けない場合があることを説明しました。

そういったアルゴリズムやマシンを用いて大規模問題を解く方法の一つが問題分割です。 もともとの変数の集合を、アルゴリズムやマシンで扱える大きさに分割することで問題を解きます。

例えば64変数の組み合わせ最適化問題が解けるマシンやアルゴリズムで100変数の問題を解きたい場合、何らかのアルゴリズムで100変数を64変数以下の個数の組2つ以上に分割します。 分割した内容をそれぞれ最適化して、それらを結合して結果とします。 もしも結果が良くなければ再度分割して、解いて、結合してを繰り返して答えに近づけていきます。

4. ソルバー #

ソルバーとは一般に組み合わせ最適化問題を解くツールのことを指します。

今回の場合、Qbsolvがそのものずばりソルバーとなっています。

Qbsolvのアルゴリズム #

この項目はQbsolvの仕組みについて詳しく知りたい人向けの項目です。 専門的な内容になりますので興味のない方は次のQbsolvがやりたいことからお読みください。 ただし、できれば前提知識のみは一読していただけると今後の話が分かりやすくなるかと思います。

前提知識 #

Qbsolvを理解するにあたり必要な前提知識です。

1. QUBO(Quadratic unconstrained binary optimization) #

Qbsolvでは問題の表現としてQUBOを使用しています。これはイジング模型（Ising Model）と呼ばれる模型を変数変換したもので、イジング模型と等価な模型です。QUBOでは \(0,1\) の二つの値をとる変数の組み合わせを最適化します。

詳しくはアニーリングマシンとイジング模型で説明しています。

2. 局所的最適化(Local optimization) #

最適化問題において局所的最適化とは、「全体としては最適ではないかもしれないが、部分的には最適であること」です。 関数における最小ではない極小値のようなイメージです。

3. 大域的最適化(Global optimization) #

最適化問題において大域的最適化、全体を通して最適であることを目標とする最適化です。

コンピュータで最適化問題を解く場合、2. 局所的最適化 に陥ることが多々あります。

そのため、最適化問題を解く際はいかに局所的最適化を抜け出して大域的最適化に近づくアルゴリズムを使うかということが重要になってきます。 大域的最適化(Global optimization)

Qbsolvのベースとなる戦略 #

1. 問題の一部をsubQUBOと呼ばれる単位に分割 #

問題全体の一部をsubQUBOと呼ばれる単位に分割し、それをサブソルバーで解きます。 サブソルバーには量子アニーリングなどを用います。

subQUBOのサイズは自由に設定できます。 したがって、ここでサブソルバーの制約にあったサイズのsubQUBOを作れば良いわけです。

2. 全体をタブーサーチで最適化 #

subQUBOを結合後、全体に対してTabuサーチと呼ばれるアルゴリズムによって最適化を行います。 タブーサーチについてはWikipediaをご覧ください。

タブーサーチと量子アニーリングの利点を活かしあう #

今回はサブソルバーとして量子アニーリングを選択した場合を想定して説明します。

量子アニーリングは大域的最適化が得意です。しかし、問題サイズに制限がかかります。

一方でタブーサーチは局所的最適化が得意で高速です。しかし、大域的最適化にはなりにくい場合があります。

タブーサーチは近傍探索と呼ばれる探索アルゴリズムの一種であり、その仕組みとして現在解の近傍（現在解を少し変えた変数の組み合わせの集合）を探索するという部分があります。この近傍を大きく取ると局所的最適化には陥りにくくなるのですが、一方で計算時間が大きく増えるなどの問題があります。

そこで近傍を大きくとる部分をサブソルバーで疑似的に再現します。

近傍を大きくとる近傍探索はLarge-neighborhood local searchと呼ばれ、Qbsolvもこの一種です。

キーとなるアイディア「impact」 #

QbsolvではsubQUBOへの分割の際impactと呼ばれる値を用います。 これは現在の状態に対しての変数の影響度です。 変数ごとに一つのimpact値を持ちます。

impact値は「変数の値を変化させた場合の目的関数の増加量」です。 QUBO表現での変数は \(0,1\) の値しかとらないため、この値を反転させた場合にどれくらい目的関数が増加したかがimpact値となります。 この値が大きいということは、反転させる前の状態のほうが全体としてより良い状態にあると推測できます。 impact値が大きい程、局所的な決定度が大きいとも言えます。つまり現在の状態に対して、最適化アルゴリズム内においてその変数は変化しにくくなっているということです。

しかし、これはあくまでも現在の状態に対しての影響度、すなわち局所的な決定度なので、impact値が高い変数でも大域的には最適化されていない可能性があります。 局所解に陥っているという状態です。

その場合、決定度が高い部分でもあえて反転させるなどの方法で局所解を抜け出す必要があります。 下の図のように山を越えるイメージです。 impact 1 Qbsolvでは、impact値の大きい順に変数を並べて、大きいほうからおよそ \(5 \sim 15\%\) をsubQUBOに分割します。 これによって下の図のように近傍を大きくとった状態を疑似的に作ります。 本来の近傍であれば見えなかった遠くの状態も見られるようになるというわけです。 impact 2

具体的なアルゴリズムの流れ #

具体的なアルゴリズムは次の図のようになっています。 具体的なアルゴリズムの流れ

Qbsolvがやりたいこと #

Qbsolvはもともと、量子アニーリングマシンで解けるサイズに大規模な組み合わせ最適化問題を分割するために考え出されたものと思われます。 実際、D-Waveの研究者による論文1でも量子アニーリングマシンを使って解いた結果について触れています。 しかし、その結果としては「速度的な優位性はないものの、競争力はある」というふんわりとした内容であり、実際のデータが論文内に存在しません。

論文内に実際にデータがあるのは、サブソルバーにもタブーサーチを利用したものです。競合アルゴリズム2よりおよそ二倍の速度が出るというベンチマークの結果が載っていました。

公開されているQbsolvのソースコードでは論文内のベンチマークで利用された「サブソルバーとしてタブーサーチを用いるもの」のみが実装されており、D-Wave Solver API（量子アニーリングマシンにアクセスするAPI）に関する処理が抜けています。

もしもD-Wave Solver APIをサブソルバーとして用いるならば、qOpと呼ばれるクローズドなミドルウェアが必要という仕様になっています。そのため、自由度と便利さの観点から若干の難がありました。

実験 #

概要 #

Qbsolvがやりたいことで述べたように、公開されているQbsolvのソースコードのみでは量子アニーリングをサブソルバーとして用いることができません。

そこで、社内でD-Wave Solver API用の通信クライアントや幾何学ライブラリ（グラフ埋め込みライブラリ）を実装し、Qbsolvと組み合わせてテストしました。

なお、量子アニーリングを行う際に具体的にどのような実装を行えば良いかが知りたい方は、アニーリングマシンのプログラミングを参考にしてください。

実験条件 #

問題：巡回セールスマン問題 #

今回は問題として巡回セールスマン問題を取り上げます。 巡回セールスマン問題は \(N\) 都市をすべて通って元の都市に戻ってくる際の最短経路を求める問題です。

巡回セールスマン問題の詳細な解説や、巡回セールスマン問題をQUBO表現にする方法については、巡回セールスマン問題や巡回セールスマン問題をQUBOにする方法をご覧ください。

サブソルバー #

比較のため５種類のサブソルバーを用いました。

  • タブーサーチ（Qbsolvデフォルト）
  • 量子アニーリング（D-Waveマシン）
  • ダミーソルバー dummy0 ：解として0のみを返す
  • ダミーソルバー dummy1 ：解として1のみを返す
  • ダミーソルバー dummy01 ：解として01の繰り返しを返す

なお、量子アニーリングのサブソルバーでは、量子アニーリングを10回試行したうちの最も良い結果1つを返します。

実験1 ：8都市のセールスマン問題 #

QUBOにすると64変数、896連結必要です。

8都市についてsubQUBOの大きさを変えて解きます。 分割数が計算回数、エネルギーが目的関数の値です。 エネルギーが小さいほうがより良い解となります。

実験1-1 #

subQUBOの大きさ：32変数 subQUBOの大きさ：32変数

実験1-2 #

subQUBOの大きさ：47変数 subQUBOの大きさ：47変数

実験1の結果 #

  • subQUBOの大きさを変えても、すべてのサブソルバーで最適解が得られた
  • 分割数＝計算時間にサブソルバーによる大きな変化はなし

実験2 ：16都市のセールスマン問題 #

QUBOにすると256変数、7680連結必要です。 これは64変数程度の問題までしか解けないマシンを使った場合、そのまま解くことが不可能な大きさの問題です。

ここでは2つの異なる条件（都市の配置）を用意し、それぞれsubQUBOなどのパラメータを変化させずに解きました。 不適と示されているものは結果が巡回セールスマン問題の解になっていなかった問題です。行っていない都市があったり、同じ回数の時に複数都市に行こうとしていたりしたものです。 エネルギーが赤字になっているものは最もエネルギーが小さい（最も最適化できている）結果です。

実験2-1 #

subQUBOの大きさ：64変数 実験2-1

実験2-2 #

subQUBOの大きさ：64変数 実験2-2

実験2の結果 #

  • D-Waveマシンとタブーサーチのどちらが良い結果になるかは問題による
  • D-Waveマシン, dummy0, dummy1は常に同じ結果

実験3 ：20都市の巡回セールスマン問題 #

QUBOにすると400変数、15200連結必要です。

20都市の場合を解きました。結果を見ればわかりますが、すべてのサブソルバーで巡回セールスマン問題の解を得られませんでした。 そのため、エネルギーの値を見ることで結果の良さを判断します。

実験3-1 #

subQUBOの大きさ：64変数

subQUBOの大きさ：64変数

実験3の結果 #

  • D-Waveマシンのほうがタブーサーチよりも良い結果
  • D-Waveマシン, dummy0, dummy1は常に同じ結果

実験結果から読み取れること #

巡回セールスマン問題の場合、サブソルバーが必ずしも有効に働くかといわれるとそういうわけではなさそうです。 D-Waveマシン, dummy0, dummy1がすべて同じ結果になっているのは、D-Waveマシンによるサブソルバーの結果が有効ではなかったということです。 すなわち、subQUBOに分割していない状態の最適化を行うタブーサーチがほとんど最適化を行っている状態です。

こうなってしまった原因としてはいくつか考えられます。

巡回セールスマン問題の解の性質 #

巡回セールスマン問題がQbsolvで解くには適していなかった可能性があります。

  • 巡回セールスマン問題の解は0が多い
  • 局所最適な状態に落ち込みやすく、近傍をかなり大きくとらない限り抜け出せない可能性

問題のスケールや種類 #

今回用いた問題とQbsolvがターゲットにしている問題のスケールや種類が異なっていた可能性があります。

今回用いた問題

  • 最大400変数
  • 巡回セールスマン問題の解の性質で述べたように解に偏りがある問題

Qbsolvのベンチマークで使用された問題(Qbsolvがターゲットにしている問題)

  • 2500変数
  • ランダムに生成された問題

パラメータがうまく設定できていない #

比較実験していないパラメータがあり、これらをチューニングすることでうまくいく可能性があります。

  • ベスト解が更新されない場合の最大繰り返し回数
  • 問題自体の作り方（制約の強さやコスト関数の作り方、チェインの強さなど）

まとめ #

Qbsolvを用いることで、素の量子アニーリングで解けないサイズの問題を解くことができることがわかりました。 一方、問題によってはQbsolvで量子アニーリングを使う利点はない可能性があることもわかりました。 まだ改善の余地はありますが、今回はひとまずこのような結論で締めさせていただきます。

参考文献 #

  1. Booth, M., S. Reinhardt, and A. Roy. Partitioning optimization problems for hybrid classical/quantum execution. D-Wave Technical Report ↩︎

  2. Y. Wang, Z. Lu, F. Glover, and J.-K. Hao, “Path relinking for unconstrained binary quadratic programming,” ¨ European Journal of Operational Research, vol. 223, no. 3, pp. 595–604, 2012. ↩︎

Calendar 2019-01-07