特許ウォッチ

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

発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。そして、マルコフ連鎖モンテカルロ法により、イジング型の評価関数の値（イジングモデルのエネルギーに相当する）が極小になるイジングモデルの状態の探索が行われる。評価関数の極小値のうちの最小値になる状態が最適解となる。なお、評価関数の符号を変えれば、評価関数の値が極大になる状態を探索することもできる。
【０００３】
以下、マルコフ連鎖モンテカルロ法を、ＭＣＭＣ（Markov-Chain Monte Carlo）法と略す。また、ＭＣＭＣ法による処理をＭＣＭＣ処理と呼ぶ場合もある。ＭＣＭＣ処理では、たとえば、メトロポリス法またはギブス法で規定される状態遷移の受け入れ確率で、その状態遷移が受け入れられる。ＭＣＭＣ法の一種として、疑似焼き鈍し法やレプリカ交換法がある。
【０００４】
なお、ＭＣＭＣ処理の各試行において状態遷移が棄却され続けると状態が遷移しなくなる。これを防止するため、試行ごとに異なる状態に遷移するサンプル列を発生させる手法が提案されている（たとえば、特許文献１、非特許文献１参照）。このような手法は、リジェクションフリー試行とも呼ばれる。
【０００５】
ところで、問題規模（状態変数の数（イジングモデルのスピン数に相当））が大きくなると、問題を定義する係数（各状態変数間の重み係数）の数が増大する。これにより、組合せ最適化問題を計算するデータ処理装置において、高速であるが比較的容量の小さいメモリ（たとえば、オンチップメモリ）に全ての重み係数を保持できなくなる場合がある。この場合、比較的容量の大きいメモリに重み係数が保持されることになるが、アクセスに時間がかかり、処理速度が大幅に制限される可能性がある。
【０００６】
そこで従来、重み係数がメモリに記憶可能なサイズになるように、組合せ最適化問題を複数の部分問題に分割し、部分問題ごとにリジェクションフリー試行による解探索を行う手法が提案されている（たとえば、非特許文献２参照）。部分問題の計算は、全状態変数を複数の状態変数群に分割し、各状態変数の範囲内で近傍状態（たとえば、ハミング距離が１ビットの状態）への状態遷移を発生させることで、解探索を行うものである。このため、部分問題の計算は、部分近傍探索とも呼ばれる。
【先行技術文献】
【特許文献】
【０００７】
特開２０２０－１３５７２７号公報
【非特許文献】
【０００８】
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
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、リジェクションフリー試行により部分近傍探索を行う場合、部分近傍（分割した各状態変数群）ごとに解の探索範囲に偏りが生じる可能性がある。この場合、効率的に解探索が行えなくなる可能性があった。
【００１０】
１つの側面では、本発明は、解探索を効率的に行えるデータ処理装置、プログラム及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
（【００１１】以降は省略されています）

関連特許