はじめに

本書は、Digital Annealer サービスの利用方法および運用管理方法を説明します。

本書の読者

本書は、Digital Annealer サービスを利用して組合せ最適化問題を解くためのプログラムやアプリケーションを開発する方、 および、それらのプログラムやアプリケーションを実行する方を対象として説明します。
本書を読むにあたって、以下の知識が必要です。

  • 組合せ最適化問題に関する基本的な知識

  • 量子アニーリング、シミュレーテッドアニーリングなどの組合せ最適化問題のアルゴリズムに関する基本的な知識

  • Web API に関する基本的な知識

本書の表記について

本書では、略称および記号を使用しています。

製品名/技術名の略称
製品名/技術名 略称

Google Chrome™ ブラウザ

Google Chrome

記号
記号 意味

『 』

参照先がほかのマニュアルの場合、そのマニュアル名を『 』で囲んでいます

また、以下のアイコンを使用します。

注意
備考
用語一覧

本書で使用する用語について説明します。

用語 説明

Digital Annealer (デジタルアニーラ)

量子の振る舞いをデジタル回路で表現し、組合せ最適化問題を高速に解くハードウェアです。

FujitsuDA2MixedModeSolver

Digital Annealer で QUBO を解くためのソルバーです。

FujitsuDA2PTSolver

Digital Annealer でレプリカ交換機能を使用して QUBO の最適解を求めるためのソルバーです。

FujitsuDA2Solver

Digital Annealer で QUBO の最適解を求めるためのソルバーです。

HOBO (Higher Order Binary Optimization)

組合せ最適化問題を高次単項式または高次多項式で表したものです。

QUBO (Quadratic Unconstrained Binary Optimization)

組合せ最適化問題を二次多項式で表したものです。

Web API

HTTP プロトコルを用いてネットワーク越しに呼び出すアプリケーション間およびシステム間インターフェースです。

輸出管理規制について

本ドキュメントを輸出または第三者へ提供する場合は、お客様が居住する国および米国輸出管理関連法規等の規制をご確認の うえ、必要な手続をおとりください。

高度な安全性が要求される用途への使用について

本サービスは、一般事務用、パーソナル用、家庭用、通常の産業等の一般的用途を想定して開発・設計・製造されているもので あり、原子力施設における核反応制御、航空機自動飛行制御、航空交通管制、大量輸送システムにおける運行制御、生命維持の ための医療用機器、兵器システムにおけるミサイル発射制御など、極めて高度な安全性が要求され、仮に当該安全性が確保され ない場合、直接生命・身体に対する重大な危険性を伴う用途(以下「ハイセイフティ用途」という)に使用されるよう開発・設計 ・製造されたものではありません。
お客様は本サービスを必要な安全性を確保する措置を施すことなくハイセイフティ用途に使用しないでください。また、お客様 がハイセイフティ用途に本サービスを使用したことにより発生する、お客様または第三者からのいかなる請求または損害賠償に 対しても富士通株式会社およびその関連会社は一切責任を負いかねます。

商標について
  • Google は、Google Inc. の商標または登録商標です。

  • その他の会社名、各製品名などの固有名詞は、各社の商号、登録商標または商標です。

  • その他、会社名、システム名、製品名などには必ずしも商標表示を付記しておりません。

1. 概要

この章では、Digital Annealer の概要について説明します。


1.1. Digital Annealer とは

Digital Annealer は、量子現象を用いた計算方法に着想を得て設計したデジタル回路です。アニーリング方式を用いて、組合せ 最適化問題を高速に解くことができます。従来のコンピュータのようなプログラミングは必要なく、パラメーターを設定するだけで 計算が行われます。また、任意の素子同士が自由に信号をやりとりできる全結合型の構造を採用しているため、従来のコンピュータ や量子アニーリングマシンでは計算量が膨大で解けなかった複雑な問題を計算させることができます。

Digital Annealer は、QUBO (Quadratic Unconstrained Binary Optimization) を入力データとして持ち、以下の評価関数 (エネルギー) を最小化するための組合せを探索します。

  \(\displaystyle{E(x) = \sum_{i} \sum_{j>i} J_{ij}x_{i}x_{j} + \sum_{i}h_{i}x_{i} + c}\)

