特許ウォッチ

公開番号2024123937
公報種別公開特許公報(A)
公開日2024-09-12
出願番号2023031775
出願日2023-03-02
発明の名称プログラム、データ処理方法およびデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20240905BHJP(計算;計数)
要約【課題】求解性能を向上すること。
【解決手段】データ処理装置10は、記憶部11と処理部12とを有する。処理部12は、複数の状態変数に関する制約を示すペナルティ関数とペナルティ関数に乗じる制約係数とを含む評価関数に基づいて探索された解を記憶部11に格納する。処理部12は、記憶部11に格納された複数の解それぞれの制約の充足状況に基づいて制約係数を調整する。処理部12は、調整後の制約係数を含む評価関数に基づいて新たな解の探索を開始させる。
【選択図】図1
特許請求の範囲【請求項１】
コンピュータに、
複数の状態変数に関する制約を示すペナルティ関数と前記ペナルティ関数に乗じる制約係数とを含む評価関数に基づいて探索された解を記憶部に格納し、
前記記憶部に格納された複数の解それぞれの前記制約の充足状況に基づいて前記制約係数を調整し、調整後の前記制約係数を含む前記評価関数に基づいて新たな解の探索を開始させる、
処理を実行させるプログラム。
続きを表示（約 1,500 文字）【請求項２】
前記評価関数は、複数の前記制約に対応する複数の前記ペナルティ関数を含み、
前記複数の解それぞれの前記制約ごとの充足状況に基づいて、当該制約に対応する前記制約係数を調整する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項３】
前記制約は、等式制約または不等式制約である、
請求項１記載のプログラム。
【請求項４】
複数の前記制約は、等式制約および不等式制約の何れか一方または両方を含む、
請求項２記載のプログラム。
【請求項５】
前記複数の解に前記制約を満たす解が所定数存在しない場合、前記制約に対応する前記制約係数を増加させ、前記複数の解に前記制約を満たす解が所定数存在する場合、前記制約に対応する前記制約係数を減少させる、
処理を前記コンピュータに実行させる請求項１または２記載のプログラム。
【請求項６】
複数の前記制約は、等式制約および不等式制約を含み、
前記複数の解に前記等式制約および前記不等式制約を全て満たす解が存在しない場合、前記等式制約に対応する第１の制約係数および前記不等式制約に対応する第２の制約係数の少なくとも何れかを所定確率で増加させる、
処理を前記コンピュータに実行させる請求項２記載のプログラム。
【請求項７】
前記制約係数を調整すると、調整後の前記制約係数を含む前記評価関数に基づいて前記記憶部に格納された前記複数の解それぞれに対応するエネルギーを計算し、
前記探索により新たに得られた第１の解に対して前記評価関数により計算される第１のエネルギーと前記複数の解のうちの最悪解に対応する前記エネルギーとの比較に応じて、前記記憶部に記憶される前記複数の解のうちの前記最悪解を前記第１の解に置換する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項８】
前記記憶部に記憶される前記複数の解に基づいて、次の前記探索に用いる探索開始状態を生成する、
処理を前記コンピュータに実行させる請求項７記載のプログラム。
【請求項９】
前記複数の解とは別に、最終的に出力する候補となる１以上の解と前記制約係数を前記探索ごとに変化させない固定値とした前記評価関数に基づいて計算される、前記１以上の解それぞれに対応する出力評価用エネルギーとを前記記憶部に格納し、
前記探索により新たに得られた第１の解に対して前記制約係数を前記固定値とした前記評価関数により計算される第１の出力評価用エネルギーと前記１以上の解のうちの最悪解に対応する前記出力評価用エネルギーとの比較に応じて、前記記憶部に記憶される前記１以上の解のうちの前記最悪解を前記第１の解に置換し、
前記制約係数の調整と前記探索とを繰り返す処理を終了すると、前記記憶部に記憶される前記１以上の解の少なくとも一部を出力する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項１０】
コンピュータが、
複数の状態変数に関する制約を示すペナルティ関数と前記ペナルティ関数に乗じる制約係数とを含む評価関数に基づいて探索された解を記憶部に格納し、
前記記憶部に格納された複数の解それぞれの前記制約の充足状況に基づいて前記制約係数を調整し、調整後の前記制約係数を含む前記評価関数に基づいて新たな解の探索を開始させる、
データ処理方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、データ処理方法およびデータ処理装置に関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
組合せ最適化問題の求解に情報処理装置が用いられることがある。情報処理装置は、評価関数に含まれる状態変数の値の組合せのうち、例えば評価関数の値を最小化する組合せを探索する。この場合、評価関数の値を最小化する状態変数の値の組合せは、状態変数の組により表される基底状態または最適解に相当する。実用的な時間で組合せ最適化問題の近似解を得る手法には、タブーサーチ（tabu search）法やシミュレーテッドアニーリング（ＳＡ：Simulated Annealing）法などがある。
【０００３】
組合せ最適化問題がバイナリ二次計画問題（ＢＱＰ：Binary Quadratic Programming Problem）である場合、磁性体のスピンの振る舞いを表すモデルであるイジングモデルのエネルギーを示す評価関数に変換し、量子アニーラ等を用いて問題を解く場合がある。例えば、制約ありの二次計画問題のラグランジュ双対を量子アニーラを用いて解くシステムの提案がある。また、二値多項的に制約された多項計画問題（ＢＰＣＰＰＰ：Binary Polynomially Constrained Polynomial Programming Problem）のラグランジュ双対を量子アニーラを用いて解くシステムの提案がある。
【０００４】
また、量子アニーリングを使用して最小支配集合問題を解くシステムの提案がある。
更に、ＢＱＰを半正定計画問題（ＳＤＰ：Semidefinite Programming）と呼ばれる解きやすい問題に緩和し、ＳＤＰの解を基にＢＱＰを最適化する最適化システムの提案がある。
【先行技術文献】
【特許文献】
【０００５】
米国特許出願公開第２０１６／０２２４５１５号明細書
国際公開第２０１７／１４５０８６号
米国特許出願公開第２０１７／０２８６８５２号明細書
国際公開第２０１７／０５６３６８号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＢＱＰなどに対応する評価関数では、状態変数に対する制約がペナルティ関数として表されることがある。ペナルティ関数により、状態変数の値に応じた制約違反量が評価関数に加算される。
【０００７】
評価関数には、ペナルティ関数を重み付けする係数である制約係数が用いられることがある。この場合、制約係数を適切に決定することは容易ではない。例えば、制約係数が大き過ぎると解の探索範囲が狭まり、より良い解に到達し難くなる。一方、制約係数が小さ過ぎると制約を満たす解が得られ難くなる。
【０００８】
１つの側面では、本発明は、求解性能を向上することを目的とする。
【課題を解決するための手段】
【０００９】
１つの態様では、プログラムが提供される。このプログラムは、コンピュータに、複数の状態変数に関する制約を示すペナルティ関数とペナルティ関数に乗じる制約係数とを含む評価関数に基づいて探索された解を記憶部に格納し、記憶部に格納された複数の解それぞれの制約の充足状況に基づいて制約係数を調整し、調整後の制約係数を含む評価関数に基づいて新たな解の探索を開始させる、処理を実行させる。
【００１０】
また、１つの態様では、データ処理方法が提供される。また、１つの態様では、記憶部と処理部とを有するデータ処理装置が提供される。
【発明の効果】
（【００１１】以降は省略されています）

関連特許