特許ウォッチ

公開番号2025034584
公報種別公開特許公報(A)
公開日2025-03-13
出願番号2023141060
出願日2023-08-31
発明の名称プログラム、データ処理方法およびデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250306BHJP(計算;計数)
要約【課題】求解性能を向上する。
【解決手段】処理部12は、複数の状態変数を含む評価関数に基づく解探索において、所定時間内に第1の状態が出現した回数が所定回数を超えると、第1の状態から複数の状態変数の何れかの状態変数の値を変化させた場合の評価関数の第1の値と第1の状態に対応する評価関数の第2の値との差に基づいて、第1の状態から値を変化させる状態変数の数を決定する。処理部12は、第1の状態における複数の状態変数のうちの、決定した数の状態変数の値を変化させた第2の状態を生成し、第2の状態を用いて解探索を継続する。
【選択図】図1
特許請求の範囲【請求項１】
コンピュータに、
複数の状態変数を含む評価関数に基づく解探索において、所定時間内に第１の状態が出現した回数が所定回数を超えると、前記第１の状態から前記複数の状態変数の何れかの状態変数の値を変化させた場合の前記評価関数の第１の値と前記第１の状態に対応する前記評価関数の第２の値との差に基づいて、前記第１の状態から値を変化させる前記状態変数の数を決定し、
前記第１の状態における前記複数の状態変数のうちの前記数の前記状態変数の値を変化させた第２の状態を生成し、
前記第２の状態を用いて前記解探索を継続する、
処理を実行させるプログラム。
続きを表示（約 1,300 文字）【請求項２】
前記数の決定では、前記差の統計値に基づいて、前記数を決定する、
請求項１記載のプログラム。
【請求項３】
前記統計値は、平均値、最大値および最小値の何れかである、
請求項２記載のプログラム。
【請求項４】
前記数の決定では、前記統計値を前記第２の値で割った第３の値と第１の閾値とを比較し、
前記第３の値が前記第１の閾値より小さい場合、前記数を第１の数とし、
前記第３の値が前記第１の閾値以上の場合、前記数を、前記第１の数よりも小さい第２の数とする、
請求項２記載のプログラム。
【請求項５】
前記第２の状態の生成では、値を変化させる前記状態変数を、ランダムに、または、前記第１の値に基づいて、選択する、
請求項１記載のプログラム。
【請求項６】
前記数の決定では、
前記差と乱数値と前記解探索に用いられる温度値とに基づいて、前記第１の状態から値を変化させる第１の状態変数を選択し、
選択した前記第１の状態変数の値を変化させた状態を新たな前記第１の状態とする場合の前記第１の値と前記第２の値との前記差に基づいて新たな前記第１の状態から他の状態への遷移確率の指標値を算出する、
処理を前記指標値が第２の閾値よりも大きくなるまで繰り返し実行する、
請求項１記載のプログラム。
【請求項７】
前記数の決定では、前記複数の状態変数の中から所定数の状態変数を選択し、前記所定数の状態変数の各々に対して、前記第１の状態から当該状態変数の値を変化させる場合の前記第１の値を計算する、
請求項１記載のプログラム。
【請求項８】
コンピュータが、
複数の状態変数を含む評価関数に基づく解探索において、所定時間内に第１の状態が出現した回数が所定回数を超えると、前記第１の状態から前記複数の状態変数の何れかの状態変数の値を変化させた場合の前記評価関数の第１の値と前記第１の状態に対応する前記評価関数の第２の値との差に基づいて、前記第１の状態から値を変化させる前記状態変数の数を決定し、
前記第１の状態における前記複数の状態変数のうちの前記数の前記状態変数の値を変化させた第２の状態を生成し、
前記第２の状態を用いて前記解探索を継続する、
データ処理方法。
【請求項９】
複数の状態変数の値を記憶する記憶部と、
前記複数の状態変数を含む評価関数に基づく解探索において、所定時間内に第１の状態が出現した回数が所定回数を超えると、前記第１の状態から前記複数の状態変数の何れかの状態変数の値を変化させた場合の前記評価関数の第１の値と前記第１の状態に対応する前記評価関数の第２の値との差に基づいて、前記第１の状態から値を変化させる前記状態変数の数を決定し、前記第１の状態における前記複数の状態変数のうちの前記数の前記状態変数の値を変化させた第２の状態を生成し、前記第２の状態を用いて前記解探索を継続する処理部と、
を有するデータ処理装置。

発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、データ処理方法およびデータ処理装置に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
組合せ最適化問題の求解に情報処理装置が用いられることがある。組合せ最適化問題は、磁性体のスピンの振る舞いを表すモデルであるイジングモデルのエネルギーを表す評価関数に変換される。情報処理装置は、評価関数に含まれる状態変数の値の組合せのうち、評価関数を最小化または最大化する組合せを探索する。評価関数を最小化または最大化する状態変数の値の組合せは、状態変数の組により表される基底状態または最適解に相当する。実用的な時間で組合せ最適化問題の近似解を得る手法には、マルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov-Chain Monte Carlo）法を基に、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法やレプリカ交換法などを組合せた手法がある。
【０００３】
例えば、インデックス順に状態変数を選択し、当該状態変数の値が変化する状態遷移を許容するかを判定するシーケンシャルＭＣＭＣを実行する情報処理装置の提案がある。提案の情報処理装置は、状態変数の値を変化させないと連続して判定された回数が所定回数に達すると、エネルギーの変化量をオフセット値により補正することで、遷移受入れ確率を大きくする。
【０００４】
また、状態遷移の否定を連続して特定回繰り返した場合、対応するエネルギー増分が小さい順に所定個選択された候補状態から１つの状態をランダムに選択し、選択した１つの状態へ現在の状態から遷移させる最適化装置の提案もある。
【０００５】
なお、ボルツマン分布をアニーリングして近似的にサンプリングする代わりに、準平衡モデルをアニーリングする変分ニューラルアニーリングと呼ばれる方法の提案がある。また、複雑な磁気システムの微視的な磁気構造をシミュレートし、それらの巨視的な物理的特性を調査するための量子モンテカルロシミュレーション方法の提案もある。
【先行技術文献】
【特許文献】
【０００６】
特開２０２２－１７４６１６号公報
特開２０２３－４９６３０号公報
米国特許出願公開第２０２２／０１９８２４６号明細書
米国特許出願公開第２０２１／０３４２５０５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＭＣＭＣ法に基づく解探索では、状態遷移が継続して採択されなかったり、特定の状態ばかりが採択されたりして、より良い解を得るまでに時間がかかることがある。
１つの側面では、本発明は、求解性能を向上することを目的とする。
【課題を解決するための手段】
【０００８】
１つの態様では、プログラムが提供される。このプログラムは、コンピュータに次の処理を実行させる。コンピュータは、複数の状態変数を含む評価関数に基づく解探索において、所定時間内に第１の状態が出現した回数が所定回数を超えると、第１の状態から複数の状態変数の何れかの状態変数の値を変化させた場合の評価関数の第１の値と第１の状態に対応する評価関数の第２の値との差に基づいて、第１の状態から値を変化させる状態変数の数を決定する。コンピュータは、第１の状態における複数の状態変数のうちの当該数の状態変数の値を変化させた第２の状態を生成する。コンピュータは、第２の状態を用いて解探索を継続する。
【０００９】
また、１つの態様では、データ処理方法が提供される。また、１つの態様では、記憶部と処理部とを有するデータ処理装置が提供される。
【発明の効果】
【００１０】
１つの側面では、求解性能を向上できる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許