当社はCookieを使用して、お客様が当社のWebサイトでより良い体験を得られるようにしています。引き続き閲覧する場合は、当社グループのプライバシーポリシー 
に同意したことになります。
Jupyter Notebookで実行する
チュートリアルそもそも最適化問題とは、「さまざまな制約の下で、数ある選択肢の中からある観点で最適な選択を決定 する」ような問題を指します。最適化問題の例として以下のようなものがあります。
このような問題を数式(数理モデル)で記述し、数理的な計算手法で最善策を求めることを「数理最適化」といいます。
組合せ最適化問題の具体例として、数の分割問題について考えてみます。
$n$ 個の整数の集合 $A$ が
$$ A = \{a_0, a_1, \cdots, a_{n-1} \} $$で与えられているとします。 $A$ を二つの集合 $A_0$ と $A_1$ に分割することを考えます。以下のような問題が数の分割問題です。
10個の整数の集合 $A=\{2,10,3,8,5,7,9,5,3,2\}$ の分割を考えてみます。
例えば $A_0=\{2,3,5,7,10\}, A_1=\{2,3,5,8,9\}$のように分割すると、それぞれの集合の要素の和が等しいことが確認できます。 よって、判定問題としては「存在する」が解答となり、最適化問題としては上記の $A_0, A_1$ が解答となります。
ここでは、数の分割問題のうち、最適化問題を解くことを考えます。
集合 $A$ に属する $n$ 個の各要素に対応した $n$ 個のバイナリ変数とイジング変数を $$ \begin{align} q_i &\in\{0, 1\}\quad (i=0, 1, \cdots, n-1) \quad \text{(Binary)}\\ s_i &\in\{-1, 1\}\quad (i=0, 1, \cdots, n-1) \quad \text{(Ising)} \end{align} $$ とします。これらの変数は、$q_i=0$ ($s_i=-1$) の場合は $a_i$ は $A_0$ に属し、$q_i=1$ ($s_i=1$) の場合は $a_i$ は $A_1$ に属することを意味します。 集合 $A_0$ の要素の和を $S_0$、集合 $A_1$ の要素の和を$S_1$とします。 $$ \begin{align} S_0 &= \sum_{a_i\in A_0}a_i\\ S_1 &= \sum_{a_i\in A_1}a_i \end{align} $$
次に、目的関数を作成することを考えます。 目的関数は上記のバイナリ変数、もしくはイジング変数の関数であり、求めるべき条件が満たされた場合に最小値をとるような関数です。 ここでは、 $S_0 = S_1$ の条件を満たす分割を探すため、目的関数を $(S_1 - S_0)^2$ とすると、条件が満たされた時に $0$ となり最小値をとります。 したがって、バイナリ変数、またはイジング変数を使うと、目的関数 $f$ は以下のように書き下すことができます。
$$ \begin{align} f &= \left(S_1 - S_0\right)^2 = \left(\sum_{a_i\in A_1}a_i - \sum_{a_i\in A_0}a_i\right)^2\\ &= \left(\sum_{i=0}^{n-1}(2q_i -1)a_i\right)^2 \quad \text{(Binary)}\\ &= \left(\sum_{i=0}^{n-1} a_i s_i \right)^2\quad \text{(Ising)} \end{align} $$1行目から2行目（3行目）への変換は、$q_i=1$ ($s_i=1$) または $q_i=0$ ($s_i=-1$) によって、$a_i$ は $A_0$ または $A_1$ に割り当てられることを使いました。 $f$ の値が $0$ かどうか確認することで、条件を満たす分割がなされたかどうかを確かめることができます。
from amplify import (
IsingSymbolGenerator,
IsingPoly,
)
# 数の集合Aに対応する数のリスト
A = [2, 10, 3, 8, 5, 7, 9, 5, 3, 2]
# len(A): 変数の数
n = len(A)
# イジング変数を生成
gen = IsingSymbolGenerator()
s = gen.array(n)
# 変数を確認
print(s)
数のリスト $A$ と先ほど生成したイジング変数を用いて目的関数を構築します。
# 目的関数の構築: イジング
f = IsingPoly()
for i in range(n):
f += s[i] * A[i]
f = f**2
イジングマシンで問題を実行してみます。
from amplify.client import FixstarsClient
from amplify import Solver
from amplify import decode_solution
# クライアントの設定
client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウト1秒
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境で使用する場合は、Amplify AEのアクセストークンを入力してください
solver = Solver(client)
result = solver.solve(f)
# 解が得られなかった場合、len(result) == 0
if len(result) == 0:
raise RuntimeError("No solution was found")
energy = result[0].energy
values = result[0].values
# エネルギー値 (f の最小値) を確認
print(f"f = {energy}")
# valuesを確認
# 変数 s_i の i=0, 1, ..., N-1 の値を格納した辞書
print(f"values = {values}")
$f$ の値が $0$ となる解となっているので、条件を満たす解が見つかったことがわかります。
見つかった解を元の変数 s に代入するには、decode メソッドを使います。
solution = s.decode(values)
print(solution)
最後に、得られた解を元に、集合 $A$ の数字を二つのグループに分割します。
二つのリスト $A_0$ と $A_1$ を用意し、解が $0$ に対応する数字は $A_0$に、そうで無い場合は $A_1$ に割り振ります。
A0 = sorted([A[idx] for idx, val in enumerate(solution) if val != 1])
A1 = sorted([A[idx] for idx, val in enumerate(solution) if val == 1])
print(f"A0 = {A0}")
print(f"A1 = {A1}")
$A_0$ と $A_1$ のそれぞれの数字の和が等しいことを確かめます。和は 27 となっていることが確認できます。
print(f"{sum(A0) == sum(A1)}, {sum(A0)}")
先ほどの問題では、解を一つだけ得る方法を紹介しました。しかしながら、この問題では、条件を満たす解は複数個見つけることができます。この分割問題の設定では、条件は目的関数が $0$
であることと等価であるため、条件を満たす解が複数個ある場合は、エネルギー値が $0.0$ である解が複数個あるということになります。一部のマシンは、同じエネルギーを持つ解を複数得ること出来ます。Fixstars
Amplify AE の場合はパラメータ client.parameters.outputs.duplicate を True
に設定することで複数の解が出力されます。
from amplify.client import FixstarsClient
from amplify import Solver
client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウト1秒
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境で使用する場合は、Amplify AEのアクセストークンを入力してください
client.parameters.outputs.duplicate = True # 同じエネルギー値の解を列挙するオプション（解が複数個あるため）
solver = Solver(client)
result = solver.solve(f)
解が複数個あることは以下のようにして確かめることができます。46個の解が見つかるはずです。
len(result)
次に、見つけてきた複数の解を元の変数に代入して全ての分割を求めます。$(A_1, A_0)$ と $(A_0, A_1)$ の組合せを同一視する必要があることに注意して下さい。
from amplify import decode_solution
partitions = set()
for sol in result:
solution = decode_solution(s, sol.values)
A0 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val != 1]))
A1 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val == 1]))
# 同じ分割がすでにリストに含まれていない場合
if (A1, A0) not in partitions:
partitions.add((A0, A1))
for p in partitions:
print(f"sum = {sum(p[0])}, {sum(p[1])}, partition: {p}")
バイナリ変数は $q_i\in\{1, 0\}$ の二値変数です。
BinarySymbolGenerator を用いてバイナリ変数の配列を生成することができます。
バイナリ変数を用いた目的関数は次のように与えられます。
$$ f = \left(\sum_{i=0}^{N-1}(2q_i -1)a_i\right)^2 $$これをAmplifyで実装してみます。
from amplify import (
BinarySymbolGenerator,
BinaryPoly,
)
# 数の集合Aに対応する数のリスト
A = [2, 10, 3, 8, 5, 7, 9, 5, 3, 2]
# 変数の数
n = len(A)
# バイナリ変数を生成
gen = BinarySymbolGenerator()
q = gen.array(n)
# 目的関数の構築: バイナリ
f = BinaryPoly()
for i in range(n):
f += (2 * q[i] - 1) * A[i]
f = f**2
イジング変数の場合と同様に実行してみます。
from amplify.client import FixstarsClient
from amplify import Solver
client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウト1秒
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境で使用する場合は、Amplify AEのアクセストークンを入力してください
client.parameters.outputs.duplicate = True # 同じエネルギー値の解を列挙するオプション（解が複数個あるため）
solver = Solver(client)
result = solver.solve(f)
partitions = set()
for sol in result:
solution = q.decode(sol.values)
A0 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val != 1]))
A1 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val == 1]))
# 同じ分割がすでにリストに含まれていない場合
if (A1, A0) not in partitions:
partitions.add((A0, A1))
for p in partitions:
print(f"sum = {sum(p[0])}, {sum(p[1])}, partition: {p}")
イジング変数で解いた場合と同様の解が得られました。
