TOP特許意匠商標
特許ウォッチ Twitter
10個以上の画像は省略されています。
公開番号2024049202
公報種別公開特許公報(A)
公開日2024-04-09
出願番号2022155524
出願日2022-09-28
発明の名称データ処理装置、プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20240402BHJP(計算;計数)
要約【課題】解探索を効率的に行う。
【解決手段】第2記憶部12は、複数の重み係数のうち、評価関数に含まれる複数の状態変数を分割した複数の状態変数群から選択された状態変数群に関する、重み係数群の値を記憶する。探索部13は、第2記憶部12から読み出した重み係数群の値を用いて、状態変数群の各状態変数の値を変化させたときの評価関数の値の変化量を計算する処理と、変化量と温度値に基づいて、状態変数群の何れかの状態変数の値を変化させる処理を含む更新処理を繰り返すことで、組合せ最適化問題の解を探索する。処理部14は、MCMC法を用いて解の探索を行う場合に、状態変数群の値が維持される試行回数である多重度を、上記変化量と温度値に基づいて計算し、多重度の積算値が所定の閾値を超えた場合、他の状態変数群に関する重み係数群の値を用いた上記更新処理を、探索部13に実行させる。
【選択図】図1
特許請求の範囲【請求項1】
組合せ最適化問題を変換した評価関数に含まれる複数の重み係数の値を記憶する第1記憶部と、
前記複数の重み係数のうち、前記評価関数に含まれる複数の状態変数を分割した複数の状態変数群から選択された状態変数群に関する、重み係数群の値を記憶する第2記憶部と、
前記第2記憶部から読み出した前記重み係数群の値を用いて、前記状態変数群の各状態変数の値を変化させたときの前記評価関数の値の変化量を計算する処理と、前記変化量と温度値に基づいて、前記状態変数群の何れかの状態変数の値を変化させる処理とを含む更新処理を繰り返すことで、前記組合せ最適化問題の解を探索する探索部と、
マルコフ連鎖モンテカルロ法を用いて前記解の探索を行う場合に、前記状態変数群の値が維持される試行回数である多重度を、前記変化量と前記温度値に基づいて計算し、前記多重度の積算値が所定の閾値を超えた場合、前記複数の状態変数群から選択した他の状態変数群に関する前記重み係数群の値を用いた前記更新処理を、前記探索部に実行させる処理部と、
を有するデータ処理装置。
続きを表示(約 1,400 文字)【請求項2】
前記探索部は、前記更新処理ごとの前記複数の状態変数の値を出力し、前記処理部は、前記複数の状態変数の値ごとの前記多重度を出力する、請求項1に記載のデータ処理装置。
【請求項3】
前記処理部は、
前記変化量と前記温度値に基づいて、前記状態変数群の各状態変数について、値の変化を受け入れる確率を計算し、
前記確率の総和を、前記状態変数群に含まれる状態変数の数で割ることで脱出確率を計算し、
前記脱出確率と乱数値に基づいて前記多重度を計算する、
請求項1に記載のデータ処理装置。
【請求項4】
前記処理部は、シフト演算により前記確率を計算する請求項3に記載のデータ処理装置。
【請求項5】
前記第2記憶部は、第1記憶領域及び第2記憶領域を有し、
前記第1記憶領域に記憶されている前記重み係数群の値を用いて、前記探索部が前記更新処理を行っている間に、前記他の状態変数群に関する前記重み係数群の値が前記第1記憶部から読み出されて、前記第2記憶領域に書き込まれる、
請求項1に記載のデータ処理装置。
【請求項6】
組合せ最適化問題を変換した評価関数に含まれる複数の重み係数の値を第1記憶部に記憶し、
前記複数の重み係数のうち、前記評価関数に含まれる複数の状態変数を分割した複数の状態変数群から選択された状態変数群に関する、重み係数群の値を第2記憶部に記憶し、
前記第2記憶部から読み出した前記重み係数群の値を用いて、前記状態変数群の各状態変数の値を変化させたときの前記評価関数の値の変化量を計算する処理と、前記変化量と温度値に基づいて、前記状態変数群の何れかの状態変数の値を変化させる処理とを含む更新処理を繰り返すことで、前記組合せ最適化問題の解を探索し、
マルコフ連鎖モンテカルロ法を用いて前記解の探索を行う場合に、前記状態変数群の値が維持される試行回数である多重度を、前記変化量と前記温度値に基づいて計算し、
前記多重度の積算値が所定の閾値を超えた場合、前記複数の状態変数群から選択した他の状態変数群に関する前記重み係数群の値を用いた前記更新処理を実行する、
処理をコンピュータに実行させるプログラム。
【請求項7】
第1記憶部が、組合せ最適化問題を変換した評価関数に含まれる複数の重み係数の値を記憶し、
第2記憶部が、前記複数の重み係数のうち、前記評価関数に含まれる複数の状態変数を分割した複数の状態変数群から選択された状態変数群に関する、重み係数群の値を記憶し、
探索部が、前記第2記憶部から読み出した前記重み係数群の値を用いて、前記状態変数群の各状態変数の値を変化させたときの前記評価関数の値の変化量を計算する処理と、前記変化量と温度値に基づいて、前記状態変数群の何れかの状態変数の値を変化させる処理とを含む更新処理を繰り返すことで、前記組合せ最適化問題の解を探索し、
処理部が、マルコフ連鎖モンテカルロ法を用いて前記解の探索を行う場合に、前記状態変数群の値が維持される試行回数である多重度を、前記変化量と前記温度値に基づいて計算し、前記多重度の積算値が所定の閾値を超えた場合、前記複数の状態変数群から選択した他の状態変数群に関する前記重み係数群の値を用いた前記更新処理を、前記探索部に実行させる、
データ処理方法。

