3. 多項式と目的関数¶

目的関数は組合せ最適化問題における目的の達成度を表す数式です。Amplify SDK では最小化したい多項式のことを指します。このページでは、Amplify SDK を用いて多項式を表現する方法について解説します。

Tip

多項式を最大化したい組合せ最適化問題を解きたい場合は、その目的関数を -1 倍することで最小化問題に変換することができ、 Amplify SDK による最適化が可能となります。

参考

目的関数を表現する別の方法として、多項式の係数からなる多次元配列を用いる方法も用意されています。この方法は、目的関数が \(x^\top Q x + p^\top x + c\) と表されるような実数値の 2 次元配列 \(Q\) と実数ベクトル \(p\) がすでに計算されている場合などに便利となります。詳細は「係数行列による目的関数の作成」を参照してください。

3.1. 多項式の構築¶

組合せ最適化問題の目的関数や制約条件式を表現するために、多項式クラス Poly が用意されています。前節で VariableGenerator クラスを使って発行した変数も、Poly のインスタンスとなっています。

VariableGenerator により作成した変数に対して四則演算や冪乗を行うことで、簡単に任意の多項式を作成することができます。

from amplify import VariableGenerator

gen = VariableGenerator()
q = gen.array("Binary", 6)
p = -q[0] + 2.3 * q[1] * q[2] - (q[3] + q[4]) ** 2 * q[5]

>>> print(p)
- 2 q_3 q_4 q_5 + 2.3 q_1 q_2 - q_3 q_5 - q_4 q_5 - q_0

Tip

以下で定義される論理演算子も実装されています。これは、単一のバイナリ変数など、0 または 1 の値しかとらないことが分かっている多項式から制約条件を作る場合に便利です。

演算子	効果
`&` (論理積)	`x & y` は `x * y` と等価
`\|` (論理和)	`x \| y` は `-x * y + x + y` と等価
`^` (排他的論理和)	`x ^ y` は `-2 * x * y + x + y` と等価

同じ VariableGenerator から作成された変数であれば、異なる変数配列の変数や、種類の異なる変数を同じ多項式に含めることもできます。

gen = VariableGenerator()
q = gen.array("Binary", 3)
s = gen.array("Ising", 2)
n = gen.scalar("Integer", bounds=(-1, 2))
p = q[0] + s[1] - 2 * n

>>> print(p)
q_0 + s_1 - 2 n_0

注意

異なる VariableGenerator のインスタンスから発行された変数同士を組み合わせて目的関数や制約条件を作成することはできません。 1つの定式化には、共通の VariableGenerator のインスタンスから発行された変数を使用する必要があります。

作成した多項式は、そのまま目的関数として利用することができます。したがって、たとえば目的関数が \(q_0 q_1 - q_2\) であるとき、目的関数は以下のように表現できます。

gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]

3.2. 多項式配列を用いた多項式の構築¶

注釈

この節で解説する内容は、 NumPy ライブラリにある程度なじみがある方を対象としています。

多項式配列クラスの持つ配列演算を用いると多項式の生成が高速になり、NumPy ライブラリに慣れ親しんでいる方にとっては直感的になります。ただし、上記で解説した方法で既に任意の多項式を作成することができるため、この節は必要に応じて読み飛ばしても構いません。

多項式の構築をより簡単で高速にするために、多項式の配列を表すクラスとして PolyArray クラスが用意されています。

PolyArray クラスは NumPy-like な多次元配列であり、NumPy の ndarray 配列と互換性のある多くのメソッドが実装されています。前節で VariableGenerator の array() により作成された変数配列はPolyArray のインスタンスです。

次の例では 3x3 の変数配列を作成します。NumPy の多次元配列と全く同様にして、変数配列の形状 shape や次元数 ndim を表すアトリビュートが取得できます。

from amplify import VariableGenerator

gen = VariableGenerator()
q = gen.array("Binary", shape=(3, 3))

>>> q.shape
(3, 3)
>>> q.ndim
2

配列要素を取得するには、NumPy 配列と同様にインデックスを指定します。

>>> print(q[0, 0])
q_{0,0}

スライスを活用した部分配列の取得も可能です。部分配列はコピーではなくビューを返します。

>>> print(q[1:3, 0:2])
[[q_{1,0}, q_{1,1}],
 [q_{2,0}, q_{2,1}]]
>>> print(q[0, ::-1])
[q_{0,2}, q_{0,1}, q_{0,0}]
>>> print(q[..., 0])
[q_{0,0}, q_{1,0}, q_{2,0}]

