特許ウォッチ

公開番号2025157966
公報種別公開特許公報(A)
公開日2025-10-16
出願番号2024060359
出願日2024-04-03
発明の名称プログラム、データ処理方法およびデータ処理装置
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20251008BHJP(計算;計数)
要約【課題】求解を高速化する。
【解決手段】処理部12は、複数の状態変数に関する2次以上の第1目的関数に基づいて、複数の状態変数で表される解の探索を行う。第1目的関数は、各々が、係数が正である1個の項または係数が正である2個以上の項の和である複数の第1サブ関数と、各々が、係数が負である1個の項または係数が負である2個以上の項の和である複数の第2サブ関数との和で表される。処理部12は、探索において第1の解に達すると、第1目的関数から得られる第2目的関数に基づいて、第1の解から探索を継続する。第2目的関数は、複数の第1サブ関数のうち、第1の解における値が正である項を含む第1サブ関数、および、複数の第2サブ関数のうち、第1の解における値がゼロである項を含む第2サブ関数の少なくとも何れかに、1より大きい重み値を乗じたものである。
【選択図】図1
特許請求の範囲【請求項１】
コンピュータに、
複数の状態変数に関する２次以上の第１目的関数であって、各々が、係数が正である１個の項または前記係数が正である２個以上の項の和である複数の第１サブ関数と、各々が、前記係数が負である１個の項または前記係数が負である２個以上の項の和である複数の第２サブ関数との和で表される前記第１目的関数に基づいて、前記複数の状態変数で表される解の探索を行い、
前記探索において第１の解に達すると、前記第１目的関数から得られる第２目的関数であって、前記複数の第１サブ関数のうち、前記第１の解における値が正である項を含む前記第１サブ関数、および、前記複数の第２サブ関数のうち、前記第１の解における値がゼロである項を含む前記第２サブ関数の少なくとも何れかに、１より大きい重み値を乗じた前記第２目的関数に基づいて、前記第１の解から前記探索を継続する、
処理を実行させるプログラム。
続きを表示（約 1,600 文字）【請求項２】
前記複数の状態変数に関する２次以上の元の目的関数に含まれる複数の項のうち、前記係数が正である項を、前記第１サブ関数ごとの前記係数の合計の差が小さくなるように前記複数の第１サブ関数に分類し、前記元の目的関数に含まれる複数の項のうち、前記係数が負である項を、前記第２サブ関数ごとの前記係数の絶対値の合計の差が小さくなるように前記複数の第２サブ関数に分類する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項３】
前記探索において前記第１の解に達すると、前記複数の第１サブ関数の項のうち、前記第１の解における値が正である項、および、前記複数の第２サブ関数の項のうち、前記第１の解における値がゼロである項の中から所定数の項を選択し、選択した前記所定数の項の各々を含む前記第１サブ関数および前記第２サブ関数に１より大きい重み値を乗じることで、前記第２目的関数を生成する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項４】
前記複数の第１サブ関数の中に前記第１の解における値が正である項がなく、かつ、前記複数の第２サブ関数の中に前記第１の解における値がゼロである項がない場合、前記第１の解を最適解として出力する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項５】
前記第１目的関数および前記第２目的関数における前記探索で得られた解に対応する前記元の目的関数の値を計算し、前記元の目的関数の値が最良の解を記憶部に保持し、一定時間の前記探索を行うと、前記記憶部に保持される前記最良の解を出力する、
処理を前記コンピュータに実行させる請求項２記載のプログラム。
【請求項６】
前記探索において前記第１目的関数の値が改良されなくなると、前記第１の解に達したことを検出する、
処理を前記コンピュータに実行させる請求項１記載のプログラム。
【請求項７】
コンピュータが、
複数の状態変数に関する２次以上の第１目的関数であって、各々が、係数が正である１個の項または前記係数が正である２個以上の項の和である複数の第１サブ関数と、各々が、前記係数が負である１個の項または前記係数が負である２個以上の項の和である複数の第２サブ関数との和で表される前記第１目的関数に基づいて、前記複数の状態変数で表される解の探索を行い、
前記探索において第１の解に達すると、前記第１目的関数から得られる第２目的関数であって、前記複数の第１サブ関数のうち、前記第１の解における値が正である項を含む前記第１サブ関数、および、前記複数の第２サブ関数のうち、前記第１の解における値がゼロである項を含む前記第２サブ関数の少なくとも何れかに、１より大きい重み値を乗じた前記第２目的関数に基づいて、前記第１の解から前記探索を継続する、
データ処理方法。
【請求項８】
複数の状態変数に関する２次以上の第１目的関数であって、各々が、係数が正である１個の項または前記係数が正である２個以上の項の和である複数の第１サブ関数と、各々が、前記係数が負である１個の項または前記係数が負である２個以上の項の和である複数の第２サブ関数との和で表される前記第１目的関数の情報を記憶する記憶部と、
前記第１目的関数に基づいて、前記複数の状態変数で表される解の探索を行い、前記探索において第１の解に達すると、前記第１目的関数から得られる第２目的関数であって、前記複数の第１サブ関数のうち、前記第１の解における値が正である項を含む前記第１サブ関数、および、前記複数の第２サブ関数のうち、前記第１の解における値がゼロである項を含む前記第２サブ関数の少なくとも何れかに、１より大きい重み値を乗じた前記第２目的関数に基づいて、前記第１の解から前記探索を継続する処理部と、
を有するデータ処理装置。

