組み合わせ最適化問題は、工学、金融、情報科学といった多様な分野において、実用上極めて重要な課題です。しかし、問題が複雑化し、探索すべき解の候補が爆発的に増加するにつれて、従来型の数学的な手法で厳密な最適解を求めることは困難になります。特に、現実世界の多くの問題はNP困難であることが知られており、その計算コストは現実的ではありません。

このような背景から、統計物理学における物理現象に着想を得たメタヒューリスティック最適化手法の一つである「アニーリング」が、有効な解決策として注目されています。アニーリングは、金属の焼きなまし（アニーリング）過程を模倣したアルゴリズムです。高温状態から徐々に温度を下げ、エネルギーを最小状態へと遷移させる物理プロセスを利用することで、複雑なコスト関数の局所解に陥ることなく、大域的な最適解を効率的に探索します。

本記事では、このアニーリングが機能する基本的な仕組みと、多くの問題を統一的に扱うためのQUBO（Quadratic Unconstrained Binary Optimization）形式について解説します。さらに、Pythonライブラリである「OpenJij」と、問題を直感的に定式化するための「PyQUBO」を用いた実装例を示し、そのアルゴリズムの具体的な動作と有用性を実践的に探ります。

アニーリング（焼きなまし法）とは

アニーリングは、より良い解を見つけ出すためのアルゴリズムの一種で、そのアイデアは金属加工の「焼きなまし（焼鈍）」という工程から来ています。焼きなましとは、金属を高温に熱したあと、ゆっくりと冷やすことで、内部の歪みを取り除き、安定した状態にするための熱処理技術です。

最適化問題において、このプロセスを模倣することで、複雑な問題の最適な解（あるいはそれに非常に近い解）を探索するのがアニーリング法です。

「解の良さ」を「エネルギー」で表現する

アニーリングを理解する上で重要なのが、「エネルギー」という考え方です。最適化問題では、解の「悪さ」の度合いをエネルギー（またはコスト）という指標で表現します。つまり、「エネルギーが低い」状態ほど、「より良い解」であると考えます。アニーリングの目的は、このエネルギーが最も低い状態、すなわち最適解を見つけ出すことです。

多くの複雑な問題では、最適解（全体で最もエネルギーが低い状態）の近くに、それなりに良い解（局所的にエネルギーが低い状態、局所最適解）がいくつも存在します。単純な方法では、これらの局所最適解の一つに捕まってしまい、本当の最適解（大域最適解）にたどり着けないことがよくあります。

「温度」を利用した探索

アニーリングは、この問題を「温度」というパラメータを使って巧みに解決します。

1. 高温状態：大胆な探索 アルゴリズムは、まず「高温」状態から探索を開始します。温度が高い状態では、エネルギーが多少高くなるような「悪い」解であっても、確率的に受け入れます。この「改悪を許す」動きによって、局所最適解という”居心地の良い場所”から抜け出し、より広い範囲を大胆に探索することが可能になります。
2. 冷却過程：徐々に最適な解へ 次に、温度をスケジュールに沿って徐々に下げていきます。温度が下がるにつれて、アルゴリズムはより慎重になります。エネルギーが高くなるような悪い解は、次第に受け入れられにくくなります。探索の範囲は徐々に絞り込まれ、エネルギーの低い、より良い解の方向へと収束していきます。
3. 低温状態：解の確定 最終的に温度が十分に低くなると、アルゴリズムはエネルギーを改善する動きしかしなくなり、一つの安定した状態に落ち着きます。この状態が、アニーリングによって見つけ出された最適解（またはそれに近い解）となります。

この「悪い解をどのくらいの確率で受け入れるか」を決定するのが、以下のメトロポリス基準と呼ばれる数式です。

$$P=\exp \left(−\frac{\Delta E}{T}​ \right)$$

この式は少し難しく見えるかもしれませんが、意味するところは非常にシンプルです。

• \(P\)：悪い解を受け入れる確率
• \(\Delta E\)：現在の解と新しい解の「エネルギーの差」（悪化の度合い）
• \(T\)：現在の「温度」