sum() は多項式配列から多項式を作成する際に便利なメソッドの1つです。

全ての変数の和を計算する:

>>> print(q.sum())
q_{0,0} + q_{0,1} + q_{0,2} + q_{1,0} + q_{1,1} + q_{1,2} + q_{2,0} + q_{2,1} + q_{2,2}

行ごとに和を計算する:

>>> print(q.sum(axis=1))  
[q_{0,0} + q_{0,1} + q_{0,2},
 q_{1,0} + q_{1,1} + q_{1,2},
 q_{2,0} + q_{2,1} + q_{2,2}]

列ごとに和を計算する:

>>> print(q.sum(axis=0))  
[q_{0,0} + q_{1,0} + q_{2,0},
 q_{0,1} + q_{1,1} + q_{2,1},
 q_{0,2} + q_{1,2} + q_{2,2}]

数値や numpy 配列との四則演算も可能です。

>>> print(2 * q)
[[2 q_{0,0}, 2 q_{0,1}, 2 q_{0,2}],
 [2 q_{1,0}, 2 q_{1,1}, 2 q_{1,2}],
 [2 q_{2,0}, 2 q_{2,1}, 2 q_{2,2}]]

>>> import numpy as np
>>> a = np.array([[1,2,3],[4,5,6],[7,8,9]])
>>> print(q * a)
[[  q_{0,0}, 2 q_{0,1}, 3 q_{0,2}],
 [4 q_{1,0}, 5 q_{1,1}, 6 q_{1,2}],
 [7 q_{2,0}, 8 q_{2,1}, 9 q_{2,2}]]

参考

上記以外にも、PolyArray クラスには、ブロードキャストや行列積、einsum() 関数など様々な機能やメソッドが用意されています。全ての機能については PolyArray クラスのリファレンスを参照してください。 NumPy 互換のメソッドの効果については、numpy.ndarray を参照してください。

3.3. 多項式のプロパティとメソッド¶

この節では、多項式の情報の取得や変更のための Poly クラスのメソッドやプロパティを紹介します。

多項式の次数を知るには degree() メソッドを用います。また、is_number(), is_linear(), is_quadratic() メソッドを使用することで、多項式が特定の次数以下であるかどうかを判定できます。

from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", 4)

>>> p = q[0] * q[1]
>>> p.degree()
2
>>> p.is_number()
False
>>> p.is_linear()
False
>>> p.is_quadratic()
True

is_variable() メソッドにより、多項式が 1 つの変数と見なせるかどうか、つまり、係数が 1 の 1 次元単項式であるかどうかをチェックすることができます。特に、VariableGenerator により生成されたスカラー変数や変数配列の要素に対して、is_variable() は True を返します。

>>> q[0].is_variable()
True
>>> (q[0] + 1).is_variable()
False
>>> (2 * q[0]).is_variable()
False

is_variable() が True を返すとき、変数の名前 name や種類 type といったプロパティが有効になります。

>>> q[0].name
'q_0'
>>> print(q[0].type)
Binary

参考

name や type など、多項式に含まれる変数の詳細情報に関する解説は「変数情報の取得」を参照してください。

多項式に含まれるすべての変数の情報は、 variables プロパティにより得ることができます。

>>> (q[0] + 2 * q[1]).variables 
[Variable({name: q_0, id: 0, type: Binary}),
 Variable({name: q_1, id: 1, type: Binary})]

substitute() メソッドを使うと、多項式の変数に数値や別の多項式を代入した結果を得ることができます。このメソッドは 1 つの dict を引数にとり、Poly クラスのインスタンスを返します。引数のキーは 1 つの変数と見なせる Poly または Variable である必要があり、値は float または Poly である必要があります。

>>> p = q[0] + q[1]
>>> print(p.substitute({q[0]: 1, q[1]: 0}))
1
>>> print(p.substitute({q[0]: 1}))
q_1 + 1
>>> print(p.substitute({q[1]: q[2] * q[3]}))
q_2 q_3 + q_0
>>> v = p.variables
>>> print(p.substitute({v[0]: 1, v[1]: 0}))
1

Tip

多項式配列に含まれるすべての多項式に対して一括で代入を行いたい場合は、多項式配列 PolyArray の substitute() メソッドを用いることができます。

>>> print(q)
[q_0, q_1, q_2, q_3]
>>> print(q.substitute({q[0]: 1, q[1]: 0}))
[  1,   0, q_2, q_3]
>>> print(q.substitute({q[1]: q[2] * q[3]}))
[    q_0, q_2 q_3,     q_2,     q_3]