発明の詳細な説明【技術分野】
【0001】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示(約 1,600 文字)【背景技術】
【0002】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。そして、マルコフ連鎖モンテカルロ法により、イジング型の評価関数の値(イジングモデルのエネルギーに相当する)が極小になるイジングモデルの状態の探索が行われる。評価関数の極小値のうちの最小値になる状態が最適解となる。なお、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。
【0003】
以下、マルコフ連鎖モンテカルロ法を、MCMC(Markov-Chain Monte Carlo)法と略す。また、MCMC法による処理をMCMC処理と呼ぶ場合もある。MCMC処理では、たとえば、メトロポリス法またはギブス法で規定される状態遷移の受け入れ確率で、その状態遷移が受け入れられる。MCMC法の一種として、疑似焼き鈍し法やレプリカ交換法がある。
【0004】
なお、MCMC処理の各試行において状態遷移が棄却され続けると状態が遷移しなくなる。これを防止するため、試行ごとに異なる状態に遷移するサンプル列を発生させる手法が提案されている(たとえば、特許文献1、非特許文献1参照)。このような手法は、リジェクションフリー試行とも呼ばれる。
【0005】
ところで、問題規模(状態変数の数(イジングモデルのスピン数に相当))が大きくなると、問題を定義する係数(各状態変数間の重み係数)の数が増大する。これにより、組合せ最適化問題を計算するデータ処理装置において、高速であるが比較的容量の小さいメモリ(たとえば、オンチップメモリ)に全ての重み係数を保持できなくなる場合がある。この場合、比較的容量の大きいメモリに重み係数が保持されることになるが、アクセスに時間がかかり、処理速度が大幅に制限される可能性がある。
【0006】
そこで従来、重み係数がメモリに記憶可能なサイズになるように、組合せ最適化問題を複数の部分問題に分割し、部分問題ごとにリジェクションフリー試行による解探索を行う手法が提案されている(たとえば、非特許文献2参照)。部分問題の計算は、全状態変数を複数の状態変数群に分割し、各状態変数の範囲内で近傍状態(たとえば、ハミング距離が1ビットの状態)への状態遷移を発生させることで、解探索を行うものである。このため、部分問題の計算は、部分近傍探索とも呼ばれる。
【先行技術文献】
【特許文献】
【0007】
特開2020-135727号公報
【非特許文献】
【0008】
J.S. Rosenthal, “Jump Markov Chains and Rejection-Free Metropolis Algorithms”, Computational Statistics 36.4, pp.2789-2811, 2021
Sigeng Chen et al, “Optimization via Rejection-Free Partial Neighbor Search”, arXiv:2205.02083, Apr. 15, 2022
【発明の概要】
【発明が解決しようとする課題】
【0009】
しかし、リジェクションフリー試行により部分近傍探索を行う場合、部分近傍(分割した各状態変数群)ごとに解の探索範囲に偏りが生じる可能性がある。この場合、効率的に解探索が行えなくなる可能性があった。
【0010】
1つの側面では、本発明は、解探索を効率的に行えるデータ処理装置、プログラム及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
(【0011】以降は省略されています)

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

関連特許

富士通株式会社
光送信機
26日前
富士通株式会社
光受信装置
1か月前
富士通株式会社
プロセッサ
1か月前
富士通株式会社
光送信装置
1か月前
富士通株式会社
アバター制御
3日前
富士通株式会社
ドハティ増幅装置
1か月前
富士通株式会社
キャッシュメモリ
10日前
富士通株式会社
受光素子及び赤外線撮像装置
19日前
富士通株式会社
光リンク電力プロファイル推定
26日前
富士通株式会社
生成プログラムおよび生成方法
9日前
富士通株式会社
演算処理装置および演算処理方法
1か月前
富士通株式会社
光送信機、及びバイアス制御方法
1か月前
富士通株式会社
情報処理装置および情報処理方法
6日前
富士通株式会社
光伝送システムでの異常の位置特定
2日前
富士通株式会社
業務管理プログラム、装置、及び方法
12日前
富士通株式会社
プログラム,方法,及び情報処理装置
1か月前
富士通株式会社
評価プログラム、評価方法、評価装置
1か月前
富士通株式会社
制御プログラム、制御方法及び制御装置
1か月前
富士通株式会社
性能監視プログラムおよび性能監視方法
26日前
富士通株式会社
機械学習プログラムおよび機械学習方法
26日前
富士通株式会社
優先度決定方法及び優先度決定プログラム
1か月前
富士通株式会社
検出プログラム,検出方法および検出装置
1か月前
富士通株式会社
3次元人体動的着装モデル推定装置及び方法
3日前
富士通株式会社
制御プログラム,制御方法及び情報処理装置
10日前
富士通株式会社
予測プログラム、情報処理装置および予測方法
9日前
富士通株式会社
出力プログラム、出力方法および情報処理装置
16日前
富士通株式会社
探索プログラム、探索システム、及び探索方法
9日前
富士通株式会社
抽出プログラム、抽出方法および情報処理装置
1か月前
富士通株式会社
光伝送システム、波長変換器、及び光伝送装置
1か月前
富士通株式会社
生成プログラム、生成方法および情報処理装置
9日前
富士通株式会社
生成プログラム、生成方法および情報処理装置
9日前
富士通株式会社
光伝送システム、光伝送装置および光伝送方法
1か月前
富士通株式会社
制御方法、制御プログラム、および情報処理装置
1か月前
富士通株式会社
指標項目特定方法および指標項目特定プログラム
1か月前
富士通株式会社
判定プログラム、判定方法、および情報処理装置
1か月前
富士通株式会社
データ処理装置、プログラム及びデータ処理方法
1か月前
続きを見る