2 値変数 \(x \; (x \in \{0, 1\})\) により、組合せの状態を表現しています。

1.1.1. Digital Annealer サービス

Digital Annealer サービスとは、最適化回路 Digital Annealer を実装したハードウェア、および、1QBit 社が開発した量子 コンピュータ向けソフトウェアを使用して、組合せ最適化問題を高速に解くクラウドサービスです。

サービス
図 1. Web API サービス



2. サービス利用開始

この章では、サービスの利用開始について説明します。


2.1. アカウント登録

Digital Annealer サービスを利用するには、Digital Annealer ポータルのDAアカウント作成ページ (下記のURL) にアクセスして、アカウント登録を行ってください。

  https://portal.aispf.global.fujitsu.com/#/digitalannealer

  • Digital Annealer ポータルへは、Google Chrome でアクセスしてください。
    画面解像度は 1366 \(\times\) 768 ピクセル以上を推奨します。


3. サービスの利用

この章では、サービスの利用方法および注意事項について説明します。


3.1. 提供する API

Web API サービスで提供する API を以下に示します。

3.1.1. QUBO API

契約のタイプ API 種別 説明

スタンダード (Standard)
トライアル (Trial)
アカデミック (Academic)

qubo/hobo2qubo

同期 (sync)

HOBO (Higher Order Binary Optimization) を QUBO (Quadratic Unconstrained Binary Optimization) に変換する

qubo/solve

QUBO の最適解を求める

プレミアム-2 (Premium-2)
スタンダード-2 (Standard-2)
トライアル-2 (Trial-2)
アカデミック-2 (Academic-2)

qubo/hobo2qubo

同期 (sync)

HOBO (Higher Order Binary Optimization) を QUBO (Quadratic Unconstrained Binary Optimization) に変換する

qubo/solve

QUBO の最適解を求める

async/qubo/solve

非同期 (async)

QUBO の最適解を求めるジョブを登録する

async/jobs

ジョブの一覧を取得する

async/jobs/result

ジョブの結果を取得または削除する

async/jobs/cancel

ジョブをキャンセルする


  • スタンダード (Standard)、トライアル (Trial)、または アカデミック (Academic) を契約した場合、対応可能な問題の規模は下記のとおりです。
     同期 (sync):1Kbit 以下

  • スタンダード (Standard)、トライアル (Trial)、または アカデミック (Academic) を契約した場合、種別が非同期 (async) の API は使用できません。

  • スタンダード-2 (Standard-2)、トライアル-2 (Trial-2)、または アカデミック-2 (Academic-2) を契約した場合、API の種別により対応可能な問題の規模が異なります。
     同期 (sync):2Kbit 以下
     非同期 (async):8Kbit 以下

  • スタンダード-2 (Standard-2)、トライアル-2 (Trial-2)、または アカデミック-2 (Academic-2) を契約した場合、種別が非同期 (async) の API を使用するには、非同期サービスの契約が必要です。

  • スタンダード-2 (Standard-2)、トライアル-2 (Trial-2)、アカデミック-2 (Academic-2)、スタンダード (Standard)、トライアル (Trial)、または アカデミック (Academic) の月額固定を契約した場合、使用時間の上限値が設定されています。
    同期型と非同期型それぞれに上限値が設定されており、その上限を超えて使用することはできません。

  • qubo/solve は、同一アカウントで同時に最大 2 多重までリクエストできます。

  • async/qubo/solve は、同一アカウントで最大 16 多重までリクエストできます。なお、async/qubo/solve の処理結果の数も多重数に含まれるため、不要な処理結果は削除してください。

  • QUBO API の詳細は、『Digital Annealer API リファレンス(QUBO API)』を参照してください。
    上記以外にも 1QBit 社から API が提供されています。
    1QBit 社から提供されている API の種類や仕様については、以下を参照してください。
      http://portal.1qbit.com/documentation
    FujitsuDA2PTSolver、FujitsuDA2Solver、FujitsuDA2MixedModeSolver 以外のソルバーを使用する場合、リクエスト時の URI は /v1/…​ を指定してください。


3.1.2. 最適化ソリューションAPI

契約のタイプ API 説明

倉庫内ピッキング API (Warehouse Pickup Optimization API)

picking/mapfile

