OpenJij SA Parameter Dependency Experiment with MINTO - MINTO - 最適化のための管理・洞察ツール

ここでは、OpenJijのシミュレーテッドアニーリング(SA)アルゴリズムのパラメータが、SAのパフォーマンスにどう影響を与えるかを簡単に調べてみます。 SAアルゴリズムは温度をパラメータとして持ち、OpenJijではQUBOもしくはIsing模型の係数をベースに温度を自動で設定します。グリッドサーチを用いて、このパラメータの自動設定の有効性を調べてみましょう。グリッドサーチの場合でも、MINTOをログ記録として利用すれば、データをpandas.DataFrameに簡単に変換し可視化することができます。これにより、様々なパラメータの組合せと、それらが解の品質や実行時間に与える影響を分析することが可能です。

import matplotlib.pyplot as plt
import numpy as np
import openjij as oj
import seaborn as sns

import minto

1. Create Random QUBO¶

def random_qubo(n, sparsity=0.5):
    q = np.random.uniform(-1, 1, (n, n))
    q = (q + q.T) / 2
    zero_num = int(n**2 * sparsity)
    zero_i = np.random.choice(n, zero_num, replace=True)
    zero_j = np.random.choice(n, zero_num, replace=True)
    q[zero_i, zero_j] = 0
    q[zero_j, zero_i] = 0
    qubo = {}
    for i in range(n - 1):
        for j in range(i, n):
            qubo[(i, j)] = q[i, j]
            qubo[(j, i)] = q[j, i]
    return qubo

n = 200
q = random_qubo(n)

2. デフォルトの設定で実行する¶

OpenJijでは、.sample_quboの戻り値の中にある.info['schedule']を通して、自動で決定されたSAパラメータを確認することができます。 SAの温度設定はアニーリングスケジュールと呼ばれ、これらのパラメータは’schedule’のキーの下に保存されます。

sampler = oj.SASampler()
response = sampler.sample_qubo(q)
schedule = response.info["schedule"]
schedule

MINTOを用いたグリッドサーチ¶

SAの逆温度パラメータを変化させることで、最適化結果がどのように変わるかを見てみましょう。比較のために、OpenJijのデフォルトのパラメータも検索範囲に含めておきます。 OpenJijの結果から重要な値は、.log_parameterメソッドを用いて保存されます。完全なOpenJijのresponseオブジェクトも、.to_serializableを指定した.log_objectを用いて保存されます。

exp = minto.Experiment(auto_saving=False, verbose_logging=False)

# log_object accepts only serializable objects
# so we need to convert qubo to serializable object
qubo_edges = [[i, j] for i, j in q.keys()]
qubo_vales = [q[i, j] for i, j in qubo_edges]
exp.log_global_object("qubo", {"qubo_edges": qubo_edges, "qubo_vales": qubo_vales})

beta_min_list = [schedule["beta_min"], 0.1, 1.0, 2.0, 3.0, 4.0, 5.0]
beta_max_list = [10.0, 20, 30.0, 40.0, 50.0, 12404, schedule["beta_max"]]
num_reads = 300

exp.log_global_parameter("num_reads", num_reads)

for beta_min in beta_min_list:
    for beta_max in beta_max_list:
        run = exp.run()
        with run:
            # Log the beta parameters for this run
            run.log_parameter("beta_min", beta_min)
            run.log_parameter("beta_max", beta_max)

            sampler = oj.SASampler()
            response = exp.log_solver(sampler.sample_qubo)(
                q, num_reads=num_reads, beta_min=beta_min, beta_max=beta_max
            )
            run.log_object("response", response.to_serializable())
            energies = response.energies
            run.log_parameter("mean_energy", np.mean(energies))
            run.log_parameter("std_energy", np.std(energies))
            run.log_parameter("min_energy", np.min(energies))
            run.log_parameter("exec_time", response.info["execution_time"])

run_table = exp.get_run_table()
run_table

4. 結果の可視化¶

pivotメソッドをしようし、run_tableをヒートマップでの可視化に適した形式に変換しましょう。 MINTOの.get_run_table()は二重ヘッダーを持つDataFrameを返します。そのため、関連するDaFrameを抽出するためにparameterキーを使用し、得られたものをヒートマップで可視化するために変換します。

param_table = run_table["parameter"].pivot(
    index="beta_min", columns="beta_max", values="mean_energy"
)
param_table

sns.heatmap(param_table, annot=True, fmt="1.1f", cmap="coolwarm")
plt.xlabel("beta_max")
plt.ylabel("beta_min")
plt.title("mean energy")
plt.show()

5. 結果の解析¶

この結果を見ると、OpenJijのデフォルトのパラメータは悪くありません。しかし、beta_max=40.0, beta_min=0.1付近でより最適なパラメータがあるように見えます。別の視点から見てみましょう。 OpenJijのアルゴリズムでは、スピンフリップが拒否された場合、その計算は行われません。スピンフリップが発生した場合には、そのエネルギー差を計算します。そのため、温度が高い(逆温度 $\beta$ が低い)状態が長期間続くと、スピンフリップ回数が増加し、計算時間が長くなります。結果として、温度設定に依存して計算時間が変化します。これらの結果を可視化してみましょう。 OpenJijの計算時間は、マイクロ秒単位で測定されています。

exec_table = run_table["parameter"].pivot(
    index="beta_min", columns="beta_max", values="exec_time"
)
sns.heatmap(exec_table, annot=True, cmap="coolwarm", annot_kws={"size": 8})
plt.xlabel("beta_max")
plt.ylabel("beta_min")
plt.title("Execution time")
plt.show()

OpenJijのデフォルトのパラメータについての解析¶

残念なことに、OpenJij のデフォルトのパラメータは、計算時間の点で最適ではないことがわかりました。温度パラメータは、SAのステップ数を制御するnum_sweepsパラメータの影響も受けます。この数値実験により、OpenJijの温度パラメータ設定には、依然として改善の余地があることが明らかとなりました。そしてMINTOは、ソルバーパラメータの設定に関する知見を得る上で有用であることがわかります。