TOP特許意匠商標
特許ウォッチ Twitter
10個以上の画像は省略されています。
公開番号2024077351
公報種別公開特許公報(A)
公開日2024-06-07
出願番号2022189402
出願日2022-11-28
発明の名称データ処理装置、プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20240531BHJP(計算;計数)
要約【課題】複数ビット遷移処理の実装を容易にする。
【解決手段】遷移候補決定回路13は、メモリ12に記憶した局所場の値に基づいて、複数の状態変数のそれぞれの値が変化したときの評価関数の値の変化量を計算するとともに、所定の時点から、複数の状態変数のうち値を変化させる候補を1つずつ決定し、更新回路14は、候補が決定されるたび、メモリ12に記憶されている候補の値と局所場の値を更新し、累積値計算回路15は、候補の値を変化させたときの上記変化量の累積値を計算し、判定回路16は、累積値に基づいて、2以上の第1の数の候補の値の変化を受け入れるか否かを判定し、制御回路17は、判定回路16が第1の数の候補の値の変化を受け入れないと判定した場合、更新された複数の状態変数の値と更新された局所場の値を、メモリ12に記憶されている上記所定の時点における値に戻す。
【選択図】図1
特許請求の範囲【請求項1】
組合せ最適化問題の評価関数に含まれる複数の状態変数の値と、前記複数の状態変数のそれぞれにおける局所場の値と、所定の時点における前記複数の状態変数の値と、前記所定の時点における前記局所場の値と、を記憶するメモリと、
前記局所場の値に基づいて、前記複数の状態変数のそれぞれの値が変化したときの前記評価関数の値の変化量を計算するとともに、前記所定の時点から、前記複数の状態変数のうち値を変化させる候補を1つずつ決定する遷移候補決定回路と、
前記候補が決定されるたび、前記メモリに記憶されている前記候補の値と前記局所場の値を更新する更新回路と、
前記候補の値を変化させたときの前記変化量の累積値を計算する累積値計算回路と、
前記累積値に基づいて、2以上の第1の数の前記候補の値の変化を受け入れるか否かを判定する判定回路と、
前記判定回路が前記第1の数の前記候補の値の変化を受け入れないと判定した場合、更新された前記複数の状態変数の値と更新された前記局所場の値を、前記所定の時点における前記複数の状態変数の値と前記局所場の値に戻す制御回路と、
を有するデータ処理装置。
続きを表示(約 2,200 文字)【請求項2】
前記制御回路は、前記遷移候補決定回路に、前記変化量に基づいて前記複数の状態変数のそれぞれの値の変化を許容するか否かを判定する第1の処理をさせるか、前記所定の時点から、前記候補を1つずつ決定する第2の処理をさせるかを切り替え、
前記所定の時点は、前記第2の処理が開始する時点である、
請求項1に記載のデータ処理装置。
【請求項3】
前記メモリは、前記複数の状態変数の値と前記局所場の値を、複数のレプリカの数分記憶し、
前記制御回路は、前記遷移候補決定回路と、前記更新回路と、前記累積値計算回路と、前記判定回路に、前記複数のレプリカに対するパイプライン処理を行わせる、
請求項1に記載のデータ処理装置。
【請求項4】
前記判定回路は、前記第1の数より少ない第2の数の前記候補の値が変化した場合の前記変化量の前記累積値に基づいて、前記第2の数の前記候補の値の変化を受け入れるか否かを判定する、
請求項1に記載のデータ処理装置。
【請求項5】
前記遷移候補決定回路は、複数のモジュールに分かれており、前記複数のモジュールは、前記複数の状態変数のうち互いに異なる状態変数群の範囲内で、前記候補を1つずつn個決定し、
前記メモリは、前記複数の状態変数の値と、前記局所場の値と、前記所定の時点における前記複数の状態変数の値と、前記所定の時点における前記局所場の値によるセットを、前記複数のモジュールの数で分割して記憶し、
前記更新回路は、前記複数のモジュールのそれぞれに対応して記憶されている前記複数の状態変数の値と前記局所場の値とを、前記複数のモジュールのそれぞれが決定した前記候補にしたがって更新し、
前記累積値計算回路は、前記複数のモジュールのそれぞれに対して前記累積値を計算するとともに、前記複数のモジュールのそれぞれに対して計算した前記累積値のうちの1つを選択し、
前記判定回路は、選択された前記累積値に基づいて、選択された前記累積値に対応した前記第1の数の前記候補の値の変化を受け入れるか否かを判定する、
請求項1に記載のデータ処理装置。
【請求項6】
前記制御回路は、
前記判定回路が前記第1の数の前記候補の値の変化を受け入れると判定した場合、前記更新回路に、前記メモリに記憶されている前記複数のモジュールの前記複数の状態変数の値と前記局所場の値を、前記所定の時点における前記複数の状態変数の値と前記局所場の値に戻したのち、前記第1の数の前記候補にしたがって更新させ、
前記判定回路が前記第1の数の前記候補の値の変化を受け入れないと判定した場合、前記複数のモジュールの更新された前記複数の状態変数の値と更新された前記局所場の値を、前記所定の時点における前記複数の状態変数の値と前記局所場の値に戻す、
請求項5に記載のデータ処理装置。
【請求項7】
組合せ最適化問題の評価関数に含まれる複数の状態変数の値と、前記複数の状態変数のそれぞれにおける局所場の値と、所定の時点における前記複数の状態変数の値と、前記所定の時点における前記局所場の値と、をメモリに記憶し、
前記局所場の値に基づいて、前記複数の状態変数のそれぞれの値が変化したときの前記評価関数の値の変化量を計算するとともに、前記所定の時点から、前記複数の状態変数のうち値を変化させる候補を1つずつ決定し、
前記候補が決定されるたび、前記メモリに記憶されている前記候補の値と前記局所場の値を更新し、
前記候補の値を変化させたときの前記変化量の累積値を計算し、
前記累積値に基づいて、2以上の第1の数の前記候補の値の変化を受け入れるか否かを判定し、
前記第1の数の前記候補の値の変化を受け入れないと判定した場合、更新された前記複数の状態変数の値と更新された前記局所場の値を、前記所定の時点における前記複数の状態変数の値と前記局所場の値に戻す、
処理をコンピュータに実行させるプログラム。
【請求項8】
メモリが、組合せ最適化問題の評価関数に含まれる複数の状態変数の値と、前記複数の状態変数のそれぞれにおける局所場の値と、所定の時点における前記複数の状態変数の値と、前記所定の時点における前記局所場の値と、を記憶し、
遷移候補決定回路が、前記局所場の値に基づいて、前記複数の状態変数のそれぞれの値が変化したときの前記評価関数の値の変化量を計算するとともに、前記所定の時点から、前記複数の状態変数のうち値を変化させる候補を1つずつ決定し、
更新回路が、前記候補が決定されるたび、前記メモリに記憶されている前記候補の値と前記局所場の値を更新し、
累積値計算回路が、前記候補の値を変化させたときの前記変化量の累積値を計算し、
判定回路が、前記累積値に基づいて、2以上の第1の数の前記候補の値の変化を受け入れるか否かを判定し、
制御回路が、前記判定回路が前記第1の数の前記候補の値の変化を受け入れないと判定した場合、更新された前記複数の状態変数の値と更新された前記局所場の値を、前記所定の時点における前記複数の状態変数の値と前記局所場の値に戻す、
データ処理方法。