マップファイル(倉庫内の棚と通路のリスト)をアップロード(POST)またはダウンロード(GET)する

picking/showroute

最短のピッキングルートと総距離を求める


  • picking/showroute で指定できる棚の数は、以下の範囲です。
     \(\sum x^2 \leq 1024\)
     \(x\):同じ優先度の棚数。ただし、同じ優先度の棚数が1個の場合は除く。
    例1:優先度 0 の棚が 1 個、優先度 1 の棚が 30 個、優先度 2 の棚が 5 個、優先度 3 の棚が 2 個の場合
     \(30^2 + 5^2 + 2^2 = 900 + 25 + 4 = 929\) (優先度 0 は、棚数が 1 個のため除外)
     ⇒ 1024以下のため最適化できます。
    例2:優先度 1 の棚が 30 個、優先度 2 の棚が 10 個、優先度 3 の棚が 1 個、優先度 4 の棚が 5 個の場合
     \(30^2 + 10^2 + 5^2 = 900 + 100 + 25 = 1025\) (優先度 3 は、棚数が 1 個のため除外)
     ⇒ 1,024 を超えるため、最適化できません。
    上記の条件を満たしていても、リクエストボディで指定する棚(node)の数が 200 を超える場合は 処理に 時間がかかるため、タイムアウト(HTTP 504 Gateway Time-out)のエラーが発生する可能性があります。

  • picking/mapfile で Digital Annealer サーバに登録できるマップファイルは 1 つだけです。最後にアップ ロードしたマップファイルが Digital Annealer サーバに登録されます。以前に登録したマップファイルは上 書きされるため、必要に応じてマップファイルをバックアップしてください。


4. QUBO API の使用方法

 この章では、数理モデルを使用して組合せ最適化問題を解く方法について説明します。


4.1. Digital Annealer の計算精度

Digital Annealer は、二次のバイナリ多項式の係数を整数としてエンコードします。
Digital Annealer の計算精度は以下のとおりです。最適解を求めるには、QUBO の各項の係数を Digital Annealer の計算精度の範囲内で指定する必要があります。

問題の規模 二次項 線形項

~4Kbit

64bitの符号付き整数(*1)

76bit の符号付き整数

4Kbit 超~ 8Kbit

16bit の符号付き整数

76bit の符号付き整数

 *1: \(-2^{63} + 1\)~\(2^{63} - 1\)の範囲とします。

4.1.1. Scaling and Rounding

整数でない係数や Digital Annealer の計算精度範囲外の係数を持つ項が含まれる QUBO を、Digital Annealer の計算精度範囲内の整数を係数にもつ項だけを含む QUBO に自動で変換する機能です。
以下のソルバーを使用している場合、アニーリング時にこの機能が有効になります。

  • FujitsuDA2PTSolver

  • FujitsuDA2Solver を使用し、expert_mode パラメーターに false を指定する場合

  • FujitsuDA2MixedModeSolver

qubo/solve で指定可能な QUBO の各項の係数の範囲は、『Digital Annealer API リファレンス(QUBO API)』を参照してください。

4.2. API の使用方法

提供する各 API の仕様および使用方法については、『Digital Annealer API リファレンス(QUBO API)』を参照してください。

4.3. 注意事項

