特許ウォッチ

公開番号2025001157
公報種別公開特許公報(A)
公開日2025-01-08
出願番号2023100596
出願日2023-06-20
発明の名称プログラム、データ処理方法およびデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20241225BHJP(計算;計数)
要約【課題】パラメータ値に対する評価を効率的に行う。
【解決手段】処理部12は、評価関数に基づいて、第1パラメータ値を用いた解探索が実行されると、評価関数により計算される評価関数の値の第1指標値と、解探索の期間の開始時点よりも後の時点から当該期間の終了時点までの第1期間で得られた評価関数の値の第2指標値とに基づいて、第1指標値と第2指標値との差の度合いを示す変化率を計算する。処理部12は、当該評価関数で表される問題に対する第1パラメータ値による求解性能を、変化率に基づいて評価する。
【選択図】図1
特許請求の範囲【請求項１】
コンピュータに、
評価関数に基づいて、第１パラメータ値を用いた解探索が実行されると、前記評価関数により計算される前記評価関数の値の第１指標値と、前記解探索の期間の開始時点よりも後の時点から前記期間の終了時点までの第１期間で得られた前記評価関数の値の第２指標値とに基づいて、前記第１指標値と前記第２指標値との差の度合いを示す変化率を計算し、
前記評価関数で表される問題に対する前記第１パラメータ値による求解性能を、前記変化率に基づいて評価する、
処理を実行させるプログラム。
続きを表示（約 1,000 文字）【請求項２】
前記評価関数はイジングモデルのエネルギー関数である請求項１記載のプログラム。
【請求項３】
前記変化率の計算では、前記第１指標値と前記第２指標値との差を前記第１指標値で割ることで前記変化率を計算する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項４】
前記第１期間で得られた前記評価関数の値の中央値を前記第２指標値として取得する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項５】
前記開始時点を起点とする、前記第１期間よりも前の第２期間で得られた前記評価関数の値の中央値を、前記第１指標値として取得する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項６】
前記第１指標値は、前記解探索における初期解に対応する前記評価関数の値である、
請求項１記載のプログラム。
【請求項７】
前記第１指標値は、前記評価関数に対して予め計算される、所定解に対応する前記評価関数の値である、
請求項１記載のプログラム。
【請求項８】
前記求解性能の評価では、前記変化率を所定の基準値と比較し、前記変化率が前記基準値未満の場合に前記求解性能が十分でないと判定し、前記変化率が前記基準値以上の場合に前記求解性能が十分であると判定する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項９】
前記第１パラメータ値は、複数の問題に対して汎用的に用いられる汎用パラメータ値であり、
前記求解性能が十分でない場合、前記問題に特化した第２パラメータ値の取得を行うと判定し、前記求解性能が十分である場合、前記第２パラメータ値の取得を行わないと判定する、
処理を前記コンピュータに実行させる請求項８記載のプログラム。
【請求項１０】
複数の学習問題それぞれに対して、前記第１パラメータ値の取得のために行われた前記解探索により得られた前記評価関数の値の履歴を取得し、取得した前記評価関数の値の履歴に基づいて前記基準値を算出する、
処理を前記コンピュータに実行させる請求項９記載のプログラム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、データ処理方法およびデータ処理装置に関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
評価関数を用いた組合せ最適化問題の求解の一例としてイジングマシンが用いられることがある。組合せ最適化問題は、磁性体のスピンの振る舞いを表すモデルであるイジングモデルのエネルギー関数に変換される。イジングマシンは、エネルギー関数に含まれる状態変数の値の組合せのうち、例えばエネルギー関数の値を最小化する組合せを探索する。この場合、エネルギー関数の値を最小化する状態変数の値の組合せは、基底状態または最適解に相当する。
【０００３】
実用的な時間で組合せ最適化問題の近似解を得る手法には、例えばシミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）、シミュレーテッド量子アニーリング（ＳＱＡ：Simulated Quantum Annealing）法、タブーサーチ法などがある。これらの各手法では解探索の実行に所定のパラメータが用いられる。
【０００４】
例えば、ＳＡ法において温度パラメータの値を徐々に小さくしながら基底状態の探索を行う最適化装置の提案がある。
また、熱ノイズ（温度）の初期値、熱ノイズ（温度）の減衰率を含む入力パラメータを用いて、ＳＡ法による解探索を実行する最適化装置の提案がある。
【０００５】
また、問題の解空間を探索するヒューリスティックアルゴリズムを実行するソルバに対して探索期間、範囲および開始点を含むパラメータのセットを問題の特徴に基づいて生成するコンピューティングシステムの提案がある。
【０００６】
更に、量子アニーリングを行う場合に、機械学習技術を用いて問題に対するアニーリングパラメータのセットを決定するコンピュータシステムの提案がある。
なお、イジングモデルに変換した組合せ最適化問題の仮最適解を用いてシミュレーションを行い、その結果に基づいた制約項を加えてイジングモデルを更新し、仮最適解の探索を繰り返す最適化装置の提案がある。
【先行技術文献】
【特許文献】
【０００７】
特開２０２０－１９４２７３号公報
特開２０２１－４３７８７号公報
米国特許出願公開第２０１１／００６０７１０号明細書
米国特許出願公開第２０２１／０２４１１４３号明細書
米国特許出願公開第２０２０／０３８００６５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
組合せ最適化問題の求解では、該当の問題に対して、求解に使用されるパラメータ値を適切に定めることが重要となる。そこで、該当の問題に対してパラメータ値が適切であるか否かを評価する方法が問題となる。
【０００９】
１つの側面では、本発明は、パラメータ値に対する評価を効率的に行うことを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、プログラムが提供される。このプログラムは、コンピュータに次の処理を実行させる。コンピュータは、評価関数に基づいて、第１パラメータ値を用いた解探索が実行されると、評価関数により計算される評価関数の値の第１指標値と、解探索の期間の開始時点よりも後の時点から当該期間の終了時点までの第１期間で得られた評価関数の値の第２指標値とに基づいて、第１指標値と第２指標値との差の度合いを示す変化率を計算する。コンピュータは、当該評価関数で表される問題に対する第１パラメータ値による求解性能を、変化率に基づいて評価する。
（【００１１】以降は省略されています）

関連特許