特許ウォッチ

公開番号2023079015
公報種別公開特許公報(A)
公開日2023-06-07
出願番号2021192401
出願日2021-11-26
発明の名称情報処理装置、情報処理方法およびプログラム
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20230531BHJP(計算;計数)
要約【課題】パラメータ探索を効率化する。
【解決手段】処理部12は、イジングモデルのエネルギー関数に基づく問題の解の探索に用いられるパラメータの候補値範囲である第1範囲からの第1候補値の取得および第1候補値を用いた場合の当該探索の結果に応じた第1候補値の評価を繰り返し行い、候補値範囲を第1範囲から第1範囲よりも狭い第2範囲に変更する。処理部12は、第2範囲からの第2候補値の取得および第2候補値を用いた場合の当該探索の結果に応じた第2候補値の評価を繰り返し行う。処理部12は、第1候補値を用いた評価により複数の第1候補値に対して算出された複数の評価値のうちの最良の評価値と最良の評価値よりも前の評価で得られた他の評価値との第1差分、および、エネルギー関数に応じた問題の性質を示す指標の少なくとも一方に基づいて、第1範囲から第2範囲に変更するタイミングと、第1範囲と第2範囲との第2差分とを決定する。
【選択図】図1
特許請求の範囲【請求項１】
問題に対応する、イジングモデルのエネルギー関数を示す情報を記憶する記憶部と、
前記エネルギー関数に基づく前記問題の解の探索に用いられるパラメータの候補値範囲である第１範囲からの第１候補値の取得および前記第１候補値を前記パラメータの値として用いた場合の前記探索の結果に応じた前記第１候補値の評価を複数回行い、前記候補値範囲を、第１範囲から、前記第１範囲よりも狭い第２範囲に変更し、前記第２範囲からの第２候補値の取得および前記第２候補値を前記パラメータの値として用いた場合の前記探索の結果に応じた前記第２候補値の評価を複数回行う処理部と、を有し、
前記処理部は、前記第１候補値を用いた評価により複数の前記第１候補値に対して算出された複数の第１評価値のうちの最良の評価値と当該最良の評価値よりも前の評価によって得られた他の評価値との第１差分、および、前記エネルギー関数に応じた前記問題の性質を示す指標の少なくとも一方に基づいて、前記候補値範囲を前記第１範囲から前記第２範囲に変更するタイミングと、前記第１範囲と前記第２範囲との第２差分とを決定する、
情報処理装置。
続きを表示（約 1,400 文字）【請求項２】
前記処理部は、前記第１差分が大きいほど、前記タイミングを遅くし、前記第２差分を小さくする、請求項１記載の情報処理装置。
【請求項３】
前記処理部は、前記第１差分が閾値以下の場合に、前記第１差分が前記閾値より大きい場合よりも前記タイミングを早くし、前記第２差分を大きくする、請求項１記載の情報処理装置。
【請求項４】
前記問題の性質を示す指標は、前記問題の難易度を示し、
前記処理部は、前記難易度が高いほど、前記タイミングを遅くし、前記第２差分を小さくする、請求項１記載の情報処理装置。
【請求項５】
前記問題の性質を示す指標は、前記エネルギー関数に含まれる状態変数の数、制約の種類および制約の数の少なくとも何れかを示す指標である、請求項１記載の情報処理装置。
【請求項６】
前記処理部は、前記エネルギー関数に含まれる状態変数の数および制約の数の少なくとも一方が多いほど、前記タイミングを遅くし、前記第２差分を小さくする、請求項５記載の情報処理装置。
【請求項７】
前記処理部は、前記候補値範囲を前記第１範囲から前記第２範囲に変更する際、前記第１範囲から取得された前記第１候補値のうち、前記最良の評価値に対応する前記第１候補値を、前記第２範囲の中心値に設定する、請求項１記載の情報処理装置。
【請求項８】
前記処理部は、前記第１候補値を用いた場合の一定時間の前記探索により得られた前記エネルギー関数の最良値、および、前記最良値に達するまでに要した時間に基づいて前記第１候補値に対応する前記最良の評価値を算出する、請求項１記載の情報処理装置。
【請求項９】
前記処理部は、
前記第２範囲から取得された複数の前記第２候補値に対して得られた複数の第２評価値のうちの最良の評価値に対応する前記第２候補値を前記パラメータの値として決定し、
決定した前記パラメータの値を用いて前記問題に対する解の前記探索を実行する、または、決定した前記パラメータの値を前記探索を行う探索部に入力して前記探索部に前記探索を実行させる、
請求項１記載の情報処理装置。
【請求項１０】
前記パラメータは複数あり、
前記処理部は、
複数の前記パラメータの候補値それぞれの前記第１範囲からの前記候補値の組の取得および前記候補値の組を用いた場合の前記探索の結果に応じた前記候補値の組の前記評価を複数回行い、複数の前記パラメータの候補値それぞれの前記第１範囲を前記第２範囲に変更し、複数の前記パラメータの候補値それぞれの前記第２範囲からの前記候補値の組の取得および前記候補値の組を用いた場合の前記探索の結果に応じた前記候補値の組の前記評価を複数回行い、
前記第２範囲への変更の前に、前記第１範囲を用いた前記評価により前記候補値の各組に対して算出された評価値のうちの最良の評価値と当該最良の評価値よりも前に得られた他の評価値との前記第１差分、および、前記エネルギー関数に応じた前記問題の性質を示す前記指標の少なくとも一方に基づいて、前記タイミングと前記第２差分とを決定する、
請求項１記載の情報処理装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は情報処理装置、情報処理方法およびプログラムに関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
組合せ最適化問題の求解に情報処理装置が用いられることがある。情報処理装置は、組合せ最適化問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルのエネルギー関数に変換し、エネルギー関数に含まれる状態変数の値の組合せのうち、エネルギー関数の値を最小化する組合せを探索する。エネルギー関数の値を最小化する状態変数の値の組合せは、状態変数の組により表される基底状態または最適解に相当する。
【０００３】
実用的な時間で組合せ最適化問題の近似解を得る手法には、マルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov-Chain Monte Carlo）法に基づく、シミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法やレプリカ交換法などがある。ＳＡ法やレプリカ交換法などによる解の探索では、温度値などを表すパラメータが用いられる。そこで、当該パラメータの値を決定する方法が考えられている。
【０００４】
例えば、イジングモデルのエネルギーの分解能と温度パラメータが最低値のときのイジングモデルの状態遷移の許容確率とから、温度パラメータの最低値を決定する最適化装置の提案がある。提案の最適化装置は、イジングモデルに含まれる状態変数の数や状態変数間の重みを示す重み係数から決定したエネルギーの変化分の最大値に基づき、温度パラメータが最高値のときの許容確率から温度パラメータの最高値も決定する。
【０００５】
なお、複数の評価項目を持つ組合せ最適化問題を、ＳＡ法を用いて解決する組合せ最適化方法の提案がある。提案の組合せ最適化方法では、各評価項目の重み係数を温度パラメータの変化とともに動的に変化させる。
【０００６】
また、所定の探索範囲をもつパラメータを用いて遺伝的アルゴリズムにより解を探索する解探索装置の提案もある。提案の解探索装置は、複数のパラメータを持った遺伝子データを記憶する。解探索装置は、入力されたパラメータの探索範囲の少なくとも一部分に対するパラメータ値の対数値が所定の分布になるようなパラメータ値を生成し、当該パラメータ値が設定されたパラメータを用いて遺伝的アルゴリズムにより解を探索する。
【先行技術文献】
【特許文献】
【０００７】
特開２０２０－４６７１８号公報
特開平９－３４９５１号公報
米国特許出願公開第２００６／００１００９１号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＳＡ法やレプリカ交換法などで用いられるパラメータの値は、情報処理装置の求解性能に影響する。そこで、情報処理装置は、ＳＡ法やレプリカ交換法などで用いられるパラメータの値を決定するために、本番の解の探索の前にパラメータ探索を行うことがある。
【０００９】
パラメータ探索では、情報処理装置は、所定範囲に属する値の中からパラメータの候補値を抽出し、抽出した候補値による解探索の試行の結果により当該候補値を評価する処理を当該所定範囲内の各候補値に対して繰り返し行う。情報処理装置は、各候補値のうち評価の結果が良い候補値を実際に使用するパラメータの値として採用する。
【００１０】
しかし、パラメータ探索では候補値の範囲が広いほど、評価対象の候補値の数が多くなり、パラメータの値の決定に時間がかかる。一方、候補値の範囲を狭めることで評価対象の候補値の数を絞り過ぎると、より良い候補値が当該範囲から外れ、パラメータの値を適切に決定できない可能性がある。
（【００１１】以降は省略されています）

関連特許