QUBO API 使用時の注意事項について説明します。

  • リクエスト時に指定したパラメーター名(キー)に誤り(スペルミスを含む)がある場合、その指定が無視され処理が続行されることがあります。それにより期待する処理結果が得られないことがありますので注意して指定してください。

  • リクエスト後に、実行中のジョブを中断することはできません。間違ってリクエストしてしまったり、処理に時間がかかったりしている場合でも、処理が終了するまでお待ちください。
    ただし、Premium-2 または 非同期サービスを契約している場合、ジョブが実行前であればキャンセル (async/jobs/cancel を使用) できます。

  • Digital Annealer がアニーリング処理中に、qubo/solve の新たなリクエストを発行した場合の処理は、実行中のアニーリング処理の完了を待ち合わせます。
    実行中のアニーリング処理完了後に、新たなリクエストの処理が開始されます。

  • アニーリングにかかる時間 (anneal_time) は、以下のパラメーターに指定する値で決まります。

    • number_iterations パラメーター

    • number_replicas パラメーター (FujitsuDA2PTSolver の場合)

    • number_runs パラメーター (FujitsuDA2Solver または FujitsuDA2MixedModeSolver の場合)

      例:number_iterations = 10000000、number_runs = 100 を指定した場合
          FujitsuDA2Solver または FujitsuDA2MixedModeSolver を使用:5 秒程度

      値を 10 倍、100 倍 … すると、anneal_time もそれに比例して 10 倍、100 倍 … に増加するため、注意して指定してください。

  • 問題の規模(ビット数)が大きいと、スケーリング処理やエネルギーの再計算など、CPU を使用して計算する処理に時間がかかることがあります。 指定したソルバーやパラメーターの設定値によって、CPU を使用して計算する処理にかかる時間は異なります。

  • 以下のパラメーターに、下限値および上限値が設定されています。

    ソルバー

    パラメーター

    下限値

    上限値

    同期型

    非同期型

    FujitsuDA2PTSolver

    number_replicas

    26

    128

    128

    number_iterations

    1

    2000000000

    2000000000

    number_replicas \(\times\) number_iterations

    100000

    25600000000

    256000000000

    FujitsuDA2Solver/
    FujitsuDA2MixedModeSolver

    number_runs

    16

    128

    128

    number_iterations

    1

    2000000000

    2000000000

    number_runs \(\times\) number_iterations

    100000

    25600000000

    256000000000

  • FujitsuDA2Solver および FujitsuDA2MixedModeSolver でのアニーリングの温度スケジュールは、temperature_decay、 temperature_interval、temperature_mode および temperature_start のパラメーターで規定されます。
    例えば、以下のように number_iterations=100000、temperature_interval=100 の場合、100 回の探索ごとに temperature_mode パラメーターで指定したモードで算出した温度に変更します。
    1 回のアニーリングあたりの探索回数 (number_iterations) が 100000 なので、\(100000 \div 100 = 1000\)回の温度変更をすることになります。

    注意1
  • FujitsuDA2Solver および FujitsuDA2MixedModeSolver での 1 回のアニーリングは、上記アニーリングの温度スケジュー ルで設定された各温度で、number_iterations パラメーターで指定した回数分探索が実施され、number_runs パラメーターで指定した回数分アニーリングを繰り返します。
    どちらのパラメーターも大きな値を指定するほど時間がかかります。

  • offset_increase_rate は、探索を加速するためのパラメーターです。局所解に落ち込んで状態遷移が起こらない場合に、探索ごとに offset_increase_rate の値分ずつエネルギーを上げる処理を行い、 状態遷移を起こす確率を向上させます。
    状態遷移が発生したら、offset_increase_rate によって累積されたエネルギーはリセットされます。
    使用しない場合は、0 を指定します。

    注意2
  • FujitsuDA2Solver および FujitsuDA2MixedModeSolver では、以下の 5 つのパラメーターのうち、どれか1つでも指定する 場合は、必ず 5 つのすべてのパラメーター、および number_iterations パラメーターを指定してください。

    • offset_increase_rate

    • temperature_decay

    • temperature_interval

    • temperature_mode

    • temperature_start

  • FujitsuDA2Solver および FujitsuDA2MixedModeSolver では、特に temperature_decay、temperature_interval および temperature_start は、温度スケジュールに関わるパラメーターであり、適切な値を指定しないと最適解が得られません。
    各パラメーターの値の組合せは無数にあり、最適解が得られる適切な値を探すチューニング作業が必要となります。
    FujitsuDA2PTSolver (レプリカ交換機能を使用) では、以下のパラメーターの指定が不要となり、チューニング作業にかかる時間を大幅に短縮できます。

    • noise_model

    • temperature_decay

    • temperature_interval

    • temperature_mode

    • temperature_start

  • 1QBit 社から提供されているソルバーも使用可能です。
    1QBit 社から提供されているソルバーの種類や仕様については、以下を参照してください。
      http://portal.1qbit.com/documentation
    FujitsuDA2PTSolver、FujitsuDA2Solver、FujitsuDA2MixedModeSolver 以外のソルバーを使用する場合、リクエスト時の URI は /v1/…​ を指定してください。

5. 最適化ソリューションAPIの使用方法