発明の詳細な説明【技術分野】
【0001】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示(約 1,800 文字)【背景技術】
【0002】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。そして、マルコフ連鎖モンテカルロ法により、イジング型の評価関数の値、つまりイジングモデルのエネルギーに相当する値が極小になるイジングモデルの状態の探索が行われる。評価関数の極小値のうちの最小値になる状態が最適解となる。イジング型の評価関数に含まれる状態変数は、0または1の値を取るバイナリ変数である。状態変数はビットと表記されてもよい。なお、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。
【0003】
以下、マルコフ連鎖モンテカルロ法を、MCMC(Markov-Chain Monte Carlo)法と略す。また、MCMC法による処理をMCMC処理と呼ぶ場合もある。MCMC処理では、たとえば、メトロポリス法またはギブス法で規定される状態遷移の受け入れ確率で、その状態遷移が受け入れられる。MCMC法の一種として、疑似焼き鈍し法やレプリカ交換法がある。
【0004】
従来、MCMC処理の1試行あたりに状態変数の変化(以下、遷移という)を許容するビット数を1とする処理(以下単一ビット遷移処理という)がある。しかし、単一ビット遷移処理では、解が局所解に嵌まった場合に、その局所解から脱出することが難しくなり、探索速度が低下する場合がある。
【0005】
そのため、複数ビットの遷移が生じる場合の評価関数の値の変化量の計算結果に基づいて、当該複数ビットの遷移の可否を判定し、遷移が許容された場合には複数ビットの遷移を生じさせる処理が提案されている(たとえば、特許文献1-4参照)。以下このような処理を複数ビット遷移処理という。複数ビット遷移処理によれば、解の局所解からの脱出が促進され、探索範囲を広げることができる。
【先行技術文献】
【特許文献】
【0006】
特開2020-021209号公報
特開2020-064536号公報
特開2021-157361号公報
特開2021-165965号公報
【発明の概要】
【発明が解決しようとする課題】
【0007】
従来の複数ビット遷移処理では、複数ビットの遷移が生じる場合の評価関数の値の変化量を計算するための構成やデータを伝搬する構成などが複雑となるため、実装が容易ではなかった。
【0008】
1つの側面では、本発明は、複数ビット遷移処理の実装が比較的容易に実現可能なデータ処理装置、プログラム及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【0009】
1つの実施態様では、組合せ最適化問題の評価関数に含まれる複数の状態変数の値と、前記複数の状態変数のそれぞれにおける局所場の値と、所定の時点における前記複数の状態変数の値と、前記所定の時点における前記局所場の値と、を記憶するメモリと、前記局所場の値に基づいて、前記複数の状態変数のそれぞれの値が変化したときの前記評価関数の値の変化量を計算するとともに、前記所定の時点から、前記複数の状態変数のうち値を変化させる候補を1つずつ決定する遷移候補決定回路と、前記候補が決定されるたび、前記メモリに記憶されている前記候補の値と前記局所場の値を更新する更新回路と、前記候補の値を変化させたときの前記変化量の累積値を計算する累積値計算回路と、前記累積値に基づいて、2以上の第1の数の前記候補の値の変化を受け入れるか否かを判定する判定回路と、前記判定回路が前記第1の数の前記候補の値の変化を受け入れないと判定した場合、更新された前記複数の状態変数の値と更新された前記局所場の値を、前記所定の時点における前記複数の状態変数の値と前記局所場の値に戻す制御回路と、を有するデータ処理装置が提供される。
【0010】
また、1つの実施態様では、プログラムが提供される。
また、1つの実施態様では、データ処理方法が提供される。
【発明の効果】
(【0011】以降は省略されています)