発明の詳細な説明【技術分野】
【０００１】
本発明はプログラム、データ処理方法およびデータ処理装置に関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
組合せ最適化問題の求解に情報処理装置が用いられることがある。組合せ最適化問題は、イジングモデルのエネルギーを示す目的関数により定式化される。イジングモデルは、磁性体のスピンの振る舞いを表すモデルである。目的関数は、エネルギー関数や評価関数と呼ばれることもある。
【０００３】
情報処理装置は、例えば目的関数に含まれる複数の状態変数の値の組合せのうち、目的関数の値を最小化する組合せを探索する。この場合、目的関数の値を最小化する複数の状態変数の値の組合せは、状態変数の組により表される基底状態または最適解に相当する。実用的な時間で組合せ最適化問題の近似解を得る手法には、例えば貪欲法やタブーサーチ法などがある。
【０００４】
ここで、例えばシミュレーテッド分岐アルゴリズムと呼ばれる手法により組合せ最適化問題の求解を行う情報処理装置の提案がある。
また、ＱＵＢＯ（Quadratic Unconstrained Binary Optimization）問題を量子アニーリングマシンで解くために、ＱＵＢＯ問題の変数をキメラグラフ上の複数のノードに割り当てる処理を行う割り当て装置の提案がある。
【０００５】
また、解決すべき最適化問題を２つのサブ問題に分解し、１つのサブ問題を古典コンピュータに割り当て、１つのサブ問題を量子コンピュータに割り当て、古典コンピュータおよび量子コンピュータの求解の結果を相互に送信するシステムの提案がある。
【０００６】
更に、根本原因分析（ＲＣＡ：Root Cause Analysis）を最小頂点被覆問題に関連付けてＱＵＢＯで定式化し、量子アニーリングプロセスによって解く方法の提案がある。
【先行技術文献】
【特許文献】
【０００７】
特開２０２１－４３６６７号公報
特開２０２２－１９４３２号公報
米国特許出願公開第２０２２／０４１４５１８号明細書
米国特許出願公開第２０２２／０２２４５９０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＱＵＢＯまたはＨＯＢＯ（Higher Order Binary Optimization）などの高次の目的関数で表される問題の求解には時間がかかるという問題がある。例えば、解の探索において局所解に陥ると、局所解からの脱出が困難になり、より良い解を得ることが難しくなる。
【０００９】
１つの側面では、本発明は、求解を高速化することを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、プログラムが提供される。このプログラムは、コンピュータに次の処理を実行させる。コンピュータは、複数の状態変数に関する２次以上の第１目的関数であって、各々が、係数が正である１個の項または係数が正である２個以上の項の和である複数の第１サブ関数と、各々が、係数が負である１個の項または係数が負である２個以上の項の和である複数の第２サブ関数との和で表される第１目的関数に基づいて、複数の状態変数で表される解の探索を行う。コンピュータは、探索において第１の解に達すると、第１目的関数から得られる第２目的関数であって、複数の第１サブ関数のうち、第１の解における値が正である項を含む第１サブ関数、および、複数の第２サブ関数のうち、第１の解における値がゼロである項を含む第２サブ関数の少なくとも何れかに、１より大きい重み値を乗じた第２目的関数に基づいて、第１の解から探索を継続する。
（【００１１】以降は省略されています）

関連特許