この式から、温度 \(T\) が高いほど、あるいはエネルギーの差 \(\Delta E\) が小さい（悪化の度合いが低い）ほど、確率 \(P\) が高くなる、つまり悪い解を受け入れやすくなることがわかります。アニーリングは、この確率的な判断を繰り返しながら、巧みに最適解を探し出します。

QUBOとイジングモデル

アニーリングアルゴリズムを適用するためには、解決したい問題を「エネルギー関数」という数式の形で表現する必要があります。このとき、様々な問題を統一的な形式で扱うためのモデルとして「QUBO（キューボ、またはクボ）」が広く用いられています。

QUBO (Quadratic Unconstrained Binary Optimization)

QUBOは、日本語では「二次制約なしバイナリ最適化」と訳され、その名の通り以下の特徴を持つ最適化問題の形式です。

1. バイナリ変数 (Binary): 問題に使われる変数は、すべて0か1のどちらかの値しか取りません。これにより、「Yes/No」「選ぶ/選ばない」「Aグループ/Bグループ」といった、現実世界の多くの選択を表現することができます。
2. 二次形式 (Quadratic): エネルギー（コスト）を計算する目的関数が、変数の二次式（最大で変数の2乗の項まで）で構成されます。具体的には、各変数の一次の項（例：\(Q_1 x_1\)​）と、異なる2つの変数の積の項（例：\(Q_{12}​ x_1​ x_2\)​）の和で表されます。これにより、個々の選択肢のコストだけでなく、選択肢間の相互作用や関連性も表現できます。
3. 制約なし (Unconstrained): QUBOの基本的な形式には、「\(x_1​+x_2​=1\)」のような制約条件は含まれません。その代わり、制約条件は「ペナルティ項」として目的関数自体に組み込まれます。つまり、制約を破った場合にエネルギーが非常に高くなるように設計することで、実質的に制約を満たす解へと誘導します。

このQUBO形式に変換することで、例えば「どの都市をどの順番で巡るか」という巡回セールスマン問題や、「どの商品をナップサックに入れるか」というナップサック問題など、一見全く異なる問題も、アニーリングという単一の手法で解くことが可能になります。

イジングモデルとの関係

QUBOと非常によく似たモデルに、物理学の磁性体の研究から生まれた「イジングモデル」があります。イジングモデルでは、\(0\)か\(1\)のバイナリ変数の代わりに、\(+1\)か\(-1\)のスピン変数（磁石のN極とS極の向きのようなもの）を用います。

この二つのモデルは、簡単な変数変換によって相互に変換することが可能です。

\(s_i​=2 x_i ​− 1\) （QUBOの変数 \(x_i\)​ をイジングの変数 \(s_i​\) に変換）

歴史的にはイジングモデルが先にありましたが、現代の組み合わせ最適化の文脈では、0/1の概念が問題の表現と直結しやすいことから、QUBO形式が広く利用されています。重要なのは、どちらの形式を使っても本質的に同じ問題を解くことができるという点です。

OpenJij とは

「OpenJij」は、アニーリングを用いて組み合わせ最適化問題を解くために開発された、オープンソースのPythonライブラリです。前の章で説明したQUBO形式で表現された問題をインプットとして受け取り、そのエネルギー（コスト）を最小化する解を探索する「ソルバー」としての役割を担います。

OpenJijの主な役割と特徴

OpenJijは、複雑なアニーリングのアルゴリズムを、利用者が意識することなく簡単に実行できる環境を提供します。

1. 多様なアニーリングソルバーを提供 OpenJijには、複数のアニーリングアルゴリズムが「サンプラー」として実装されています。
   • Simulated Annealing (SA): これまで説明してきた、古典的な焼きなまし法です。
   • Simulated Quantum Annealing (SQA): 量子アニーリングの挙動を古典コンピュータ上で擬似的に再現するアルゴリズムです。量子効果を模倣することで、問題によってはSAよりも高速に良質な解を見つけられる場合があります。 利用者は、これらのサンプラーを数行のコードで切り替えて、性能を比較することが可能です。