この特許をJ-PlatPatで参照する

関連特許

富士通株式会社
画像処理方法
1か月前
富士通株式会社
増幅装置及び増幅方法
1か月前
富士通株式会社
電子装置及び改竄検知方法
1か月前
富士通株式会社
演算回路及び演算処理方法
1か月前
富士通株式会社
情報処理装置及び情報処理方法
13日前
富士通株式会社
光通信装置および伝送制御方法
8日前
富士通株式会社
分散学習プログラム、方法、及び装置
22日前
富士通株式会社
表示制御方法及び表示制御プログラム
22日前
富士通株式会社
足位置の補正方法、装置及び記憶媒体
16日前
富士通株式会社
病変検出方法および病変検出プログラム
1か月前
富士通株式会社
情報処理プログラムおよび情報処理装置
28日前
富士通株式会社
情報処理方法および情報処理プログラム
1か月前
富士通株式会社
情報処理装置,プログラムおよび制御方法
13日前
富士通株式会社
スイッチング電源、増幅装置及び通信装置
1か月前
富士通株式会社
プログラム、算出方法および情報処理装置
29日前
富士通株式会社
働きかけ表示方法、働きかけ表示プログラム
1か月前
富士通株式会社
類似度判定方法および類似度判定プログラム
8日前
富士通株式会社
車両経路選択問題及びその変形例の経路生成
1か月前
富士通株式会社
制御方法、制御プログラムおよび情報処理装置
15日前
富士通株式会社
特定プログラム、特定方法および情報処理装置
13日前
富士通株式会社
データ処理装置、プログラム及びデータ処理方法
27日前
富士通株式会社
半導体装置、半導体装置の製造方法及び電子装置
9日前
富士通株式会社
署名支援プログラム、署名支援方法、署名支援装置
9日前
富士通株式会社
データ処理装置、データ処理方法およびプログラム
13日前
富士通株式会社
基地局装置、無線通信システム、及び通信制御方法
27日前
富士通株式会社
光ノード装置、光通信システム、及び波長変換回路
1か月前
富士通株式会社
グラフェン光素子及びグラフェン光素子の製造方法
23日前
富士通株式会社
プロセッサ、命令実行プログラムおよび情報処理装置
16日前
富士通株式会社
機械学習プログラム、機械学習方法及び機械学習装置
27日前
富士通株式会社
情報出力プログラム、情報出力方法及び情報処理装置
14日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
27日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
今日
富士通株式会社
構造解析プログラム、構造解析方法および情報処理装置
20日前
富士通株式会社
設計支援プログラム、設計支援方法および設計支援装置
21日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
14日前
富士通株式会社
情報処理プログラム、情報処理方法および情報処理装置
13日前
続きを見る