特許ウォッチ

公開番号2025039876
公報種別公開特許公報(A)
公開日2025-03-21
出願番号2025006641,2021080535
出願日2025-01-17,2021-05-11
発明の名称プログラム、情報処理方法および情報処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250313BHJP(計算;計数)
要約【課題】解探索を効率化する。
【解決手段】処理部12は、複数の状態変数のうちの一部である変化候補の状態変数を所定の順序で選択し、選択した変化候補の状態変数の値の変化に対応する、エネルギー関数の値の変化量に基づいて、変化候補の状態変数の値を変化させるか否かを判定する。処理部12は、変化候補の状態変数の値を変化させると判定した場合、変化候補の状態変数の値を変化させる。処理部12は、変化候補の状態変数の値を変化させないと連続して判定した回数をカウントし、当該回数が所定回数に達すると、エネルギー関数の値の変化量と乱数値とに応じて計算される確率キー値に基づいて複数の状態変数から第1の状態変数を選択し、第1の状態変数の値を変化させる。
【選択図】図1
特許請求の範囲【請求項１】
複数の状態変数を含むエネルギー関数で表される問題の解を探索する探索処理をコンピュータに実行させるプログラムであって、前記探索処理は、
前記複数の状態変数のうちの一部である変化候補の状態変数を所定の順序で選択する選択処理と、
前記選択処理において選択された前記変化候補の状態変数の値の変化に対応する、前記エネルギー関数の値の変化量に基づいて、前記変化候補の状態変数の値を変化させるか否かを判定する判定処理と、
前記判定処理において、前記変化候補の状態変数の値を変化させると判定された場合、前記変化候補の状態変数の値を変化させる状態変更処理と
を有し、
前記探索処理において、前記プログラムは前記コンピュータに、前記選択処理と前記判定処理と前記状態変更処理を、前記所定の順序に沿って繰り返し実行させ、
前記探索処理は更に、
繰り返し実行される前記探索処理において前記変化候補の状態変数の値を連続して変化させないと判定された回数をカウントするカウント処理を有し、
前記カウント処理においてカウントされた前記回数が所定回数に達すると、前記変化量と乱数値とに応じて計算される確率キー値に基づいて前記複数の状態変数から第１の状態変数を選択し、前記第１の状態変数の値を変化させる、
処理を前記コンピュータに実行させるプログラム。
続きを表示（約 1,600 文字）【請求項２】
前記回数が前記所定回数に達する間に、各々の前記変化候補の状態変数に対して得られた前記変化量と前記乱数値とに応じた前記確率キー値を計算し、
計算した前記確率キー値のうちの最小値または最大値に対応する前記変化候補の状態変数を、前記第１の状態変数とする、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項３】
前記変化量と前記乱数値と前記解の探索に用いられる温度値とに基づいて前記確率キー値を計算する処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項４】
前記所定の順序による前記変化候補の状態変数の一巡の選択に要する選択回数を、前記所定回数とする処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項５】
前記変化候補の状態変数の数を変化させるか否かの一回の判定に対して選択する前記変化候補の状態変数の数を、１つまたは複数とする処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項６】
複数の状態変数を含むエネルギー関数で表される問題の解を探索する探索処理を実行する情報処理装置が実行する情報処理方法であって、前記探索処理は、
前記複数の状態変数のうちの一部である変化候補の状態変数を所定の順序で選択する選択処理と、
前記選択処理において選択された前記変化候補の状態変数の値の変化に対応する、前記エネルギー関数の値の変化量に基づいて、前記変化候補の状態変数の値を変化させるか否かを判定する判定処理と、
前記判定処理において、前記変化候補の状態変数の値を変化させると判定された場合、前記変化候補の状態変数の値を変化させる状態変更処理と
を有し、
前記探索処理において、前記情報処理装置が、前記選択処理と前記判定処理と前記状態変更処理を、前記所定の順序に沿って繰り返し実行し、
前記情報処理装置が更に、
繰り返し実行される前記探索処理において前記変化候補の状態変数の値を連続して変化させないと判定された回数をカウントするカウント処理を実行し、
前記カウント処理においてカウントされた前記回数が所定回数に達すると、前記変化量と乱数値とに応じて計算される確率キー値に基づいて前記複数の状態変数から第１の状態変数を選択し、前記第１の状態変数の値を変化させる、
情報処理方法。
【請求項７】
複数の状態変数を含むエネルギー関数で表される問題の解を探索する探索処理を実行する情報処理装置であって、
前記複数の状態変数の値を記憶する記憶部と、
前記探索処理を実行する処理部とを有し、
前記探索処理は、
前記複数の状態変数のうちの一部である変化候補の状態変数を所定の順序で選択する選択処理と、
前記選択処理において選択された前記変化候補の状態変数の値の変化に対応する、前記エネルギー関数の値の変化量に基づいて、前記変化候補の状態変数の値を変化させるか否かを判定する判定処理と、
前記判定処理において、前記変化候補の状態変数の値を変化させると判定された場合、前記変化候補の状態変数の値を変化させる状態変更処理と
を有し、
前記探索処理において、前記処理部は、前記選択処理と前記判定処理と前記状態変更処理を、前記所定の順序に沿って繰り返し実行し、
前記処理部は更に、
繰り返し実行される前記探索処理において前記変化候補の状態変数の値を連続して変化させないと判定された回数をカウントするカウント処理を実行し、
前記カウント処理においてカウントされた前記回数が所定回数に達すると、前記変化量と乱数値とに応じて計算される確率キー値に基づいて前記複数の状態変数から第１の状態変数を選択し、前記第１の状態変数の値を変化させる、
情報処理装置。