2. シンプルなAPI OpenJijの使い方は非常に直感的です。QUBOをPythonの辞書形式で定義し、それをサンプラーに渡すだけで、アニーリング計算が実行され、結果が返ってきます。問題解決のロジックそのものに集中することができます。
3. 量子アニーリングへの橋渡し OpenJijは、D-Wave社などが開発する「量子アニーリングマシン」の挙動をシミュレートする目的も持って設計されています。将来的に量子コンピュータを利用する際にも、OpenJijで得た知識や経験はスムーズな移行を助けるでしょう。まずは手元のPCでアニーリングの概念を掴むための、優れた入門ツールとなります。

インストール

OpenJijは、Pythonのパッケージ管理ツールであるpipコマンドで簡単にインストールできます。なお、OpenJijは、本記事執筆時点でPythonのv3.8～3.12がサポート対象です。最新のv3.13ではインストール時にエラーになるので注意してください。

$ pip install openjij

OpenJijの詳しい使い方については、公式ドキュメントを参照してください。

OpenJijのワークフロー

OpenJijを利用した問題解決は、以下のような単純な流れで行われます。

1. QUBOの準備: 解決したい問題をQUBO形式（Pythonの辞書）で表現。
2. サンプラーの選択: SASamplerなど、使用するアニーリングアルゴリズムを選択。
3. 実行と結果の取得: サンプラーにQUBOを渡して計算を実行し、得られた解（エネルギーが最も低かった0と1の組み合わせ）を取得。

このように、OpenJijはアニーリング計算を実行する強力なエンジンですが、「どのようにして最適化問題をQUBOの形に変換するか」という課題が残ります。この課題を解決してくれるのが、次章で解説する「PyQUBO」です。

PyQUBO とは

「PyQUBO」は、組み合わせ最適化問題をQUBO形式で記述するための、オープンソースのPythonライブラリです。前の章で、OpenJijに入力するためには問題をQUBO形式（Pythonの辞書）で表現する必要があると説明しました。しかし、問題が複雑になるほど、このQUBOの係数を手計算で導き出し、辞書形式で正確に記述するのは非常に煩雑で、間違いやすい作業となります。

PyQUBOは、この「QUBOへの変換」という最も手間のかかる部分を自動化し、人間がより直感的に問題を記述できるようにするための強力なツールです。

PyQUBOの主な役割と特徴

1. 数式のように直感的な問題記述 PyQUBOの最大の特長は、最適化したい目的関数や制約条件を、まるで数式を書くかのようにPythonコードで直接表現できる点にあります。\(x_1\), \(x_2\) といった0/1のバイナリ変数を記号（シンボル）として扱い、それらを四則演算で組み合わせることで、可読性の高い形で問題を定式化できます。
2. QUBOへの自動コンパイル 数式のように記述された問題は、compile()メソッドを呼び出すだけで、PyQUBOが自動的に展開・整理し、OpenJijが受け取れるQUBO形式（辞書）へと変換してくれます。これにより、開発者は面倒な係数計算から解放され、問題のロジック構築に専念できます。
3. 制約条件の簡単な組み込み 多くの最適化問題には「AとBは同時に選べない」「合計で5個までしか選べない」といった制約条件が伴います。PyQUBOでは、こうした制約も数式として記述するだけで、自動的にペナルティ項として目的関数に組み込んでくれます。これにより、制約を満たさない解のエネルギーが非常に高くなり、結果として制約を満たす解が選ばれやすくなります。

インストール

PyQUBOも、pipコマンドで簡単にインストールできます。

$ pip install pyqubo

PyQUBOの詳しい使い方については、公式ドキュメントを参照してください。

PyQUBOとOpenJijの連携ワークフロー

PyQUBOとOpenJijを組み合わせると、問題解決のプロセスは以下のようになります。

