特許ウォッチ

公開番号2025005635
公報種別公開特許公報(A)
公開日2025-01-17
出願番号2023105888
出願日2023-06-28
発明の名称データ処理装置、プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250109BHJP(計算;計数)
要約【課題】複数ビット遷移を効率よく評価する。
【解決手段】等価スピン保持回路23は組合せ最適化問題の評価関数に含まれる異値または同値の2以上の2値変数からなる複数の変数群のそれぞれの、2以上の2値変数のうちの1つの値である代表値を保持する。等価結合係数メモリ21は複数の変数群の間の相互作用の大きさを表す複数の第1結合係数を記憶する。ΔE算出回路26は複数の変数群のそれぞれの代表値の変化に伴う評価関数の値の第1変化量の特定に用いられる第1局所場を用いて第1変化量を算出する。遷移等価スピン選択回路29は第1変化量に基づき複数の変数群の何れかの代表値の変化を受け入れ、等価スピン更新回路22は変化が受け入れられた第1変数群の代表値を更新する。等価局所場更新回路24は複数の第1結合係数のうち、第1変数群の第1識別番号に基づいて読み出された第2結合係数を用いて第1局所場を更新する。
【選択図】図7
特許請求の範囲【請求項１】
組合せ最適化問題の評価関数に含まれる異値または同値の２以上の２値変数からなる複数の変数群のそれぞれの、前記２以上の２値変数のうちの１つの値である代表値を保持する第１保持回路と、
前記複数の変数群の間の相互作用の大きさを表す複数の第１結合係数を記憶する第１メモリと、
前記複数の変数群のそれぞれの前記代表値の変化に伴う、前記評価関数の値の第１変化量の特定に用いられる第１局所場を保持する第２保持回路と、
前記第１局所場を用いて、前記第１変化量を、前記複数の変数群のそれぞれに対して算出する変化量算出回路と、
前記複数の変数群のそれぞれに対して算出された前記第１変化量に基づいて、前記複数の変数群の何れかの前記代表値の変化を受け入れる選択回路と、
前記複数の変数群のうち、前記代表値の変化が受け入れられた第１変数群の前記代表値を更新する第１更新回路と、
前記第１メモリに記憶されている前記複数の第１結合係数のうち、前記第１変数群の第１識別番号に基づいて読み出された第２結合係数を用いて、前記第１局所場を更新する第２更新回路と、
を有するデータ処理装置。
続きを表示（約 2,300 文字）【請求項２】
前記第１保持回路、前記第１メモリ、前記第２保持回路、前記変化量算出回路、前記選択回路、前記第１更新回路、前記第２更新回路と、を含む第１回路部と、
前記複数の変数群を含む、前記評価関数の複数の２値変数のそれぞれの値の変化に伴う、前記評価関数の値の第２変化量に基づいて、前記複数の２値変数の何れか１つの値の変化を受け入れる第２回路部と、
前記第１回路部による処理と、前記第２回路部による処理とを切り替える制御回路と、
を有する請求項１に記載のデータ処理装置。
【請求項３】
前記第１識別番号に基づいて、前記第１変数群に含まれる前記２以上の２値変数を特定する２以上の第２識別番号を出力するデコーダ回路を、さらに有し、
前記第２回路部は、前記２以上の第２識別番号に対応する前記２以上の２値変数の値を更新する、
請求項２に記載のデータ処理装置。
【請求項４】
前記複数の変数群の前記代表値の変化を許容するか否かを示すイネーブル信号を生成するイネーブル判定回路をさらに有し、
前記イネーブル判定回路は、前記第２回路部が前記複数の２値変数のうち、第１の２値変数の値の変化を受け入れた場合、前記複数の変数群のうち、前記第１の２値変数を含む第２変数群に関する前記イネーブル信号の値を反転させる、
請求項２に記載のデータ処理装置。
【請求項５】
前記第２回路部は、
前記評価関数の、前記複数の２値変数のそれぞれの値を保持する第３保持回路と、
前記複数の２値変数のそれぞれの間の相互作用の大きさを表す複数の第３結合係数を記憶する第２メモリと、
前記第２変化量の特定に用いられる第２局所場を保持する第４保持回路と、
を有し、
前記データ処理装置は、前記第２回路部の処理により得られた、前記複数の２値変数の値と、前記複数の第３結合係数及び前記第２局所場を用いて、前記第１局所場の初期値を算出する初期値算出回路を、さらに有する、
請求項２に記載のデータ処理装置。
【請求項６】
前記第２回路部は、
前記評価関数の、前記複数の２値変数のそれぞれの値を保持する第３保持回路と、
前記複数の２値変数のそれぞれの間の相互作用の大きさを表す複数の第３結合係数を記憶する第２メモリと、
前記第２変化量の特定に用いられる第２局所場を保持する第４保持回路と、
を有し、
前記第１回路部は、
前記複数の第３結合係数のうち、前記複数の変数群に含まれる２値変数が関係する複数の第４結合係数を記憶する第３メモリをさらに有し、
前記第２更新回路は、前記第２回路部が前記複数の２値変数のうちの第１の２値変数の値の変化を受け入れたとき、前記第１の２値変数の値の変化量と、前記第１の２値変数が関係する前記複数の第４結合係数の何れかを用いて、前記第１局所場を更新する、
請求項２に記載のデータ処理装置。
【請求項７】
前記第１回路部と前記第２回路部の一部が共通化されている、請求項２に記載のデータ処理装置。
【請求項８】
組合せ最適化問題の評価関数に含まれる異値または同値の２以上の２値変数からなる複数の変数群のそれぞれの、前記２以上の２値変数のうちの１つの値である代表値を保持し、
前記複数の変数群の間の相互作用の大きさを表す複数の第１結合係数をメモリに記憶し、
前記複数の変数群のそれぞれの前記代表値の変化に伴う、前記評価関数の値の第１変化量の特定に用いられる第１局所場を保持し、
前記第１局所場を用いて、前記第１変化量を、前記複数の変数群のそれぞれに対して算出し、
前記複数の変数群のそれぞれに対して算出された前記第１変化量に基づいて、前記複数の変数群の何れかの前記代表値の変化を受け入れ、
前記複数の変数群のうち、前記代表値の変化が受け入れられた第１変数群の前記代表値を更新し、
前記メモリに記憶されている前記複数の第１結合係数のうち、前記第１変数群の第１識別番号に基づいて読み出された第２結合係数を用いて、前記第１局所場を更新する、
処理をコンピュータに実行させるプログラム。
【請求項９】
コンピュータが、
組合せ最適化問題の評価関数に含まれる異値または同値の２以上の２値変数からなる複数の変数群のそれぞれの、前記２以上の２値変数のうちの１つの値である代表値を保持し、
前記複数の変数群の間の相互作用の大きさを表す複数の第１結合係数をメモリに記憶し、
前記複数の変数群のそれぞれの前記代表値の変化に伴う、前記評価関数の値の第１変化量の特定に用いられる第１局所場を保持し、
前記第１局所場を用いて、前記第１変化量を、前記複数の変数群のそれぞれに対して算出し、
前記複数の変数群のそれぞれに対して算出された前記第１変化量に基づいて、前記複数の変数群の何れかの前記代表値の変化を受け入れ、
前記複数の変数群のうち、前記代表値の変化が受け入れられた第１変数群の前記代表値を更新し、
前記メモリに記憶されている前記複数の第１結合係数のうち、前記第１変数群の第１識別番号に基づいて読み出された第２結合係数を用いて、前記第１局所場を更新する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする大規模な離散最適化問題を計算する装置として、イジング型の評価関数を用いたイジングマシンがある。イジングマシンを用いる場合、組合せ最適化問題が磁性体のスピンの振る舞いを表すイジングモデルに変換される。イジングマシンは、疑似焼き鈍し法やレプリカ交換法（パラレルテンパリング法などとも呼ばれる）などのマルコフ連鎖モンテカルロ法により、イジング型の評価関数の値が極小になるイジングモデルの状態を探索する。以下、マルコフ連鎖モンテカルロ法を、ＭＣＭＣ（Markov-Chain Monte Carlo）法と略す。評価関数の極小値のうちの最小値になる状態が最適解となる。イジングモデルの状態は、複数の２値変数の値の組合せにより表現できる。各２値変数の値として、０または１を用いることができる。このため、２値変数はビットと表記されてもよい。
【０００３】
イジング型の評価関数は、たとえば、以下の式（１）で定義される。
【０００４】
TIFF
2025005635000002.tif
16
163
【０００５】
右辺の１項目は、イジングモデルの全２値変数の全組合せについて、漏れと重複なく、２つの２値変数の値（０または１）と重み値（結合係数とも呼ばれる）との積を積算したものである。ｘ
ｉ
は、識別番号がｉの２値変数、ｘ
ｊ
は、識別番号がｊの２値変数であり、Ｗ
ｉｊ
は、識別番号がｉとｊの２値変数間の相互作用の大きさを表す結合係数である。右辺の２項目は、各識別番号についてのバイアス係数と２値変数との積の総和を求めたものである。ｂ
ｉ
は、識別番号＝ｉについてのバイアス係数を示している。
【０００６】
また、ｘ
ｉ
の値の変化に伴う評価関数の値の変化量（ΔＥ
ｉ
）は、以下の式（２）で表される。
【０００７】
TIFF
2025005635000003.tif
23
163
【０００８】
式（２）において、ｘ
ｉ
が１から０に変化するとき、Δｘ
ｉ
は－１となり、ｘ
ｉ
が０から１に変化するとき、Δｘ
ｉ
は１となる。なお、ｈ
ｉ
は局所場と呼ばれ、ΔＥ
ｉ
を特定する変数である。Δｘ
ｉ
に応じてｈ
ｉ
に符号（＋１または－１）を乗じたものがΔＥ
ｉ
となる。
【０００９】
イジングマシンは、たとえば、ΔＥ
ｉ
が、乱数と温度パラメータの値に基づいて得られるノイズ値より小さい場合、ｘ
ｉ
の値を反転させ局所場を更新する、という処理を繰り返すことで解の探索を行う。なお、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。
【００１０】
ΔＥ
ｉ
の算出やｘ
ｉ
の値を反転させるか否かの判定などの処理は、複数並列に行うことができるため、複数の２値変数に対する並列試行が可能である。
従来、ＭＣＭＣ法による処理の１試行あたりに２値変数の値の変化（以下、遷移ということもある）を許容する数を１とする処理（以下単一ビット遷移処理という）がある。しかし、単一ビット遷移処理では、解が局所解に嵌まった場合に、その局所解から脱出することが難しくなり、探索速度が低下する場合がある。
（【００１１】以降は省略されています）

関連特許