特許ウォッチ

公開番号2025077388
公報種別公開特許公報(A)
公開日2025-05-19
出願番号2023189546
出願日2023-11-06
発明の名称プログラム、データ処理方法およびデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250512BHJP(計算;計数)
要約【課題】求解性能を向上する。
【解決手段】処理部12は、温度値T(1)～T(m)に対応するレプリカR(1)～R(m)を用いて行われる解探索において、レプリカR(k)で所定時間内に状態s1が出現した回数が所定回数を超えると、レプリカR(k)に対応する温度値T(k)との温度値の差が小さいものを優先して所定数のレプリカを選択する。処理部12は、所定数のレプリカの各々において解探索により取得された状態に基づいて、状態s1との比較対象とする状態s2を取得する。処理部12は、状態s1に対応する評価関数の値H(s1)と状態s2に対応する評価関数の値H(s2)との比較に応じて、状態s1における複数の状態変数のうち、値を変化させる状態変数の数を決定する。処理部12は、状態s1のうちの当該数の状態変数の値を変化させた第3の状態を生成する。処理部12は、第3の状態を用いてレプリカR(k)における解探索を継続する。
【選択図】図1
特許請求の範囲【請求項１】
コンピュータに、
複数の状態変数を含む評価関数に基づく解探索であって、各々が複数の状態変数の値を示しており、複数の温度値に対応する複数のレプリカを用いて行われる前記解探索において、前記複数のレプリカのうちの第１のレプリカで所定時間内に前記複数の状態変数の値により示される第１の状態が出現した回数が所定回数を超えると、前記第１のレプリカに対応する第１の温度値との温度値の差が小さいものを優先して所定数のレプリカを前記複数のレプリカから選択し、
前記所定数のレプリカの各々において前記解探索により取得された状態に基づいて、前記第１の状態との比較対象とする第２の状態を取得し、
前記第１の状態に対応する前記評価関数の第１の値と前記第２の状態に対応する前記評価関数の第２の値との比較に応じて、前記第１の状態における前記複数の状態変数のうち、値を変化させる前記状態変数の数を決定し、
前記第１の状態における前記複数の状態変数のうちの前記数の前記状態変数の値を変化させた第３の状態を生成し、
前記第３の状態を用いて前記第１のレプリカにおける前記解探索を継続する、
処理を実行させるプログラム。
続きを表示（約 1,700 文字）【請求項２】
前記第２の状態の取得では、前記所定数のレプリカの各々における現在の前記状態のうち、前記評価関数の値が最小である前記状態を、前記第２の状態として取得する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項３】
前記第２の状態の取得では、前記所定数のレプリカの各々において前記解探索で得られた前記状態のうち、前記評価関数の値が最小である前記状態を、前記第２の状態として取得する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項４】
前記第２の状態の取得では、前記所定数のレプリカの各々における現在の前記状態に含まれる、同じインデックスに対応する前記状態変数の値の多数決により、前記第２の状態に含まれる、前記インデックスに対応する前記状態変数の値を決定する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項５】
前記数の決定では、
前記第１の値が前記第２の値よりも小さい場合、前記数を第１の数とし、
前記第１の値が前記第２の値以上の場合、前記数を、前記第１の数よりも小さい第２の数とする、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項６】
前記数の決定では、
前記第１の状態において前記第２の状態とは値が異なる前記状態変数の第３の数を取得し、
前記第１の値が前記第２の値以上の場合、前記第３の数に基づいて前記数を決定し、
前記第１の値が前記第２の値よりも小さい場合、前記数を所定値とする、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項７】
前記第３の数に基づく前記数の決定では、
前記第３の数が前記複数の状態変数の個数の半数以上の場合、前記数を前記複数の状態変数の個数の半数とし、
前記第３の数が前記複数の状態変数の個数の半数未満の場合、前記数を前記第３の数とする、
処理を前記コンピュータに実行させる請求項６記載のプログラム。
【請求項８】
前記第３の状態の生成では、前記第１の状態において前記第２の状態とは値が異なる前記状態変数を、決定した前記数だけ選択し、前記第１の状態における前記複数の状態変数のうち、選択した前記数の前記状態変数の値を変化させる、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項９】
前記数の前記状態変数の選択では、前記第１の状態における前記複数の状態変数から前記数の前記状態変数を、ランダムに、または、前記状態変数のインデックスに基づいて選択する、
処理を前記コンピュータに実行させる請求項８記載のプログラム。
【請求項１０】
コンピュータが、
複数の状態変数を含む評価関数に基づく解探索であって、各々が複数の状態変数の値を示しており、複数の温度値に対応する複数のレプリカを用いて行われる前記解探索において、前記複数のレプリカのうちの第１のレプリカで所定時間内に前記複数の状態変数の値により示される第１の状態が出現した回数が所定回数を超えると、前記第１のレプリカに対応する第１の温度値との温度値の差が小さいものを優先して所定数のレプリカを前記複数のレプリカから選択し、
前記所定数のレプリカの各々において前記解探索により取得された状態に基づいて、前記第１の状態との比較対象とする第２の状態を取得し、
前記第１の状態に対応する前記評価関数の第１の値と前記第２の状態に対応する前記評価関数の第２の値との比較に応じて、前記第１の状態における前記複数の状態変数のうち、値を変化させる前記状態変数の数を決定し、
前記第１の状態における前記複数の状態変数のうちの前記数の前記状態変数の値を変化させた第３の状態を生成し、
前記第３の状態を用いて前記第１のレプリカにおける前記解探索を継続する、
データ処理方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、データ処理方法およびデータ処理装置に関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
組合せ最適化問題の求解に情報処理装置が用いられることがある。組合せ最適化問題は、磁性体のスピンの振る舞いを表すモデルであるイジングモデルのエネルギーを表す評価関数に変換される。情報処理装置は、評価関数に含まれる状態変数の値の組合せのうち、評価関数を最小化または最大化する組合せを探索する。評価関数を最小化または最大化する状態変数の値の組合せは、状態変数の組により表される基底状態または最適解に相当する。実用的な時間で組合せ最適化問題の近似解を得る手法には、マルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov-Chain Monte Carlo）法を基に、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法やレプリカ交換法などを組合せた手法がある。
【０００３】
例えば、求解対象の問題の状態変数のコピーである複数のレプリカを用いて、レプリカ交換法による解探索を行う最適化装置の提案がある。
また、ボルツマンマシンの複数のレプリカを用いて、ポピュレーションアニーリング法により大規模な組合せ最適化問題の解を探索する装置の提案がある。
【０００４】
なお、量子アニーリングまたは断熱量子計算を実行する量子プロセッサおよびデジタルプロセッサを含むハイブリッドコンピューティングシステムにより目的関数に変換された問題に対する解を得る方法の提案もある。また、量子アニーリングを用いて、作業者や物と関連付けて定義されるタスクやジョブを実行可能な適切なスケジュールを特定する装置の提案もある。
【先行技術文献】
【特許文献】
【０００５】
特開２０２２－５２２２２号公報
特開２０２３－５６４７１号公報
米国特許出願公開第２０１７／０１１６１５９号明細書
米国特許出願公開第２０１７／００８３８７３号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＭＣＭＣ法に基づく解探索では、状態遷移が継続して採択されなかったり、特定の状態ばかりが採択されたりして、より良い解を得るまでに時間がかかることがある。
１つの側面では、本発明は、求解性能を向上することを目的とする。
【課題を解決するための手段】
【０００７】
１つの態様では、プログラムが提供される。このプログラムは、コンピュータに次の処理を実行させる。コンピュータは、複数の状態変数を含む評価関数に基づく解探索であって、各々が複数の状態変数の値を示しており、複数の温度値に対応する複数のレプリカを用いて行われる解探索において、複数のレプリカのうちの第１のレプリカで所定時間内に複数の状態変数の値により示される第１の状態が出現した回数が所定回数を超えると、第１のレプリカに対応する第１の温度値との温度値の差が小さいものを優先して所定数のレプリカを複数のレプリカから選択する。コンピュータは、所定数のレプリカの各々において解探索により取得された状態に基づいて、第１の状態との比較対象とする第２の状態を取得する。コンピュータは、第１の状態に対応する評価関数の第１の値と第２の状態に対応する評価関数の第２の値との比較に応じて、第１の状態における複数の状態変数のうち、値を変化させる状態変数の数を決定する。コンピュータは、第１の状態における複数の状態変数のうちの当該数の状態変数の値を変化させた第３の状態を生成する。コンピュータは、第３の状態を用いて第１のレプリカにおける解探索を継続する。
【０００８】
また、１つの態様では、コンピュータにより実行されるデータ処理方法が提供される。また、１つの態様では、記憶部と処理部とを有するデータ処理装置が提供される。
【発明の効果】
【０００９】
１つの側面では、求解性能を向上できる。
【図面の簡単な説明】
【００１０】
第１の実施の形態のデータ処理装置を説明する図である。
第２の実施の形態のデータ処理装置のハードウェア例を示す図である。
状態とエネルギーとの関係の例を示す図である。
データ処理装置の機能例を示す図である。
レプリカ処理部の機能例を示す図である。
レプリカ処理部の解探索例を示すフローチャートである。
交換制御例を示すフローチャートである。
リファレンスの第１の決定例を示すフローチャートである。
リファレンスの第２の決定例を示すフローチャートである。
リファレンスの第３の決定例を示すフローチャートである。
多数決によるリファレンスの状態の生成例を示す図である。
遷移先の候補状態の生成例を示す図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許