発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、情報処理方法および情報処理装置に関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
組合せ最適化問題の求解に情報処理装置が用いられることがある。情報処理装置は、組合せ最適化問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルのエネルギー関数に変換し、エネルギー関数に含まれる状態変数の値の組合せのうち、エネルギー関数を最小化または最大化する組合せを探索する。エネルギー関数を最小化または最大化する状態変数の値の組合せは、状態変数の組により表される基底状態または最適解に相当する。実用的な時間で組合せ最適化問題の近似解を得る手法には、マルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov-Chain Monte Carlo）法を基に、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法やレプリカ交換法などを組み合わせた手法がある。
【０００３】
例えばＭＣＭＣ法を実行する装置には、インデックス順（シーケンシャル）に状態変数を選択し、当該状態変数の値が変化する状態遷移を許容するかを判定するものや、複数の状態遷移を同時に遷移候補として１つの状態遷移を選択する並列探索を行うものがある。
【先行技術文献】
【特許文献】
【０００４】
特開２０２０－１３５７２７号公報
米国特許出願公開第２０１４／０２７９８１６号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のように、エネルギー関数で表される問題に対する求解において、状態変数のインデックスなどの所定の順序で状態変数を選択し、当該状態変数に係る状態遷移を許容するかを判定することが考えられる。この方法では、例えば複数の状態変数を一巡して何れの状態遷移も許容されない場合には次の一巡の判定を開始するというように、状態遷移が行われるまで、各状態変数に対する判定を繰り返し行うことになる。しかし、状態遷移が行われないまま当該繰り返しの回数が増すほど、求解に要する時間が増える。
【０００６】
１つの側面では、本発明は、解探索を効率化するプログラム、情報処理方法および情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
１つの態様では、複数の状態変数を含むエネルギー関数で表される問題の解を探索する探索処理をコンピュータに実行させるプログラムが提供される。探索処理は、複数の状態変数のうちの一部である変化候補の状態変数を所定の順序で選択する選択処理と、選択処理において選択された変化候補の状態変数の値の変化に対応する、エネルギー関数の値の変化量に基づいて、変化候補の状態変数の値を変化させるか否かを判定する判定処理と、判定処理において、変化候補の状態変数の値を変化させると判定された場合、変化候補の状態変数の値を変化させる状態変更処理とを有する。探索処理において、プログラムはコンピュータに、選択処理と判定処理と状態変更処理を、所定の順序に沿って繰り返し実行させる。探索処理は更に、繰り返し実行される探索処理において変化候補の状態変数の値を連続して変化させないと判定された回数をカウントするカウント処理を有する。プログラムは、カウント処理においてカウントされた回数が所定回数に達すると、変化量と乱数値とに応じて計算される確率キー値に基づいて複数の状態変数から第１の状態変数を選択し、第１の状態変数の値を変化させる、処理をコンピュータに実行させる。
【０００８】
また、１つの態様では、情報処理方法が提供される。
また、１つの態様では、情報処理装置が提供される。
【発明の効果】
【０００９】
１つの側面では、解探索を効率化できる。
【図面の簡単な説明】
【００１０】
第１の実施の形態の情報処理装置を説明する図である。
第２の実施の形態の情報処理装置を説明する図である。
第３の実施の形態の情報処理装置のハードウェア例を示す図である。
情報処理装置の機能例を示す図である。
レプリカ更新部の機能例を示す図である。
情報処理装置の処理例を示すフローチャートである。
求解結果の例（その１）を示す図である。
求解結果の例（その２）を示す図である。
第４の実施の形態のレプリカ更新部の機能例を示す図である。
情報処理装置の処理例を示すフローチャートである。
比較例を示すフローチャートである。
第５の実施の形態の情報処理装置の機能例を示す図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許