当社はCookieを使用して、お客様が当社のWebサイトでより良い体験を得られるようにしています。引き続き閲覧する場合は、当社グループのプライバシーポリシー 
に同意したことになります。
Jupyter Notebookで実行する
チュートリアルこのチュートリアルでこれまで扱ってきた最適化問題では決定変数が取りうる値に制限がなく、決定変数が取りうるすべての値の組み合わせの中から目的関数を最小化する値を探索しました。
しかし、一般の最適化問題では決定変数がある特定の条件を満たす場合の中から最適解を求めなければならない場合があります。 このような問題を制約付き最適化問題といいます。
制約付き最適化問題としては下記のような例があります。
上では不等式制約を例として挙げましたが、それ以外にも
などがあります。 制約が課されていると、制約条件を満たす「実行可能解」の中から最適解を見つける必要があります。
しかし、 QUBO やイジングモデルでは制約を扱うことができません。 そのため、制約条件付きの最適化問題を QUBO に帰着させて解く場合は、その制約条件を目的関数の一部として表現する必要があります。
基本的なアプローチとして、制約条件を満たす場合に最小値をとるようなペナルティ関数 $g$ を元の目的関数 $f$ に重みを付けて追加する方法が行われます。 $f$ の代わりに、$h = f + \lambda g \quad (\lambda \gt 0)$ の最適解を求めることで、ペナルティ関数 $g$ が最小、すなわち制約条件を満たす実行可能解の取得が可能になります。 実際には、得られた解が必ずしも最適解であるとは限らないので、$h$ の解を $g$ で評価したときに最小値であるかを確認することで、実行可能解かどうかを識別します。
例えば、等式制約
$x_1 + x_2 = 1$
は以下のようなペナルティ関数を用いて表現できます。
$g(\mathbf{x}) = (x_1 + x_2 - 1)^2$
この関数は $x_1 + x_2 = 1$ のときのみ $g(\mathbf{x}) = 0$ となり、それ以外の場合は正の値 $g(\mathbf{x}) > 0$をとります。
各制約に対してこのようなペナルティ関数を考える必要がありますが、Amplify を用いることによって上で挙げた制約条件 (不等式制約、等式制約、論理式制約) を自動でペナルティ関数として目的関数に追加することができます。
Amplify では典型的な制約条件について、目的関数とは別に制約条件オブジェクトという形で抽象化します。
制約条件オブジェクトを用いることで、以下のようなメリットを得られます。
equal_toone_hotless_equal, greater_equal, clamp3つのバイナリ変数 $\mathbf{q} = (q_0, q_1, q_2)$ を生成し、これらの変数間に
$$ q_0 q_1 + q_2 = 1 $$の等式制約を課すことを考えます。Amplify では、equal_to 関数を用いて等式制約に対応したオブジェクトを生成することができます。
from amplify import (
BinarySymbolGenerator,
BinaryPoly,
sum_poly,
Solver,
)
from amplify.client import FixstarsClient
from amplify.constraint import equal_to
gen = BinarySymbolGenerator()
q = gen.array(3) # バイナリ変数を3個生成
g = equal_to(q[0] * q[1] + q[2], 1) # 等式制約
print(f"g: {g}") # 制約条件を表示
この制約条件では、以下のソースコードを動作させることで
$$ (q_0, q_1, q_2) = (1, 1, 0),\, (1, 0, 1),\, (0, 0, 1),\, (0, 1, 1) $$となる4つの解を得ることが確認できます。
# クライアント設定
client = FixstarsClient() # Fistars Amplify AE
client.parameters.timeout = 1000 # タイムアウト1秒
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境で使用する場合は、Amplify AEのアクセストークンを入力してください
client.parameters.outputs.duplicate = True # エネルギー値が同一の解を出力
client.parameters.outputs.num_outputs = 0 # 0: 見つかった解を全て出力
solver = Solver(client) # 設定済みのクライアントからソルバーを定義
result = solver.solve(g) # 与えられた制約条件を解く
# 結果を表示
for sol in result:
print(f"energy = {sol.energy}, {q} = {q.decode(sol.values)}")
等式制約の例として、 one-hot 制約を紹介します。
$N$個のバイナリ変数 $q_0, q_1, \cdots, q_{N-1}$ が与えられている際に、これらの変数のどれか一つだけが $1$ となり、それ以外の変数は全て $0$ となるような制約を課すような場合があります。 このような制約は one-hot 制約と呼ばれ、以下の式として表すことができます。
$$ \sum_{i=0}^{N-1}q_i = q_0 + q_1 + \cdots + q_{N-1} = 1 $$この制約を表すペナルティ関数は
$$ g(\mathbf{q}) = \left(\sum_{i=0}^{N-1}q_i - 1\right)^2 $$となり、制約条件が満たされた場合は最小値 $0$ をとり、それ以外の場合は正の値をとる関数となります。
以下では バイナリ変数が3つの場合の one-hot 制約に対応したペナルティ関数の実装と確認方法を紹介します。
$q_0, q_1, q_2$ の3つのバイナリ変数に $q_0 + q_1 + q_2 = 1$ の制約を課したプログラムを動作させることで、
$$ (q_0, q_1, q_2) = (0, 0, 1),\, (0, 1, 0),\, (1, 0, 0) $$となることが確認できます。
from amplify.constraint import one_hot
g = one_hot(q) # one-hot 制約のヘルパ関数
print(f"g: {g}") # 制約条件を表示
# 問題を解いて結果を表示
result = solver.solve(g)
for sol in result:
energy = sol.energy
values = sol.values
print(f"energy = {energy}, {q} = {q.decode(values)}")
Amplifyでは、整数値をとる多項式と整数定数の大小関係を制約条件として設定できます。
整数値多項式$f$、整数定数$c$,$c_1$,$c_2$に対して、Amplifyで用いることのできる不等式制約条件と、対応する制約条件オブジェクトを生成する関数を下の表に示します。
| 制約 | 関数 |
|---|---|
| f(q) ≦ c | less_equal(f,c) |
| f(q) ≧ c | greater_equal(f,c) |
| c_1 ≦ f(q) ≦ c_2 | clamp(f, c_1, c_2) |
less_equalの例¶3つのQUBO変数 $\mathbf{q} = (q_0, q_1, q_2)$ を生成し、これらの変数間に
$ q_0 + q_1 + q_2 \leq 1 $
の不等式制約を課すことを考えます。less_equal 関数を用いて不等式制約に対応したオブジェクトを生成することができます。
from amplify.constraint import less_equal
gen = BinarySymbolGenerator()
q = gen.array(3) # バイナリ変数を3個生成
g2 = less_equal(q, 1) # 不等式制約
print(f"g2: {g2}") # 制約条件を表示
result = solver.solve(g2) # 与えられた制約条件を解く
for sol in result:
print(f"energy = {sol.energy}, {q} = {q.decode(sol.values)}")
この制約条件では、上記のソースコードを実行することで
$ (q_0, q_1, q_2) = (0, 0, 0),\,(0, 0, 1),\, (0, 1, 0),\, (1, 0, 0) $
となる4つの解を得ることが確認できます。
greater_equalの例¶3つのQUBO変数 $\mathbf{q} = (q_0, q_1, q_2)$ を生成し、これらの変数間に
$ q_0 + q_1 + q_2 \ge 2 $
の不等式制約を課すことを考えます。greater_equal 関数を用いて不等式制約に対応したオブジェクトを生成することができます。
from amplify.constraint import greater_equal
gen = BinarySymbolGenerator()
q = gen.array(3) # バイナリ変数を3個生成
g2 = greater_equal(q, 2) # 不等式制約
print(f"g2: {g2}") # 制約条件を表示
result = solver.solve(g2) # 与えられた制約条件を解く
for sol in result:
print(f"energy = {sol.energy}, {q} = {q.decode(sol.values)}")
この制約条件では、上記のソースコードを実行することで
$ (q_0, q_1, q_2) = (1, 1, 1),\,(0, 1, 1),\, (1, 1, 0),\, (1, 0, 1) $
となる4つの解を得ることが確認できます。
clampの例¶3つのQUBO変数 $\mathbf{q} = (q_0, q_1, q_2)$ を生成し、これらの変数間に
$ 1 \le q_0 + q_1 + q_2 \le 2 $
の不等式制約を課すことを考えます。clamp 関数を用いて不等式制約に対応したオブジェクトを生成することができます。
from amplify.constraint import clamp
gen = BinarySymbolGenerator()
q = gen.array(3) # バイナリ変数を3個生成
g2 = clamp(q, 1, 2) # 不等式制約
print(f"g2: {g2}") # 制約条件を表示
result = solver.solve(g2) # 与えられた制約条件を解く
for sol in result:
print(f"energy = {sol.energy}, {q} = {q.decode(sol.values)}")
この制約条件では、上記のソースコードを実行することで
$ (q_0, q_1, q_2) = (0, 0, 1),\, (0, 1, 0),\, (1, 0, 0),\,(0, 1, 1),\, (1, 1, 0),\, (1, 0, 1) $
となる6つの解を得ることが確認できます。
制約条件同士を足すことによって複数の制約条件を課すことができます。例えば、制約条件オブジェクトg1と制約条件オブジェクトg2が与えられたとき、「g1 かつ
g2」という制約条件はg1 + g2で得られます。
from amplify.constraint import penalty
gen = BinarySymbolGenerator()
q = gen.array(2) # バイナリ変数を2個生成
g1 = penalty(q[0])
g2 = penalty(q[1])
print(f"g1 + g2 : {g1 + g2}")
制約条件オブジェクトががもたらすペナルティ値の大きさはスカラーとの掛け算を用いることで調整できます。
gen = BinarySymbolGenerator()
q = gen.array(1) # バイナリ変数を1個生成
g = penalty(q[0])
print(f"g : {g}")
# 制約条件の重みを2倍にする
g_2 = 2 * g
print(f"g_2 : {g_2}")
上の例では $q_0 = 1$ のときに $g(q) = 1$ 、 $q_0 = 0$ のときに $g(q) = 0$ となります。
g_2 = 2 * g とすることによって、$q_0 = 1$ のときに $g_2(q) = 2$ 、 $q_0 = 0$ のときに $g_2(q) = 0$ となります。
目的関数に制約を足すことによって制約付き最適化問題を表すモデルを生成することができます。
例として以下のような制約付き最適化問題を考えます。
制約条件がなければ、$(q_0,q_1) = (0,0)$が最適解となりますが、制約条件をつけることで解が$(q_0,q_1) = (0,1)$へと変化します。
gen = BinarySymbolGenerator()
q = gen.array(2) # バイナリ変数を2個生成
# 目的関数
objective = 2 * q[0] + q[1]
result_cost_only = solver.solve(objective) # 制約なし最適化問題を解く
print("制約なし最適化問題の解")
for sol in result_cost_only:
print(f"energy = {sol.energy}, {q} = {q.decode(sol.values)}")
# 制約条件
p = one_hot(q)
# 制約付き最適化問題
model = objective + p
result = solver.solve(model) # 制約付き最適化問題を解く
print("制約付き最適化問題の解")
for sol in result:
print(f"energy = {sol.energy}, {q} = {q.decode(sol.values)}")
