特許ウォッチ

公開番号2025109070
公報種別公開特許公報(A)
公開日2025-07-24
出願番号2024002774
出願日2024-01-11
発明の名称情報処理装置、方法及びプログラム
出願人株式会社東芝
代理人弁理士法人鈴榮特許綜合事務所
主分類G06N 99/00 20190101AFI20250716BHJP(計算;計数)
要約【課題】組合せ最適化問題の計算精度の向上及び/又は処理時間の低減を可能とする情報処理装置、方法及びプログラムを提供すること。
【解決手段】情報処理装置は、第一探索部と第二探索部とを有する。第一探索部は、目的関数を偏微分可能な組合せ最適化問題の第一の暫定解を、組合せ最適化問題の全体問題を求解する第一探索器を使用して探索する。第二探索部は、第一の暫定解と目的関数の偏微分値との符号の比較に基づいて、組合せ最適化問題の最終解を出力する。
【選択図】図3
特許請求の範囲【請求項１】
目的関数を偏微分可能な組合せ最適化問題の第一の暫定解を、前記組合せ最適化問題の全体問題を求解する第一探索器を使用して探索する第一探索部と、
前記第一の暫定解と前記目的関数の偏微分値との符号の比較に基づいて、前記組合せ最適化問題の最終解を出力する第二探索部と、
を具備する情報処理装置。
続きを表示（約 1,400 文字）【請求項２】
前記第二探索部は、
前記第一の暫定解から、当該第一の暫定解に対応する前記偏微分値との符号が一致する次元である第一の次元を抽出し、
前記組合せ最適化問題の部分問題を求解する第二探索器を使用して、前記第一の次元を部分問題として前記組合せ最適化問題を演算して前記最終解を探索する、
請求項１記載の情報処理装置。
【請求項３】
前記第二探索部は、
前記第一の暫定解と前記偏微分値との符号が全ての次元について不一致である場合、前記第一の暫定解を前記最終解として出力し、
前記第一の暫定解と前記偏微分値との符号が全ての次元について不一致でない場合、前記第一の暫定解から前記第一の次元を抽出する、
請求項２記載の情報処理装置。
【請求項４】
前記第二探索部は、
前記第二探索器を使用して、前記第一の次元を部分問題として前記組合せ最適化問題を演算して第二の暫定解を出力し、
前記第二の暫定解から、当該第二の暫定解に対応する前記偏微分値との符号が一致する次元である第二の次元を抽出し、
前記第二探索器を使用して、前記第二の次元を部分問題として前記組合せ最適化問題を演算して前記最終解を探索する、
請求項３記載の情報処理装置。
【請求項５】
前記第二探索部は、
前記第二の暫定解と前記第一の暫定解のうちの残りの次元との統合解を生成し、
前記統合解と前記第二の暫定解に対応する前記偏微分値との符号が全ての次元について不一致である場合、前記統合解を前記最終解として出力し、
前記統合解と前記第二の暫定解に対応する前記偏微分値との符号が全ての次元について不一致でない場合、前記第二の暫定解から前記第二の次元を抽出する、
請求項４記載の情報処理装置。
【請求項６】
前記組合せ最適化問題は、前記第一の暫定解及び前記最終解として複数の格子点の量子状態の組合せを表すベクトルを出力するための、前記目的関数が前記複数の格子点のイジングエネルギーに設定されたイジング問題であり、
前記量子状態は、二値状態であり、
前記目的関数の偏微分は、前記量子状態に関する前記目的関数の微分である、
請求項２記載の情報処理装置。
【請求項７】
前記イジング問題は、線形回帰問題、サポートベクターマシン分類問題及び巡回セールス問題の何れか一つである、請求項６記載の情報処理装置。
【請求項８】
前記第一探索器及び前記第二探索器は、前記イジングエネルギーを最小にする前記ベクトルを出力するイジングマシンである、請求項６記載の情報処理装置。
【請求項９】
前記第一探索器及び前記第二探索器各々は、シミュレーテッドアニーリングマシン又はシミュレーテッド分岐マシンである、請求項８記載の情報処理装置。
【請求項１０】
前記第一探索器及び前記第二探索器各々がシミュレーテッド分岐マシンである場合、前記第一探索器及び／又は前記第二探索器により前記組合せ最適化問題を求解するための計算ステップ数は、前記イジング問題の次元の個数に比例する値に設定される、請求項９記載の情報処理装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、情報処理装置、方法及びプログラムに関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
大規模な組合せ最適化問題を求解する際、精度の良い解が得られない、あるいは精度の良い解を得るには膨大な処理時間を要してしまうという問題がある。
【先行技術文献】
【非特許文献】
【０００３】
Hayato Goto, Kotaro Endo, Masaru Suzuki, Yoshisato Sakai, Taro Kanao, Yohei Hamakawa, Ryo Hidaka, Masaya Yamasaki, Kosuke Tatsumura, “High-performance combinatorial optimization based on classical mechanics”, SCIENCE ADVANCES, Vol 7, Issue 6
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする課題は、組合せ最適化問題の計算精度の向上及び／又は処理時間の低減を可能とする情報処理装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【０００５】
実施形態に係る情報処理装置は、第一探索部と第二探索部とを有する。前記第一探索部は、目的関数を偏微分可能な組合せ最適化問題の第一の暫定解を、前記組合せ最適化問題の全体問題を求解する第一探索器を使用して探索する。前記第二探索部は、前記第一の暫定解と前記目的関数の偏微分値との符号の比較に基づいて、前記組合せ最適化問題の最終解を出力する。
【図面の簡単な説明】
【０００６】
情報処理装置のハードウェア構成例を示す図
イジングエネルギーＥ
ｉｓｉｎｇ
とスピンｓとの関係を表す図
最適化処理の処理手順を例示する図
図３に示す最適化処理における解の符号と偏微分の符号との変遷を模式的に示す図
二値分類問題をシミュレーテッド分岐マシンで求解した際の予測精度と一致次元（不完全最適化次元）の個数とを比較する図
二値分類問題をシミュレーテッド分岐マシン（ＳＢ）とシミュレーテッドアニーリングマシン（ＳＡ）で求解したときの予測精度を、本実施例と比較例とで比較する図
線形回帰問題をシミュレーテッド分岐マシン（ＳＢ）とシミュレーテッドアニーリングマシン（ＳＡ）で求解したときの予測精度を、本実施例と比較例とで比較する図
巡回セールスマン問題（ｇｒ９６）をシミュレーテッド分岐マシン（ＳＢ）とシミュレーテッドアニーリングマシン（ＳＡ）で求解したときの予測精度を、本実施例と比較例とで比較する図
巡回セールスマン問題（ｃｈ１３０）をシミュレーテッド分岐マシン（ＳＢ）とシミュレーテッドアニーリングマシン（ＳＡ）で求解したときの予測精度を、本実施例と比較例とで比較する図
変形例に係る最適化処理の処理手順を例示する図
図１０に示す最適化処理における解の符号と偏微分の符号との変遷を模式的に示す図
【発明を実施するための形態】
【０００７】
以下、図面を参照しながら本実施形態に係わる情報処理装置、方法及びプログラムを説明する。
【０００８】
図１は、情報処理装置１００のハードウェア構成例を示す図である。図１に示すように、情報処理装置１００は、プロセッサ１、記憶装置２、入力機器３、表示機器４及び通信機器５を有するコンピュータである。プロセッサ１、記憶装置２、入力機器３、表示機器４及び通信機器５間のデータ及び各種信号の送受信は、バス（Bus）を介して行われる。
【０００９】
プロセッサ１は、情報処理装置１００の全体の動作を制御する集積回路である。例えば、プロセッサ１は、ＣＰＵ（Central Processing Unit）、ＧＰＵ（Graphics Processing Unit）、ＤＳＰ（Digital Signal Processor）及び／又はＦＰＵ（Floating-Point Unit）を有する。プロセッサ１は、内部メモリやＩ／Ｏインタフェースを備えてもよい。プロセッサ１は、記憶装置２等が予め記憶するプログラムを解釈及び演算することにより種々の処理を実行する。なおプロセッサ１は、一部又は全体がＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）等のハードウェアにより実現されてもよい。
【００１０】
記憶装置２は、種々のデータを記憶する揮発性メモリ及び／又は不揮発性メモリである。例えば、記憶装置２は、プロセッサ１が各種の処理を実行する際に使用するデータや設定値、プロセッサ１での各種処理により生成されたデータ等を記憶する。記憶装置２は、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、集積回路記憶装置等により構成される。なお、記憶装置２は、プロセッサ１が実行するプログラムを記憶する非一時的なコンピュータ可読記憶媒体を有してもよい。
（【００１１】以降は省略されています）

関連特許