Skip to content

Latest commit

 

History

History
389 lines (294 loc) · 24.5 KB

README-ja.md

File metadata and controls

389 lines (294 loc) · 24.5 KB

Fixstars Amplify Benchmark

Fixstars Fixstars Amplify README.md

Amplify Benchmark とは？

Fixstars Amplify Benchmark は二次計画問題 (QUBO) の求解性能のベンチマークを行うフレームワークです。ベンチマークの実行を担うコマンドラインインターフェースとベンチマーク問題の定義を提供します。

バックエンドに Fixstars Amplify SDK が用いられているため、量子アニーリングマシン、イジングマシン、数理最適化ソルバー等、数多くのソルバーを用いてベンチマークを実行することが可能です。ベンチマークは、対象の問題とその実行回数、使用するソルバーを指定したジョブが定義されるジョブセットファイルに基づいて実行されるため、実行から結果の取得までを自動で容易に行うことが出来ます。

このライブラリの実行結果を Amplify Benchmark Viewer で読み込むことで、結果を WEB ブラウザ上で可視化することが出来ます。Amplify AE を対象としたベンチマーク結果のデモはこちらです。

特徴

  • 実行が容易
  • 並列実行
  • 自動評価と解析
  • ベンチマーク結果ビューアを提供
  • カスタマイズ可能なソルバーと問題パラメータ
  • 複数のベンチマークセットに対する定式化が定義済み
  • ユーザ定義問題を追加可能

事前定義済みベンチマークセット

  • 巡回セールスマン問題: TSPLIB
  • 二次割当問題: QAPLIB
  • 最大カット問題: Gset
  • 容量制約付き配車ルート問題: CVRPLIB
  • 二次計画問題: QPLIB
  • 数独 (ペンシルパズル)

Amplify SDK により対応するソルバー:

Gallery

Objective value for execution time Time To Solution (TTS)
Probability of obtaining a feasible solution Probability of obtaining the best solution Rate
Table DATA

始め方

インストール

Amplify benchmark は Python (>=3.8) ライブラリとして提供されています。次のようにして pip でインストール出来ます。

$ pip install amplify-bench

サンプルセットの実行

インストール後、amplify-bench コマンドが有効になります。

$ amplify-bench --help
Usage: amplify-bench [OPTIONS] COMMAND [ARGS]...

Options:
  --help  Show this message and exit.

Commands:
  download  Download all supported instance files in the specified...
  run       QUBO Benchmark
  stats     Generate QUBO benchmark stats data.

ベンチマークを実行するためには、ベンチマーク定義 (以下、ジョブセット) ファイルを作成する必要があります。example/benchmark.yml ファイルはジョブセットファイルの例が記述されています。

example/benchmark.yml

jobs:
  - problem:
      class: Tsp
      instance: eil51
    client:
      - FixstarsClient
      - token: INPUT_API_TOKEN
        parameters:
          timeout: 3000
    num_samples: 2

ベンチマークジョブセットファイルには YAML あるいは JSON ファイル形式でベンチマークジョブのリストを記述します。ジョブは実行回数、ベンチマーク対象の問題リスト、実行する Client クラス に与える設定値で構成されています。このジョブセットの場合、次のベンチマークジョブで構成されます。

  • 対象の問題
    • TSPLIB: eil51 instance
  • 実行回数: 2
  • 実行するクライアント: FixstarsClient
    • token: INPUT_API_TOKEN
    • parameter.timeout: 3000

それでは、このジョブセットファイルを用いてベンチマークを実行してみましょう。amplify-bench コマンドの run サブコマンドにジョブセットファイルのパス与えて実行します。

Note INPUT_API_TOKEN を自身の API トークンで置き換えてください。トークンを未入手の場合は、Amplify WEBサイト にアクセスし、アカウントを作成してください。

$ amplify-bench run benchmark.yml
input_json: benchmark.yml
label: 20230803_223440
output: None
parallel: 1
aws_profile: None
dry_run: False
cli_benchmark_impl() 20230803_223440
2023-08-03 22:34:41,308 [pid:94470] [INFO]:    542.49 ms in amplify_bench.cli.parser.parse_input_data
2023-08-03 22:34:41,309 [pid:94470] [INFO]: make model of eil51
2023-08-03 22:34:41,519 [pid:94470] [INFO]:    209.08 ms in amplify_bench.problem.tsp.make_tsp_model
total jobs:  2
success jobs:  2
error jobs:  0
Jobs not yet started:  0

