効率的な分割方法の提案

大規模な整数最適化問題を分割する方法として，整数分割と2^値分割の2^{つの方法を提} 案する．整数分割は先行研究[38]と同様の分割方法であるが，前章で提案したアルゴリズ ムを発展させて大きな部分問題を埋め込めるように改良する．2値分割は部分問題の解空 間が許容解のみで構成される分割方法で，整数分割と比較して多くの許容解を解空間に含 む部分問題を抜き出すことができる．

5.4.1 整数分割の方法

整数分割では先行研究 [38]と同様の考え方によって部分問題を抜き出す．この方法で は，暫定解でSi = qとなっている整数変数に対して，xqi = 1のブール変数に加えて，

x_q′i = 0(q^′ ̸=q)のブール変数の少なくとも1つ以上を部分問題として抜き出す．整数分割 の簡単な例を図5.4に示す．この例では，部分問題の最適化によってSi = 2^やSi = 3^に

図5.3: ^先行研究[38]^{の分割方法}

ϭ Ϭ Ϭ Ϭ

^

ŝ

сϭ

㒊ศၥ㢟

ᬻᐃゎ

Ϭ ϭ Ϭ Ϭ

^

ŝ

сϮ

᭦᪂ྍ⬟䛺チᐜゎ

Ϭ Ϭ ϭ Ϭ

^

ŝ

сϯ

図5.4: 整数分割の例

更新される可能性がある．図5.4では簡単のため1つの整数変数を用いて説明したが，実 際の整数最適化問題は複数の整数変数によって定義されるので，それぞれの整数変数に対 して同様の処理をして部分問題を抜き出す．また，整数変数が多い場合には部分問題に含 まれない整数変数も発生する．

整数分割を実際に利用する際には，整数分割の条件を満たす大きな部分問題をどのよ うにして埋め込むかが課題となる．前章で提案した部分問題の埋め込みアルゴリズムは 埋め込み易い変数のみで部分問題を構成していた．一方で，整数分割ではone-hot制約に 起因して埋め込まれるべき変数が決められる．このため，整数分割で前章のアルゴリズム を利用するためには，「埋め込み易い変数」と「埋め込まれるべき変数」という2^つの要素 を両立するように修正を加える必要がある．ここでは，「埋め込むべき変数」の存在を考慮 してブール変数の埋め込み順序を工夫することにした．具体的には，最初に整数変数Sinit

をランダムに1つ選択し，S_initに割当てられたブール変数を埋め込んだ後，以下の手続き に沿って次に埋め込まれるブール変数を選択する．ここで，以下の文章に出てくる「埋め 込み済みの整数変数」とは，整数変数に割当てられたブール変数が既にハードウェアグラ フ上に埋め込まれた整数変数を指す．

1. 埋め込み済みの整数変数Sctrを埋め込んだ順番に選択する．

2. S_ctrに隣接する未埋め込みの整数変数{S_i}^{を取得する．}

3. 隣接変数{S_i}^{の中から整数変数}S_iをランダムに1つ選択する．

4. ^整数変数Siに割当てられたブール変数{xqi}q=1,2,...,Qを取得する．

5. {x_qi}の中から，暫定解においてx_qi= 1となっているブール変数を選択してハード ウェアグラフに埋め込む．

6. {xqi}の中から，暫定解においてxqi= 0となっているブール変数をランダムな順番 でハードウェアグラフに埋め込む．

提案アルゴリズムでは重複割当てが必要な場合に埋め込みを諦めるため，S_iに割当てられ たブール変数{x_qi}q=1,2,...,Qの埋め込みが終了した時点で，以下の要件を満たしているか を確認する必要がある．

ϭ Ϭ Ϭ Ϭ

^ŝсϭ

㒊ศၥ㢟

ϭ Ϭ Ϭ Ϭ

^ŝсϭ

ᬻᐃゎ ᬻᐃゎ

䚾džƋŝсϭ䛾䝤䞊䝹ኚᩘ䛜ྵ䜎䜜䛶䛔䛺䛔䚿 䚾䝤䞊䝹ኚᩘ䛜ϭಶ䛧䛛ྵ䜎䜜䛶䛔䛺䛔䚿

図 5.5: 部分問題から除外するべき例

• x_qi= 1のブール変数を含めて2つ以上のブール変数の埋め込みに成功している．

図5.5に示すように，もしこの要件を満たしていない場合はSiを部分問題として含めるべ きではなく，埋め込みに成功したブール変数をハードウェアグラフ上から取り除かなけれ ばならない．前章のアルゴリズムに埋め込み順序の修正を加えることで，整数分割の要件 を満たす部分問題を埋め込めることは第5.5節で示す．

5.4.2 2値分割の方法

2値分割の方法では，部分問題の解空間が許容解のみで構成されるように分割する．2 値分割では以下の手順に沿って部分問題をハードウェアグラフに埋め込む（図5.6参照）．

