@yuichirominato 2018.12.22更新 516views

【ハイブリッド】タブーサーチ+量子アニーリングで大規模問題の分割

qbsolv QUBO タブーサーチ 量子アニーリング

はじめに

組合せ最適化問題をイジングモデルで解こうとするとまず接続数と量子ビットを確認する必要があります。大概の問題は量子ビット数は足りませんので、その量子ビット数の足りない社会問題を現代で量子コンピュータもしくは量子アニーラを利用してときたい場合があります。その際に量子古典ハイブリッドで大規模問題を分割して計算をする手法が取れます。それを今回はみてみます。

ネットワーク問題の大規模問題分割

大きなネットワーク問題をそのまま特にはD-Waveなどの量子アニーリングマシンではサイズが足りません。VW社が北京で行なった交通流最適化問題では、タクシーの数は1万台を超えています。それに対してイジングのサイズは2000で、さらに1台のタクシーに対して提案されるルートの数は3つあります。なので、全然足りません。

ということで、大きな問題を分割する必要があります。分割手法についてはこちらが詳しいです。(英語ですが)

Combinatorial Optimization by Decomposition on Hybrid CPU–non-CPU Solver Architectures
https://arxiv.org/abs/1708.03439

実際にはシンプルに大規模問題を小規模問題に分割し、最終的に統合、良い解に到達するまで繰り返すことを行います。

タブーサーチとqbsolv

大規模問題の分割はD-Wave Systems Inc.のqbsolvが有名ですので、少しみてみたいと思います。

qbsolv
https://github.com/dwavesystems/qbsolv

qbsolvの使い方は最近よくブログなどで紹介されていますので検索して探してもらえると活用方法がわかると思います。今回は少しタブーサーチについて調べてみて、今後実際にどのような実行がされているのかD-Waveを確認してみたいと思います。

タブーサーチ: tabu search)やタブー探索とは、1989年にフレッド・グローバー(Fred Glover)により考案されたメタヒューリスティック探索アルゴリズムの一つである。

タブーサーチはメタヒューリスティクスの手法であり、人工知能の概念に基づいた局所探索法の一般化として認知されている。同じメタヒューリスティクスの手法には、遺伝的アルゴリズム焼きなまし法のように特定の自然現象を模倣した手法がある。

この手法は状態の近傍を複数探索しその中で最も良い近傍状態に遷移する、このときタブーリストと呼ばれるキューに状態遷移時の操作を書き込む。このタブーリストに書き込まれている操作は行わないことにより状態がループするのを防ぐことで探索が停滞せずに最適解を探索する。ここで重要なのはタブーリストに載っていない場合は状態が悪くなっても遷移を行うことである。このことにより局所解で探索が停滞するのを防いでいる。

引用:https://ja.wikipedia.org/wiki/%E3%82%BF%E3%83%96%E3%83%BC%E3%82%B5%E3%83%BC%E3%83%81

つまり、アニーリングのような最適化アルゴリズムで、タブーリストと呼ばれるリストを活用しながら周辺の最適解を探索するアルゴリズムのようです。

量子アニーリングも最適化アルゴリズムなのでタブーサーチと組み合わせることで、最適化アルゴリズム*最適化アルゴリズムで最適化しまくりです。

タブーサーチは
1、初期値をランダムで生成
2、局所会探索のために近傍を作成
3、近傍に含まれるがタブーリストに含まれない解の中で最良のものを採用
4、タブーリストを更新
5、条件を満たすまで繰り返す

という手順で進みます。

まとめ

大規模問題は小規模の部分的な最適化を繰り返し、タブーリストを作りながら最適解を探していく手順となっているのが現在の標準となっています。量子アニーリングは部分的な最適化で活用され、全体としてはタブーサーチが優先となっているため、繰り返し計算が収束するまで比較的時間がまだかかりそうです。古典の最適化計算を量子コンピュータ向けにチューニングするのがとても大事になりそうです。


Recommended


Wikiへ移動