実行が完了すると、デフォルトでは入力ファイルと同じディレクトリに実行結果として JSON ファイルが出力されます。ファイル名には実行時刻が付与されます。出力ファイルパスは --output <path> オプションで変更が可能です。

Amplify Benchmark Viewer を用いた結果の可視化

実行結果は Amplify Benchmark Viewer で可視化することが出来ます。Amplify Benchmark Viewer で読み込むには stas サブコマンドに実行結果のファイル、あるいはディレクトリを与えて解析します。

$ amplify-bench stats preset_20230803_223440.json

デフォルトではカレントディレクトリに report/data.json ファイルが作成されます。出力ファイルのパス・ディレクトリは --output オプションで変更が可能です。

作成した report/data.json ファイルを Amplify Benchmark Viewer の GitHub pages にドラッグ&ドロップすることで、結果を可視化出来ます。

Note データはブラウザ上で展開され、サーバには保存されません。

Drag and Drop data.json file Show the evaluated problem list The detailed evaluation for each problem

高度な使い方

ジョブセットファイルの書き方

JobsetObject

ジョブセットファイルには下記のキーを持つ JSON オブジェクトを記述します。ジョブセットファイルのスキーマは amplify_bench/cli/schemas に記述されています。

key type description
jobs array[JobObject] ベンチマークジョブのリスト
variables object ジョブで使用可能な変数の定義 (Optional)
imports array[string] ユーザー定義の問題のファイルパス (Optional)

ファイルの中の $ から始まる文字列は変数名として扱われます。最初に実行時の環境変数によって展開され、その後 variables キーに与えた変数定義が jobs 内で参照されます。例えば次のように全ての問題に共通する設定を与えるときに有用です。

variables:
  CLIENT:
    - FixstarsClient
    - parameters:
        timeout: 3000
jobs:
  - problem:
      class: Tsp
      instance: eil51
    client: $CLIENT
    num_samples: 2
  - problem:
      class: Tsp
      instance: burma14
    client: $CLIENT
    num_samples: 1

importsにはユーザー定義の問題ファイルのパスのリストを指定します。パスは本ジョブセットファイルからの相対パス、カレントディレクトリからの相対パス、または絶対パスで記載します。ユーザー定義の問題ファイルの詳細はユーザ定義問題の追加を参照してください。

JobObject

key type description
num_samples int 実行回数
client array クライアントの設定
problem ProblemObject 問題設定
matrix object[array] 変数の組合わせパターン定義 (Optional)

num_samples に 1 より大きな整数値を入れると同じ設定で複数回実行します。matrix キーには後述する変数の組合わせパターンを設定します。

client キーには長さ2の配列を与えます。第一要素にクライアントクラス名を指定し、第二要素にはクライアントクラスのプロパティ値をオブジェクトで与えます。例えば、次の Amplify SDK におけるクライアント設定に対して、

from amplify.client import FixstarsClient

client = FixstarsClient()
client.token = "INPUT_API_TOKEN"
client.parameters.timeout = 1000

以下のようにジョブセットファイルに記述します。

jobs:
  - client:
      - FixstarsClient
      - token: INPUT_API_TOKEN
        parameters:
          timeout: 1000

Note それぞれの Client クラスにおける設定可能なプロパティ値は ドキュメント を参照してください。

ProblemObject

problem キーには以下のキーで構成されるオブジェクトを与えます。

key type description
class string 問題クラス名
instance string インスタンス名
parameters object 定式化パラメータ

class には amplify_bench/problem に含まれる問題クラス名を指定します。フレームワークにで事前に定義されている問題クラスは、Tsp (TSPLIB), Qap (QAPLIB), Cvrp (CVRPLIB), MaxCut (GSET), Sudoku, Qplib (QPLIB) です。instance にはそれぞれの問題クラスに対応する問題セットに含まれるインスタンス名を記述します。詳細は amplify_bench/problem/data を参照してください。問題クラスにはコンストラクタに与える定式化のパラメータを指定出来ることがあり、parameter で指定します。

マトリックス変数を用いた自動ジョブ生成