1. 問題の定式化 (PyQUBO): pyqubo.Binaryでバイナリ変数を定義し、それらを使って目的関数と制約条件を数式のように記述します。
2. QUBOへのコンパイル (PyQUBO): 作成した式をコンパイルし、QUBO（辞書）を生成します。
3. アニーリング実行 (OpenJij): 生成されたQUBOをOpenJijのサンプラーに渡し、最適解を探索します。
4. 結果の解釈 (PyQUBO): OpenJijから得られた0/1の解を、PyQUBOを使って元の変数名に対応した分かりやすい形式にデコードします。

このように、PyQUBOは最適化問題の「定式化」を担い、OpenJijは「計算実行」を担います。この2つを組み合わせることで、アニーリングを用いた問題解決のサイクルを極めて効率的に回すことができるのです。

古典的な問題で試してみる

これまでの章で、アニーリングの理論、そしてそれを実装するためのライブラリ「OpenJij」と「PyQUBO」について学んできました。この章では、それらの知識を統合し、古典的な組み合わせ最適化問題である「数分割問題」を実際に解いてみましょう。

数分割問題 (Number Partitioning Problem) とは

数分割問題とは、「与えられた数の集合を2つの部分集合に分割し、それぞれの部分集合に含まれる数の合計値の差を可能な限り小さくする」という問題です。

例えば、{10, 8, 7, 6, 4} という数の集合がある場合、これを {10, 7} (合計17) と {8, 6, 4} (合計18) に分けると、合計値の差は |17 - 18| = 1 となり、これが最適解となります。

この問題は、数の個数が増えるにつれて組み合わせが爆発的に増加するため、全てのパターンを総当たりで調べるのは困難になります。アニーリングが非常に有効な問題の一つです。

Pythonコードによる実装

以下に、PyQUBOで数分割問題を定式化し、OpenJijで解くためのサンプルコードを示します。このコードでは、問題をQUBOに変換する部分と、アニーリングを実行する部分をそれぞれ関数にまとめています。

import numpy as np
from openjij import SASampler, SQASampler
from openjij.sampler.response import Response
from pyqubo import Array


def build_qubo(numbers: np.ndarray) -> tuple[dict, float]:
    # スピン変数の定義
    x = np.array(Array.create("X", shape=(len(numbers)), vartype="BINARY"))

    # ハミルトニアン (誤差関数の定義)
    hamiltonian = (numbers.sum() - 2.0 * np.dot(numbers.T, x)) ** 2
    problem = hamiltonian.compile()

    # QUBO行列を生成
    return problem.to_qubo()


def sample_qubo_with_sa(qubo: dict, num_reads: int = 200, num_sweeps: int = 20) -> Response:
    sampler = SASampler()
    samplesets = sampler.sample_qubo(qubo, num_reads=num_reads, num_sweeps=num_sweeps)
    return samplesets


def sample_qubo_with_sqa(qubo: dict, num_reads: int = 200, num_sweeps: int = 20) -> Response:
    sampler = SQASampler()
    samplesets = sampler.sample_qubo(qubo, num_reads=num_reads, num_sweeps=num_sweeps)
    return samplesets


if __name__ == "__main__":
    # 数分割問題（Number Partitioning Problem）をアニーリングで解くために、
    # ランダムな数値の配列を作成する
    numbers = np.random.uniform(low=0.0, high=1.0, size=(10,))
    print(f"数分割問題: {numbers}")

    # 数分割問題をQUBO形式に変換する
    qubo, offset = build_qubo(numbers)

    # シミュレーテッドアニーリング（Simulated Annealing）でQUBO問題を解く
    samplesets = sample_qubo_with_sa(qubo)
    best_record = sorted(samplesets.record, key=lambda x: x[1])
    print(f"最適解: {best_record[0][0]}, エネルギー: {best_record[0][1]}")

    # シミュレーテッド量子アニーリング（Simulated Quantum Annealing）でQUBO問題を解く
    samplesets = sample_qubo_with_sqa(qubo)
    best_record = sorted(samplesets.record, key=lambda x: x[1])
    print(f"最適解: {best_record[0][0]}, エネルギー: {best_record[0][1]}")