この章では、業務に特化した組合せ最適化問題を解く方法について説明します。


5.1. 倉庫内ピッキング API

倉庫内ピッキング API は、倉庫内にある複数の棚などから指定された商品を取り出す(ピッキング)ときに、移動距離が最短となるルート(ピッキングルート:閉路)を求める Web API サービスです。

5.1.1. 使用手順

移動距離が最短となるピッキングルートを求める手順を以下に示します。

  1. マップファイルの作成

  2. マップファイルの登録および取得

  3. ピッキングルートの最適化

以下で、上記の各手順について説明します。

1. マップファイルの作成

倉庫内ピッキング API を使用するには、ピッキングを行う倉庫(ピッキングエリア)にある棚と通路の位置情報などを記載したマップファイルをクライアント上で作成する必要があります。

  • マップファイルを作成するために用意するもの

    • ピッキングエリアの平面図(縮尺図)

    • ピッキング対象の商品が配置してある棚の位置

  • マップファイルの作成手順

    手順(1)

    ピッキングエリアの平面図 (縮尺図) に、ピッキング対象の商品が配置してある各棚と、ピッキング時に通行可能な通路を記載します。(「図2: マップファイル作成例」の「ピッキングエリアの平面図例」を参照)

    手順(2)

    手順 (1) に記載した各棚および通路上の通過ポイントにプロット点を置いて、その座標(絶対座標)を求めます。プロット点は、通路同士の交点や曲がり角、棚と通路を結んだ場所にも置きます。

    手順(3)

    手順 (2) で求めた各座標に基づいて、マップファイル (.json) を作成します。 エリア内の各プロット点の座標は nodes として定義し、nodes で定義したプロット点のうちピッキングで通行可能な経路を edges として定義します。(「図 2: マップファイル作成例」の「マップファイル作成例 1」を参照)
    エリアが複数ある場合、nodes と edges はエリアごとに定義し、エリア間の距離と経路を cedges で定義します。(「図 2: マップファイル作成例」の「マップファイル作成例 2」を参照)
    edges および cedges で定義した経路の向き (双方通行(false) または 一方通行(true)) は、directed で定義します。
    マップファイルのデータ形式の詳細は、『Digital Annealer API リファレンス(倉庫内ピッキング API)』を参照してください。

  • nodes と edges に定義する棚や通路のプロット点の名前、およびプロット点の座標は、各エリア内で重複しないようにしてください。

  • マップファイルに定義する座標の値は、実際の距離である必要はありません。縮尺した平面図上の座標の値でもかまいません。

マップファイルの作成は、Digital Annealer テクニカルサービスでも承ります(有償)。

2. マップファイルの登録および取得

picking/mapfile を使用して作成したマップファイルを登録し、登録したマップファイルを取得(表示)することによって、マップファイルが正しく登録されていることを確認します。
API の仕様については、『Digital Annealer API リファレンス(倉庫内ピッキング API)』を参照してください。

3. ピッキングルートの最適化

picking/showroute を使用して、移動距離が最短となるピッキングルートを求めます。
API の仕様については、『Digital Annealer API リファレンス(倉庫内ピッキング API)』を参照してください。

  • リクエスト時にマップファイルに存在しない棚 (node) を指定した場合、最適化対象からは除外されます。

  • 優先度 (priority) の指定は省略できません。優先度の指定が不要の場合は、優先度 (priority) に 0 を指定してください。

総距離(distance)は、マップファイルに記載した棚や通路のプロット点の座標で定義した単位で表します。
例えば、座標 1 単位を 50cm で定義した場合、下記レスポンス例の実際の総距離は \(1672 \times 0.5m = 836m\) となります。

レスポンス例:
{
   "distance": 1672.0,
   "route": [
       {"area": "A1F", "node": "DEPOT"},
       {"area": "A1F", "node": "F52"},
       {"area": "A1F", "node": "F32"},
       {"area": "A1F", "node": "R-4"},
       {"area": "A2F", "node": "R-1"},
       {"area": "A2F", "node": "B46"},
       {"area": "A2F", "node": "A10"},
       {"area": "A2F", "node": "B45"
   ]
}


サービス
図 2. マップファイル作成例


改版履歴
版数 日付 変更箇所 変更内容

初版

2020年1月

全体

新規作成