実行時間情報の取得

Amplify SDK は、組合せ最適化問題を解く一連のシーケンスにおいて、実行時間に関する情報を取得するインターフェースを提供しています。

_images/timing_light.drawio.svg _images/timing_dark.drawio.svg

実行時間情報の種類

取得できる実行時間情報の種類は以下の表の通りです。datetime.timedelta オブジェクトとして取得することができます。

amplify.Result.total_time

amplify.solve() にかかった時間を表します。

amplify.Result.response_time

ソルバーにリクエストを送ってからレスポンスが返ってくるまでの時間を表します。

amplify.Result.execution_time

ソルバーが求解に費やした時間を表します。

amplify.Result.Solution.time

ソルバーが返したそれぞれの解について、ソルバーが求解を始めてからその解が得られるまでの時間を表します。

実行時間の取得例

実行時間を取得する例を以下に示します。まず、solve() 関数を実行して Result オブジェクトを得ます。

from amplify import VariableGenerator, one_hot, FixstarsClient, solve
from datetime import timedelta

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

objective = q[0] * q[1] - q[2]
constraint = one_hot(q)

model = objective + constraint

client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)

result = solve(model, client)

Resulttotal_time アトリビュートは solve() 関数の開始から終了までにかかった時間を表します。これは、ソルバーのレスポンス時間に加えて、モデルの変換やソルバーに渡すリクエストデータの作成にかかった Amplify SDK の処理時間を含みます。

>>> result.total_time 
datetime.timedelta(seconds=1, microseconds=870877)

Resultresponse_time アトリビュートは solve() 関数内でソルバーにリクエストを送ってからレスポンスが返ってくるまでの時間を表します。

>>> result.response_time 
datetime.timedelta(seconds=1, microseconds=865211)

Resultexecution_time アトリビュートは、ソルバーが求解に使用した時間を表します。これは通常、ソルバーのレスポンスに含まれる値が用いられます。

>>> result.execution_time 
datetime.timedelta(microseconds=980543)

Result に含まれるそれぞれの解 (Solution) について、ソルバーが求解を始めてからその解を見つけるまでの時間を time アトリビュートにより取得することができます。これは通常、ソルバーのレスポンスに含まれる値が用いられますが、ソルバーがそのような情報を返却しない場合は execution_time と同じ値が入ります。

>>> result.best.time 
datetime.timedelta(microseconds=27925)

solve() 関数に dry_run オプションをつけて実行した場合、total_time は Amplify SDK がモデル変換やリクエストデータの作成を行うのにかかった時間とおおよそ等しくなります。また、response_time および execution_time は 0 になります。

>>> dry_run_result = solve(model, client, dry_run=True)
>>> dry_run_result.total_time 
datetime.timedelta(microseconds=59)

解の取得時刻のプロット

複数の解を返すように設定されたソルバーに対して、ソルバーがそれぞれの解を得た時刻をプロットする方法を紹介します。これを用いると、与えられたソルバーの実行時間の範囲においてソルバーがある時刻でどのような解を見つけたのかを確認することができます。解の収束の様子などから実行時間の過不足の判断に用いると良いでしょう。

例として、50 都市のランダムな巡回セールスマン問題に対して、Amplify AE がどのように解に対応する目的関数値を更新していくのかを図示します。

まず、モデルの作成を行います。定式化の詳細については巡回セールスマン問題を参照してください。

import numpy as np
from amplify import VariableGenerator, einsum, one_hot

N = 50
x = np.random.rand(N)
y = np.random.rand(N)
d = (
    (x[:, np.newaxis] - x[np.newaxis, :]) ** 2
    + (y[:, np.newaxis] - y[np.newaxis, :]) ** 2
) ** 0.5

gen = VariableGenerator()
q = gen.array("Binary", N + 1, N)
q[-1, :] = q[0, :]

objective = einsum("ij,ki,kj->", d, q[:-1], q[1:])
constraints = one_hot(q[:-1], axis=1) + one_hot(q[:-1], axis=0)

model = objective + d.max() * constraints

ソルバークライアントを設定します。デフォルトでは Amplify AE は最良解 1 個しか返さないので、探索中に見つけた解をすべて返すように設定します。

from amplify import FixstarsClient

client = FixstarsClient()
client.parameters.timeout = 1000  # 実行時間 1000 ms
client.parameters.outputs.num_outputs = 0  # 発見した全ての解を返す

ソルバーの実行を行い、得られた全ての解の時刻と目的関数の値を図示します。

from amplify import solve
import matplotlib.pyplot as plt

# ソルバーの実行
result = solve(model, client)

# それぞれの解の時刻と目的関数の値を取得
times = [solution.time.total_seconds() for solution in result]
objective_values = [solution.objective for solution in result]

# プロット
plt.scatter(times, objective_values)
plt.plot(times, objective_values)
plt.xlabel("elapsed time in seconds")
plt.ylabel("objective value")
plt.grid(True)
_images/c8c29e5b151cf0daa6ef9c2677931812dc3422a1aaffc08ac64a28dabd4f73ff.png

50都市の巡回セールスマン問題における Amplify AE の取得した解の更新履歴

次のようにして、探索の初期解と最良解を取得し、各々をプロットして比較することもできます。

def tsp_plot(q_values, x, y):
    route_x = q_values @ x
    route_y = q_values @ y

    plt.scatter(x, y)
    plt.plot(route_x, route_y)
    plt.show()

# 初期解のプロット
tsp_plot(q.evaluate(result[-1].values), x, y)
# 最良解のプロット
tsp_plot(q.evaluate(result[0].values), x, y)
_images/b240e8cb58e2deefde959b4118b6f6c0498236db3a8c49f45fb71ecadd3ece23.png

初期解 (0.08 秒) の経路

_images/1e57ccffb3f392e7cb4ee2ea71bb5f51b276ed3aa14e2d8cd3809516de96b57b.png

最良解 (0.71 秒) の経路