特許ウォッチ

公開番号2025163739
公報種別公開特許公報(A)
公開日2025-10-30
出願番号2024067224
出願日2024-04-18
発明の名称データ処理装置、データ処理方法およびプログラム
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20251023BHJP(計算;計数)
要約【課題】大規模問題の求解を効率的に行う。
【解決手段】処理部12は、複数の状態変数の間の重みを示す第1重み係数群30のうち試行対象部分に属する各第1状態変数に対応する第1重み係数、および、各状態変数と各制約条件の間の重みを示す第2重み係数群40のうち各第1状態変数に対応する第2重み係数を記憶装置20から読み出し、記憶部11に格納する。処理部12は、第1状態変数の値の変化に応じて、記憶部11に記憶される第1重み係数に基づき、状態変数に対応する第1局所場を更新し、記憶部11に記憶される第2重み係数に基づき、制約条件に対応する第2局所場を更新し、更新前後の第2局所場に基づき第1局所場を更に更新する探索処理を繰り返す。処理部12は、当該探索処理後に、当該探索処理の開始時と終了後の第2局所場を基に、試行対象部分に属さない第2状態変数の第1局所場を更新し、試行対象部分を次の部分に変更する。
【選択図】図1
特許請求の範囲【請求項１】
複数の状態変数と複数の制約条件に対応する項とを含むイジング型の評価関数に基づいて前記複数の状態変数の値の組合せで表される解を探索するデータ処理装置において、
前記複数の状態変数の各々の間の重みを示す第１重み係数群および前記複数の状態変数の各々と前記複数の制約条件の各々との間の重みを示す第２重み係数群を記憶する記憶装置に記憶される前記第１重み係数群のうちの一部と、前記記憶装置に記憶される前記第２重み係数群のうちの一部と、前記複数の状態変数の各々の値が変化する場合の前記評価関数の値の変化量を表す第１局所場と、前記複数の制約条件の各々に対する制約違反量の特定に用いられる第２局所場と、を記憶する記憶部と、
前記複数の状態変数のうち、値の更新を行うか否かの試行の対象とする複数の第１状態変数を含む部分である試行対象部分について、前記第１重み係数群のうちの前記試行対象部分に属する第１状態変数に対応する第１重み係数と、前記第２重み係数群のうちの前記試行対象部分に属する前記第１状態変数に対応する第２重み係数と、を前記記憶装置から読み出して前記記憶部に格納し、
前記試行対象部分に属する前記第１状態変数の値の変化を許容するか否かを前記第１局所場に基づいて判定する第１処理と、前記第１状態変数の値の変化を許容すると判定した場合、前記記憶部に記憶される前記第１重み係数に基づいて前記第１局所場を更新し、前記記憶部に記憶される前記第２重み係数に基づいて前記第２局所場を更新し、更新前の前記第２局所場と更新後の前記第２局所場とに基づいて、前記複数の第１状態変数の各々に対応する前記第１局所場を更に更新する第２処理とを繰り返す探索処理を実行し、
今回の前記試行対象部分に対する前記探索処理を終えると、今回の前記試行対象部分に対する前記探索処理の開始時の前記第２局所場と、今回の前記試行対象部分に対する前記探索処理の後の前記第２局所場とに基づいて、今回の前記試行対象部分に属さない第２状態変数に対応する前記第１局所場を更新し、
前記試行対象部分を前記複数の状態変数のうちの次の部分に変更する、
処理を繰り返す処理部と、
を有するデータ処理装置。
続きを表示（約 3,700 文字）【請求項２】
前記処理部は、
前記試行対象部分に属する前記第１状態変数に対応する全ての前記第２重み係数を、前記記憶装置から読み出して前記記憶部に格納し、
前記探索処理では、前記第１状態変数の値の変化が許容されると、前記記憶部に記憶される前記第２重み係数に基づいて前記複数の制約条件の各々に対応する前記第２局所場を更新する、
請求項１記載のデータ処理装置。
【請求項３】
前記処理部は、
前記試行対象部分に属する前記複数の第１状態変数に対応する全ての前記第２重み係数のうちの一部の前記第２重み係数であって、前記複数の制約条件のうちの一部の制約条件に対応する前記第２重み係数を、前記記憶装置から読み出して前記記憶部に格納し、前記記憶部に記憶された当該第２重み係数に基づいて前記探索処理を行い、
前記探索処理では、前記第１状態変数の値の変化が許容されると、前記第１局所場に基づいて前記評価関数の値を計算して前記記憶部に格納し、前記記憶部に保持される前記第２重み係数に基づいて、前記一部の制約条件に対応する前記第２局所場を更新し、更新前後の前記第２局所場に基づいて前記複数の第１状態変数の各々に対応する前記第１局所場を更に更新し、
前記探索処理を終えると、前記試行対象部分に属する前記第１状態変数の値の変化と、前記第１状態変数に対応する全ての前記第２重み係数のうち、前記探索処理で用いられた一部の前記第２重み係数とは異なる部分の前記第２重み係数とに基づいて、前記複数の制約条件のうち、前記一部の制約条件以外の制約条件に対応する前記第２局所場を更新し、当該更新後に、今回の前記試行対象部分に対する前記探索処理の開始時の前記第２局所場と現在の前記第２局所場とに基づいて、今回の前記試行対象部分に属さない前記第２状態変数に対応する前記第１局所場を更新するとともに、前記試行対象部分に属する前記第１状態変数に対応する前記第１局所場を補正し、
前記試行対象部分に属する前記第１状態変数の値の変化と、前記一部の制約条件以外の前記制約条件に対応する前記第２局所場とに基づいて、前記記憶部に記憶される前記評価関数の値を補正し、
前記試行対象部分に属する前記複数の第１状態変数および前記複数の制約条件のうちの次の一部の制約条件に対応する前記第２重み係数を、前記記憶装置から読み出して前記記憶部に格納し、前記記憶部に記憶された当該第２重み係数に基づく前記探索処理に移る、
処理を繰り返し、
今回の前記試行対象部分に対して、全ての前記制約条件に関する前記探索処理を行うと、前記試行対象部分を前記複数の状態変数のうちの次の部分に変更する、
請求項１記載のデータ処理装置。
【請求項４】
前記処理部は、
前記試行対象部分に属する前記複数の第１状態変数の各々に対応する全ての前記第１重み係数のうちの前記第１状態変数のペアに対応する第１部分の前記第１重み係数を、前記記憶装置から読み出して前記記憶部に格納し、
前記探索処理では、前記第１状態変数の値の変化が許容されると、前記記憶部に記憶される前記第１部分の前記第１重み係数に基づいて、前記複数の状態変数のうち、前記試行対象部分に属する前記複数の第１状態変数の各々に対応する前記第１局所場を更新し、
今回の前記試行対象部分に対する前記探索処理を終えた際の前記第２状態変数に対応する前記第１局所場の更新では、更に、今回の前記試行対象部分に属する前記第１状態変数の値の変化と、前記第１状態変数および前記第２状態変数のペアに対応する前記第１重み係数とに基づいて、前記第２状態変数に対応する前記第１局所場を更新する、
請求項１記載のデータ処理装置。
【請求項５】
前記処理部は、
前記試行対象部分に属する前記複数の第１状態変数の各々に対応する全ての前記第１重み係数を、前記記憶装置から読み出して前記記憶部に格納し、
前記探索処理では、前記第１状態変数の値の変化が許容されると、前記記憶部に記憶される前記第１重み係数に基づいて前記複数の状態変数の各々に対応する前記第１局所場を更新する、
請求項１記載のデータ処理装置。
【請求項６】
前記処理部は、前記評価関数によって示される前記複数の状態変数の数と、前記複数の制約条件の数と、前記複数の状態変数の数および前記複数の制約条件の数の和に対して許容される上限値とに基づいて、前記複数の状態変数および前記複数の制約条件の少なくとも一方を分割して前記探索処理を行うか否かを決定する、
請求項１記載のデータ処理装置。
【請求項７】
複数の状態変数と複数の制約条件に対応する項とを含むイジング型の評価関数に基づいて前記複数の状態変数の値の組合せで表される解を探索するデータ処理方法において、
データ処理装置が、
前記複数の状態変数の各々の間の重みを示す第１重み係数群および前記複数の状態変数の各々と前記複数の制約条件の各々との間の重みを示す第２重み係数群を記憶する記憶装置から、前記複数の状態変数のうち、値の更新を行うか否かの試行の対象とする複数の第１状態変数を含む部分である試行対象部分について、前記第１重み係数群のうちの前記試行対象部分に属する第１状態変数に対応する第１重み係数と、前記第２重み係数群のうちの前記試行対象部分に属する前記第１状態変数に対応する第２重み係数と、を読み出して記憶部に格納し、
前記複数の状態変数の各々の値が変化する場合の前記評価関数の値の変化量を表す第１局所場に基づいて、前記試行対象部分に属する前記第１状態変数の値の変化を許容するか否かを判定する第１処理と、前記第１状態変数の値の変化を許容すると判定した場合、前記記憶部に記憶される前記第１重み係数に基づいて前記第１局所場を更新し、前記記憶部に記憶される前記第２重み係数に基づいて、前記複数の制約条件の各々に対する制約違反量の特定に用いられる第２局所場を更新し、更新前の前記第２局所場と更新後の前記第２局所場とに基づいて、前記複数の第１状態変数の各々に対応する前記第１局所場を更に更新する第２処理とを繰り返す探索処理を実行し、
今回の前記試行対象部分に対する前記探索処理を終えると、今回の前記試行対象部分に対する前記探索処理の開始時の前記第２局所場と、今回の前記試行対象部分に対する前記探索処理の後の前記第２局所場とに基づいて、今回の前記試行対象部分に属さない第２状態変数に対応する前記第１局所場を更新し、
前記試行対象部分を前記複数の状態変数のうちの次の部分に変更する、
処理を繰り返す、
データ処理方法。
【請求項８】
複数の状態変数と複数の制約条件に対応する項とを含むイジング型の評価関数に基づいて前記複数の状態変数の値の組合せで表される解を探索するプログラムにおいて、
前記複数の状態変数の各々の間の重みを示す第１重み係数群および前記複数の状態変数の各々と前記複数の制約条件の各々との間の重みを示す第２重み係数群を記憶する記憶装置から、前記複数の状態変数のうち、値の更新を行うか否かの試行の対象とする複数の第１状態変数を含む部分である試行対象部分について、前記第１重み係数群のうちの前記試行対象部分に属する第１状態変数に対応する第１重み係数と、前記第２重み係数群のうちの前記試行対象部分に属する前記第１状態変数に対応する第２重み係数と、を読み出して記憶部に格納し、
前記複数の状態変数の各々の値が変化する場合の前記評価関数の値の変化量を表す第１局所場に基づいて、前記試行対象部分に属する前記第１状態変数の値の変化を許容するか否かを判定する第１処理と、前記第１状態変数の値の変化を許容すると判定した場合、前記記憶部に記憶される前記第１重み係数に基づいて前記第１局所場を更新し、前記記憶部に記憶される前記第２重み係数に基づいて、前記複数の制約条件の各々に対する制約違反量の特定に用いられる第２局所場を更新し、更新前の前記第２局所場と更新後の前記第２局所場とに基づいて、前記複数の第１状態変数の各々に対応する前記第１局所場を更に更新する第２処理とを繰り返す探索処理を実行し、
今回の前記試行対象部分に対する前記探索処理を終えると、今回の前記試行対象部分に対する前記探索処理の開始時の前記第２局所場と、今回の前記試行対象部分に対する前記探索処理の後の前記第２局所場とに基づいて、今回の前記試行対象部分に属さない第２状態変数に対応する前記第１局所場を更新し、
前記試行対象部分を前記複数の状態変数のうちの次の部分に変更する、
処理を繰り返す、
処理をコンピュータに実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明はデータ処理装置、データ処理方法およびプログラムに関する。
続きを表示（約 1,300 文字）【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする大規模な離散最適化問題を計算する装置として、イジング型の評価関数（エネルギー関数などとも呼ばれる）を用いたイジング装置（ボルツマンマシンとも呼ばれる）がある。
【０００３】
イジング装置は、離散最適化問題を磁性体のスピンの振る舞いを表すイジングモデルに変換する。そして、イジング装置は、疑似焼き鈍し法やレプリカ交換法などのマルコフ連鎖モンテカルロ法により、イジング型の評価関数の値が極小になるイジングモデルの状態を探索する。評価関数の値は、イジングモデルのエネルギーに相当する。評価関数の極小値のうちの最小値になる状態が最適解となる。なお、イジング装置は、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。イジングモデルの状態は、複数の状態変数の値の組合せにより表現できる。各状態変数の値として、０または１を用いることができる。
【０００４】
評価関数は、例えば以下の式（１）で表される。
【０００５】
TIFF
2025163739000002.tif
20
154
【０００６】
右辺の１項目は、イジングモデルのＮ個の状態変数の全組合せについて、漏れと重複なく、２つの状態変数の値（０または１）と重み係数（２つの状態変数の間の相互作用の強さを表す）との積を積算したものである。ｘ
ｉ
は、識別番号がｉの状態変数、ｘ
ｊ
は、識別番号がｊの状態変数であり、Ｗ
ｉｊ
は、識別番号がｉとｊの状態変数間の相互作用の大きさを示す重み係数である。右辺の２項目は、各識別番号についてのバイアス係数と状態変数との積の総和を求めたものである。ｂ
ｉ
は、識別番号がｉについてのバイアス係数を示している。
【０００７】
また、ｘ
ｉ
の値の変化に伴うエネルギーの変化量（ΔＥ
ｉ
）は、以下の式（２）で表される。
【０００８】
TIFF
2025163739000003.tif
20
155
【０００９】
式（２）において、ｘ
ｉ
が１から０に変化するとき、Δｘ
ｉ
は－１となり、状態変数ｘ
ｉ
が０から１に変化するとき、Δｘ
ｉ
は１となる。なお、ｈ
ｉ
は局所場と呼ばれ、Δｘ
ｉ
に応じてｈ
ｉ
に符号（＋１または－１）を乗じたものがΔＥ
ｉ
となる。このため、ｈ
ｉ
はエネルギーの変化量を表す変数、またはエネルギーの変化量を決める変数ということもできる。
【００１０】
そして、例えばｅｘｐ（－βΔＥ
ｉ
）（βは温度を表すパラメータの逆数）と表せる受け入れ確率でｘ
ｉ
の値を更新することで状態遷移を発生させ、局所場も更新する、という処理が繰り返される。
（【００１１】以降は省略されています）

関連特許