特許ウォッチ

公開番号2025114234
公報種別公開特許公報(A)
公開日2025-08-05
出願番号2024008804
出願日2024-01-24
発明の名称データ処理装置、プログラム及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20250729BHJP(計算;計数)
要約【課題】組合せ最適化問題の解の探索効率を向上させる。
【解決手段】記憶部11は、2次のコスト項と、複数の制約条件のそれぞれの重みを表す係数により重み付けられた複数の制約項の和である1次のコスト項との和で表される組合せ最適化問題の評価関数の、評価関数情報を記憶し、処理部12は、評価関数情報を記憶部11から取得し、評価関数情報に基づいて組合せ最適化問題の解を探索し、解の探索途中の第1の時点において、上記複数の制約条件のうち制約違反が生じている第1制約条件がある場合、第1制約条件に対応した上記係数の値を増加させ、第1の時点において、上記複数の制約条件が満たされている場合、第1の時点における2次のコスト項の値と、第1の時点より前に得られた評価関数の値との比較結果に基づいて、上記複数の制約条件に対応した上記係数の値を減少させるか維持するかを決定する。
【選択図】図1
特許請求の範囲【請求項１】
２次のコスト項と、複数の制約条件のそれぞれの重みを表す係数により重み付けられた複数の制約項の和である１次のコスト項との和で表される組合せ最適化問題の評価関数の、評価関数情報を記憶する記憶部と、
前記評価関数情報を前記記憶部から取得し、前記評価関数情報に基づいて前記組合せ最適化問題の解を探索し、前記解の探索途中の第１の時点において、前記複数の制約条件のうち制約違反が生じている第１制約条件がある場合、前記第１制約条件に対応した前記係数の値を増加させ、前記第１の時点において、前記複数の制約条件が満たされている場合、前記第１の時点における前記２次のコスト項の値と、前記第１の時点より前に得られた前記評価関数の値との比較結果に基づいて、前記複数の制約条件に対応した前記係数の値を減少させるか維持するかを決定する処理部と、
を有するデータ処理装置。
続きを表示（約 1,200 文字）【請求項２】
前記処理部は、前記第１の時点における前記２次のコスト項の値が、前記第１の時点より前に得られた前記評価関数の値のうちの最小値以上であるとき、前記複数の制約条件に対応した前記係数の値を減少させ、前記最小値よりも小さいとき、前記複数の制約条件に対応した前記係数の値を維持する、
請求項１に記載のデータ処理装置。
【請求項３】
前記第１の時点は、前記解の探索処理が所定回数行われるたびに到来する時点である、請求項１に記載のデータ処理装置。
【請求項４】
前記処理部は、前記係数の値を変更した場合、前記係数の値の変化量を用いて前記１次のコスト項の値を補正する、請求項１に記載のデータ処理装置。
【請求項５】
前記処理部は、前記１次のコスト項の値が０の場合、前記複数の制約条件が満たされていると判定し、前記１次のコスト項の値が０より大きい場合、前記複数の制約条件の何れかにおいて制約違反が生じていると判定する、請求項１に記載のデータ処理装置。
【請求項６】
２次のコスト項と、複数の制約条件のそれぞれの重みを表す係数により重み付けられた複数の制約項の和である１次のコスト項との和で表される組合せ最適化問題の評価関数の、評価関数情報を記憶する記憶部から、前記評価関数情報を取得し、
前記評価関数情報に基づいて前記組合せ最適化問題の解を探索し、
前記解の探索途中の第１の時点において、前記複数の制約条件のうち制約違反が生じている第１制約条件がある場合、前記第１制約条件に対応した前記係数の値を増加させ、
前記第１の時点において、前記複数の制約条件が満たされている場合、前記第１の時点における前記２次のコスト項の値と、前記第１の時点より前に得られた前記評価関数の値との比較結果に基づいて、前記複数の制約条件に対応した前記係数の値を減少させるか維持するかを決定する、
処理をコンピュータに実行させるプログラム。
【請求項７】
記憶部が、２次のコスト項と、複数の制約条件のそれぞれの重みを表す係数により重み付けられた複数の制約項の和である１次のコスト項との和で表される組合せ最適化問題の評価関数の、評価関数情報を記憶し、
処理部が、前記評価関数情報を前記記憶部から取得し、
前記処理部が、前記評価関数情報に基づいて前記組合せ最適化問題の解を探索し、
前記処理部が、前記解の探索途中の第１の時点において、前記複数の制約条件のうち制約違反が生じている第１制約条件がある場合、前記第１制約条件に対応した前記係数の値を増加させ、
前記処理部が、前記第１の時点において、前記複数の制約条件が満たされている場合、前記第１の時点における前記２次のコスト項の値と、前記第１の時点より前に得られた前記評価関数の値との比較結果に基づいて、前記複数の制約条件に対応した前記係数の値を減少させるか維持するかを決定する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、データ処理装置、プログラム及びデータ処理方法に関する。
続きを表示（約 1,800 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する際に、組合せ最適化問題を、磁性体のスピンの振る舞いを表すイジングモデルに変換する手法がある。イジングモデルは、組合せ最適化問題の解を評価するイジング型の評価関数で表される。イジング型の評価関数は、複数の状態変数（イジングモデルの状態を表す）と複数の重み値を含む。イジング型の評価関数では、状態変数は、０か１（または－１か＋１）の値を取る２値変数である。状態変数はビットと表記されてもよい。また、イジング型の評価関数の値は、イジングモデルのエネルギーということもできる。
【０００３】
解の探索では、マルコフ連鎖モンテカルロ（ＭＣＭＣ：Markov-Chain Monte Carlo）法が用いられる。以下、ＭＣＭＣ法による解の探索をＭＣＭＣ探索という。ＭＣＭＣ探索では、たとえば、メトロポリス法またはギブス法で規定される状態遷移の受け入れ確率で、状態遷移が受け入れられる。このとき、エネルギーを増加させる状態遷移も確率的に許容される。なお、エネルギーの増加量が大きいほど受け入れ確率は低くなる。ＭＣＭＣ法の一種として、疑似焼き鈍し法やレプリカ交換法がある。このようなＭＣＭＣ探索では、イジング型の評価関数の値が極小になるイジングモデルの状態の探索が行われる。評価関数の極小値のうちの最小値になる状態が最適解となる。
【０００４】
ところで、組合せ最適化問題には解が満たすべき制約条件をもつものがあり、制約条件を考慮した探索を行う手法が提案されている（たとえば、特許文献１～４参照）。制約条件には、不等式制約、等式制約、絶対値制約などがある。制約条件を反映した評価関数は、制約条件違反の有無に応じた値をもつ制約項を含む。制約項は、制約条件の重みを表す係数により重み付けられている。
【先行技術文献】
【特許文献】
【０００５】
特開２０２１－０８９５９６号公報
特開２０２２－０４７３６２号公報
米国特許出願公開第２０１６／０２１７３８０号明細書
特開２０２３－１４９７２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
制約条件の重みを表す係数の値が適切でない場合、ＭＣＭＣ探索において、探索効率が悪化する場合がある。たとえば、制約条件の重みを表す係数の値が小さいと、制約条件を満たさない状態（以下制約違反解という）へ遷移する場合のエネルギーの増加量が小さくなる。この場合、制約違反解が生じやすくなり、探索効率が悪化する。逆に上記係数の値が大きいと状態遷移が生じにくくなり、探索効率が悪化する。
【０００７】
１つの側面では、本発明は、組合せ最適化問題の解の探索効率を向上可能なデータ処理装置、プログラム及びデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、２次のコスト項と、複数の制約条件のそれぞれの重みを表す係数により重み付けられた複数の制約項の和である１次のコスト項との和で表される組合せ最適化問題の評価関数の、評価関数情報を記憶する記憶部と、前記評価関数情報を前記記憶部から取得し、前記評価関数情報に基づいて前記組合せ最適化問題の解を探索し、前記解の探索途中の第１の時点において、前記複数の制約条件のうち制約違反が生じている第１制約条件がある場合、前記第１制約条件に対応した前記係数の値を増加させ、前記第１の時点において、前記複数の制約条件が満たされている場合、前記第１の時点における前記２次のコスト項の値と、前記第１の時点より前に得られた前記評価関数の値との比較結果に基づいて、前記複数の制約条件に対応した前記係数の値を減少させるか維持するかを決定する処理部と、を有するデータ処理装置が提供される。
【０００９】
また、１つの実施態様では、プログラムが提供される。
また、１つの実施態様では、データ処理方法が提供される。
【発明の効果】
【００１０】
１つの側面では、本発明は、組合せ最適化問題の解の探索効率を向上できる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許