一つのジョブ定義に与えた複数の変数パターンの全ての組合わせに対して複数のジョブを自動的に生成することが出来ます。例えば、複数のインスタンスと複数の実行時間にする全ての組合わせに対して実行する場合、次のように記述します。

variables:
  NUM_SAMPLES: 100
  FIXSTARS:
    - FixstarsClient
    - token: INPUT_API_TOKEN
      parameters:
        timeout: $TIMEOUT
jobs:
  - problem:
      class: Qap
      instance: $INSTANCE
    client: $FIXSTARS
    num_samples: $NUM_SAMPLES
    matrix:
      INSTANCE:
        - esc32a
        - sko56
      TIMEOUT:
        - 10000
        - 30000

matrix には変数名をキーにして、値を配列で与えます。この場合、esc32a と sko56 それぞれに対して、timeout が 10000 と 30000 のジョブが生成されます。variables に定義されている変数の中で matrix に与えている変数を参照できることに注意してください。

Note 変数の参照は再帰的に行われますが、無限ループが発生するとエラーになります。

ユーザ定義問題の追加

ユーザが定義した定式化をベンチマーク問題として追加することが出来ます。

次の例では mytsp.py ファイルで定義された MyTsp クラスに対するベンチマークが実行されます。imports キーには問題クラスが定義されたファイルパスを指定します。ファイルパスは絶対パスあるいはジョブセットファイルまたはカレントディレクトリからの相対パスで指定してください。

imports:
  - mytsp.py
jobs:
  - problem:
      class: MyTsp
      instance: random8

Note ユーザ定義のクラス名はフレームワークに内蔵の問題クラスと重複しないようにしてください。

問題クラスは Problem クラスを継承し、コンストラクタ (__init__) と make_model と evaluate メソッドを実装する必要があります。make_model メソッドはAmplify SDK を用いた定式化を、evaluate メソッドは解を入力として、定式化したモデルに対する評価を行います。

次のコードは MyTsp 問題クラスの例です。

mytsp.py

class MyTsp(Problem):
    def __init__(
        self,
        instance: str,
        constraint_weight: float = 1.0,
        seed: int = 0,
    ):
        super().__init__()
        self._instance: str = instance
        self._problem_parameters["constraint_weight"] = constraint_weight
        if instance.startswith("random"):
            self._problem_parameters["seed"] = seed
        self._symbols = None

        ncity, distances, locations, best_known = self.__load(self._instance, seed)
        self._ncity = ncity
        self._distances = distances
        self._locations = locations  # not used
        self._best_known = best_known

    def make_model(self):
        symbols, model = make_tsp_model(self._ncity, self._distances, self._problem_parameters["constraint_weight"])
        self._symbols = symbols
        self._model = model

    def evaluate(self, solution: SolverSolution) -> Dict[str, Union[None, float, str]]:
        value: Optional[float] = None
        path: str = ""

        if solution.is_feasible:
            spins = solution.values
            variables = np.array(self._symbols.decode(spins))  # type: ignore
            index = np.where(variables == 1)[1]
            index_str = [str(idx) for idx in index]
            value = calc_tour_dist(list(index), self._distances)
            path = " ".join(index_str)
        else:
            pass

        return {"label": "total distances", "value": value, "path": path}
...

コンストラクタ

def __init__(self, instance: str, **kwargs) -> None

コンストラクタの引数は少なくとも instance: str 引数を受け取る必要があります。それ以外で、例えばコンストラクタの引数に constraint_weight: float を追加した場合は、ProblemObject の parameters キーには constraint_weight が指定可能になります。

make_model メソッド

def make_model(self) -> None

make_model メソッドは定式化を行い self._model にamplify.BinaryQuadraticModel クラスのインスタンスを格納する責務があります。

evaluate メソッド

def evaluate(self, solution: amplify.SolverSolution) -> Dict[str, Union[None, float, str]]

evaluate メソッドは amplify.SolverSolution を受け取り解の評価を行います。返り値は Dict[str, Union[None, float, str]] として任意のキーと値を返すことが出来ます。返り値はベンチマーク結果の JSON ファイルにおいて objective_value キーに出力されます。

プロジェクトへのコントリビューション

Amplify Benchmark はオープンソースプロジェクトです。バグの報告や機能の追加、ドキュメントの改善等、コントリビューションを歓迎します。

開発元

関連プロジェクト: