特許ウォッチ

公開番号2024167800
公報種別公開特許公報(A)
公開日2024-12-04
出願番号2023084138
出願日2023-05-22
発明の名称データ処理装置、プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20241127BHJP(計算;計数)
要約【課題】多値変数で表現された組合せ最適化問題を、並列試行により計算可能とする。
【解決手段】記憶部11が、複数の多値変数を用いて表される組合せ最適化問題の評価関数に関する評価関数情報11aを記憶し、処理部12が、評価関数情報11aに基づいて、複数の多値変数のそれぞれの値の遷移可能範囲のうちの一部である遷移先候補を生成し、複数の多値変数のそれぞれに対して、評価関数情報11aに基づいて、遷移先候補への遷移に伴う評価関数の値の変化量を算出し、変化量に基づいて遷移を受け入れる多値変数を複数の多値変数の中から決定し、決定した多値変数の値を遷移先候補の値へ遷移させる。
【選択図】図1
特許請求の範囲【請求項１】
複数の多値変数を用いて表される組合せ最適化問題の評価関数に関する評価関数情報を記憶する記憶部と、
前記評価関数情報に基づいて、前記複数の多数変数のそれぞれの値の遷移可能範囲のうちの一部である遷移先候補を生成し、前記複数の多値変数のそれぞれに対して、前記評価関数情報に基づいて、前記遷移先候補への遷移に伴う前記評価関数の値の変化量を算出し、前記変化量に基づいて前記遷移を受け入れる多値変数を前記複数の多値変数の中から決定し、決定した前記多値変数の値を前記遷移先候補の値へ遷移させる処理部と、
を有するデータ処理装置。
続きを表示（約 2,200 文字）【請求項２】
前記処理部は、
前記複数の多値変数のそれぞれの前記遷移に伴う前記変化量を保持する保持回路と、
前記複数の多値変数のそれぞれに対して、前記遷移を受け入れる前記多値変数の値の変化に伴う前記変化量の差分値を算出する算出回路と、
前記差分値を用いて前記変化量を更新する更新回路と、
を含む請求項１に記載のデータ処理装置。
【請求項３】
前記組合せ最適化問題は、フロー行列及び距離行列を用いて表される割当問題であり、
前記記憶部は、
前記フロー行列と前記距離行列の一方である第１行列を記憶する第１メモリと、
前記フロー行列と前記距離行列の他方であって、前記複数の多値変数の値に基づいて配列された行列要素を含む第２行列を記憶する第２メモリと、
前記フロー行列と前記距離行列の他方であって、前記複数の多値変数の前記遷移先候補の値に基づいて配列された行列要素を含む第３行列を記憶する第３メモリと、
を有し、
前記算出回路は、前記遷移を受け入れる前記多値変数の識別番号により指定される前記第１行列の第１行列要素と、前記遷移を受け入れる前記多値変数の前記遷移の前の値により指定される、前記第２行列の第２行列要素及び前記第３行列の第３行列要素と、前記多値変数の前記遷移の後の値により指定される、前記第２行列の第４行列要素及び前記第３行列の第５行列要素と、に基づいて前記差分値を算出する、
請求項２に記載のデータ処理装置。
【請求項４】
前記第２行列及び前記第３行列の、行または列の一方が、前記遷移を受け入れる前記多値変数の値または前記多値変数の前記遷移の後の値により指定され、
指定された前記行または前記列に含まれる前記第２行列要素、前記第３行列要素、前記第４行列要素または前記第５行列要素が、前記第２メモリまたは前記第３メモリから読み出される、
請求項３に記載のデータ処理装置。
【請求項５】
前記第２行列要素及び前記第３行列要素は、第１読み出しタイミングで前記第２メモリと前記第３メモリから並列に読み出され、
前記第４行列要素及び前記第５行列要素は、第２読み出しタイミングで前記第２メモリと前記第３メモリから並列に読み出される、
請求項３に記載のデータ処理装置。
【請求項６】
前記第１乃至第５行列要素は、共通の読み出し経路を用いて、互いに異なる読み出しタイミングで前記第１メモリ、前記第２メモリまたは前記第３メモリから読み出され、
前記算出回路は、前記第１乃至第５行列要素を、共通の演算回路に入力して前記差分値を算出する、請求項３に記載のデータ処理装置。
【請求項７】
前記処理部は、前記遷移を受け入れる前記多値変数の前記識別番号により指定される、前記第２行列と前記第３行列の列または行を、前記第２行列と前記第３行列との間で入れ替える、請求項３に記載のデータ処理装置。
【請求項８】
前記複数の多値変数のそれぞれに対して、前記遷移先候補は第１遷移先候補と第２遷移先候補を含み、
前記第３行列は、前記第１遷移先候補の値に基づいて配列されており、
前記記憶部は、さらに、前記フロー行列と前記距離行列の他方であって、前記第２遷移先候補の値に基づいて配列された行列要素を含む第４行列を記憶する第４メモリを有する、
請求項３に記載のデータ処理装置。
【請求項９】
前記組合せ最適化問題は、フロー行列及び距離行列を用いて表される割当問題であり、
前記記憶部は、
前記フロー行列と前記距離行列の一方である第１行列を記憶する第１メモリと、
前記フロー行列と前記距離行列の他方であって、前記複数の多値変数の値に基づいて配列された第２行列の行列要素の値と、前記フロー行列と前記距離行列の他方であって、前記複数の多値変数の前記遷移先候補の値に基づいて配列された第３行列の行列要素の値との差により表現される行列要素を含む第４行列を記憶する第２メモリと、
を有し、
前記算出回路は、前記遷移を受け入れる前記多値変数の識別番号により指定される前記第１行列の第１行列要素と、前記遷移を受け入れる前記多値変数の前記遷移の前の値により指定される前記第４行列の第２行列要素と、前記多値変数の前記遷移の後の値により指定される、前記第４行列の第３行列要素と、に基づいて前記差分値を算出する、
請求項２に記載のデータ処理装置。
【請求項１０】
メモリに記憶されている、複数の多値変数を用いて表される組合せ最適化問題の評価関数に関する評価関数情報に基づいて、前記複数の多値変数のそれぞれの値の遷移可能範囲のうちの一部である遷移先候補を生成し、
前記複数の多値変数のそれぞれに対して、前記評価関数情報に基づいて、前記遷移先候補への遷移に伴う前記評価関数の値の変化量を算出し、
前記変化量に基づいて前記遷移を受け入れる多値変数を前記複数の多値変数の中から決定し、
決定した前記多値変数の値を前記遷移先候補の値へ遷移させる、
処理をコンピュータに実行させるプログラム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする大規模な離散最適化問題を計算する装置として、イジング型の評価関数を用いたイジングマシンがある。イジングマシンを用いる場合、組合せ最適化問題が磁性体のスピンの振る舞いを表すイジングモデルに変換される。そして、イジングマシンは、疑似焼き鈍し法やレプリカ交換法（パラレルテンパリング法などとも呼ばれる）などのマルコフ連鎖モンテカルロ法により、イジング型の評価関数の値が極小になるイジングモデルの状態を探索する。評価関数の極小値のうちの最小値になる状態が最適解となる。イジングモデルの状態は、複数の状態変数の値の組合せにより表現できる。各状態変数の値として、０または１を用いることができる。
【０００３】
イジング型の評価関数は、たとえば、以下の式（１）で定義される。
【０００４】
TIFF
2024167800000002.tif
17
145
【０００５】
右辺の１項目は、イジングモデルの全状態変数の全組合せについて、漏れと重複なく、２つの状態変数の値（０または１）と重み値（２つの状態変数の間の相互作用の強さを表す）との積を積算したものである。ｘ
ｉ
は、識別番号がｉの状態変数、ｘ
ｊ
は、識別番号がｊの状態変数であり、Ｗ
ｉｊ
は、識別番号がｉとｊの状態変数間の相互作用の大きさを示す重み値である。右辺の２項目は、各識別番号についてのバイアス係数と状態変数との積の総和を求めたものである。ｂ
ｉ
は、識別番号＝ｉについてのバイアス係数を示している。
【０００６】
また、ｘ
ｉ
の値の変化に伴う評価関数の値の変化量（ΔＥ
ｉ
）は、以下の式（２）で表される。
【０００７】
TIFF
2024167800000003.tif
16
145
【０００８】
式（２）において、ｘ
ｉ
が１から０に変化するとき、Δｘ
ｉ
は－１となり、状態変数ｘ
ｉ
が０から１に変化するとき、Δｘ
ｉ
は１となる。なお、ｈ
ｉ
は局所場と呼ばれ、Δｘ
ｉ
に応じてｈ
ｉ
に符号（＋１または－１）を乗じたものがΔＥ
ｉ
となる。
【０００９】
イジングマシンは、たとえば、ΔＥ
ｉ
が、乱数と温度パラメータの値に基づいて得られるノイズ値より小さい場合、ｘ
ｉ
の値を反転させ局所場を更新する、という処理を繰り返すことで解の探索を行う。
【００１０】
ΔＥ
ｉ
の算出やｘ
ｉ
の値を反転させるか否かの判定などの処理は、複数並列に行うことができるため、複数の状態変数に対する並列試行が可能である。
ところで、組合せ最適化問題には、割当問題などのように多値変数を用いて表すことができるものがある。割当問題では、ある要素がどの割当先に割り当てられているかを示す割当状態を、多値変数で表すことができる。従来、割当問題の解を、イジングマシンを用いて探索する技術が提案されている（たとえば、特許文献１，２参照）。
【先行技術文献】
【特許文献】
（【００１１】以降は省略されています）

関連特許