特許ウォッチ

公開番号2025014338
公報種別公開特許公報(A)
公開日2025-01-30
出願番号2023116823
出願日2023-07-18
発明の名称情報処理装置、情報処理方法、プログラムおよび回路情報
出願人株式会社東芝
代理人弁理士法人酒井国際特許事務所
主分類G06N 99/00 20190101AFI20250123BHJP(計算;計数)
要約【課題】組合せ最適化問題を高速に生成する。
【解決手段】実施形態に係る情報処理装置は、データに対して処理を実行する。情報処理装置は、ソルバ装置と、情報処理回路と、を備える。情報処理回路は、データを取得する。情報処理回路は、データに基づき組合せ最適化問題を生成して、組合せ最適化問題をソルバ装置に求解させる。複数の重み値のうちの一部分である第1部分重み群は、他の一部分である第2部分重み群と同一である。情報処理回路は、第1部分重み群および第2部分重み群を第1メモリにおける共通の領域に書き込み、第1メモリにおける複数の重み値のそれぞれの記憶位置を示す第1情報をソルバ装置に与える。ソルバ装置は、第1情報に基づき、第1メモリから複数の重み値を読み出して、解を求解する。
【選択図】図7
特許請求の範囲【請求項１】
データに対して処理を実行する情報処理装置であって、
組合せ最適化問題を求解するソルバ装置と、
情報処理回路と、
を備え、
前記情報処理回路は、
前記データを取得し、
前記データに基づき前記組合せ最適化問題を生成して、前記組合せ最適化問題を前記ソルバ装置に求解させ、
前記組合せ最適化問題におけるコスト関数は、複数の決定変数および複数の重み値を含み、
前記コスト関数に含まれる項は、前記複数の決定変数のうちの１以上の決定変数と、前記複数の重み値のうちの何れか１つの重み値との乗算により表され、
前記複数の重み値のうちの一部分である第１部分重み群は、他の一部分である第２部分重み群と同一であり、
前記ソルバ装置は、前記複数の重み値を記憶する第１メモリを含み、
前記情報処理回路は、
前記組合せ最適化問題の生成において、前記データに基づき前記複数の重み値を生成し、前記複数の重み値を前記第１メモリに書き込み、
前記複数の重み値の書き込みにおいて、前記第１部分重み群および前記第２部分重み群を前記第１メモリにおける共通の領域に書き込み、前記第１メモリにおける前記複数の重み値のそれぞれの記憶位置を示す第１情報を前記ソルバ装置に与え、
前記ソルバ装置は、前記第１情報に基づき、前記第１メモリから前記複数の重み値を読み出して、解を求解する
情報処理装置。
続きを表示（約 1,400 文字）【請求項２】
前記情報処理回路は、さらに、前記ソルバ装置から前記組合せ最適化問題の解を取得し、前記解に基づく処理を実行する
請求項１に記載の情報処理装置。
【請求項３】
前記複数の重み値のうちの第１重み値は、所定の第１領域における位置を表すインデックスにより識別され、
前記所定の第１領域は、同一の形状を有するＭ個の部分領域（Ｍは、３以上の整数）に分割され、
前記Ｍ個の部分領域のうちの第１部分領域は、前記複数の重み値の一部である部分重み群を含み、
前記Ｍ個の部分領域のそれぞれに配置される前記部分重み群は、Ｋ個のパターン（Ｋは、２以上、Ｍより小さい整数）のうちの何れかのパターンにより表され、
前記第１メモリは、前記Ｋ個のパターンを記憶し、
前記第１情報は、前記Ｍ個の部分領域のそれぞれが前記Ｋ個のパターンのうちの何れのパターンの前記部分重み群を含むかを示す
請求項１に記載の情報処理装置。
【請求項４】
前記ソルバ装置は、前記第１情報を記憶する第２メモリをさらに含み、
前記情報処理回路は、前記組合せ最適化問題の生成において、
前記データに基づき前記Ｋ個のパターンの前記部分重み群を生成して前記第１メモリに書き込み、
前記データに基づき前記第１情報を生成して前記第２メモリに書き込む
請求項３に記載の情報処理装置。
【請求項５】
前記複数の重み値のうちの前記第１重み値を読み出す場合、前記ソルバ装置は、
前記Ｍ個の部分領域のうち、前記第１重み値が含まれる部分領域を特定し、
前記第１情報に基づき、前記Ｋ個のパターンのうちの、前記第１重み値が含まれる前記部分領域におけるパターンを特定し、
前記第１重み値が含まれる前記部分領域における前記第１重み値の位置を表す第１アドレスを特定し、
前記第１メモリから、特定した前記パターンの前記部分重み群における、前記第１アドレスにより特定される重み値を、前記第１重み値として読み出す
請求項４に記載の情報処理装置。
【請求項６】
前記コスト関数は、前記複数の決定変数として、Ｎ個の決定変数（Ｎは２以上の整数）を含み、前記複数の重み値として、Ｎ行×Ｎ列の重み値を含む行列を含み、
前記コスト関数は、前記Ｎ個の決定変数の二次関数により表される
請求項３に記載の情報処理装置。
【請求項７】
前記複数の決定変数のそれぞれは、二値の離散変数である
請求項６に記載の情報処理装置。
【請求項８】
前記組合せ最適化問題は、ＱＵＢＯ（Quadratic Unconstrained Binary Optimization）問題である
請求項７に記載の情報処理装置。
【請求項９】
前記ソルバ装置は、前記ＱＵＢＯ問題を、イジングモデルを最小化するイジング問題に帰着させて解く
請求項８に記載の情報処理装置。
【請求項１０】
前記ソルバ装置は、シミュレーテッド分岐アルゴリズムにより前記イジング問題を解く
請求項９に記載の情報処理装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、プログラムおよび回路情報に関する。
続きを表示（約 2,700 文字）【背景技術】
【０００２】
制御、金融、通信、物流、化学などの様々な応用分野における系の最適化は、多くの場合、組合せ最適化問題へ数学的に帰着される。組合せ最適化問題を解くことによって、認識、判断および計画等の様々な情報処理機能を実現およびこのような機能の効率化をする情報処理システムが提案されている。
【０００３】
組合せ最適化問題とは、最適化の対象となる系の状態を表す複数の決定変数（例えば離散変数）を引数とするコスト関数を定義し、定義したコスト関数を最小化する複数の決定変数の値の組合せを求解する問題である。複数の決定変数により表される系の状態は、解と呼ばれる。組合せ最適化問題は、決定変数の数が増えるほど、解として取り得る状態の数が指数関数的に増大する。解として取り得る状態の数が増大することを、組み合わせ爆発と呼ぶ。全ての解の候補から最適な一つの解を選ぶという組み合わせ最適化は計算困難な問題として知られている。大規模な組み合わせ最適化を短時間に実行することは、いまだチャレンジングな課題である。
【０００４】
近年、イジングマシンと呼ばれる、イジングスピンモデルの基底状態を探索する特定目的装置が注目されている。イジングスピンモデルの基底状態を探索する問題を、イジング問題と呼ぶ。イジング問題は、二値変数の一つであるイジングスピンの二次関数で与えられたコスト関数を最小化する組合せ最適化問題である。イジング問題において、コスト関数は、イジングエネルギーと呼ばれる。多くの実用的な組み合わせ最適化問題は、イジング問題に変換することが可能である。イジングマシンは、イジング問題を高速に解くことが可能である。従って、多くの実用的な組み合わせ最適化問題は、イジングマシンを用いて、高速に解くことが可能である。
【０００５】
ところで、時々刻々と状況が変化する場合において、状況の変化に応じて新たな組合せ最適化問題を生成して求解をし、得られた解に基づき処理をすることがある。例えば、金融取引市場において株式を電子的に取引する取引装置に組合せ最適化問題を適用する場合、株式の価格変動に応じて、新たな組合せ最適化問題を生成し、得られた解に基づき取引をする。また、周辺風景を撮像した画像に基づき移動体を制御する制御システムに組合せ最適化問題を適用する場合、画像の変化に応じて、新たな組合せ最適化問題を生成し、得られた解に基づき移動体を制御する。
【０００６】
このようなシステムでは、状況が変化する毎に、組合せ最適化問題を生成し、生成した組合せ最適化問題をソルバ装置に与える。例えば、組合せ最適化問題がＮサイズのイジング問題である場合には、Ｎ×Ｎ個の２次係数およびＮ個の１次係数を生成して、ソルバ装置に与えなければならない。このため、このようなシステムでは、状況が変化してから、解に基づき処理をするまでの時間までの応答性を良くするためには、組合せ最適化問題を高速に生成して、ソルバ装置に与えることができることが好ましい。
【先行技術文献】
【特許文献】
【０００７】
特許第６６２９８６４号公報
特開２０２１－０６０８６４号公報
特開２０１９－１４５０１０号公報
特開２０１９－１５９５６６号公報
特開２０２１－０４３６６７号公報
特開２０２１－０４３５８９号公報
【非特許文献】
【０００８】
Hayato Goto， Kosuke Tatsumura and Alexander R. Dixon， “Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems，” Science Advances 5， eaav2372， 2019
Hayato Goto， Kotaro Endo， Masaru Suzuki， Yoshisato Sakai， Taro Kanao， Yohei Hamakawa， Ryo Hidaka， Masaya Yamasaki and Kosuke Tatsumura， “High-performance combinatorial optimization based on classical mechanics”， Science Advances 7， eabe7953， 2021
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明が解決しようとする課題は、組合せ最適化問題を高速に生成することである。
【課題を解決するための手段】
【００１０】
実施形態に係る情報処理装置は、データに対して処理を実行する。前記情報処理装置は、組合せ最適化問題を求解するソルバ装置と、情報処理回路と、を備える。前記情報処理回路は、前記データを取得する。前記情報処理回路は、前記データに基づき前記組合せ最適化問題を生成して、前記組合せ最適化問題を前記ソルバ装置に求解させる。前記組合せ最適化問題におけるコスト関数は、複数の決定変数および複数の重み値を含む。前記コスト関数に含まれる項は、前記複数の決定変数のうちの１以上の決定変数と、前記複数の重み値のうちの何れか１つの重み値との乗算により表される。前記複数の重み値のうちの一部分である第１部分重み群は、他の一部分である第２部分重み群と同一である。前記ソルバ装置は、前記複数の重み値を記憶する第１メモリを含む。前記情報処理回路は、前記組合せ最適化問題の生成において、前記データに基づき前記複数の重み値を生成し、前記複数の重み値を前記第１メモリに書き込む。前記情報処理回路は、前記複数の重み値の書き込みにおいて、前記第１部分重み群および前記第２部分重み群を前記第１メモリにおける共通の領域に書き込み、前記第１メモリにおける前記複数の重み値のそれぞれの記憶位置を示す第１情報を前記ソルバ装置に与える。前記ソルバ装置は、前記第１情報に基づき、前記第１メモリから前記複数の重み値を読み出して、解を求解する。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許