求解のアルゴリズム¶

Fixstars Amplify Annealing Engine (Amplify AE) は、シミュレーテッドアニーリング (焼きなまし法) 法をベースにした最適化アルゴリズムで実行されます。このページでは、Amplify AE のアルゴリズムの概要と、ソルバー内部の処理ステップについて説明します。

GPU アニーリング法¶

シミュレーテッドアニーリング (焼きなまし) 法では、最適化問題を解くために、目的関数を最小化することを目指します。最初に変数セットの初期解を生成し、徐々に解を改善していきます。解を繰り返し改善していく中で、各ステップでの温度と呼ばれるパラメータの値に応じて状態遷移を行います。温度が高い場合には、現在の状態から離れた新しい状態 (目的関数の値が現在より大きくなる解) に遷移する確率が高く、温度が低い場合には、現在の状態に近い (目的関数の値が現在より小さい) 新しい状態に遷移する確率が高くなります。温度が高いうちは、探索範囲が広くより大きな変化を許容します。温度が低くなるにつれて探索範囲は狭まり、より細かい解の改善に焦点を当てます。このようにして温度を徐々に下げていくことで、最適解を見つけることを目指します。

このプロセスは次のように定式化されます。現在の温度を \(T\)、現在の状態を \(S\)、新しい状態を \(S'\)、目的関数 \(f\) の差分を \(\varDelta f = f\left(S'\right) - f\left(S\right)\) とした場合、状態遷移の確率 \(P_{S \rightarrow S'}\) は次のように表されます (メトロポリス法の場合)。

\[ P_{S \rightarrow S'} = \min \left( 1, \exp \left( -\varDelta f / T \right) \right) \]

新しく状態 \(S'\) を生成し、上記の式を評価することで状態遷移を行うかどうかを確率的に決定します。遷移が許可される場合は現在の状態が \(S'\) に更新されます。温度 \(T\) を高温から低温に変化させながら更新を繰り返すことで、解の改善が期待されます。

このプロセスが逐次的に行われるために、一般的にシミュレーテッドアニーリング法は並列化が難しいとされています。並列化のアルゴリズムはいくつかの方針が提案されていますが、Amplify AE では、GPU の計算性能を活かすことに特化した独自の並列化アルゴリズム [1] を採用することで、探索プロセス全体を高速かつ効果的に実行します。具体的には、遷移先の状態の候補の生成や目的関数の評価について GPU の並列計算を活用し、複数の遷移先の候補を用いた効率的な探索を実現しています。

注釈

疑似乱数を用いて確率的に状態遷移を行うため、実行する度に同じ入力に対しても異なる解が得られることがあります。 GPU による並列計算では計算順序を制御できないため、たとえ疑似乱数のシード値を固定しても計算結果が同一になる保証がありません。
そのため、現在の Amplify AE ではシード値の設定はサポートされていません。

一方、シミュレーテッドアニーリング法では温度変化のスケジューリングが重要です。ここで温度の変化のスケジューリングとは、初期温度と最終温度の決定と、その初期温度から最終温度への変化の仕方のことを意味します。温度スケジュールのチューニングは高精度の解を得るために必須の要素です。この問題に対し、Amplify AE では温度スケジューリングを自動的に調整する機能を有しており、ユーザーは温度に関するパラメータを設定する必要なく、適切な求解を可能としています。通常の温度スケジュールでは最終温度までのステップ数を指定して探索を終了しますが、Amplify AE は探索過程の最小単位を入力された問題や求解の状況に応じて自動的に決定します。さらにこれを継続的に繰り返すことで、与えられた求解時間 (time_limit_ms リクエストパラメータ) が経過するまで探索を続けます。これにより、実行時間を長く指定するほど高精度な解を得る可能性が高まります。

目的関数の最適化¶

上記のアルゴリズムに従い、入力された目的関数に対して次のようにして新しい状態 \(S'\) と目的関数の値 \(f\left(S'\right)\) を計算します。まずは制約条件が存在しない場合の目的関数の最適化について説明します。

Amplify AE はバイナリ変数の多項式を入力として受け付けるため、ある変数 \(q\) に対してその変数の値を反転 (\(0\) を \(1\) あるいは \(1\) を \(0\) に) する操作 \(q \leftarrow 1 - q\) を行うことで新しい状態 \(S'\) を生成します。このとき、目的関数の差分 \(\varDelta f\) は次のように表されます。

\[ \varDelta f_{\rm{obj}}^q = f\left(S'\,|\,q \leftarrow 1 - q \right) - f\left(S \,|\,q\right) \]

この値から状態遷移確率 \(P_{S \rightarrow S'}\) を計算し、一様乱数を生成して状態遷移が許可されるかどうかを決定します。状態遷移が許可される場合は、現在の状態 \(S\) が新しい状態 \(S'\) に更新されます。

制約条件の最適化¶

アニーリング法で制約条件を扱う場合、与えられた全ての制約条件が満たされる解について目的関数の最小化を実行する必要があります。制約条件を満たす解を得るためには、例えば制約条件を満たす状態遷移のみを許可する方法が考えられます。しかし、候補となる状態遷移が制約条件を満たすかどうかを確認するために、全ての制約条件を評価する必要があり、計算量が増大してしまいます。さらに、制約条件を満たす状態遷移のみを許可すると、探索空間が狭まり必ずしも最適解に到達できない可能性があります。

そこで、Amplify AE では、制約条件を満たす解を得るために、制約条件に相当するペナルティ関数を導入し、これを目的関数の追加項として扱います。基本的に、ペナルティ関数は制約条件を満たす解に対しては \(0\) となり、制約条件を満たさない解に対しては \(0\) より大きな値をとる性質を持ちます。これにより、目的関数の最小化と同時にペナルティ関数の値が \(0\) となれば、制約条件を満たす解が得られることになります。

この方針は、量子アニーリングやイジングマシンハードウェアなどの QUBO ソルバーで制約条件を扱う際に広く用いられる方法です。探索の途中ではあえて制約条件を満たさない状態遷移を許可することで探索空間を広げることができます。

ある制約条件 \(c\) のペナルティを \(g_c\) とした場合、目的関数と同様にして、変数 \(q\) を反転するときのペナルティ関数の差分 \(\varDelta g_c\) を次のように定義します。

\[ \varDelta g_c^{q} = g_c\left(S'\,|\,q \leftarrow 1 - q \right) - g_c\left(S \,|\,q\right) \]

さらに、目的関数の差分を \(\varDelta f\) を次のように読み替えます。

\[ \varDelta f = \varDelta f_{\rm{obj}}^q + w \sum_c \varDelta g_c^{q} \]

この \(\varDelta f\) から状態遷移確率 \(P_{S \rightarrow S'}\) を計算して状態を更新していきます。

ここで \(w \left(> 0 \right)\) はペナルティ関数の重みを表します。終状態で制約条件を満たすためには、ペナルティ関数を適切に調整する必要がある点に注意を要します。目的関数の変化に対して制約条件の重みが小さいと、制約条件を満たさない解が選択される可能性が高くなります。一方で、重みが大きすぎると目的関数の最小化が難しくなる可能性があります。このバランスが高い精度で解を得るために非常に重要です。Amplify AE では、ペナルティ関数の重みを自動的に調整する機能を有しており、ユーザーはこのパラメータを設定することなく適切な求解を行うことができます。

Amplify AE によるペナルティ関数の評価は、ユーザの入力に応じて次の 2 通りの方法で行われます。

(i) デフォルトの場合

ユーザから制約条件式を受け取った場合、ペナルティ関数は制約の違反量に対して単調増加する式として Amplify AE が実行時に計算します。このとき、Amplify AE はペナルティ関数 \(g_c\) を違反量 \(d\) の関数として以下の性質を満たすように生成します。

\[\begin{split} \begin{align*} g_c\left(d \right) & = \begin{cases} 0 & (d = 0; c \text{ is satisfied}) \\ \text{positive value} & (d > 0; c \text{ is not satisfied}) \end{cases} \\ g_c \left(d_1 \right) & = g_c \left(d_2 \right) \quad \text{for} \quad d_1 = d_2 \\ g_c \left(d_1 \right) & < g_c \left(d_2 \right) \quad \text{for} \quad d_1 < d_2 \end{align*} \end{split}\]

ペナルティ関数は、ユーザが入力した制約条件に基づき、Amplify AE の求解中に自動生成されます。もしペナルティ関数をユーザが直接指定したい場合は、次の PUBO モードを利用します。

(ii) PUBO モードの場合

ユーザが制約条件の代わりにペナルティ関数を与えた場合、指定されたペナルティ関数を利用してペナルティ値を評価します。この動作状態を PUBO モードと呼びます。ここでペナルティ関数は以下を満たす必要があります。

\[ g_c\left(d \right) \ge 0 \]

PUBO モードでは、ユーザはペナルティ関数 \(g_c\) とその重み \(w_c\) を直接指定します。これらを用いて状態遷移の差分は以下のように計算されます。

\[ \varDelta f = \varDelta f_{\rm{obj}}^q + w \sum_c w_c \varDelta g_c^{q} \]

ペナルティ関数全体にかかる \(w\) は、前述の Amplify AE が自動調整する重みです。PUBO モードでのみ、この機能の制御をリクエストデータの penalty_weight_calibration フィールドで設定できます。これを無効 (false) にした場合は \(w = 1\) に固定化されます。

一方 \(w_c\) はユーザがペナルティ関数ごとに個別に指定可能で、相対的な重み付けを担います。デフォルトは \(w_c = 1\) です。制約条件を満たす解が得られない場合などには、ユーザがこの値を調整することで求解の精度を向上させることができます。

通常、違反量 \(d\) が \(0\) のときはペナルティ関数の値も \(0\) となり、制約が満たされていると解釈されます。これに対して、オプションとして違反量に対して制約が満たされていると見なす閾値 \(d_{\text{th}}\) を設定することもできます。これを用いると、\(d \le d_{\text{th}}\) の場合、仮にペナルティ関数の値が \(0\) でなくても、制約条件が満たされていると見なします。この値を設定する必要があるのは、例えば緩和法を用いて制約条件のペナルティを設定する場合です。この値を用いて Amplify AE は取得した解が制約条件を満たすかを判定するのに利用します。Amplify SDK を用いて定式化した場合、ペナルティ関数の性質に応じて \(d_{\text{th}}\) は適切な値が自動的に設定されます。

参考

Amplify SDK を用いてモードの切り替えやペナルティ関数の設定を行う方法についてはクライアントのページを参照してください。