コードの解説

1. build_qubo 関数: この関数は、問題設定（数値のリスト）を受け取り、PyQUBOを使ってQUBOを構築する役割を担います。問題を定式化するプロセスを一つの関数にまとめることで、コードの再利用性が高まり、見通しが良くなります。
2. sample_qubo_with_sa / sample_qubo_with_sqa 関数: これらは、それぞれ異なるアニーリングアルゴリズム（SAとSQA）を実行するための関数です。引数としてQUBOを受け取り、OpenJijの各サンプラーを呼び出して計算を実行します。このようにソルバー部分を関数化しておくことで、メインの処理からはアルゴリズムの詳細が隠蔽され、手軽に異なる手法を試すことができます。
   • num_reads: アニーリングを独立して実行する回数（試行回数）を指定するパラメータです。シミュレーテッドアニーリング（SA）やシミュレーテッド量子アニーリング（SQA）は、確率的な振る舞いをするアルゴリズムです。そのため、1回実行しただけで必ず最適解にたどり着けるとは限りません。そこで、同じ設定で何度もアニーリングを繰り返し実行し、その中で最も良い結果（最もエネルギーが低い状態）を解として採用する戦略をとります。ただし、実行回数に比例して全体の計算時間が増加することに注意が必要です。
   • num_sweeps: 1回のアニーリング（1 read）の中で行われる計算のステップ数を指定するパラメータです。これは「1回の試行の丁寧さ」と考えることができます。シミュレーテッドアニーリングでは、温度をゆっくりと下げていく過程で、各温度において変数の状態を何度も更新し、より安定した（エネルギーの低い）状態へと遷移させます。ただし、この値を大きくすることで、1回あたりの計算時間が長くなります。
3. メイン処理 (if __name__ == "__main__":)
   • まず、分割したいランダムな数値のリストを生成します。
   • 次に、build_qubo関数を呼び出して、この問題をQUBO形式に変換します。
   • 最後に、sample_qubo_with_saとsample_qubo_with_sqaをそれぞれ呼び出し、同じQUBOを異なるアルゴリズムで解いています。
   • それぞれの結果から、得られた最もエネルギーの低い解（最適解）のエネルギー値を出力しています。これにより、どちらのアルゴリズムがより良い解を見つけられたかを比較することができます。
     • offset: 問題をQUBOで定式化したときの目的関数（ハミルトニアン）に現れる定数値です。バイナリ変数の値によらず一定の値を取るため、最適解を見つけるプロセスそのものには影響を与えません。ただし、ハミルトニアンのエネルギー値を正確に計算するために必要なります（材料科学や創薬分野において、物理的・化学的な意味を持つエネルギー値を求めたい場合など）。

おわりに

本記事では、メタヒューリスティック最適化手法の一つであるアニーリングの基本的な概念から、その実装を強力に支援するPythonライブラリ「PyQUBO」と「OpenJij」の活用法を、具体的な問題例を交えて解説しました。

かつては専門的な知識が要求された最適化問題の定式化やアルゴリズムの実装が、これらのライブラリを用いることで、直感的かつ簡潔に記述できるようになりました。複雑な数式を手で展開することなく、問題の本質的な構造を数式に近い形で表現し、それをシームレスにソルバーに渡すことができる一連のワークフローは、多様な分野で最適化問題に取り組むすべての人にとって大きな武器となります。

今回取り上げた数分割問題は一例に過ぎません。身の回りにあるスケジューリング、ルート最適化、リソース割り当てといった様々な課題も、QUBOとして定式化することで、本記事で紹介したアプローチを適用できる可能性があります。

More Information

• arXiv:1811.11538, Fred Glover, Gary Kochenberger, Yu Du, 「A Tutorial on Formulating and Using QUBO Models」, https://arxiv.org/abs/1811.11538
• arXiv:2103.01708, Mashiyat Zaman, Kotaro Tanahashi, Shu Tanaka, 「PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form」, https://arxiv.org/abs/2103.01708