1. 全ての整数変数に対して，xqi = 1のブール変数に加えて，x_q′i = 0(q^′ ̸= q)^のブー ル変数を1つランダムに選択して部分問題として抜き出す．このように部分問題を 抜き出した場合，各整数変数で探索可能な許容解は1つに絞られるため，「暫定解を 維持する」か「探索可能な許容解に遷移する」かの2択問題に落とし込むことがで きる．

2. 上記の2択を表す新たな2値変数{y_i}i=1,2,...,N（y_i = 0: 維持，y_i = 1: 遷移）をそ れぞれの整数変数に対して導入し，2値の部分問題を生成する．

3. 2値の部分問題に対して部分問題の埋め込みアルゴリズムを適用して，{yi}^の一部 をキメラグラフに埋め込む．

次に，{yi}i=1,2,...,Nで定義される2値の部分問題のハミルトニアンを示す．もともとの

問題のハミルトニアンがxqi∈(0,1)^を用いて

H0 = ∑

(ij)∈Ep

∑Q q=1

∑Q q^′=1

Q^qq_ij^′x_qix_q′j+∑

i∈Vp

∑

q

Q^qq_iix_qi+λ∑

i∈Vp



∑^Q

q=1

x_qi−1





2

, (5.5)

で与えられているとする．ここで，Q^qq_ij^{′ は}xqiとx_q′jの相互作用を，∑

i∈Vpは全ての整数 変数に対する和を，∑

(ij)∈Epは相互作用する整数変数のペアに対する和を表す．この場合

䐟ᩚᩘኚᩘ䛛䜙䝤䞊䝹ኚᩘ䜢Ϯಶ㑅ᢥ 䐠Ϯ್䛾㒊ศၥ㢟䜢⏕ᡂ

⥔ᣢŽƌ㑄⛣䜢⾲䛩Ϯ್ኚᩘ΂LJ_ŝ΃䜢ᑟධ

䐡Ϯ್䛾㒊ศၥ㢟䛻ᑐ䛧䛶 ๓❶䛾䜰䝹䝂䝸䝈䝮䜢㐺⏝

ᬻᐃゎ䜢⥔ᣢŽƌ᥈⣴ྍ⬟䛺チᐜゎ䛻㑄⛣

䛾஧ᢥၥ㢟䛸䛺䜛

ϭ Ϭ Ϭ Ϭ

^ŝсϭ

ᬻᐃゎ ᥈⣴ྍ⬟䛺チᐜゎ

Ϭ ϭ Ϭ Ϭ

^ŝсϮ

ϭ Ϭ

Ϭ ϭ

Žƌ

⥔ᣢ 㑄⛣

LJ_ŝсϬ͗⥔ᣢ LJ_ŝсϭ͗㑄⛣

図5.6: 2^{値分割の方法の説明図} の2値の部分問題のハミルトニアンHBinaryは

HBinary= ∑

(ij)∈Ep

R_ijy_iy_j+∑

i∈Vp

R_iiy_i, (5.6)

R_ij =Q^α_ij^iαj−Q^α_ij^iβj−Q^β_ij^iαj+Q^β_ij^iβj, (5.7) Rii= ∑

k∈∂i

(Q^β_ik^iαk−Q^α_ik^iαk)−Q^α_ii^iαi+Q^β_ii^iβi, (5.8) となることが容易に示せる．ここで，暫定解においてSi=αiであり，βiはSiの遷移先の 候補を表す．2値の部分問題を定義する2^値変数{yi}は許容解の間の遷移を表しているの で，2値の部分問題に含まれる全ての状態はone-hot制約を満たしている．このため，式 (5.6)にはペナルティ項が含まれていない．ペナルティ項がx_qiとx_q′i の間で全結合相互 作用を発生させることも考慮すると，2値分割の長所として以下の3つを挙げることがで きる．

• 部分問題の解空間が許容解のみで構成される．

• 2値の部分問題では相互作用が少なくなっており，多くのブール変数を埋め込める．

• ペナルティ項の強さを決めるパラメータλを調整する手間が省ける．

特に1^番目と2^{番目の長所によって，}2値分割で抽出した部分問題の解空間には，整数分 割で抽出した場合に比べて多くの許容解が含まれるようになる．一方で，各整数変数に対 して2つの状態しか考慮していないことに起因して，次節で示すように強磁性Pottsモデ ルにおける性能が著しく悪化する．

表5.1: ハミルトニアンのパラメータ設定

モデル Jij ∆ij

強磁性Potts^モデル +1 0

反強磁性Potts^モデル -1 0

Potts^{グラスモデル} +1(50%) or -1(50%) 0

Pottsゲージグラスモデル -1 0(50%) or +1(25%) or -1(25%)

ドキュメント内 大規模な組合せ最適化問題に対する量子アニーリングマシンの活用方法に関する研究 (ページ 51-56)